Двадцятий розділ

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

Відрізняти граматику та мову напрочуд важливо, коли разом із синтаксисом розглядається й семантика.

Д.Кнут.

Чи замислювався читач над питанням, яким чином відбувається трансляція програм, записаних мовою Паскаль, у машинні програми? Або, принаймні, як при трансляції виявляються синтаксичні помилки в Паскаль-програмі, коли, наприклад, замість знака ":=" записано "=" або замість цілих операндів операції div записано дійсні? Якщо над цим трохи замислитися, то стане очевидним, що в програму трансляції якимсь чином закладено синтаксичні правила побудови Паскаль-програм та їх складових частин.

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

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

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

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

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

Приклади

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

v Î ( X È N )* N ( X È N )* , w Î ( X È N )*

тобто правий ланцюжок є довільною послідовністю терміналів і нетерміналів, а лівий містить принаймні один нетермінал.

Sпочатковий нетермінал із множини N, або позначення головного поняття, яким позначаються слова мови.

Нетермінали записуються словами в дужках <> або великими латинськими буквами. Термінали за необхідності часом беруться в апострофи. Як і в мові БНФ, замість продукцій вигляду v® w1ww2 і v® w1w2 записується продукція v® w1[w]w2, а замість продукцій v® w1u1w2 і v® w1u2w2 продукція v1® w1(u1|u2)w2 .

Приклад 21.3. Множину продукцій граматики

G1 =({ a, 1, 2 },

{ A, B, C, D },

{ A ® BC, A ® BD, A ® B, B ® a, C ® 1, D ® 2 },

A )

можна переписати у вигляді

{ A ® B [ C | D ], B ® a, C ® 1, D ® 2 }.ç

Як бачимо, продукції граматики дуже схожі на БНФ як за формою, так і за змістом – лише замість знака "::=" вживається "® ". Проте в лівій частині їх продукцій може бути не поодинокий нетермінал, а цілий ланцюжок, у якому обов'язково є нетермінал. За рахунок такого узагальнення граматики виявляються більш потужним засобом задання мов, ніж системи БНФ, тобто існують мови, які задаються граматиками, але не задаються БНФ. Тепер опишемо спосіб, у який граматика G = (X, N, P, S) задає мову.

1. На множині слів об'єднаного алфавіту (XÈ N)* означається відношення безпосередньої виводимості, позначене знаком Þ G (або Þ , коли відомо, якою саме є G):

v Þ G w, якщо v = x1 u x2 , w = x1 y x2 , u ® y Î P.

При цьому кажуть, що w безпосередньо виводиться з v застосуванням продукції u® y. Наприклад, у граматиці G1 із прикладу 21.3 BCÞ aC застосуванням продукції B® a, aCÞ a1застосуванням C® 1.

2. На множині (XÈ N)* означається відношення виводимості, позначене Þ *G (або Þ *, коли відомо, якою саме є G): vÞ *w, якщо v=w або існує послідовність w1, w2, … , wn слів, де n³ 1, така, що vÞ w1, w1Þ w2, … , wn-1Þ wn, wn=w. Так, у граматиці G1 BCÞ *a1, оскільки BCÞ aC, aCÞ a1. Послідовність vÞ w1Þ w2Þ Þ wn називається виведенням wn із v, а nдовжиною виведення. Інколи довжину записують замість '*' таким чином: vÞ nw, наприклад, BC Þ 2a1.

3. Якщо SÞ G*w, то послідовність SÞ Þ w називається виведенням слова w у граматиці G, а слово wвивідним. Так, слова A, BC, aC, a1 вивідні в граматиці G1.

4. Вивідні слова в алфавіті X називаються породжуваними, а множина їх усіх – мовою, що задається (породжується) граматикою G: L(G) = {w | wÎ X* та S Þ * w }.

Приклади

21.4. Граматика G1 із прикладу 21.3 задає мову { a, a1, a2 }.ç

21.5. Граматика

G2 = ( { a, …, z, 0, …, 9 }, { I, L, D },

{ I ® L | IL | ID, L ® a | … | z, D ® 0 | ... | 9 },

I )

породжує множину ідентифікаторів.ç

