Generowanie parserów LR

Generowanie parserów LR – zautomatyzowany proces tworzenia parsera LR. Ze względu na swoją złożoność, parsery LR trudno jest programować ręcznie. Dlatego powstały generatory parserów. Parsery LR są zazwyczaj implementowane jako parsery sterowane tabelą parsingu – poszczególne typy różnią się głównie metodą tworzenia takiej tabeli.

Konstrukcja tabeli parsingu LR(0)

Jako przykładu użyjemy poniższej gramatyki:

(1) E → E * B

(2) E → E + B

(3) E → B

(4) B → 0

(5) B → 1

Sytuacje

Konstrukcja tabeli parsingu bazuje na pojęciu "sytuacji LR(0)" (w źródłach anglojęzycznych określanych jako ang. "items"), które są produkcjami gramatyki formalnej, wraz ze znakiem kropki dodawanej na którymś miejscu po prawej stronie. Sytuacja LR(0) ma postać [A→β₁•β₂] gdzie (A→β₁β₂) jest produkcją. Na przykład produkcja (E → E + B) ma 4 odpowiednie sytuacje:

E → • E + B

E → E • + B

E → E + • B

E → E + B •

Produkcje postaci A → ε mają tylko jedną sytuację A → •. Sytuacje będą używane w celu określenia stanu parsera. Na przykład sytuacja [E → E • + B] wskazuje, że parser rozpoznał ciąg odpowiadający E w strumieniu wejściowym i teraz oczekuje na odczyt '+', za którym znajdzie się inny ciąg odpowiadający B.

Zbiory sytuacji

Zazwyczaj nie można opisać stanu parsera pojedynczą sytuacją, ponieważ może on nie wiedzieć z wyprzedzeniem, którą regułę będzie używał do redukcji. Na przykład jeśli istnieje również reguła (E → E * B) wtedy obie sytuacje [E → E • + B] i [E → E • * B] zostaną zastosowane po tym jak zostanie odczytany ciąg odpowiadający E. Dlatego będziemy charakteryzować stan parsera przez zbiór sytuacji, w tym przypadku zbiór { E → E • + B, E → E • * B }.

Domknięcie zbiorów sytuacji

Sytuacja z kropką przed symbolem nieterminalnym taka jak E → E + • B oznacza, że parser ma przetwarzać jako następny symbol nieterminalny B. Zbiór sytuacji musi zawierać wszystkie sytuacje oznaczające stan automatu w którym rozpoczyna się przetwarzanie symbolu B. Oznacza to, że jeśli istnieją takie reguły jak B → 1 i B → 0 wtedy zbiór sytuacji musi również zawierać B → • 1 i B → • 0. Zasada ta działa rekurencyjnie: jeśli sytuacja którą dodalibyśmy zawierała by kropkę przed symbolem nieterminalnym, należałoby dodać sytuacje dla tego symbolu. W ogólności można to sformułować następująco:

Jeśli w zbiorze mamy sytuację postaci A → α•Bβ i gramatyka ma regułę postaci B → γ wtedy również sytuacja B → •γ powinna być w zbiorze sytuacji. Gdzie A i B oznaczają symbole nieterminalne a α,β i γ oznaczają ciągi (być może puste) składające się z symboli terminalnych i nieterminalnych.

Dowolny zbiór sytuacji może być rozszerzony w ten sposób przy pomocy dodawania kolejnych sytuacji dotąd aż uwzględni się wszystkie (w tym nowo pojawiające się w zbiorze) sytuacje w których mamy symbol nieterminalny poprzedzony kropką. Rozszerzenie takie nazywa się domknięciem (Closure) zbioru sytuacji i zapisywane jest jako Closure(S) gdzie S jest zbiorem sytuacji. Te domknięte zbiory sytuacji będą stanami parsera ale tylko te, które są osiągalne ze stanu początkowego.

Algorytm tworzenia domknięcia Closure(S) wygląda następująco:

powtarzaj
  dla każdej sytuacji [A → α•Bβ] ∈ S
    dla każdej produkcji (B → η)
      dodaj do zbioru S sytuację [B → •η]
