Паскаль. Прикладне програмне забезпечення


Побудова алгоритму LA1аналізу

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

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

Процедура, відповідна нетерміналу A, описує аналіз ланцюжків, вивідних із A. Цими ланцюжками є слова мови або їхні підслова. Алгоритм процедури такий. Нехай A ® w1|| Wk – усі продукції з нетерміналом A ліворуч, A1 A2 An – ланцюжок, початок якого треба виводити з A. Спочатку визначається, якій із множин first W1, , first Wk належить символ A1. Нехай нею буде first W1, і в найпростішому випадку W1= Y1 Y2 Ym, де Yi – термінал або нетермінал. Початок ланцюжка має виводитися з Y1.

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

Якщо Y1 – нетермінал, то з A1 починається частина слова, вивідна з Y1, і для аналізу початку ланцюжка A1 A2 викликається процедура 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 S K Then Оператордляwk Else

Error

End

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

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

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

Ch:=getc.

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

If ch = Y Then ch:=getc Else error,

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

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

Y.

· Якщо Y має вигляд U1|| Um і Ti позначає first Ui при I=1,, M, то треба визначити, до якої з множин Ti належить поточний символ, і виконати оператор, відповідний до Ui:

If ch In T1 Then Оператордляu1 Else

If ch In Tm Then Оператордляum 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= Xu1, де X X, то цикл має вигляд

While ch = X Do

Begin

Ch:= getc;

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

End.

Оператори, відповідні до U, U1, , Um, записуються за цими ж правилами.

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

Розширена LA1граматика 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.

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

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