shkolaw.in.ua 1 2 ... 7 8

Теоретичні основи трансляції

Мови програмування - це штучно створені формальні системи, які можуть вивчатися математичними методами. Розглянемо їх формальні властивості.

Формальна система - це сукупність абстрактних об'єктів, не пов'язаних із зовнішнім світом, у якій представлені правила оперування множиною символів у строго синтаксичному трактуванні без врахування значеннєвого змісту, тобто семантики.

Формальні мови і граматики


Теорія формальних мов і граматик - це велика область математики, що примикає до алгебри, математичної логіки і теорії автоматів. У наше завдання, однак, не входить її детальне вивчення. Ціль нашого курсу - познайомитися з поняттями і результатами теорії формальних мов і граматик у тій мірі, у який це потрібно для розуміння принципів конструювання трансляторів.

Основні терміни і визначення


Розглянемо основні поняття, які будуть використовуватися у визначенні формальної мови.

Алфавіт - кінцева непуста множина символів.

Термін символ варто розуміти тут у самому широкому змісті. Це може бути буква, цифра або розділовий знак. Але символом можна вважати і будь-який інший знак, розглянутий як щось неподільне - службове слово мови программування, ієрогліф і т.д. Будемо позначати алфавіти буквою  (сигма).

Приклади алфавітів:

1 = {0,1}

2 = {а, b, c}


3 = {A, В, C,…, Z, a, b, c, …, z,

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -, *, …, dіv, , program}

Алфавіт - це множина, тому при перерахуванні його елементів використовуються фігурні дужки, як це прийнято в математиці. Алфавіт 1 містить два символи, алфавіт 2 - три. Під 3 мається на увазі алфавіт мови Паскаль.

Ланцюжок над алфавітом  - довільна кінцева послідовність символів з .

Приклади ланцюжків над алфавітом 2:

 (альфа) = abbca

 (бета) = ab

γ (гама) = ba

δ (дельта) = c

Ланцюжки будемо позначати грецькими буквами.

Порожній ланцюжок - ланцюжок, який не містить символів (що містить нуль символів). Позначається буквою  (епсілон).

Якщо  і  - ланцюжки, то запис  означає їх конкатенацію (склеювання), тобто  - це ланцюжок, утворений приписуванням до ланцюжка  ланцюжка  праворуч.

Якщо  - ланцюжок , то n означає ланцюжок, утворений n-кратним повторенням ланцюжка :

n =  ... 

n разів

В окремому випадку, якщо  - символ, то

n =  ... 

n разів


Будемо позначати * - (нескінченну) множину всіх ланцюжків над алфавітом , включаючи порожній ланцюжок; + - множина всіх ланцюжків над алфавітом , не включаючи порожнього ланцюжка. Наприклад, якщо 1 = {0, 1}, то 1* являє собою множину всіх ланцюжків, які можуть бути складені із символів 0, 1 та порожнього ланцюжка. У цю множину входять порожній ланцюжок, всі ланцюжки, що складаються з одного символу, всі ланцюжки, що складаються із двох символів, і т.д.: 1* = { (епсілон) , 0,1, 00,01,10,11, 000, 001,...}.

* = +{}, де  - знак операції об'єднання множин. Тепер можна дати і визначення формальної мови.

Мовою над алфавітом називається довільна множина ланцюжків, складених із символів .

Будемо позначати мову над алфавітом - L() або просто L, якщо алфавіт зрозумілий.

Таким чином, мова йде про те, що мова - це деяке, тим або іншим способом визначена, підмножина множини всіх ланцюжків, які можуть бути побудовані із символів даного алфавіту. L()  (включено) *. На рис. 2.1 наочно показане співвідношення множин * і L().

Приналежні мові ланцюжки називають також реченнями мови.

Ще раз відзначимо, що множина ланцюжків * завжди нескінчена, у той час як множина ланцюжків, що утворюють мову, може бути і скінченою. Практичний інтерес представляють, звичайно, мови, що містять нескінчену множину ланцюжків; до числа таких мов відносяться і мови програмування.



следующая страница >>