Елементи синтаксичного аналізу

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



1. Формальні мови та їх задання
1.1. Формальна мова та задача належності
Алфавітомназивається скінченна множина символів. Позначатимемо його X. Словом (фразою, або ланцюжком) у алфавіті Xназивається послідовність символів із X. Множина всіх скінченних слів у алфавіті Xпозначається X*. Зауважимо, що вона нескінченна. Вона містить порожнє слово– послідовність довжиною 0, позначену буквою . Множину X*\{} позначимо X+, а слово вигляду www, де слово w із X+записано nразів – wn. Вважатимемо, що w= .
Довільна підмножина множини X*називається формальною мовою. Далі в цьому розділі вона буде називатися просто мовою.
Приклади
21.1.Множина всіх слів у алфавіті {a} позначається {a}* = {, 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 ми вже познайомилися з одним із них – це були БНФ та їх сукупності. Розглянемо ще деякі.
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={, b} катенація L1L2={a, ab, abb}.--PAGE_BREAK--
Від катенації походить піднесення до степеня: L={}, Li=Li-1Lза i>0. Так, вираз {, a, aa}2задає мову {, a, aa, aaa, aaaa}.
Вираз L*позначає ітераціюмови L– мову {wi|wLза i0}, тобто {}LL2. Зазначимо, що ітерація не подається жодним скінченним виразом з операціями катенації та і тому не є похідною від них. Якщо в мові Lє непорожнє слово, то мова L*нескінченна. Наприклад, вираз {ab}*задає мову {,ab,abab,ababab,}, {a,b}{a,b,1}*– множину ідентифікаторів у алфавіті {a, b, 1}.
Регулярні вирази й задані ними регулярні мови означимо індуктивно. Вирази , та aпри aXє регулярнимив алфавіті Xі задають відповідно регулярні мови, {}, {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)*    продолжение
--PAGE_BREAK--
тобто правий ланцюжок є довільною послідовністю терміналів і нетерміналів, а лівий містить принаймні один нетермінал.
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Gw, якщо v= x1ux2, w= x1yx2, uyP.
При цьому кажуть, що w безпосередньо виводиться з vзастосуванням продукції uy. Наприклад, у граматиці G1із прикладу 21.3BC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. Так, у граматиці G1BC*a1, оскільки BCaC, aCa1. Послідовність vw1w2…wnназивається виведеннямwnіз v, а n– довжиною виведення. Інколи довжину записують замість '*' таким чином: vnw, наприклад, BC2a1.    продолжение
--PAGE_BREAK--
3. Якщо SG*w, то послідовність S…wназивається виведенням слова w у граматиці G, а слово w– вивідним. Так, слова A, BC, aC, a1 вивідні в граматиці G1.
4. Вивідні слова в алфавіті Xназиваються породжуваними, а множина їх усіх –мовою, що задається (породжується) граматикою G: L(G) = {w| wX* та S * w}.
Приклади
4.Граматика G1із прикладу 21.3 задає мову { a, a1, a2 }.
5.Граматика
G2= ( { a, …, z, 0, …, 9 }, { I, L, D},
{ IL| IL| ID, L a| … | z, D0 |… | 9 },
I)
породжує множину ідентифікаторів.
6.Граматика G3= ( { (, )}, { S}, { S| (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|C(a|…|z|0|…|9)}, I)
– граматиці G2.
Є два види граматик з продукціями обмеженого вигляду, якими задаються регулярні мови, – це праволінійні та ліволінійні граматики. Праволінійною(ліволінійною) називається граматика, всі продукції якої мають вигляд Awабо AwB(відповідно, Awабо ABw), де A, B– нетермінали, wX*. Усі можливі праволінійні та ліволінійні граматики з термінальним алфавітом Xпороджують в точності клас регулярних мов над X. Це доводиться, наприклад, в [АУ].     продолжение
--PAGE_BREAK--
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    продолжение
--PAGE_BREAK--
 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 1symbol", тобто «подивитися спереду на 1 символ».
Нехай G=(X, N, P, S) – КВ-граматика, і за словом wтреба визначити, чи належить воно до L(G). Нехай Sv1|…|vp– усі продукції з нетерміналом Sліворуч. Потрібну для розгортання Sпродукцію Sviможна визначити безпосередньо за першим символом слова w, якщо множини перших символів ланцюжків, вивідних із v1, v2, …, vp, не перетинаються. Взагалі, нехай am…an– нерозпізнана частина слова, початок якої має виводитися з нетермінала 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).
Граматика може мати так звані -продукціївигляду A. У такому разі, якщо Av*b1…bn, то b1може починати слово, вивідне як з A, так і з v. Визначити за символом b1, з чого саме виводиться слово, можна за умови, що first(A) не містить перших символів слів, вивідних із v. Множину цих перших символів ланцюжків, що виводяться з усіх можливих правих контекстів нетермінала A, позначимо follow(A):
follow ( A) = { a| S* uAv, afirst ( v) }.    продолжение
--PAGE_BREAK--
Граматика називається LA(1)-граматикою, якщо:
(1) для кожного нетермінала Aз продукціями Aw1|…|wk, де wiдля всіх i=1,…,k, справджується умова
first ( wi) first ( wj) = при 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}. Продукції з регулярними виразами в правій частині називаються розширеними, як і граматики з такими продукціями. Неважко переконатися, що розширені правила не збагачують множину мов, породжених КВ-граматиками.    продолжение
--PAGE_BREAK--
Приклад 10. Розширена граматика G01із правилами ET{+T}, TF{*F}, F(E)|aеквівалентна граматиці G. Фактично РБНФ є іншим записом розширених продукцій, а сукупності РБНФ – іншою формою розширених КВ-граматик.
3.1. Правила побудови
Нехай G=(X, N, P, S) – LA(1)-граматика без -правил, можливо, розширена. Опишемо побудову програми синтаксичного аналізу слів мови L(G). Програма буде містити процедури, іменами яких є відповідні їм нетермінали граматики.
Процедура, відповідна нетерміналу A, описує аналіз ланцюжків, вивідних із A. Цими ланцюжками є слова мови або їхні підслова. Алгоритм процедури такий. Нехай Aw1|…|wk– усі продукції з нетерміналом Aліворуч, a1a2…an– ланцюжок, початок якого треба виводити з A. Спочатку визначається, якій із множин first(w1), …, first(wk) належить символ a1. Нехай нею буде first(w1), і в найпростішому випадку w1=Y1Y2…Ym, де 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) andok )
end.
Нехай Aє нетерміналом із продукціями Aw1|…|wk, а S1,…, Skпозначають множини first(w1),…,first(wk), які не перетинаються. За таких умов тілом процедури Aє складений оператор
begin
ifch inS1thenоператор-для-w1else
…
ifch inSkthenоператор-для-wkelse
error
end
Зокрема, якщо Siмістить лише один символ x, то замість умови chinSiможна записати ch = x.    продолжение
--PAGE_BREAK--
Праві частини розширених граматик є виразами, складеними з послідовностей символів алфавіту X і метасимволів, якими є дужки (), [], {} та символи |. Розглянемо праву частину vрозширеного правила як послідовність виразів Y1… Yk, в якій Yiє або символом з XN, або виразом вигляду (u), [u], чи {u}, що не міститься всередині інших дужок, де u– послідовність нетерміналів, терміналів и дужок. За правою частиною vбудується складений оператор із послідовністю операторів, відповідних до Y1,…,Yk. Нехай Yпозначає один із виразів Y1,…,Yk. Відповідний оператор визначається виглядом Yза наступними правилами.
Якщо Yє першим терміналом Y1,то оператором є
ch:=getc.
Якщо Y є терміналом, але не першим у ланцюжку v,то оператор має вигляд
ifch = Ythench:=getc elseerror,
тобто треба перевірити збігання поточного символу з Yта перейти до наступного символу.
Якщо Yє нетерміналом, то оператором є виклик процедури
Y.
Якщо Yмає вигляд (u1|…|um) і Tiпозначає first(ui) при i=1,…,m, то треба визначити, до якої з множин Tiналежить поточний символ, і виконати оператор, відповідний до ui:
ifch inT1thenоператор-для-u1 else
…
ifch inTmthenоператор-для-um else
error.
Якщо Yмає вигляд [u], T=first(u), то за виконання умови chTтреба виконати оператор, відповідний до u:
ifch inTthenоператор-для-u.
Якщо Y має вигляд {u}, T=first(u), то за виконання умови chTтреба повторювати виконання оператора, відповідного до u:
whilech inT doоператор-для-u.
Зокрема, коли ланцюжок uпочинається терміналом, тобто u=xu1, де xX, то цикл має вигляд
whilech = xdo
begin
ch := getc;
оператор-для-u1
end.
Оператори, відповідні до u, u1, …, um, записуються за цими ж правилами.
3.2. Побудова аналізатора арифметичних виразів
Розширена LA(1)-граматика G01із продукціями ET{+T}, TF{*F}, F(E)|aпороджує мову арифметичних виразів. Згідно з наведеними правилами запишемо процедури E, T, F:
procedureE;
begin
T;
whilech = '+' do
beginch := getc; T end    продолжение
--PAGE_BREAK--
end;
procedureT;
begin
F;
whilech = '*' do
beginch := getc; F end
end;
procedureF;
begin
ifch = '(' then
begin
ch := getc; E;
ifch = ')' thench := getc
elseerror
end
else
ifch = 'a' thench := getc
elseerror
end
Побудовані процедури взаємно рекурсивні: тіло E містить виклики процедури T, тіло T – виклики F, а тіло F – виклики E. У мові Паскаль кожне ім'я повинно бути означеним вище від його вживання, тому незрозуміло, в якій послідовності треба записати процедури E, T, F. У таких випадках використовують конструкцію forward.
Якщо в програмі є взаємно рекурсивні підпрограми, то за правилами мови Паскаль спочатку в блоці охоплюючої їх програми (підпрограми) записуються лишезаголовкикількох із них (зокрема, однієї), а замість їх блоків пишеться слово forward, тобто, «попереду». Решту підпрограм розміщують так, щоб вони містили виклики підпрограм, чиї заголовки (разом із блоком чи словом forward) уже записано вище. Підпрограми, записані спочатку без блоку, розміщаються в кінці зі скороченим заголовкомвигляду
procedure; або function.
Список параметрів, дужки й тип функції в скороченому заголовку відсутні. У даному прикладі процедури E, T, F не мають параметрів, тому скорочені заголовки не відрізняються від повних.
Запишемо програму аналізу арифметичних виразів, вважаючи, що вираз набирається на клавіатурі, а читання його символів задається процедурою getc із модуля Inbuf (розділ 20):
programAexan ( input, output );
uses Inbuf;
varch: char;
ok: boolean;
procedureerror;
beginok := false; ch := finch end;
procedureE; { тут повний заголовок }
forward;
procedureF;
… E … { виклик процедури E }
end;
procedureT;
… F … { виклик процедури F }
end;
procedureE; { тут скорочений заголовок }
… T … { виклик процедури T }
end;
begin
ok := true; ch := getc;
E; { виклик процедури, відповідної до }
{ головного нетермінала }
writeln ( (ch = finch) andok )
end.
Як бачимо, всі виклики посилаються на процедури, чиї імена вже означено раніше.
Уживання взаємно рекурсивних підпрограм інколи називається непрямою рекурсією.
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" відповідно, тобто «Арифметична стала», «Виклик функції», "Ім'я функції".    продолжение
--PAGE_BREAK--
Побудуємо програму 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;
ifislx and( lx.lxt = par ) and( lx.prt = ')' )
then islx := getlx ( lx )
else beginerror; F := 1 end
end
else
iflx.lxt = con then
beginF := lx.numb; islx := getlx ( lx ) end
else
iflx.lxt = nam then F := C
else beginerror; F := 1 end
end
Функція C задає обчислення значення, що має повернутися з указаного у виразі виклику функції sin чи cos:
function C: real;
varlx1: Tlx; v: real;
begin
lx1 := lx; islx := getlx ( lx );
ifislx and( lx.lxt = par ) and( lx.prt = '(' ) then
begin
islx := getlx ( lx ); v := E;
ifislx and( lx.lxt = par ) and( lx.prt = ')' )
thenislx := getlx ( lx )
else beginerror; C := 1 end;
ifok then
iflx1.name = 'sin' then C := sin ( v )
elseC := cos ( v )
else beginerror; C := 1 end
end
else beginerror; C := 1 end
end
Функція E задає обчислення виразу, вивідного з E:
function E: real;
varlx1: Tlx; v: real;
begin
v := T;
whileok 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;
ifok then E := v else E := 1
end
Функцію T обчислення доданка у виразі, яка має аналогічну функції E структуру, залишаємо для самостійної розробки. Головна програма подібна до програми Aexan:
programAexval ( input, output );
usesInbuf, Glx
varislx, ok: boolean;
v: real; lx: Tlx;
procedureerror;
beginok := false; islx := falseend;
functionE: real; forward;
functionC: real; … end;
functionF: real; … end;
functionT: real; … end;
functionE; { скорочений заголовок } … end;
begin
ok := true;
v := 0;
islx := getlx ( lx );
v := E;
ifok andnotislx then writeln ( v )
else writeln ( '***error***' )
end.