dopóki nie dodano nic nowego do zbioru S.

Gramatyka uzupełniona

Zanim zaczniemy określać przejścia pomiędzy stanami należy uzupełnić gramatykę o dodatkową regułę.

(0) Z → E

Z jest tutaj nowym symbolem startowym. Parser użyje tej reguły do redukcji dokładnie wtedy, gdy zostanie zaakceptowany cały napis wejściowy. Gramatyka wymaga uzupełnienia, gdy nie zawiera symbolu nieterminalnego który by występował tylko raz po lewej stronie pierwszej produkcji.

Gramatyka przyjmuje postać:

(0) Z → E

(1) E → E * B

(2) E → E + B

(3) E → B

(4) B → 0

(5) B → 1

Dla tej powiększonej o pierwszą produkcję gramatyki określimy zbiory sytuacji i przejścia między nimi.

Konstrukcja tabeli

Znajdowanie osiągalnych zbiorów sytuacji i przejść pomiędzy nimi

Pierwszy krok konstruowania tabel polega na określeniu przejść pomiędzy domkniętymi zbiorami sytuacji. Przejścia określamy tak jak byśmy mieli automat skończony czytający zarówno symbole terminalne jak i nieterminalne. Początkowym stanem tego automatu jest zawsze domknięcie pierwszej sytuacji dodanej reguły: Z → • E:

Zbiór sytuacji 0

Z → • E

+ E → • E * B

+ E → • E + B

+ E → • B

+ B → • 0

+ B → • 1

Znak "+" przed sytuacją oznacza, że była ona dodana do zbioru przy tworzeniu domknięcia. Oryginalne sytuacje bez "+" są zwane bazą zbioru sytuacji.

Tworzymy zbiór J - zbiór wszystkich stanów automatu, gdzie każdy stan jest określony przez domknięty zbiór sytuacji. Na początku do J należy początkowy stan S₀. Zaczynając od S₀ określimy stany, które mogą być osiągnięte z tego stanu. Możliwe przejścia dla zbioru sytuacji związane są z symbolami (terminalnymi lub nieterminalnymi), które występują po kropce. W przypadku zbioru sytuacji o numerze 0 mamy symbole terminalne '0' i '1' i nieterminalne E i B. Aby znaleźć zbiór sytuacji, do którego przechodzimy za pomocą symbolu X wykonujemy następującą procedurę:

Goto(S_i,X)

1. na początku wynikowy zbiór S jest pusty
2. dla każdej sytuacji postaci [A → α•Xβ] ∈ S_i dodajemy do zbioru wynikowego [A → αX•β], czyli dla każdego sytuacji w zbiorze S_i gdzie mamy kropkę przed X, w wynikowym zbiorze tworzymy sytuację w, której przemieszczamy kropkę za symbol X
3. jeśli wynikowy zbiór S nie jest pusty, domykamy S = Closure(S) i mamy dwie możliwości:
   • znaleźliśmy w J zbiór S_j który ma taki sam zbiór sytuacji - usuwamy S, dodajemy przejście Goto(S_i,X)=S_j
   • nie znaleźliśmy - dodajemy nowemu zbiorowi kolejny wolny indeks k i dodajemy przejście Goto(S_i,X)=S_k.

Dla symbolu terminalnego '0' rezultatem będzie:

Zbiór sytuacji 1

B → 0 •

dla symbolu terminalnego '1':

Zbiór sytuacji 2

B → 1 •

dla symbolu nieterminalnego E:

Zbiór sytuacji 3

Z → E •

E → E • * B

E → E • + B

i dla symbolu nieterminalnego B:

Zbiór sytuacji 4

E → B •

Należy zauważyć, że domknięcie nie dodało nowych sytuacji w żadnym z tych przypadków. Kontynuujemy ten proces dotąd aż nie znajdziemy nowych zbiorów. Dla zbiorów sytuacji o numerach 1, 2 i 4 nie będzie przejść, ponieważ kropka nie znajduje się przed żadnym symbolem. Dla zbioru sytuacji numer 3 widzimy, że kropka jest przed symbolami terminalnymi ' * ' i '+'. Dla ' * ' przejście prowadzi do:

