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

end

Відмітимо, якщо одна з B-продукцій додається в closure(I)із точкою ліворуч, то до замикання будуть додані усі В-продукції, так що насправді у деяких випадках досить указати список доданих нетерміналів, а не список усіх продукцій. Це приводить до того, що ми можемо розділити будь-яку множину пунктів, які нас цікавлять, на два класи.

1 Базисні пункти, або пункти ядра (kernel items), що включають початковий пункт S’→S, і всі пункти, у яких точки розміщені не з лівого краю.

2 Небазисні(nonkernel) пункти, у яких точки розміщені ліворуч.

Більше того, кожна множина пунктів, що нас цікавлять,  формується як замикання множини базисних пунктів; пункти, що додаються до замикання, не можуть бути базисними. Таким чином, ми можемо представити множину пунктів, що нас цікавлять,  з використанням дуже невеликого обсягу пам'яті, якщо відкинемо всі небазисні пункти, знаючи, що вони можуть бути відновлені процесом замикання.

Другою корисною функцією є goto(I, X), де I є множиною пунктів, а X – символом граматики.  goto (I, X) визначається як замикання множини всіх пунктів αXВ], таких, що αXВ]I.Інтуїтивно, якщо I є множиною пунктів, припустимих для деякого активного префікса γ, то goto (I, X) є множина пунктів, припустимих для активного префікса γХ.

Приклад 4.2

Якщо I являє собою множину із двох пунктів {[Е'Е],[ЕЕ]}, то goto (1, +) складається з

ЕЕ+Т ,                  T→•Т*F ,

T→•F ,                        F→•(Е),

F→• (id) .

Ми обчислили goto (I, X), розглянувши пункти з I, у яких відразу за точкою йде +. Таким пунктом є  ЕЕна відміну від пункту Е' →E•. Ми переміщаємо точку за символ +, одержуючи { ЕЕ+Т}, і розглядаємо замикання цієї множини.          

Тепер ми можемо представити алгоритм для побудови С – канонічної системи множин LR(0)-пунктів для розширеної граматики G'.

Алгоритм 4.7  Алгоритм побудови множин пунктів

procedure items(G');

begin

C := {closure ( { [S'→S] }) } ;

     repeat

         for кожної множини пунктів  I  в  С  і кожного

               символа граматики  X,  такого,  що   goto (I, X)

   не є порожнім і не належить С

do додати   goto (I, X) доС

until більше  немає  множин,  які можна додати  до  С

end

Канонічна система множин LR(0)-пунктів для граматики (4.4) має вигляд

I0 :       Е'→•E ,                       T→• F ,

Е→•Е+Т,                  Е→•(Е),

Е→• Т ,                       F→• (id) ;                 

T→•Т*F ,

I1 :       Е'→E• ,                      ЕЕ  ;

 I2 :      Е Т• ,                      TТ*F  ;

I3 :       T→ F•  ;

I4 :       F→(• E) ,                    T→• F ,

Е→•Е+Т,                  Е→•(Е),

Е→• Т ,                      F→• (E) ,                   

T→•Т*F ,                   F→• id  ;

I5 :       Fid •  ;                  

I6 :       ЕЕ+Т,                  F→• (E) ,                                           T→•Т*F ,                   F→• id  ;

T→• F ,

I7 :       TТ*•F ,                   F→• id  ;                   

F→•(Е)  ,

I8 :       F→ (Е),ЕЕ  ;

I9 :       ЕЕ+Т•  ,                 TТ*F  ;

I10 :      TТ*F•  ;

I11 :      F→ (Е)•  .

Функцію goto можна подати у вигляді діаграми переходів детермінованого скінченного автомата (рис. 4.6).

Якщо кожен стан автомата є завершальним, а I0 початковий стан, то автомат розпізнає активні префікси граматики (4.4), і це не випадково. Для кожної граматики Gфункція gotoканонічної системи множин пунктів визначає детермінований скінченний автомат, що розпізнає активні префікси G. Можна уявити собі недетермінований скінченний автомат N, станами якого є пункти. Є перехід з Аα•Xβ  в  АαXβ, позначений X, і перехід з Аα•Bβ у B→ •γ, позначений ε.

Тоді closure(I) для множини пунктів I являє собою ε-closure множини станів недетермінованого автомата. Отже, значенням goto (I, X) є перехід з I по символу X у детермінованому автоматі, побудованому з N за алгоритмом побудови підмножини. Звідси випливає, що процедура items(G')являє собою алгоритм побудови підмножини, застосований до N, побудованого на основіG' описаним способом.

                                                                

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