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. "item"), 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 Zazwyczaj pojedyncze sytuacje nie mogą prawidłowo opisać stanu parsera. Na przykład, kiedy mamy do czynienia z dwoma regułami (E → E + B) oraz (E → E * B) to po tym jak zostanie odczytany ciąg odpowiadający E adekwatnym stanem będzie zbiór { E → E • + B, E → E • * B } bo nie wiadomo z wyprzedzeniem, którą regułę będzie używał parser do redukcji.
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:
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 → η) takiej że [B → •η] ∉ S 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 jednej reguły z symbolem startowym wyłącznie po lewej stronie.
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 (w systemie półthueowskim nie ma rozróżnienia rodzajów symboli). 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 jądrem(ang. kernel) lub 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żdej 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 zbiór/stan do J oraz 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ż przed kropką nie znajduje się żaden symbol. 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 B012341235645127612878
Tworzenie tabel action i goto Na 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 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 FollowZ1$E1$A11B12
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