Zbiór sytuacji 5

E → E * • B

+ B → • 0

+ B → • 1

dla '+' :

Zbiór sytuacji 6

E → E + • B

+ B → • 0

+ B → • 1

Dla zbioru sytuacji numer 5 mamy do rozważenia symbole terminalne '0' i '1' i symbol nieterminalny B. Jeśli chodzi o oba symbole terminalne, widzimy, że wynikowe zbiory są takie same jak już znalezione zbiory 1 i 2. Dla symbolu B przejście prowadzi do:

Zbiór sytuacji 7

E → E * B •

Dla zbioru sytuacji numer 6 mamy również do rozważania symbole terminalne '0' i '1' i symbol nieterminalny B. Jak przedtem, wynikowe zbiory sytuacji dla symboli terminalnych są takie same jak zbiory 1 i 2. Dla symbolu B przejście prowadzi do:

Zbiór sytuacji 8

E → E + B •

Ostatnie dwa zbiory sytuacji nie mają kropki przed symbolem przez co kończymy dodawanie nowych zbiorów. Tablica przejść automatu wygląda następująco:

Zbiór sytuacji	*	+	0	1	E	B
0			1	2	3	4
1
2
3	5	6
4
5			1	2		7
6			1	2		8
7
8

Tworzenie tabel action i goto

Na podstawie tej tabeli i znalezionych zbiorów sytuacji konstruujemy tabele action i goto następująco:

1. kolumny dla symboli nieterminalnych są kopiowane do tabeli goto
2. kolumny dla symboli terminalnych są kopiowane do tabeli action jako akcje przesunięcia(shift)
3. dodatkowa kolumna dla '$' (koniec strumienia wejściowego) jest dodana do tabeli action i zawiera acc dla zbioru sytuacji zawierającego sytuację Z → E •.
4. jeśli zbiór sytuacji i zawiera sytuację postaci A → α • oraz A → α jest regułą m dla m > 0 wtedy wiersz dla stanu i w tabeli action jest całkowicie wypełniona akcją redukcji rm.

W rezultacie dostajemy tabele

	action						goto
stan	*	+	0	1	$		E	B
0			s1	s2			3	4
1	r4	r4	r4	r4	r4
2	r5	r5	r5	r5	r5
3	s5	s6			acc
4	r3	r3	r3	r3	r3
5			s1	s2				7
6			s1	s2				8
7	r1	r1	r1	r1	r1
8	r2	r2	r2	r2	r2

Uwaga o różnicach między LR(0) a SLR i LALR

Zauważmy, że jedynie krok 4 powyższej procedury wytwarza akcje redukcji i wszystkie akcje redukcji muszą zajmować cały wiersz tabeli powodując to, że redukcja wykonywana jest niezależnie od następnego symbolu w strumieniu wejściowym. Z tego powodu są to tabele LR(0): nie zaglądają w przód przed decyzją, której redukcji użyć. Gramatyka, która potrzebuje spojrzeć w przód aby wybrać redukcję, będzie potrzebowała tabeli parsingu, której wiersz będzie zawierał różne akcje redukcji w różnych kolumnach i powyższa procedura nie nadaje się do tworzenia takich tabel.

Procedury konstruujące parser SLR czy LALR mają możliwość tworzenia wierszy tabeli, dla których akcja redukcji nie zajmuje całych wierszy. Dlatego parsery te mają możliwość analizy większej ilości gramatyk niż LR(0).

Konflikty konstruowania tabel

Automat jest konstruowany w sposób, który gwarantuje determinizm. Jednak kiedy akcje redukcji są dodawane do tabeli action, może się zdarzyć, że ta sama komórka jest wypełniona przez akcję redukcji i akcję przesunięcia (konflikt przesunięcie-redukcja) lub przez dwie różne akcje redukcji (konflikt redukcja-redukcja). Kiedy to się zdarza, znaczy to, że gramatyka nie jest LR(0).