21.6. Граматика G3 = ( { (, ) }, { S }, { S ® e | ( S ) }, S ) задає множину "вкладених дужок" { (n)n | n ³ 0 }.ç

21.7. Граматика

G4 = ( { a, b, c }, { S, A, B, C},

{ S ® aSBC | abC, CB ® BC, bB ® bb, bC ® bc, cC ® cc },

S )

визначає мову { anbncn | n ³ 1 }.ç

Граматики називаються еквівалентними, якщо задають ту саму мову. Наприклад, граматика

( { a, 1, 2 }, { A }, { A ® a [ 1 | 2 ] }, A )

еквівалентна граматиці G1, граматика

( {a, …, z, 0, …, 9}, {I, C}, {I ® (a|…|z)C, C ® e |C(a |…|z|0|…|9)}, I )

– граматиці G2.

Є два види граматик з продукціями обмеженого вигляду, якими задаються регулярні мови, – це праволінійні та ліволінійні граматики. Праволінійною (ліволінійною) називається граматика, всі продукції якої мають вигляд A® w або A® wB (відповідно, A® w або A® Bw), де A, B – нетермінали, wÎ X*. Усі можливі праволінійні та ліволінійні граматики з термінальним алфавітом X породжують в точності клас регулярних мов над X. Це доводиться, наприклад, в [АУ].

Задачі

21.1. Написати регулярні вирази, що задають множину

а) двійкових цілих сталих (в алфавіті { 0, 1 });

б)* двійкових цілих сталих, які не мають провідних нулів, окрім сталої 0;

в)* дійсних сталих, дробова й ціла частини яких відокремлюються символом '.' і мають принаймні по одній цифрі;

г)* літералів, що починаються й закінчуються апострофом і всередині містять довільні символи та подвоєні апострофи;

д)* записів натуральних чисел у Римській системі позначень.

21.2. Граматику задано множиною продукцій, перша з яких має головний нетермінал у лівій частині. Визначити, чи породжує граматика

а) { S ® aT, T ® abT | baT | e } слова aabba, aaabb, aabb;

б)* { S ® aSb | SS | e } слова aabb, ababab, abbaab;

в) { E ® E + T | T, T ® T * F | F, F ® (E ) | a } слова a+a, a+a*a, (), (a), a*(a+a+a);

г) { S ® aSBC | abC, CB ® BC, bB ® bb, bC ® bc, cC ® cc } слова

abc, aabbcc, abcabc, aaabbc.

21.3. Означити право- та ліволінійну граматики, що задають множину ідентифікаторів у алфавіті { a, b, 0, 1, 2 }.

21.4. Означити право- та ліволінійну граматики, що задають множину слів у алфавіті {a, b}, в яких обидві кількості символів a і b

а)* непарні; б) парні.

21.5. Означити право- та ліволінійну граматики, що задають множину коментарів, які починаються символами '(*', закінчуються '*)' і не містять пари символів '*)' усередині.

21.2. Контекстно-вільні та LA(1)-граматики

21.2.1. Контекстно-вільні граматики

Контекстно-вільною, або КВ-граматикою, називається граматика, в якій ліві частини всіх продукцій є нетерміналами. Зміст терміну "контекстно-вільна" полягає в тім, що застосування продукції A® w до ланцюжка uAv не залежить, тобто є вільним від сусідніх з A символів, які утворюють контекст uv.

Зазначимо, що БНФ вигляду A::=w цілком аналогічна продукції A® w. Отже, сукупності БНФ є просто іншою формою КВ-граматик.

Контекстно-вільною мовою (КВ-мовою) називається мова, що може бути задана КВ-граматикою.

Прикладами КВ-граматик та КВ-мов є граматики з прикладів 21.3, 21.5, 21.6 у попередньому параграфі й задані ними мови. Граматика з прикладу 21.7 не є КВ-граматикою. До речі, мова, задана нею, не є КВ-мовою, оскільки не існує КВ-граматики, яка б її задавала.

