Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Part4.doc
Скачиваний:
0
Добавлен:
01.03.2025
Размер:
583 Кб
Скачать
☆

4.11 Побудова канонічних таблиць lr-аналізу

Розглянемо найбільш загальну технологію побудови таблиці LR-аналізу для граматики. Згадаємо, що в SLR-методі стан i викликає згортання за продукцієюї А→α, якщо множина пунктів Ii містить пункт [А→α•] і a FOLLOW(А). У деяких ситуаціях, однак, коли стан i розміщується на вершині стека, активний префікс βα у стеку такий, що в правосентенціальній формі за βA не може йти символ а. Отже, згортка по продукції А→α буде неприпустимою при вхідному символі а.

Приклад 4.5

Знову звернемося до прикладу 4.4, де у стані 2 був пункт R →L•, що міг відповідати наведеній вище продукції А→α, і а міг бути знаком =, що належить FOLLOW(R). Таким чином, SLR-аналізатор у стані 2 з черговим вхідним символом = викликає згортання за продукцією R→L. Однак у граматиці правосентенціальна форма, що починається з R = ..., відсутня. Отже, стан 2, що відповідає тільки активному префіксові L, не повинен викликати згортання цього L в R.

Стан може містити додаткову інформацію, що дозволить виключити деякі з таких некоректних згортань за продукцією А→α. Розділяючи за необхідності стани, ми можемо змусити кожен стан LR-аналізатора точно вказувати, який вхідний символ може йти за основою α, для якої існує можливе згортання в А.

Додаткова інформація впроваджується у стан шляхом перевизначення пунктів для включення термінального символа як другого компонента. Загальним видом пункту стає [А→α•β, a], де А→αβ являє собою продукцію; а – термінал або маркер кінця рядка $. Такий об'єкт назвемо LR(1)-пунктом. Тут 1 означає довжину другого компонента, який називають попереднім переглядом (lookahead) пункту. Попередній перегляд не відіграє ролі у пункті вигляду [А→α•β, a], де β ≠ ε, однак пункт вигляду [А→α•, a] викликає згортання за продукцією А→α тільки тоді, коли черговий вхідний символ – а. Отже, згортання за продукцією А→α виконується тільки для тих вхідних символів а, для яких [А→α•, a] є LR(1)-пунктом у стані на вершині стека. Множина таких а завжди буде підмножиною FOLLOW(A), але може бути і власною підмножиною.

Формально ми говоримо, що LR(1)-пункт [А→α•β,a], допустимий для активного префікса γ, якщо існує породження S δAw δαβw, де

1) γ=δα ;

2) або а є першим символом w, або w являє собою ε, а а – $.

Приклад 4.6

Розглянемо граматику

S → ВВ ,

B → aВ|b .

Є праве породження S aaBab aaaBab. Ми бачимо, що пункт [B→a•B, a] допустимий для активного префікса γ=ааа, вважаючи у наведеному вище визначенні δ=аа, А=B, w=ab, α=a і β=В.

Є також праве породження S BaB BaaB, відповідно до якого пункт [B→a•B, $] допустимий для активного префікса Ваа.

Метод побудови системи множин допустимих LR(1)-пунктів, по суті, той самий, що й спосіб побудови канонічної системи множин LR(0)-пунктів. Нам необхідно внести зміни тільки у дві функції – closure і goto.

Щоб розібратися у новому визначенні операції closure, розглянемо пункт вигляду [A→a•Bβ, a] з множини пунктів, допустимих для деякого активного префікса γ. Тоді існує праве породження S δAax δαAβax, де γ=δα. Припустимо, що βax породжує термінальний рядок by. Тоді для кожної продукції вигляду B→η з деяким η ми одержуємо породження S γBby γηby. Отже, пункт [A→ •η, b] допустимий для активного префікса γ. Відмітимо, що b може бути першим терміналом, виведеним з β. Можливо також, що з β виводиться ε у породженні βAx by, і b, отже, може бути терміналом а. Резюмуючи обидві можливості, ми говоримо, що b може бути будь-яким терміналом з FIRST(βAx). Відмітимо, що х не може містити перший термінал bу, так що FIRST(βax)= =FIRST(βa). Тепер представимо спосіб побудови множин LR(1)-пунктів.