Krótki przykład gramatyki nie LR(0) z konfliktem przesunięcie-redukcja:

(1) E → 1 E

(2) E → 1

Jeden ze zbiorów sytuacji który znajdujemy:

Zbiór sytuacji 1

E → 1 • E

E → 1 •

+ E → • 1 E

+ E → • 1

Mamy tu konflikt przesunięcie-redukcja ponieważ w komórce tabeli action dla tego stanu i symbolu '1' jest jednocześnie przesunięcie do stanu 1 i redukcja regułą 2.

Krótki przykład gramatyki nie LR(0) z konfliktem redukcja-redukcja:

(1) E → A 1

(2) E → B 2

(3) A → 1

(4) B → 1

W tym przypadku otrzymujemy następujący zbiór sytuacji:

Zbiór sytuacji 1

A → 1 •

B → 1 •

Mamy tu konflikt redukcja-redukcja ponieważ w komórkach tabeli action dla tego stanu będzie jednocześnie redukcja regułą 3 i regułą 4.

Oba powyższe przykłady mogą być rozwiązane przez dopuszczenie aby parser używał zbioru Follow dla symbolu nieterminalnego A do decydowania czy używać jednej z reguły A dla redukcji; będziemy używać reguły A → α do redukcji jeśli następny symbol w strumieniu input znajduje się w zbiorze Follow dla A. Takie rozwiązanie nazywa się SLR (Simple LR parser, prosty parser LR).

Tabele SLR

Rozpatrzymy niewielką gramatykę która przy budowie tabel LR(0) dawała konflikt redukcja-redukcja; po uzupełnieniu jej o nowy symbol startowy, będzie miała postać:

(0) Z → E

(1) E → A 1

(2) E → B 2

(3) A → 1

(4) B → 1

Zbiory First i Follow dla tej gramatyki będą wyglądać następująco

Symbol	First	Follow
Z	1	$
E	1	$
A	1	1
B	1	2

Zbiory sytuacji wyglądają następująco:

S₀

Z → • E

+ E → • A 1

+ E → • B 2

+ A → • 1

+ B → • 1

S₁ = Goto(S₀, E)

Z → E •

S₂ = Goto(S₀, A)

E → A • 1

S₃ = Goto(S₀, B)

E → B • 2

S₄ = Goto(S₀, 1)

A → 1 •

B → 1 •

S₅ = Goto(S₂, 1)

E → A 1 •

S₆ = Goto(S₃, 2)

E → B 2 •

Przy tworzeniu tabel kolumny dla symboli nieterminalnych w goto i dla terminalnych w action jako przesunięcia wpisujemy jak przy tworzeniu tabeli LR(0), podobnie akceptację dla zbioru sytuacji gdzie występuje Z → E •. Różnica będzie przy wpisywaniu redukcji - będzie ona wpisywana tylko w te kolumny tabeli, które odpowiadają symbolom terminalnym znajdującym się w zbiorze Follow dla symbolu po lewej stronie reguły, za pomocą której redukujemy.

Tak więc w zbiorze sytuacji numer 4

A → 1 •

B → 1 •

mamy dwie sytuacje z kropką na końcu, które powiązane są z regułami 3 (A → 1) i 4 (B → 1). Reguła 3 po lewej stronie ma symbol A dla, którego Follow={ 1 } a reguła 4 ma symbol B dla, którego Follow = {2}. Wpisujemy redukcję regułą 3 w kolumnę symbolu terminalnego 1, a redukcję reguła 4 w kolumnę odpowiadającej symbolowi 2. W zbiorach sytuacji powiązanych ze stanami 5 i 6 automatu mamy redukcję regułami 1 i 2, które po lewej stronie mają symbol E, którego zbiór Follow = { $ }

W rezultacie otrzymujemy tabele:

	action				goto
stan	1	2	$		E	A	B
0	s4				1	2	3
1			acc
2	s5
3		s6
4	r3	r4
5			r1
6			r2

Kanoniczny LR(1)