КВ-граматики відіграють особливу роль у програмуванні, оскільки ними описується синтаксис практично всіх конструкцій мов програмування. Більше того, він описується КВ-граматиками, продукції яких задовольняють певні структурні обмеження. З використанням цих обмежень було побудовано алгоритми синтаксичного аналізу, час виконання яких прямо пропорційний довжині аналізованого слова. А лінійна складність цих алгоритмів великою мірою зумовила ефективність сучасних систем програмування.

21.2.2. Дві ідеї аналізу

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

Приклад 21.8. Нехай

G0 = ( { a, +, *, (, ) }, { E, T, F },

{ E ® E + T | T, T ® T * F | F, F ® (E ) | a },

E )

– граматика. Нетермінали E, T, F відповідно є скороченнями слів "Expression", "Term", "Factor", тобто "вираз", "доданок", "множник". Вони позначають вирази зі знаками операцій +, *, доданки та множники в них відповідно.

Виведення слова a+a*a в G0 з розгортанням нетерміналів, перших ліворуч у проміжних ланцюжках, має вигляд:

E Þ E+T Þ T+T Þ F+T Þ a+T Þ a+T*F Þ a+F*F Þ a+a*F Þ

Þ a+a*a

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

Тепер розглянемо виведення слова a+a*a з розгортанням нетерміналів, останніх праворуч:

E Þ E+TÞ E+T*F Þ E+T*a Þ E+F*a Þ E+a*a Þ T+a*a Þ F+a*aÞ

Þ a+a*a

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

Головною проблемою побудови алгоритмів аналізу в обох випадках є необхідність вибору продукції, застосованої для розгортання чи згортання. Чому, наприклад, у першому виведенні на першому кроці вибирається продукція E® E+T, а не E® T, а на другому, навпаки, E® T ? Чому за оберненого виведення в слові E+T*F, в якому є дві праві частини продукцій E+T і T*F, саме ланцюжок T*F згортається в T, а не E+T в E ? Тут необхідний вибір зроблено тому, що структура термінального слова була відома заздалегідь. Але, взагалі, структура слова до початку його аналізу невідома, і виникає необхідність перебирати продукції для застосування потрібної.

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

21.2.3. LA(1)-граматики

LA(1)-граматики дозволяють вибирати необхідну для розгортання продукцію при низхідному аналізі за першим символом ще не розпізнаної частини слова. "LA(1)" позначає речення "Look Ahead 1 symbol", тобто "подивитися спереду на 1 символ".

Нехай G=(X, N, P, S) – КВ-граматика, і за словом w треба визначити, чи належить воно до L(G). Нехай S® v1|…|vp – усі продукції з нетерміналом S ліворуч. Потрібну для розгортання S продукцію S® vi можна визначити безпосередньо за першим символом слова w, якщо множини перших символів ланцюжків, вивідних із v1, v2, … , vp, не перетинаються. Взагалі, нехай aman – нерозпізнана частина слова, початок якої має виводитися з нетермінала A, і A® w1|…|wk – усі продукції з A ліворуч. Тоді потрібна для розгортання A продукція A® wi визначається за першим символом am, якщо множини перших символів ланцюжків, вивідних з w1, w2, … , wk, не перетинаються.

Отже, для кожного нетермінала A та кожної правої частини wi продукцій A ® w1 | w2 | … | wk означимо множини

first ( wi ) = { a | a Î X* і wi Þ az для деякого слова z },

first ( A ) = first ( wi ).

Граматика може мати так звані e -продукції вигляду A® e . У такому разі, якщо AvÞ *b1bn, то b1 може починати слово, вивідне як з A, так і з v. Визначити за символом b1 , з чого саме виводиться слово, можна за умови, що first(A) не містить перших символів слів, вивідних із v. Множину цих перших символів ланцюжків, що виводяться з усіх можливих правих контекстів нетермінала A, позначимо follow (A):

follow ( A ) = { a | S Þ * uAv, a Î first ( v ) }.

Граматика називається LA(1)-граматикою, якщо:

(1) для кожного нетермінала A з продукціями A® w1|…|wk , де wi¹ e для всіх i=1,…,k, справджується умова

first ( wi ) Ç first ( wj ) = Æ при i, j = 1, … , k, i ¹ j;

(2) для кожного нетермінала A такого, що в P є продукція A ® e , справджується

first ( A ) Ç follow ( A ) = Æ .

