Синтаксичний аналіз. Спадний аналіз. Предиктивний аналізатор. Висхідний аналіз, страница 12

Додаткова інформація впроваджується у стан шляхом перевизначення пунктів для включення термінального символа як другого компонента. Загальним видом пункту стає [А→α•β, 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 .

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

Є також праве породження SBaBBaaB, відповідно до якого пункт [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може бути першим терміналом, виведеним з β. Можливо також, що з β виводиться ε у породженні βAxby, і 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]Ido додати

 [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  кожної множини  пунктів IC  і  кожного символа граматики 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)-пунктів. Початкова множина пунктів така:

I₀ :   S'→ •S, $ ,

S → •CC, $,

C → •cC, c| d ,

C → •d,c| d .

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