Parser LR

Parser LR (ang. Left to right, identifying the Rightmost production) – analizator składniowy dla gramatyk bezkontekstowych, który przetwarza wejście od lewej do prawej metodą wstępującą i produkuje prawostronne wyprowadzenie. Terminu parser LR(k), gdzie k jest liczbą naturalną lub zerem, używa się do oznaczenia analizatorów podejmujących decyzje na podstawie k podglądanych symboli na wejściu, użytych w podjęciu decyzji. Zwykle k jest równe 1 i jest często pomijane. Parser SLR i parser LALR również są typu LR, jednak pod pojęciem LR(k) zwykle mamy na myśli "kanoniczny parser LR(k)". W typowym użyciu "parser LR" oznacza konkretny parser zdolny rozpoznać konkretny język określony gramatyką bezkontekstową.

Gramatyka bezkontekstowa nazywa się gramatyką LR(k), jeżeli istnieje dla niej parser LR(k).

Mówimy, że parser LR wykonuje analizę metodą wstępującą (ang. bottom-up), ponieważ próbuje wyprowadzić produkcję najwyższego poziomu poprzez analizowanie liści.

Analizowanie typu LR przynosi następujące korzyści:

• parsery LR są często używane przez kompilatory do uprzedniej analizy składniowej (syntaktycznej) kodu źródłowego (wyjątkiem jest C++);
• parsery LR mogą być zaimplementowane bardzo wydajnie;
• parsery LR wykrywają błędy składniowe (wejście nie zgadza się z gramatyką!) tak szybko jak to możliwe.

Parsery LR są trudne do ręcznego zaprogramowania, dlatego są one zwykle konstruowane przez generator parserów. W zależności od tego jak jest generowana tabela parsingu, wyróżnia się następujące parsery LR: parser SLR (Simple LR ), LALR (Look-Ahead LR) i kanoniczny parser LR.

Zbiory gramatyk określone przez te rodzaje parserów mają następującą własność:

${\displaystyle LR(0)\subset SLR(1)\subset LALR(1)\subset LR(1)}$ .

Jednym z programów generujących parsery typu LR jest bardzo popularny Yacc. Specjalizuje się on w tworzeniu parserów dla gramatyk klasy LALR(1). Innym tego typu programem jest Bison. Jest on bardzo podobny do Yacca, jednak zawiera kilka udoskonaleń. Można nim generować parsery dla gramatyk typu LALR oraz parsery GLR.

Konwencjonalne parsery LR są implementowane jako automaty ze stosem bazujące na tabelach.

Sterowany tabelą parser bottom-up jest przedstawiony schematycznie na rysunku 1. Mamy następujący opis prawostronnego wyprowadzenia przez ten parser.

Parser jest automatem ze stanami, na który składa się:

• bufor wejścia
• stos na którym przechowywana jest lista stanów w których był automat
• tabela goto w której opisane jest, do którego nowego stanu powinniśmy przejść
• tabela action która daje regułę gramatyki do zastosowania w bieżącym stanie i dla aktualnego symbolu terminalnego w strumieniu wejściowym.

Ponieważ parser LR czyta strumień wejściowy od lewej do prawej ale potrzebuje wyprodukować prawostronne wyprowadzenie, używa redukcji zamiast wyprowadzeń do przetwarzania strumienia wejściowego. Oznacza to, że algorytm działa tworząc "lewostronną redukcję" wejścia. Końcowym rezultatem po odwróceniu będzie prawostronne wyprowadzenie.

Algorytm parsingu LR działa następująco:

1. Stos jest inicjowany przez [0]. Bieżącym stanem będzie zawsze ten stan, który jest na szczycie stosu.
2. Biorąc bieżący stan i bieżący symbol terminalny w strumieniu wejściowym, akcja jest brana z tabeli action. Mamy cztery przypadki:
   • przesunięcie (ang. shift) sn:
     • bieżący symbol terminalny jest usuwany ze strumienia wejściowego
     • stan n jest wkładany na stos i staje się bieżącym stanem
   • redukcja (ang. reduce) rm:
     • liczba m oznaczająca numer reguły wyprowadzania jest wypisywana do strumienia wyjściowego
     • dla każdego symbolu (terminalnego lub nieterminalnego) z prawej strony reguły m stan jest usuwany ze stosu
     • biorąc stan który jest następnie na szczycie stosu i symbol nieterminalny który jest po lewej stronie reguły m, nowy stan jest brany z tabeli goto i staje się nowym bieżącym stanem przez włożenie go na stos
   • akceptacja: strumień symboli terminalnych jest zaakceptowany
   • brak akcji: zgłaszany jest błąd syntaktyczny
3. Krok 2 jest powtarzany dotąd aż strumień zostanie zaakceptowany lub zostanie zgłoszony błąd składni.

Aby wyjaśnić jak to działa użyjemy następującej małej gramatyki której startowym symbolem jest E:

(1) E → E * B

(2) E → E + B

(3) E → B

(4) B → 0

(5) B → 1

i parsujemy następujący strumień wejściowy:

1 + 1

Dwie tabele LR(0) parsingu dla tej gramatyki wyglądają następująco:

	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

Tabela action jest indeksowana przez stan automatu parsującego i symbol terminalny (włączając w to specjalny terminal $ oznaczający koniec strumienia wejściowego) i zawiera trzy rodzaje akcji:

• przesunięcie (shift), które zapisujemy jako 'sn' i oznacza że następnym stanem jest n
• redukcja (reduce), którą zapisujemy jako 'rm' i oznacza że powinna być wykonana redukcja regułą gramatyki o numerze m
• akceptacja (accept), którą zapisujemy jako 'acc' i oznacza że parser akceptuje cały łańcuch symboli strumienia wejściowego

Tabela goto jest indeksowana przez stan parsera oraz symbol nieterminalny i wskazuje następny stan w jaki przejdzie automat parsujący jeśli lewa strona ostatnio użytej do redukcji reguły będzie pewnym symbolem nieterminalnym.

Poniższa tabela pokazuje każdy krok w procesie. Tutaj stan odnosi się do elementu na szczycie stosu (element najbardziej na prawo) i następna akcja jest określona przez odniesienie się do tabeli powyżej. Zauważmy, że symbol $ jest dołączany do strumienia wejściowego oznaczając koniec strumienia.

Stan	Strumień Input	Strumień Output	Stos	Następna akcja
0	1+1$		[0]	Shift 2
2	+1$		[0,2]	Reduce 5
4	+1$	5	[0,4]	Reduce 3
3	+1$	5,3	[0,3]	Shift 6
6	1$	5,3	[0,3,6]	Shift 2
2	$	5,3	[0,3,6,2]	Reduce 5
8	$	5,3,5	[0,3,6,8]	Reduce 2
3	$	5,3,5,2	[0,3]	Accept

Parser rozpoczyna swoją pracę ze stosem zawierającym jedynie początkowy stan ('0'):

[0]

Pierwszym symbolem łańcucha wejściowego, który parser widzi jest '1'. Aby dowiedzieć się jaka jest następna akcja (przesunięcie, redukcja, akceptacja lub błąd), tabela action jest indeksowana bieżącym stanem (pamiętajmy, że "bieżący stan" jest stanem, który jest na szczycie stosu), który w tym wypadku jest 0 i bieżącym symbolem wejściowym, którym jest '1'. Tabela action określa przejście do stanu 2 i tak stan 2 jest wkładany na stos (ponownie, pamiętajmy, że wszystkie informacje o stanie automatu znajdują się na stosie, więc "przejście do stanu 2" jest tym samym co włożenie 2 na stos). W wyniku tego stos ma postać:

[0 '1' 2]

gdzie na szczycie stosu jest stan 2. W celu objaśnienia jest pokazany również symbol (np.'1 ', B), który spowodował przejście do następnego stanu, chociaż ściśle rzecz biorąc nie jest częścią stosu.

W stanie 2 tabela action pokazuje nam, że niezależnie od symbolu widzianego na wejściu, powinniśmy dokonać redukcji 5-tą regułą gramatyki. Jeśli tabela jest poprawna, oznacza to że parser właśnie rozpoznał prawą stronę reguły 5, co rzeczywiście ma tu miejsce. W tym przypadku wypisujemy numer reguły, którym jest 5, do strumienia wyjściowego, zdejmujemy ze stosu jeden stan (ponieważ prawa strona reguły ma jeden symbol) i wkładamy na stos stan z komórki tabeli goto dla stanu 0 i symbolu nieterminalnego B (z lewej strony produkcji 5), czyli stan numer 4. Stos przybiera postać:

[0 B 4]

Jednak w stanie 4 tabela action informuje że powinniśmy teraz wykonać redukcję regułą 3. Tak więc wypisujemy 3 do strumienia wynikowego, zdejmujemy jeden stan ze stosu i znajdujemy nowy stan w tabeli goto dla stanu 0 i symbolu nieterminalnego E, którym jest stan o numerze 3. Stos ma postać:

[0 E 3]

Następnym symbolem terminalnym, który widzi parser jest '+' i zgodnie z tabelą action należy przejść do stanu 6:

[0 E 3 '+' 6]

Zauważmy, że wynikowy stos może być interpretowany jako historia deterministycznego automatu skończonego, który właśnie przeczytał symbol nieterminalny E z następującym za nim symbolem terminalnym '+'. Tablica przejść tego automatu jest zdefiniowana przez akcje "shift" w tabeli action i akcje "goto" w tabeli goto.

Następnym symbolem terminalnym jest teraz '1' i znaczy to, że wykonujemy przesunięcie i idziemy do stanu 2:

[0 E 3 '+' 6 '1' 2]

Podobnie jak poprzednia '1', ta jest redukowana do B co daje następujący stos:

[0 E 3 '+' 6 B 8]

Zauważmy znowu, że stos odpowiada liściom stanów automatu skończonego, który przeczytał symbol nieterminalny E, za nim '+' a następnie nieterminalny B. W stanie 8 zawsze wykonujemy redukcję regułą 2. Zauważmy, że ostatnie 3 stany na stosie odpowiadają trzem symbolom prawej strony produkcji (reguły) 2.

[0 E 3]

Na koniec czytamy '$' ze strumienia wejściowego co oznacza, że zgodnie z tabelą action (bieżący stanem jest 3) parser akceptuje wejściowy napis. Numery reguł które zostały wypisane do strumienia wynikowego to [5, 3, 5, 2], co jest istotnie odwrotnym prawostronnym wyprowadzeniem ciągu "1 + 1".

• Analiza składniowa
• Generowanie parserów LR