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

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

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

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

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

Приклади

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

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

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

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

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

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

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

Вираз L_1 L₂ позначає об'єднання L₁ і L₂ – мову {w|w L₁ або w L₂}. Наприклад, {a, ab} {a, b, ba}={a, b, ab, ba}.

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

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

Вираз L^* позначає ітерацію мови L – мову {wⁱ|w L за i 0}, тобто { } L L^{2 } . Зазначимо, що ітерація не подається жодним скінченним виразом з операціями катенації та  і тому не є похідною від них. Якщо в мові L є непорожнє слово, то мова L^* нескінченна. Наприклад, вираз {ab}^* задає мову { ,ab,abab,ababab, }, {a,b}{a,b,1}^* – множину ідентифікаторів у алфавіті {a, b, 1}.

Регулярні вирази й задані ними регулярні мови означимо індуктивно. Вирази  ,  та a при a X є регулярними в алфавіті X і задають відповідно регулярні мови  , { }, {a}. Якщо r₁ і r₂ – регулярні вирази, що задають регулярні мови L₁ і L₂ , то вирази (r₁), r₁+r₂, r₁r₂, r₁^* є регулярними й задають відповідно регулярні мови L₁, L_1 L₂, L₁L₂, L₁^*.

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

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

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

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

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

є множиною {(ⁿ)ⁿ|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 w₁ww₂ і v w₁w₂ записується продукція v w₁[w]w₂, а замість продукцій v w₁u₁w₂ і v w₁u₂w₂ – продукція v_1 w₁(u₁|u₂)w₂ .

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

G₁ =({ 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 = x₁ u x₂ , w = x₁ y x₂ , u  y  P.

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

2. На множині (X N)^* означається відношення виводимості, позначене  *_G (або  *, коли відомо, якою саме є G): v *w, якщо v=w або існує послідовність w₁, w₂, … , w_n слів, де n 1, така, що v w₁, w_1 w₂, … , w_n-1 w_n, w_n=w. Так, у граматиці G₁ BC *a1, оскільки BC aC, aC a1. Послідовність v w_1 w_2 … w_n називається виведенням w_n із v, а n – довжиною виведення. Інколи довжину записують замість '*' таким чином: v ⁿw, наприклад, BC  ²a1.

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

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

Приклади

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

5. Граматика

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

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

I )

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

6. Граматика G₃ = ( { (, ) }, { S }, { S   | ( S ) }, S ) задає множину "вкладених дужок" { (ⁿ)ⁿ | n  0 }.

21.7. Граматика

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

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

S )

визначає мову { aⁿbⁿcⁿ | n  1 }.

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

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

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

( {a, …, z, 0, …, 9}, {I, C}, {I  (a|…|z)C, C   |C(a |…|z|0|…|9)}, I )

– граматиці G₂.

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

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

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

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

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

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

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

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

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

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

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

G₀ = ( { 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 в G₀ з розгортанням нетерміналів, перших ліворуч у проміжних ланцюжках, має вигляд:

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 ? Тут необхідний вибір зроблено тому, що структура термінального слова була відома заздалегідь. Але, взагалі, структура слова до початку його аналізу невідома, і виникає необхідність перебирати продукції для застосування потрібної.

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

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

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

Нехай G=(X, N, P, S) – КВ-граматика, і за словом w треба визначити, чи належить воно до L(G). Нехай S v₁|…|v_p – усі продукції з нетерміналом S ліворуч. Потрібну для розгортання S продукцію S v_i можна визначити безпосередньо за першим символом слова w, якщо множини перших символів ланцюжків, вивідних із v₁, v₂, … , v_p, не перетинаються. Взагалі, нехай a_m…a_n – нерозпізнана частина слова, початок якої має виводитися з нетермінала A, і A w₁|…|w_k – усі продукції з A ліворуч. Тоді потрібна для розгортання A продукція A w_i визначається за першим символом a_m, якщо множини перших символів ланцюжків, вивідних з w₁, w₂, … , w_k, не перетинаються.

Отже, для кожного нетермінала A та кожної правої частини w_i продукцій A  w₁ | w₂ | … | w_k означимо множини

first ( w_i ) = { a | a  X^* і w_i  az для деякого слова z },

first ( A ) = first ( w_i ).

Граматика може мати так звані  -продукції вигляду A  . У такому разі, якщо Av *b₁…b_n, то b₁ може починати слово, вивідне як з A, так і з v. Визначити за символом b₁ , з чого саме виводиться слово, можна за умови, що first(A) не містить перших символів слів, вивідних із v. Множину цих перших символів ланцюжків, що виводяться з усіх можливих правих контекстів нетермінала A, позначимо follow (A):

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

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

(1) для кожного нетермінала A з продукціями A w₁|…|w_k , де w_{i } для всіх i=1,…,k, справджується умова

first ( w_i )  first ( w_j ) =  при i, j = 1, … , k, i  j;

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

first ( A )  follow ( A ) =  .

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

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

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

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

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

first ( T*F )  first ( F )   ,

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

Із T виводяться слова F, F*F, F*F*F, … . Додамо нетермінал B та правила B  |*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  |*FB не порушують LA(1)-умови. Аналогічно, додавши нетермінал A, а замість правил E E+T|T правила E TA, A  |+EA, одержимо LA(1)-граматику.

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

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

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

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

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

Процедура, відповідна нетерміналу A, описує аналіз ланцюжків, вивідних із A. Цими ланцюжками є слова мови або їхні підслова. Алгоритм процедури такий. Нехай A w₁|…|w_k – усі продукції з нетерміналом A ліворуч, a₁a₂…a_n – ланцюжок, початок якого треба виводити з A. Спочатку визначається, якій із множин first(w₁), … , first(w_k) належить символ a₁. Нехай нею буде first(w₁), і в найпростішому випадку w₁=Y₁Y₂…Y_m, де Y_i – термінал або нетермінал. Початок ланцюжка має виводитися з Y₁.

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

Якщо Y₁ – нетермінал, то з a₁ починається частина слова, вивідна з Y₁, і для аналізу початку ланцюжка a₁a₂… викликається процедура Y₁.

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

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

Зробимо уточнення програми та правил побудови процедур. Нехай 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 w₁|…|w_k , а S₁,…, S_k позначають множини first(w₁),…,first(w_k), які не перетинаються. За таких умов тілом процедури A є складений оператор

begin

if ch in S₁ then оператор-для-w₁ else

…

if ch in S_k then оператор-для-w_k else

error

end

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

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

• Якщо Y є першим терміналом Y₁, то оператором є

ch:=getc.

• Якщо Y є терміналом, але не першим у ланцюжку v, то оператор має вигляд

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

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

• Якщо Y є нетерміналом, то оператором є виклик процедури

Y.

• Якщо Y має вигляд (u₁|…|u_m) і T_i позначає first(u_i) при i=1,…,m, то треба визначити, до якої з множин T_i належить поточний символ, і виконати оператор, відповідний до u_i:

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

…

if ch in T_m then оператор-для-u_m else

error.

• Якщо Y має вигляд [u], T=first(u), то за виконання умови ch T треба виконати оператор, відповідний до u:

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

• Якщо Y має вигляд {u}, T=first(u), то за виконання умови ch T треба повторювати виконання оператора, відповідного до u:

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

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

while ch = x do

begin

ch := getc;

оператор-для-u₁

end.

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

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

Розширена LA(1)-граматика G₀₁ із продукціями 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.

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

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

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

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

( { 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.

Згідно з продукціями граматики G₂, функція 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.