Parser SLR

Parser SLR (ang. SLR parser, Simple LR parser) jest to parser typu LR, utworzony na podstawie zadanej gramatyki formalnej G, którego tabela parsingu konstruowana jest na podstawie kanonicznej rodziny zbiorów sytuacji LR(0) oraz zbiorów FOLLOW dla gramatyki G. Gramatyka, dla której można skonstruować deterministyczny parser SLR nazywana jest gramatyką SLR. Język posiadający generującą go gramatykę SLR nazywany jest językiem SLR. SLR(k) jest wyznaczane na podstawie sytuacji LR(0) i FOLLOW_k. Zazwyczaj przez SLR jest rozumiane SLR(1).

Parser SLR zazwyczaj jest tworzony przez generator parserów SLR, który na podstawie zadanej gramatyki bezkontekstowej konstruuje maszynę stanów LR(0) oraz oblicza zbiory następników (FOLLOW) dla symboli nieterminalnych. Następnie na tej podstawie tworzy tabele parsingu dla generowanego parsera. Sam parser od innych parserów typu LR (LALR, kanoniczny LR) różni się właśnie sposobem konstrukcji (i zazwyczaj zawartością) tej tablicy, natomiast sam algorytm analizy jest identyczny. Jeśli w tabeli parsingu istnieje konflikt (dwie różne akcje w jednej komórce tabeli) oznacza to, że powstały parser nie jest deterministyczny i w zasadzie do celów praktycznych się nie nadaje (co przez generatory jest zazwyczaj traktowane jako błąd) i trzeba albo zmodyfikować gramatykę albo zastosować lepszy generator (np. LALR).

Jeśli w gramatyce jest produkcja A → ω, to jeśli parser znajdzie się w stanie oznaczającym, że na wierzchołku stosu jest ciąg ω, a następny symbol na wejściu należy do FOLLOW(A), to dokona redukcji ω na A.

Problemem parserów SLR jest to, że wyznaczanie zbioru look-ahead jest zbyt uproszczone, ponieważ używa jedynie reguł gramatyki. Dokładniejszą metodą wyznaczania zbiorów look-ahead jest analizowanie symboli nieterminalnych w każdym ich stanie za pomocą maszyny stanów LR(0). Dokładniejsze zbiory look-ahead są nazywane zbiorami parsingu LALR. Główną zaletą SLR w stosunku do LALR jest łatwość konstrukcji, płaci się jednak za to zmniejszeniem ilości rozpoznawalnych gramatyk, gdyż dosyć często interesujące gramatyki nie są SLR, natomiast są już LALR.

Właściwości

Jeśli gramatyka jest SLR(k) to jest również LALR(k)
Można sprawdzić w sposób deterministyczny czy dana gramatyka bezkontekstowa G jest SLR(k) w czasie wielomianowym od |G|
Wielkość parsera (rozmiar tablicy parsingu) dla SLR(k) jest taki sam jak dla LALR(k) i kanonicznego LR(0)
Słowo należące do języka jest akceptowane tak samo szybko jak w LALR
Słowo nienależące do języka może być odrzucone nieco później niż w LALR

Algorytm

Algorytm parsera SLR (taki sam jak innych parserów typu LR):

 Inicjalizacja stosu wartością S
 Wczytuje symbol z wejścia
 while (true)
     if Action(top(stack), input) = S
          NS <- Goto(top(stack),input)
          push NS
          Czyta następny symbol
     else if Action(top(stack), input) = Rk
          output k
          pop |RHS| of production k from stack
          NS <- Goto(top(stack), LHS_k)
          push NS
     else if Action(top(stack),input) = A
          output valid, return
     else
          output invalid, return

Przykład

Poniższa gramatyka może być analizowana przez parser SLR, ale nie przez parser LR(0):

(1) E → 1 E

(2) E → 1

Rodzina zbiorów sytuacji LR(0) wygląda tak samo dla parserów SLR i LR(0):

Zbiór sytuacji 0

S → • E

+ E → • 1 E

+ E → • 1

Zbiór sytuacji 1

E → 1 • E

E → 1 •

+ E → • 1 E

+ E → • 1

Zbiór sytuacji 2

S → E •

Zbiór sytuacji 3

E → 1 E •

Tabele goto i action dla parsera LR(0) wyglądają następująco:

Stan	Action		Goto
Stan	1	$	E
0	s1		2
1	s1/r2	r2	3
2		acc
3	r1	r1

Jak można zaobserwować występuje konflikt przesunięcia-redukcji dla stanu 1 i symbolu terminalnego 1. Jednakże zbiór FOLLOW(E) ma postać { $ } dlatego redukcje r1 i r2 będą wstawione tylko dla kolumny $. Rezultatem będą tabele action i goto bez konfliktów:

Stan	Action		Goto
Stan	1	$	E
0	s1		2
1	s1	r2	3
2		acc
3		r1

Zobacz też

Bibliografia

Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman: Kompilatory : reguły, metody i narzędzia. Warszawa: WNT, 2002. ISBN 83-204-2656-1.

Seppo sippu, Eljas Soisalon-Soininen: Parsing Theory. Berlin i inne: Springer-Verlag. ISBN 0-387-51732-4. ISBN 3-540-51732-4.