Умови (1), (2) називаються LA(1)-умовами.

Не кожна КВ-мова породжується LA(1)-граматикою, але синтаксис практично всіх конструкцій сучасних мов програмування можна задати LA(1)-граматиками. Досить часто мова "природно" задається не LA(1)-граматикою, але таку граматику для неї можна побудувати.

Приклад 21.9. За продукціями E® E+T|T, T® T*F|F, F® (E)|a граматики G0 маємо

first ( (E) ) = { ( }, first ( a ) = { a }, звідки

first ( F ) = { a, ( }; first ( T*F ) = first ( F ), звідки

first ( T*F ) Ç first ( F ) ¹ Æ ,

тобто G0 не є LA(1)-граматикою. Проте мова виразів L(G0) задається еквівалентною LA(1)-граматикою. Побудуємо її.

Із T виводяться слова F, F*F, F*F*F, … . Додамо нетермінал B та правила B® e |*FB, T® FB замість правил T® F|T*F. Маємо

first ( T ) = first ( F ) = { a, ( }, first ( *FB ) = { * },

first ( B ) = { * }, follow ( B ) = follow ( T ) =

= follow ( E ) = { +, ) }.

Отже, продукції T® FB і B® e |*FB не порушують LA(1)-умови. Аналогічно, додавши нетермінал A, а замість правил E® E+T|T правила E® TA, A® e |+EA, одержимо LA(1)-граматику.ç

21.2.4. Ліворекурсивні та розширені продукції

Правило вигляду A® Av називається ліворекурсивним. Якщо в граматиці є продукції A® Av|u, де u¹ e , то first(Av)=first(u)¹ Æ , і граматика не є LA(1)-граматикою. Але за допомогою цих правил виводяться слова з множини {u, uv, uvv, …}, яка задається регулярним виразом uv* або u{v}. Замість продукцій A® Av|u запишемо A® u{v}. Продукції з регулярними виразами в правій частині називаються розширеними, як і граматики з такими продукціями. Неважко переконатися, що розширені правила не збагачують множину мов, породжених КВ-граматиками.

Приклад 21.10. Розширена граматика G01 із правилами E® T{+T}, T® F{*F}, F® (E)|a еквівалентна граматиці G0. Фактично РБНФ є іншим записом розширених продукцій, а сукупності РБНФ – іншою формою розширених КВ-граматик.ç

Задачі

21.6. Означити КВ-граматику, що задає мову

а) { anbm | n ³ m ³ 0 };

б) { ambn | n ³ m ³ 0 };

в)* паліндромів, тобто симетричних слів, у алфавіті { a, b };

г) слів у алфавіті { a, b }, які мають рівні кількості символів a і b.

21.7. Побудувати множини first і follow для всіх нетерміналів граматики з продукціями

а) S ® aSb | SS | e ;

б) S ® aSa | bSb | c | e ;

в) E ® E+E | E*E | (E) | a;

г) S ® aAS | b, A ® a | bSA;

д)* S ® A | B, A ® aAb | 0, B ® aBbb | e ;

е) S ® abA | e , A ® Saa | b.

Чи задовольняє граматика LA(1)-умовам?

21.8. Побудувати розширену LA(1)-граматику за ліворекурсивною з продукціями

а) S ® SAB | e , A ® A1 | 0, B ® 0B0 | 1B1 | e ;

б) I ® ID | IL | L, L ® a | b, D ® 0 | 1 | 2;

в) R ® IPF, I ® DI | D, F ® FD | D, D ® 0 | 1 | … | 9, P ® . .

21.3. Побудова алгоритму LA(1)-аналізу

21.3.1. Правила побудови

Нехай G=(X, N, P, S) – LA(1)-граматика без e -правил, можливо, розширена. Опишемо побудову програми синтаксичного аналізу слів мови L(G). Програма буде містити процедури, іменами яких є відповідні їм нетермінали граматики.

Процедура, відповідна нетерміналу A, описує аналіз ланцюжків, вивідних із A. Цими ланцюжками є слова мови або їхні підслова. Алгоритм процедури такий. Нехай A® w1|…|wk – усі продукції з нетерміналом A ліворуч, a1a2an – ланцюжок, початок якого треба виводити з A. Спочатку визначається, якій із множин first(w1), … , first(wk) належить символ a1. Нехай нею буде first(w1), і в найпростішому випадку w1=Y1Y2Ym, де Yi – термінал або нетермінал. Початок ланцюжка має виводитися з Y1.

Якщо Y1 – термінал, то перевіряється рівність a1=Y1.

Якщо Y1нетермінал, то з a1 починається частина слова, вивідна з Y1, і для аналізу початку ланцюжка a1a2… викликається процедура Y1.

В обох випадках, після перевірки рівності або повернення з виклику Y1, за деякого j³ 2 початок непроаналізованої частини ланцюжка ajaj+1… повинен виводитися з Y2 тощо. Перший символ непроаналізованої частини ланцюжка називатимемо поточним.

Отже, за правими частинами wi продукцій будуються фрагменти процедури A; вони виконуються, коли поточний символ ланцюжка міститься у відповідній множині first ( wi ).

Зробимо уточнення програми та правил побудови процедур. Нехай w – слово, що аналізується, ch – його поточний символ, функція getc задає добування наступного символу слова, змінна finch позначає спеціальний символ, що повертається функцією getc після закінчення слова w. Нехай ok – бульова змінна, що є ознакою належності wÎ L(G), а процедура error задає присвоювання ok:=false. Тілом програми є

begin

ok := true;

ch := getc;

S; { виклик процедури, відповідної }

{ головному нетерміналу }

writeln ( (ch = finch) and ok )

end.

Нехай A є нетерміналом із продукціями A® w1|…|wk , а S1,…, Sk позначають множини first(w1),…,first(wk), які не перетинаються. За таких умов тілом процедури A є складений оператор

begin

if ch in S1 then оператор-для-w1 else

if ch in Sk then оператор-для-wk else

error

end

Зокрема, якщо Si містить лише один символ x, то замість умови chinSi можна записати ch = x.

Праві частини розширених граматик є виразами, складеними з послідовностей символів алфавіту X і метасимволів, якими є дужки (), [], {} та символи |. Розглянемо праву частину v розширеного правила як послідовність виразів Y1Yk , в якій Yi є або символом з XÈ N, або виразом вигляду (u), [u], чи {u}, що не міститься всередині інших дужок, де u – послідовність нетерміналів, терміналів и дужок. За правою частиною v будується складений оператор із послідовністю операторів, відповідних до Y1,…,Yk. Нехай Y позначає один із виразів Y1,…,Yk. Відповідний оператор визначається виглядом Y за наступними правилами.

ch:=getc.

if ch = Y then ch:=getc else error,

тобто треба перевірити збігання поточного символу з Y та перейти до наступного символу.

Y.

if ch in T1 then оператор-для-u1 else

if ch in Tm then оператор-для-um else

error.

if ch in T then оператор-для-u.

while ch in T do оператор-для-u.

Зокрема, коли ланцюжок u починається терміналом, тобто u=xu1, де xÎ X, то цикл має вигляд

while ch = x do

begin

ch := getc;

оператор-для-u1

end.

Оператори, відповідні до u, u1, … , um , записуються за цими ж правилами.

21.3.2. Побудова аналізатора арифметичних виразів

Розширена LA(1)-граматика G01 із продукціями E® T{+T}, T® F{*F}, F® (E)|a породжує мову арифметичних виразів. Згідно з наведеними правилами запишемо процедури E, T, F:

procedure E;

begin

T;

while ch = '+' do

begin ch := getc; T end

end;

procedure T;

begin

F;

while ch = '*' do

begin ch := getc; F end

end;

procedure F;

begin

if ch = '(' then

begin

ch := getc; E;

if ch = ')' then ch := getc

else error

end

else

if ch = 'a' then ch := getc

else error

end

Побудовані процедури взаємно рекурсивні: тіло E містить виклики процедури T, тіло T – виклики F, а тіло F – виклики E. У мові Паскаль кожне ім'я повинно бути означеним вище від його вживання, тому незрозуміло, в якій послідовності треба записати процедури E, T, F. У таких випадках використовують конструкцію forward .