Алгоритм 4.9 Побудова множин LR(1)-пунктів

function closure(I);

begin

repeat

for кожного пункту [А→α•Bβ, a] I, кожної продукції В→γ із G' і кожного термінала b із FIRST(βa), такого, що [B→• γ, b] I do додати

[B→• γ, b] в I;

until пунктів для додавання в I більше немає;

return I;

end;

function goto (I, X);

begin

Нехай J – множина пунктів [А→αX•β, a], таких, що [А→α•Xβ, a] I;

return closure (J);

end;

procedure items (G’);

begin

C:= {closure ( {[S’→S, $]} )};

repeat

for кожної множини пунктів I C і кожного символа граматики X, таких, що goto (I, X) не порожньо і не належить C do додати goto(I,X) у C

until множин пунктів для додавання в C більше немає

end

Розглянемо таку розширену граматику:

S'→ ВВ ,

S → CC , (4.6)

C → cC|d .

Почнемо з обчислення замикання {[S' → •S, $]}. Для цього зіставимо пункт {[S' → •S, $]} з пунктом [А→α•Bβ,a] із процедури closure; таким чином, A = S', α = ε, B=S, β = ε і a = $. Функція closure вимагає додати [B → •γ, b] у FIRST(βa) для кожної продукції В → γ і термінала b. У нашій граматиці В → γ відповідає S → CC, і оскільки β дорівнює ε, а а – $, b може бути тільки $. Таким чином, ми додаємо [S' → •CC, $]}.

Далі ми продовжуємо обчислення замикання, додаючи всі пункти [C → •γ, b] для b з FIRST(C$). Зіставляючи [S → •CC, $] і [A → α•Bβ,a], одержуємо A=S, α=ε, B = C, β = C і a = $. Оскільки C не породжує порожній рядок, FIRST(C$)= FIRST(C). Тому що FIRST(C) містить термінали с і d, ми додаємо пункти [C → •cC, c], [C → •cC, d], [C → •d, c] і [C → •d, d]. Ніякі з нових пунктів не мають нетерміналів безпосередньо праворуч від точки, так що ми завершуємо на цьому побудову першої множини LR(1)-пунктів. Початкова множина пунктів така:

I0 : S' → •S, $ ,

S → •CC, $ ,

C → •cC, c| d ,

C → •d, c| d .

Тут для зручності запису опущені квадратні дужки, а також для представлення двох пунктів – [C → •cC, c] і [C→ •cC, d] – використовується позначення [C→ •cC, c|d].

