Синтаксичний аналіз. Спадний аналіз. Предиктивний аналізатор. Висхідний аналіз, страница 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) має вигляд

I₀ :       Е'→•E ,                       T→• F ,

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

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

T→•Т*F ,

I₁ :       Е'→E• ,                      Е→Е•+Т  ;

 I₂ :      Е→ Т• ,                      T→Т•*F  ;

I₃ :       T→ F•  ;

I₄ :       F→(• E) ,                    T→• F ,

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

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

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

I₅ :       F→ id •  ;                  

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

T→• F ,

I₇ :       T→Т*•F ,                   F→• id  ;                   

F→•(Е)  ,

I₈ :       F→ (Е•),Е→Е•+Т  ;

I₉ :       Е→Е+Т•  ,                 T→Т•*F  ;

I₁₀ :      T→Т*F•  ;

I₁₁ :      F→ (Е)•  .

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

Якщо кожен стан автомата є завершальним, а I₀ – початковий стан, то автомат розпізнає активні префікси граматики (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 - Діаграма переходів детермінованого скінченного автомата для активних префіксів