Якщо в програмі є взаємно рекурсивні підпрограми, то за правилами мови Паскаль спочатку в блоці охоплюючої їх програми (підпрограми) записуються лише заголовки кількох із них (зокрема, однієї), а замість їх блоків пишеться слово forward, тобто, "попереду". Решту підпрограм розміщують так, щоб вони містили виклики підпрограм, чиї заголовки (разом із блоком чи словом forward) уже записано вище. Підпрограми, записані спочатку без блоку, розміщаються в кінці зі скороченим заголовком вигляду

procedure <ім'я>; або function <ім'я>.

Список параметрів, дужки й тип функції в скороченому заголовку відсутні. У даному прикладі процедури E, T, F не мають параметрів, тому скорочені заголовки не відрізняються від повних.

Запишемо програму аналізу арифметичних виразів, вважаючи, що вираз набирається на клавіатурі, а читання його символів задається процедурою getc із модуля Inbuf (розділ 20):

program Aexan ( input, output );

uses Inbuf;

var ch : char;

ok : boolean;

procedure error;

begin ok := false; ch := finch end;

procedure E; { тут повний заголовок }

forward;

procedure F;

… E … { виклик процедури E }

end;

procedure T;

… F … { виклик процедури F }

end;

procedure E; { тут скорочений заголовок }

… T … { виклик процедури T }

end;

begin

ok := true; ch := getc;

E; { виклик процедури, відповідної до }

{ головного нетермінала }

writeln ( (ch = finch) and ok )

end.

Як бачимо, всі виклики посилаються на процедури, чиї імена вже означено раніше.

Уживання взаємно рекурсивних підпрограм інколи називається непрямою рекурсією.

21.4. Аналіз та обчислення дужкових виразів

У розділі 9 розглядалися дужкові арифметичні вирази, мова яких породжується розширеною LA(1)-граматикою G2:

( { 0, … , 9, ., c, i, n, o, s, +, *, -, /, (, ) },

{ E, T, F, A, C, D, N },

{ E ® T { +T | -T }, T ® F { *F | /F }, F ® (E) | C | A,

C ® N (E), N ® 'sin' | 'cos',

A ® D { D } [ . { D } ], D ® 0 | … | 9 },

E ).

Імена A, C, N є скороченнями фраз "Arithmetic constant", "Call of function", "Name of function" відповідно, тобто "Арифметична стала", "Виклик функції", "Ім'я функції".

Побудуємо програму Aexval аналізу та обчислення арифметичних виразів на основі програми Aexan із попереднього підрозділу. Нехай вираз подається в кількох рядках, і ознакою кінця є порожній рядок. Читання лексем виразу задається модулями Glx та Inbuf, означеними в розділі 20. Замість функції getc добування наступного символу з програми Aexan використовується функція getlx добування наступної лексеми, а замість поточного символу ch – поточна лексема lx типу Tlx. Ознака наявності лексеми, що повертається з функції getlx, присвоюється бульовій змінній islx.

Підпрограми для нетерміналів A, N тут не створюються, оскільки аналіз лексем, позначених ними, уже задаєно в модулі Glx. Кожна з процедур E, T, F перетворюється на функцію обчислення тієї частини виразу, яка аналізується при виконанні її виклику. Побудуємо їх таким чином, щоб за помилкового виразу з них поверталося значення 1.

Згідно з продукціями граматики G2, функція F обчислення множника у виразі має такий вигляд:

function F : real;

begin

if ( lx.lxt = par ) and ( lx.prt = '(' ) then

begin

islx := getlx ( lx ); F := E;

if islx and ( lx.lxt = par ) and ( lx.prt = ')' )

then islx := getlx ( lx )

else begin error; F := 1 end

end

else

if lx.lxt = con then

begin F := lx.numb; islx := getlx ( lx ) end

else

if lx.lxt = nam then F := C

else begin error; F := 1 end

end

Функція C задає обчислення значення, що має повернутися з указаного у виразі виклику функції sin чи cos:

function C : real;

var lx1 : Tlx; v : real;

begin

lx1 := lx; islx := getlx ( lx );

if islx and ( lx.lxt = par ) and ( lx.prt = '(' ) then

begin