Тепер обчислимо goto(I0 , X) для різних значень X. Для X = S ми повинні замкнути пункт [S' → S•, $]. Ніяких інших пунктів у замиканні немає, оскільки точка в пункті знаходиться справа. Таким чином, множина пунктів має вигляд

I1 : S' → S'•, $ .

Для X = С замикаємо [S → C•C, $]. Ми додаємо С-продукції з другим компонентом $ і після цього додати вже нічого. Тим самим одержуємо

I2 : S → C•C, $ ,

С → •сC, $ ,

С → •d, $ .

Далі нехай Х= c, і замикається {[ С → с•C, c|d]}. Додаємо C-продукції з другим компонентом c|d, одержуючи

I3 : С → с•C, c|d ,

С → • с C, c|d ,

С → •d, c|d .

І нарешті, для X=d знаходимо

I4: С → d•, c|d .

На цьому ми завершуємо розгляд goto на множині I0. Для I1 нові множині не утворюються, але I2 має переходи за C, c і d. Для C знаходимо

I5 : С → CC•, $ .

Для c розглядаємо замикання {[С → с•C, $]}, одержуючи

I6 : С → c•C, $ ;

С → • c C, $ ;

С → • d, $ .

Продовжуючи розгляд функції goto для I2, знаходимо goto (12, d):

I7: С → d•, $ .

Переходячи до I3, знайдемо, що переходи з I3 по символах с і d являють собою відповідно I3 та I4, а goto(I3,C) –

18: С → сC•, c|d .

I4 і I5 переходів не мають. Переходи з 16 по символах с і d являють собою відповідно I6 та I7, а goto(16,C) –

19: С → сC•, $ .

Інші множини пунктів не мають переходів, і на цьому наша робота завершена. На рис. 4.7 показані знайдені десять множин пунктів з їх переходами.

Тепер наведемо правила, за допомогою яких на основі множин LR(1)-пунктів будуються функції action і goto LR(1)-аналізу. Функції представлені, як і раніше, у вигляді таблиці; відмінність полягає у значеннях записів.

Алгоритм 4.10 Побудова канонічної таблиці LR-аналізу

1 Побудуємо C = {10, 11, ... , 1n}, систему множин LR(1)-пунктів для G'.

Рисунок 4.7 - Діаграма переходів для граматики 4.6

2 Стан i синтаксичного аналізатора будується на основі множини 1i. Дії синтаксичного аналізу для стану i визначаються в такий спосіб:

а) якщо [А→α•aβ, b] Ii і goto(Ii, а) = Ij , то установимо action[i, а] таким, що дорівнює “перенесення j”;

б) якщо [А→α•, a] Ii, А≠S', то визначимо action[i,a] як “згортання A →α ”;

с) якщо [S'→S•, $] Ii, то установимо action[i,$] таким, що дорівнює “допуск”.

Якщо застосування цих правил приводить до конфлікту, граматика не є LR(1)-граматикою, і даний алгоритм до неї незастосовний.

3 Переходи goto для стану i визначаються в такий спосіб: якщо goto(Ii, A) = Ij, то goto[i, А] =j.

4 Усі записи, не визначені правилами (2) і (3), задаються як “помилка”.

5 Початковий стан синтаксичного аналізатора являє собою стан, побудований з множини, що містить пункт [S'→S•, $].

Таблиця, побудована на основі функцій action і goto синтаксичного аналізу, отриманих з використанням даного алгоритму, називається канонічною таблицею LR(1)-аналізу. LR-аналізатор, що використовує цю таблицю, називається канонічним LR(1)-аналізатором. Якщо функція action синтаксичного аналізу не має множинних записів, то дана граматика називається LR(1)-граматикою.

Таблиця 4.7

Стан

action

goto

c d $

S C

0

1

2

3

4

5

6

7

8

9

s3 s4

acc

s6 s7

s3 s4

r3 r3

r1

s6 s7

r3

r2 r2

r2

  1. 2

5

8

9

Таблиця 4.7 являє собою таблицю синтаксичного аналізу для граматики (4.6). Продукціями 1, 2 і 3 є відповідно S→CC, С → сC і С → d.

Будь-яка SLR(1)-граматика є LR(1)-граматикою, але для SLR(1)-граматики канонічний LR-аналізатор може мати більше станів, ніж SLR-аналізатор для тієї самої граматики.

Граматика з попереднього прикладу є SLR-граматикою; SLR-аналізатор для неї має сім станів, а в даній таблиці їх десять.

Завдання до розділу 4

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

bexpr → bexpr or bterm | bterm

bterm → bterm and bfactor | bfactor

bfactor → not bfactor | (bexpr) | true | false .

2 Побудувати таблицю SLR-аналізу для граматики

E→E+T | T ;

T→TF | F;

F→F* | a | b .

3 Побудувати таблицю SLR-аналізу для граматики із завдання 2.

110

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]