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)
edytujJako 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
edytujKonstrukcja 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→β1•β2] gdzie (A→β1β2) 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
edytujZazwyczaj 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
edytujSytuacja 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
edytujZanim 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
edytujZnajdowanie osiągalnych zbiorów sytuacji i przejść pomiędzy nimi
edytujPierwszy 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 S0. Zaczynając od S0 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(Si,X)
- na początku wynikowy zbiór S jest pusty
- dla każdej sytuacji postaci [A → α•Xβ] ∈ Si dodajemy do zbioru wynikowego [A → αX•β], czyli dla każdego sytuacji w zbiorze Si gdzie mamy kropkę przed X, w wynikowym zbiorze tworzymy sytuację w, której przemieszczamy kropkę za symbol X
- 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 Sj który ma taki sam zbiór sytuacji - usuwamy S, dodajemy przejście Goto(Si,X)=Sj
- nie znaleźliśmy - dodajemy nowemu zbiorowi kolejny wolny indeks k i dodajemy przejście Goto(Si,X)=Sk.
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
edytujNa podstawie tej tabeli i znalezionych zbiorów sytuacji konstruujemy tabele action i goto następująco:
- kolumny dla symboli nieterminalnych są kopiowane do tabeli goto
- kolumny dla symboli terminalnych są kopiowane do tabeli action jako akcje przesunięcia(shift)
- dodatkowa kolumna dla '$' (koniec strumienia wejściowego) jest dodana do tabeli action i zawiera acc dla zbioru sytuacji zawierającego sytuację Z → E •.
- 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
edytujZauważ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
edytujAutomat 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
edytujRozpatrzymy 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:
S0
- Z → • E
- + E → • A 1
- + E → • B 2
- + A → • 1
- + B → • 1
S1 = Goto(S0, E)
- Z → E •
S2 = Goto(S0, A)
- E → A • 1
S3 = Goto(S0, B)
- E → B • 2
S4 = Goto(S0, 1)
- A → 1 •
- B → 1 •
S5 = Goto(S2, 1)
- E → A 1 •
S6 = Goto(S3, 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)
edytujW odróżnieniu od sytuacji LR(0) [A→β1•β2] sytuacja LR(1) ma postać [A→β1•β2, v] gdzie (A→β1β2) 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 S0. Zbiór S0 jest domknięciem sytuacji [Z → • E, $]
Goto(Si,X)
- na początku wynikowy zbiór S jest pusty
- dla każdej sytuacji postaci [A → α•Xβ, a] ∈ Si dodajemy do zbioru wynikowego [A → αX•β, a], czyli dla każdego sytuacji w zbiorze Si gdzie mamy kropkę przed X, w wynikowym zbiorze tworzymy sytuację z tym samym symbolem podglądanym w którym przemieszczamy kropkę za symbol X
- 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 Sj który ma taki sam zbiór sytuacji (wraz z symbolami podglądanymi) jak zbiór S - usuwamy S, dodajemy przejście Goto(Si,X)=Sj
- nie znaleźliśmy - dodajemy nowemu zbiorowi kolejny wolny indeks k i dodajemy przejście Goto(Si,X)=Sk.
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
edytujZamiast zestawu sytuacji w zbiorze jak
- L → •*R, $
- L → •*R, =
które różnią się tylko symbolem podglądanym, można wprowadzić reprezentację postaci [A→β1•β2, Ω] 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(Si,X)
- na początku wynikowy zbiór S jest pusty
- dla każdej sytuacji postaci [A → α•Xβ, Ω] ∈ Si dodajemy do zbioru wynikowego [A → αX•β, Ω]
- 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 Sj który ma taki sam zbiór sytuacji (wraz z symbolami podglądanymi) jak zbiór S - usuwamy S, dodajemy przejście Goto(Si,X)=Sj
- nie znaleźliśmy - dodajemy nowemu zbiorowi kolejny wolny indeks k i dodajemy przejście Goto(Si,X)=Sk.
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
edytujWeź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:
S0
- Z → •S, $
- + S → •L=R, $
- + S → •R, $
- + L → •*R, $=
- + L → •i, $=
- + R → •L, $
- Goto(S0, S) = S1
- Goto(S0, L) = S2
- Goto(S0, R) = S3
- Goto(S0, *) = S4
- Goto(S0, i) = S5
S1 = Goto(S0, S)
- Z → S•, $
S2 = Goto(S0, L)
- S → L•=R, $
- R → L•, $
- Goto(S2, =) = S6
S3 = Goto(S0, R)
- S → R•, $
S4 = Goto(S0, *) = Goto(S4, *)
- L → *•R, $=
- + R → •L, $=
- + L → •*R, $=
- + L → •i, $=
- Goto(S4, L) = S7
- Goto(S4, R) = S8
- Goto(S4, *) = S4
- Goto(S4, i) = S5
S5 = Goto(S0, i) = Goto(S4, i)
- L → i•, $=
S6 = Goto(S2, =)
- S → L=•R, $
- + R → •L, $
- + L → •*R, $
- + L → •i, $
- Goto(S6, L) = S9
- Goto(S6, R) = S10
- Goto(S6, *) = S11
- Goto(S6, i) = S12
S7 = Goto(S4, L)
- R → L•, $=
S8 = Goto(S4, R)
- L → *R•, $=
S9 = Goto(S6, L) = Goto(S11, L)
- R → L•, $
S10 = Goto(S6, R)
- S → L=R•, $
S11 = Goto(S6, *) = Goto(S11, *)
- L → *•R, $
- + R → •L, $
- + L → •*R, $
- + L → •i, $
- Goto(S11, L) = S9
- Goto(S11, R) = S13
- Goto(S11, *) = S11
- Goto(S11, i) = S12
S12 = Goto(S6, i) = Goto(S11, i)
- L → i•, $
S13 = Goto(S11, 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)
edytujScalanie stanów LR(1)
edytujJą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 S0,S1,...Sm otrzymamy T0,T1,...Tn gdzie Ti = Si0 ∪ Si1 ∪ ... ∪ Sik. Połączeniu ulegają zbiory symboli podglądanych. W powyższym przykładzie można połączyć
- S4 z S11
- S5 z S12
- S7 z S9
- S8 z S13
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
edytujZamiast 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[1]. 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→β1•β2] a [A→β1•β2, Ω] 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 Si jeśli zmieniony
- wykonaj wyżej opisaną propagację bliską na zbiorze sytuacji Si
- jeśli Sk = Goto(Si, X) wtedy zbiory symboli podglądanych sytuacji bazowych Sk [A → αX•β, Γ] zostaną uzupełnione o symbole odpowiadających im sytuacjom [A → α•Xβ, Ω] z Si; jeśli uzupełnienie powoduje jakąś zmianę wtedy zbiór Sk zaznaczamy jako zmodyfikowany
- dla zbioru Si jeśli zmieniony
- dopóki nie dodano nowego symbolu
Przykład
edytujDla 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
edytuj- 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.
Przypisy
edytuj- ↑ Zestaw narzędzi dla generatora parserów dla Delphi i Kylix (wersja 1.4a). grendelproject.nl. [dostęp 2008-06-13]. [zarchiwizowane z tego adresu (2008-06-22)]. (ang.).
Linki zewnętrzne
edytuj- Teoria Automatów i Języków Formalnych, Teoria Kompilacji dr inż. Janusz Majewski, mgr inż. Marcin Kuta, mgr inż. Marta Majewska