islx := getlx ( lx ); v := E;

if islx and ( lx.lxt = par ) and ( lx.prt = ')' )

then islx := getlx ( lx )

else begin error; C := 1 end;

if ok then

if lx1.name = 'sin' then C := sin ( v )

else C := cos ( v )

else begin error; C := 1 end

end

else begin error; C := 1 end

end

Функція E задає обчислення виразу, вивідного з E:

function E : real;

var lx1 : Tlx; v : real;

begin

v := T;

while ok and ( lx.lxt = ops )

and ( lx.sig in ['+', '-'] ) do

begin

lx1 := lx; islx := getlx ( lx );

case lx1.sig of

'+' : v := v + T;

'-' : v := v - T

end

end;

if ok then E := v else E := 1

end

Функцію T обчислення доданка у виразі, яка має аналогічну функції E структуру, залишаємо для самостійної розробки. Головна програма подібна до програми Aexan:

program Aexval ( input, output );

uses Inbuf, Glx

var islx, ok : boolean;

v : real; lx : Tlx;

procedure error;

begin ok := false; islx := false end;

function E : real; forward;

function C : real; … end;

function F : real; … end;

function T : real; … end;

function E; { скорочений заголовок } … end;

begin

ok := true;

v := 0;

islx := getlx ( lx );

v := E;

if ok and not islx then writeln ( v )

else writeln ( '***error***' )

end.

Задачі

У задачах 21.9-21.11 вхідний текст набирається на клавіатурі в кількох рядках, довжина яких не більше 80. Ознакою кінця є порожній рядок. У програмах рекомендується успадкувати модуль буферизованого читання (розділ 20).

21.9. Синтаксичні об'єкти задаються продукціями граматик, у яких нетермінали позначаються в дужках <>, а термінали – послідовностями символів у апострофах. Нетермінали <L> і <D> позначають букви та цифри:

<L> ® 'a' | … | 'z', <D> ® '0' | … | '9'.

Написати програму розпізнавання

а) арифметичних виразів <A> з однолітерними іменами змінних:

<A> ® <I> | '(' <A> { <OP> <A> } ')', <OP> ® '+' | '-', <I> ® 'a' | … | 'z';

б) арифметичних виразів <A> з ідентифікаторами:

<A> ® <I> | '(' <A> { <OP> <A> } ')', <OP> ® '+' | '-', <I> ® <L> { <L> | <D> };

в) арифметичних виразів <A> зі сталими:

<A> ® <C> | '(' <A> { <OP> <A> } ')', <OP> ® '+' | '-', <C> ® <D> { <D> };

г) бульових виразів <B> з ідентифікаторами:

<B> ® <I> | <OP1> <B> | '(' <B> { <OP> <B> } ')',

<OP1> ® '!', <OP> ® '&&' | '||', <I> ® <L> { <L> | <D> },

де знаки '!', '&&', '||', записані за зменшенням старшинства, задають відповідно операції заперечення, кон'юнкції та диз'юнкції;

д) змінних <IV>, індексованих бездужковими виразами із змінними:

<IV> ® <I> '[' <IE> { ',' <IE> } ']', <IE> ® <P> { <OP> <P> },

<OP> ® '+' | '-', <P> ® <I> | <IV>, <I> ® <L> { <L> | <D> };

е) викликів <FC> одномісних функцій з однолітерними іменами:

<FC> ® <L> '(' <E> ')',

<E> ® <T> { <AOP> <T> }, <AOP> ® '+' | '-',

<T> ® <F> { <MOP> <F> }, <MOP> ® '*' | '/',

<F> ® '(' <E> ')' | <FC> | <C>, <C> ® <D> { <D> }.

21.10. Синтаксичні об'єкти задаються продукціями граматик (задача 21.9, варіанти а-е). У вхідному виразі, що задає об'єкт, можливі помилки. Написати програму аналізу правильності виразів з указанням місця в них, де вперше порушується задана граматикою структура.

21.11. Варіантами цієї задачі є варіанти задач 20.16-20.18. Виконати відповідний варіант з урахуванням того, що у виразах можливі помилки, які мають бути вказані при виконанні програми.

Двадцять другий розділ