W odróżnieniu od sytuacji LR(0) [A→β₁•β₂] sytuacja LR(1) ma postać [A→β₁•β₂, v] gdzie (A→β₁β₂) jest produkcją a v symbolem terminalnym lub znakiem $ końca strumienia. Symbol v nazywany jest symbolem podglądanym (lookahead).

Algorytm tworzenia domknięcia Closure(S) wygląda następująco:

 
powtarzaj
  dla każdej sytuacji [A → α•Bβ, v] ∈ S
    dla każdej produkcji (B → η)
      dla każdego symbolu b ∈ First(βv)
        dodaj do zbioru S sytuację [B → •η, b]
dopóki nie dodano nic nowego do zbioru S.

First(βv) zawiera wszystkie (bez ε) symbole z First(β) a jeśli First(β) zawiera ε to oprócz tego First(βv) zawiera symbol v.

Tworzymy zbiór J - zbiór wszystkich stanów automatu który inicjowany jest początkowym zbiorem S₀. Zbiór S₀ jest domknięciem sytuacji [Z → • E, $]

Goto(S_i,X)

1. na początku wynikowy zbiór S jest pusty
2. dla każdej sytuacji postaci [A → α•Xβ, a] ∈ S_i dodajemy do zbioru wynikowego [A → αX•β, a], czyli dla każdego sytuacji w zbiorze S_i gdzie mamy kropkę przed X, w wynikowym zbiorze tworzymy sytuację z tym samym symbolem podglądanym w którym przemieszczamy kropkę za symbol X
3. jeśli wynikowy zbiór S nie jest pusty, domykamy go S = Closure(S) i mamy dwie możliwości
   • znaleźliśmy w J zbiór S_j który ma taki sam zbiór sytuacji (wraz z symbolami podglądanymi) jak zbiór S - usuwamy S, dodajemy przejście Goto(S_i,X)=S_j
   • nie znaleźliśmy - dodajemy nowemu zbiorowi kolejny wolny indeks k i dodajemy przejście Goto(S_i,X)=S_k.

Przy tworzeniu tabel kolumny dla symboli nieterminalnych w goto i dla terminalnych w action jako przesunięcia wpisujemy jak przy tworzeniu tabeli LR(0), akceptację wpisujemy w kolumnę $ w tym stanie, gdzie mamy sytuację [Z → E •, $]. Redukcję gdy mamy sytuację postaci [A → α•, v] wpisujemy w kolumnę v.

Sytuacje ze zbiorem symboli podglądanych

Zamiast zestawu sytuacji w zbiorze jak

• L → •*R, $
• L → •*R, =

które różnią się tylko symbolem podglądanym, można wprowadzić reprezentację postaci [A→β₁•β₂, Ω] gdzie Ω jest zbiorem symboli podglądanych. Oprócz pewnego uporządkowania w zbiorze sytuacji, sytuacje ze zbiorami symboli podglądanych przydadzą się w omawianiu tworzenia parsera LALR. Powyższe dwie sytuacje mogą być zapisane jako jedna [L→•*R, $=].

Algorytm tworzenia domknięcia Closure(S) przybierze postać:

 
powtarzaj
  dla każdej sytuacji [A → α•Bβ, Ω] ∈ S

    w zbiorze Ω mają się znaleźć symbole z First(βv) dla v∈Ω czyli
    inicjujemy zbiór Δ symbolami First(β) bez ε, 
    a jeśli First(β) zawiera ε, wtedy do Δ dodajemy wszystkie symbole z Ω

      dla każdej produkcji (B → η)

        dodaj do zbioru S sytuację [B → •η, Δ] jeśli nie istnieje identyczna 
        z wyjątkiem symboli podglądanych [B → •η, Γ], natomiast jeżeli istnieje 
        wtedy do Γ dodaj wszystkie symbole z Δ

dopóki nie dodano nic nowego do zbioru S.

Można również rozbić algorytm na dwie fazy aby omówić tu propagację symboli podglądanych wykorzystaną przy tworzeniu tabeli LALR.

1. Tworzymy domknięcie podobnie jak dla LR(0) nie wykorzystując symboli podglądanych i nowo dodane (niebazowe) sytuacje będą inicjowane zbiorami pustymi:

powtarzaj
  dla każdej sytuacji [A → α•Bβ, Ω] ∈ S
    dla każdej produkcji (B → η)
      dodaj do zbioru S sytuację [B → •η, ø]
dopóki nie dodano nic nowego do zbioru S.

2. Stosujemy propagację bliską (bo w obrębie jednego zbioru sytuacji) symboli podglądanych:

 
powtarzaj
  dla każdej sytuacji [A → α•Bβ, Ω] ∈ S

    w zbiorze Ω mają się znaleźć symbole z First(βv) dla v∈Ω czyli
    inicjujemy zbiór Δ symbolami First(β) bez ε, 
    a jeśli First(β) zawiera ε, wtedy do Δ dodajemy wszystkie symbole z Ω

      dla każdej produkcji (B → η)
        dla sytuacji [B → •η, Γ] do Γ dodaj wszystkie symbole z Δ
dopóki nie dodano nic nowego do zbioru S.

Goto(S_i,X)

1. na początku wynikowy zbiór S jest pusty
2. dla każdej sytuacji postaci [A → α•Xβ, Ω] ∈ S_i dodajemy do zbioru wynikowego [A → αX•β, Ω]
3. jeśli wynikowy zbiór S nie jest pusty, domykamy go S = Closure(S) i mamy dwie możliwości
   • znaleźliśmy w J zbiór S_j który ma taki sam zbiór sytuacji (wraz z symbolami podglądanymi) jak zbiór S - usuwamy S, dodajemy przejście Goto(S_i,X)=S_j
   • nie znaleźliśmy - dodajemy nowemu zbiorowi kolejny wolny indeks k i dodajemy przejście Goto(S_i,X)=S_k.

Przy tworzeniu tabel z shift i goto postępujemy jak poprzednio a redukcję mamy gdy w zbiorze jest sytuacja postaci [A → α•, Ω], wtedy redukcję wpisujemy w kolumny odpowiadające symbolom v∈Ω.

Przykład

Weźmy gramatykę:

(1) S → L=R

(2) S → R

(3) L → *R

(4) L → i

(5) R → L

Uzupełniamy o startowy symbol i regułę:

(0) Z → S

Tworzymy zbiory sytuacji:

S₀

Z → •S, $

+ S → •L=R, $

+ S → •R, $

+ L → •*R, $=

+ L → •i, $=

+ R → •L, $

Goto(S₀, S) = S₁

Goto(S₀, L) = S₂

Goto(S₀, R) = S₃

Goto(S₀, *) = S₄

Goto(S₀, i) = S₅

S₁ = Goto(S₀, S)

Z → S•, $

S₂ = Goto(S₀, L)

S → L•=R, $

R → L•, $

Goto(S₂, =) = S₆

S₃ = Goto(S₀, R)

S → R•, $

S₄ = Goto(S₀, *) = Goto(S₄, *)

L → *•R, $=

+ R → •L, $=

+ L → •*R, $=

+ L → •i, $=

Goto(S₄, L) = S₇

Goto(S₄, R) = S₈

Goto(S₄, *) = S₄

Goto(S₄, i) = S₅

S₅ = Goto(S₀, i) = Goto(S₄, i)

L → i•, $=

S₆ = Goto(S₂, =)

S → L=•R, $

+ R → •L, $

+ L → •*R, $

+ L → •i, $

Goto(S₆, L) = S₉

Goto(S₆, R) = S₁₀

Goto(S₆, *) = S₁₁

Goto(S₆, i) = S₁₂

S₇ = Goto(S₄, L)

R → L•, $=

S₈ = Goto(S₄, R)

L → *R•, $=

S₉ = Goto(S₆, L) = Goto(S₁₁, L)

R → L•, $

S₁₀ = Goto(S₆, R)

S → L=R•, $

S₁₁ = Goto(S₆, *) = Goto(S₁₁, *)

L → *•R, $

+ R → •L, $

+ L → •*R, $

+ L → •i, $

Goto(S₁₁, L) = S₉

Goto(S₁₁, R) = S₁₃

Goto(S₁₁, *) = S₁₁

Goto(S₁₁, i) = S₁₂

S₁₂ = Goto(S₆, i) = Goto(S₁₁, i)

L → i•, $

S₁₃ = Goto(S₁₁, R)

L → *R•, $

	action					goto
stan	=	*	i	$		S	L	R
0		s4	s5			1	2	3
1				acc
2	s6			r5
3				r2
4		s4	s5				7	8
5	r4			r4
6		s11	s12				9	10
7	r5			r5
8	r3			r3
9				r5
10				r1
11		s11	s12				9	13
12				r4
13				r3

LALR(1)

Scalanie stanów LR(1)

Jądro (Core) zbioru sytuacji LR(1):

• S - zbiór sytuacji LR(1)
• Core(S) = {[A → α•β] | [A → α•β, u] ∈ S}

Parser LALR(1) powstaje z LR(1) przez połączenie jego stanów o identycznym jądrze. Dla systemu zbiorów S₀,S₁,...S_m otrzymamy T₀,T₁,...T_n gdzie T_i = S_i0 ∪ S_i1 ∪ ... ∪ S_ik. Połączeniu ulegają zbiory symboli podglądanych. W powyższym przykładzie można połączyć

• S₄ z S₁₁
• S₅ z S₁₂
• S₇ z S₉
• S₈ z S₁₃

Otrzymujemy 10 stanów dla których uaktualniamy tablicę przejść Goto

Stan LR(1)	Stan LALR(1)		Stan LR(1)	Stan LALR(1)
0	0		7	7
1	1		8	8
2	2		9	7
3	3		10	9
4	4		11	4
5	5		12	5
6	6		13	8

Konstrukcja bezpośrednia

Zamiast generowania wszystkich zbiorów LR(1), które następnie łączymy, można wyjść od skonstruowania tabeli LR(0) bez symboli podglądanych a następnie wypełnienia ją tymi symbolami. Algorytm składa się z dwóch faz:

1. Tworzymy tabelę LR(0) wraz z tablicą przejść Goto bez uwzględniania symboli podglądanych; chociaż korzystamy nie z [A→β₁•β₂] a [A→β₁•β₂, Ω] to zbiór symboli podglądanych Ω zostawiamy pusty - wyjątkiem jest [Z → • E, $] zainicjowane znakiem końca strumienia.

2. Faza propagacji symboli podglądanych.

• powtarzaj
• dla kolejnych zbiorów sytuacji od 0 do m
  • dla zbioru S_i jeśli zmieniony
    • wykonaj wyżej opisaną propagację bliską na zbiorze sytuacji S_i
    • jeśli S_k = Goto(S_i, X) wtedy zbiory symboli podglądanych sytuacji bazowych S_k [A → αX•β, Γ] zostaną uzupełnione o symbole odpowiadających im sytuacjom [A → α•Xβ, Ω] z S_i; jeśli uzupełnienie powoduje jakąś zmianę wtedy zbiór S_k zaznaczamy jako zmodyfikowany
• dopóki nie dodano nowego symbolu

Przykład

Dla powyższej gramatyki tablica LALR(1) wygląda następująco:

	action					goto
stan	=	*	i	$		S	L	R
0		s4	s5			1	2	3
1				acc
2	s6			r5
3				r2
4		s4	s5				7	8
5	r4			r4
6		s4	s5				7	9
7	r5			r5
8	r3			r3
9				r1

Bibliografia

• W. Waite, G. Goos, Konstrukcja kompilatorów, Wydawnictwa Naukowo-Techniczne, Warszawa 1989
• Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman: Kompilatory : reguły, metody i narzędzia. Warszawa: WNT, 2002. ISBN 83-204-2656-1. Brak numerów stron w książce

Linki zewnętrzne

• Teoria Automatów i Języków Formalnych, Teoria Kompilacji dr inż. Janusz Majewski, mgr inż. Marcin Kuta, mgr inż. Marta Majewska