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

Реферат на тему:

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

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

Нехай G =(X , N , P , S ) – LA(1)-граматика без e -правил, можливо, розширена. Опишемо побудову програми синтаксичного аналізу слів мови 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_j a_{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 , то замість умови chin S_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 належить поточний символ, і ви

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать