Елементи синтаксичного аналізу, Детальна інформація

ЕЛЕМЕНТИ СИНТАКСИЧНОГО АНАЛІЗУ

1. Формальні мови та їх задання

1.1. Формальна мова та задача належності

Алфавітом називається скінченна множина символів. Позначатимемо його X. Словом (фразою, або ланцюжком) у алфавіті X називається послідовність символів із X. Множина всіх скінченних слів у алфавіті X позначається X*. Зауважимо, що вона нескінченна. Вона містить порожнє слово – послідовність довжиною 0, позначену буквою \xF065 . Множину X*\{\xF065 } позначимо X+, а слово вигляду ww\xF0BC w, де слово w із X+ записано n разів – wn. Вважатимемо, що w0 = \xF065 .

Довільна підмножина множини X* називається формальною мовою. Далі в цьому розділі вона буде називатися просто мовою.

Приклади

21.1. Множина всіх слів у алфавіті {a} позначається {a}* = {\xF065 , a, aa, aaa, … } = { an | n \xF0B3 0 }. {an|n–непарне} позначає множину, або мову слів непарної довжини в алфавіті {a}; обидві мови нескінченні.

21.2. Ідентифікатор є послідовністю букв і цифр, що починається буквою. Множина всіх ідентифікаторів у алфавіті X={a, b, 1} нескінченна. Якщо записати їх за зростанням довжини, то початок буде таким: { a, b, a1, aa, ab, b1, ba, bb, \xF0BC }.

Задача перевірки, чи належить слово w мові L, називається задачею належності, або проблемою слів. Як правило, множина L задається певним скінченним описанням, що визначає не тільки її саму, а й структуру її елементів.

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

Формальні мови розглядатимуться далі як мови, задані саме скінченним описом. Отже, головним у вивченні формальних мов стає засіб їх задання. У розділі 10 ми вже познайомилися з одним із них – це були БНФ та їх сукупності. Розглянемо ще деякі.

1.2. Регулярні операції, вирази та мови

Означимо регулярні операції над мовами: об'єднання, катенацію та ітерацію. Нехай L1 , L2 , L позначають довільні мови в алфавіті X.

Вираз L1\xF0C8 L2 позначає об'єднання L1 і L2 – мову {w|w\xF0CE L1 або w\xF0CE L2}. Наприклад, {a, ab}\xF0C8 {a, b, ba}={a, b, ab, ba}.

Катенацією слів v і w називається дописування w після v: vw. Вираз L1L2 позначає катенацію мов – мову {vw|v\xF0CE L1, w\xF0CE L2}. Так, за L1={a, bc}, L2={x, y} катенація L1L2={ax, bcx, ay, bcy}, за L1={a, ab}, L2={\xF065 , b} катенація L1L2={a, ab, abb}.

Від катенації походить піднесення до степеня: L0={\xF065 }, Li=Li-1L за i>0. Так, вираз {\xF065 , a, aa}2 задає мову {\xF065 , a, aa, aaa, aaaa}.

Вираз L* позначає ітерацію мови L – мову {wi|w\xF0CE L за i\xF0B3 0}, тобто {\xF065 }\xF0C8 L\xF0C8 L2\xF0C8 \xF0BC . Зазначимо, що ітерація не подається жодним скінченним виразом з операціями катенації та \xF0C8 і тому не є похідною від них. Якщо в мові L є непорожнє слово, то мова L* нескінченна. Наприклад, вираз {ab}* задає мову {\xF065 ,ab,abab,ababab,\xF0BC }, {a,b}{a,b,1}* – множину ідентифікаторів у алфавіті {a, b, 1}.

Регулярні вирази й задані ними регулярні мови означимо індуктивно. Вирази \xF0C6 , \xF065 та a при a\xF0CE X є регулярними в алфавіті X і задають відповідно регулярні мови \xF0C6 , {\xF065 }, {a}. Якщо r1 і r2 – регулярні вирази, що задають регулярні мови L1 і L2 , то вирази (r1), r1+r2, r1r2, r1* є регулярними й задають відповідно регулярні мови L1, L1\xF0C8 L2, L1L2, L1*.

Очевидно, що кожна скінченна мова є регулярною, оскільки задається регулярним виразом як скінченне об'єднання одноелементних регулярних мов.

Множина регулярних мов, заданих усіма можливими регулярними виразами в алфавіті X, називається класом регулярних мов над X.

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

Не всі мови є регулярними. Наприклад, "мова вкладених дужок", задана БНФ

<вкл-дуж> ::= ( ) | ( <вкл-дуж> ),

є множиною {(n)n|n>0}, яка не задається жодним скінченним регулярним виразом (доведення можна знайти в [АУ]). Отже, розглянемо інші, потужніші засоби задання мов.

21.1.3. Граматики Хомського

Граматикою Хомського називається четвірка G = (X, N, P, S). Тут

X – алфавіт означуваної мови, або множина термінальних символів (терміналів).

N – множина позначень понять мови, тобто нетермінальних символів (нетерміналів).

P – множина правил виведення (продукцій) вигляду v\xF0AE w, де

v \xF0CE ( X \xF0C8 N )* N ( X \xF0C8 N )* , w \xF0CE ( X \xF0C8 N )*