Tablice analizatorów SLR
Sytuacją LR(0) nazywamy produkcję z gramatyki G z kropką w
jakimś miejscu prawej strony.
Gramatyki SLR, LR(1) i LALR
Z produkcji A XYZ możemy otrzymać cztery sytuacje:
A �XYZ , A X � YZ , A XY � Z i A XYZ �, a z produkcji
Języki formalne i techniki translacji - Wykład 10
A � jedną A �.
Każdą sytuację możemy reprezentować parą liczb: numer
Maciek Gębala produkcji i pozycja kropki.
Konstruujemy z gramatyki deterministyczny automat skończony
rozpoznający odpowiednie prefiksy.
Sytuacje można traktować jak stany automatu
24 kwietnia 2012
niedeterministycznego.
Rozważane gramatyki uzupełniamy o specjalną produkcję
początkową S S.
Maciek Gębala Gramatyki SLR, LR(1) i LALR Maciek Gębala Gramatyki SLR, LR(1) i LALR
Operacja domknięcia Przykład
E E
E E + T | T
T T " F | F
Jeśli I jest zbiorem sytuacji z gramatyki G to domknięcie(I) jest
F (E) | id
zbiorem sytuacji otrzymanych z I przy zastosowaniu reguł
1
Każda z sytuacja z I należy do domknięcie(I).
Niech I = {[E �E]}.
2
Jeśli A ą � B� jest w domknięcie(I), a B ł jest produkcją to
Wtedy domknięcie(I) zawiera
do domknięcie(I) dodajemy B �ł. Powtarzamy, dopóki można
dodać nowe elementy.
E �E
E �E + T | � T
T �T " F | � F
F �(E) | � id
Maciek Gębala Gramatyki SLR, LR(1) i LALR Maciek Gębala Gramatyki SLR, LR(1) i LALR
Operacja przejścia Przykład
E E
E E + T | T
T T " F | F
F (E) | id
Jeśli I jest zbiorem sytuacji a X symbolem z gramatyki, to
przejście(I, X ) jest domknięciem zbioru wszystkich sytuacji
A ąX � � takich, że A ą � X � jest w I.
Niech I = {[E E�], [E E � +T ]}.
Wtedy przejcie(I, +) zawiera
E E + �T
T �T " F | � F
F �(E) | � id
Maciek Gębala Gramatyki SLR, LR(1) i LALR Maciek Gębala Gramatyki SLR, LR(1) i LALR
Konstruowanie zbiorów sytuacji Przykład
I0 : E �E, E �E + T , E �T , T �T " F , T �F ,
F �(E), F �id
I1 : E E�, E E � +T
I2 : E T �, T T � "F
I3 : T F �
1
C �! { domknięcie({[S �S]}) }
I4 : F (�E), E �E + T , E �T , T �T " F , T �F ,
2
Dopóki C może się powiększyć to dla każdego zbioru sytuacji
F �(E), F �id
I " C i każdego symbolu X takiego, że przejście(I, X ) = " dodaj

I5 : F id�
przejście(I, X ) do C.
I6 : E E + �T , T �T " F , T �F , F �(E), F �id
I7 : T T " �F , F �(E), F �id
I8 : F (E�), E E � +T
I9 : E E + T �, T T � "F
I10 : T T " F �
I11 : F (E)�
Maciek Gębala Gramatyki SLR, LR(1) i LALR Maciek Gębala Gramatyki SLR, LR(1) i LALR
Funkcja przejścia dla utworzonego DFA Konstrukcja tablicy analizatora SLR
E T F ( ) + " id
1
Zbuduj C = {I0, . . . , In} - rodzinę zbiorów sytuacji dla G .
I0 I1 I2 I3 I4 I5
2
Stan i budujemy z Ii. Akcje analizatora dla stanu i wyznaczamy
I1 I6
następująco:
I2 I7
1
Jeśli [A ą � a�] " Ii, a jest terminalem i przejście(Ii, a) = Ij to
I3
akcja[i, a] = j.
I4 I8 I2 I3 I5
2
Jeśli [A ą�] " Ii to akcja[i, a] = A ą dla wszystkich
I5
a " FOLLOW (A) (A = S ).

I6 I9 I3 I4 I5
3
Jeśli [S S�] " Ii to akcja[i, $] = ACC.
I7 I10 I4 I5
3
Jeśli przejście(Ii, A) = Ij to przejście[i, A] = j.
I8 I11 I6
4
Stan startowy analizatora to stan odpowiadający zbiorowi
I9 I7
sytuacji zawierającego [S �S].
I10
I11
Maciek Gębala Gramatyki SLR, LR(1) i LALR Maciek Gębala Gramatyki SLR, LR(1) i LALR
Przykład Kanoniczne tablice analizatorów LR
S L = R|R, L "R|id, R L
Przechowujemy w stanie więcej informacji aby wykluczyć
I0 : S �S, S �L = R, S �R, L � " R, L �id, R �L; I1 : niektóre konflikty.
S S�; I2 : S L� = R, R L�; I3 : S R�; I4 : L " � R, R �L,
Rozszerzamy definicję sytuacji przez dodanie do produkcji z
L � " R, L �id; I5 : L id�; I6 : S L = �R, R �L, L � " R,
kropką terminala lub $. (Sytuacja LR(1))
L �id; I7 : L "R�; I8 : R L�; I9 : S L = R�;
Drugą składową nazywamy podglądem sytuacji.
Redukcję A ą wykonujemy tylko dla tych symboli wejściowych
Co to jest akcja[2, =]?
a dla których sytuacja [A ą�, a] wyznaczyła stan z wierzchołka
akcja[2, =] = 6 bo przejście(I2, =) = I6
stosu.
akcja[2, =] = R L bo =" FOLLOW (R)
Konflikt redukcja/przesunięcie
Maciek Gębala Gramatyki SLR, LR(1) i LALR Maciek Gębala Gramatyki SLR, LR(1) i LALR
Konstruowanie sytuacji LR(1) Konstrukcja kanonicznej tablicy analizatora LR
domknięcie(I)
Dopóki można dodać nowy element do I dla każdej sytuacji
1
Zbuduj C = {I0, . . . , In} - rodzinę zbiorów sytuacji LR(1) dla G .
[A ą � B�, a] " I, każdej produkcji B ł " G i każdego terminala
b " FIRST (�a) dodaj [B �ł, b] do I. 2
Stan i budujemy z Ii. Akcje analizatora dla stanu i wyznaczamy
następująco:
1
Jeśli [A ą � a�, b] " Ii, a jest terminalem i przejście(Ii, a) = Ij to
przejście(I, X )
akcja[i, a] = j.
J  zbiór sytuacji [A ąX � �, a] takich, że [A ą � X �, a] " I.
2
Jeśli [A ą�, b] " Ii to akcja[i, b] = A ą (A = S ).

przejście(I, X ) = domknięcie(J).
3
Jeśli [S S�, $] " Ii to akcja[i, $] = ACC.
3
Jeśli przejście(Ii, A) = Ij to przejście[i, A] = j.
Konstruowanie zbiorów sytuacji LR(1)
4
Stan startowy analizatora to stan odpowiadający zbiorowi
1 sytuacji zawierającego [S �S, $].
C �! { domknięcie({[S �S, $]}) }
2
Dopóki C może się powiększyć to dla każdego zbioru sytuacji
I " C i każdego symbolu X takiego, że przejście(I, X ) = " dodaj

przejście(I, X ) do C.
Maciek Gębala Gramatyki SLR, LR(1) i LALR Maciek Gębala Gramatyki SLR, LR(1) i LALR
Gramatyki LALR Przykład
Tablice analizatorów LR(1) są często bardzo duże  tablice
S S S CC C cC|d
LALR są przeważnie mniejsze.
Główna idea to łączenie takich stanów LR(1) które nie powodują
Zbiory sytuacji
konfliktów.
I0 : [S �S, $], [S �CC, $], [C �cC, c/d], [C �d, c/d];
I1 : [S S�, $];
Jądro sytuacji
I2 : [S C � C, $], [C �cC, $], [C �d, $];
Jądrem sytuacji nazywamy te sytuacje których prawa strona nie
I3 : [C c � C, c/d], [C �cC, c/d], [C �d, c/d];
zaczyna się od kropki oraz sytuację S �S. (Rozpatrujemy sytuacje
I4 : [C d�, c/d];
LR(0)).
I5 : [S CC�, $];
I6 : [C c � C, $], [C �cC, $], [C �d, $];
I7 : [C d�, $];
Operacja domknięcia zbioru sytuacji LR(0) dodaje tylko sytuacje
I8 : [C cC�, c/d];
spoza jądra.
I9 : [C cC�, $];
Maciek Gębala Gramatyki SLR, LR(1) i LALR Maciek Gębala Gramatyki SLR, LR(1) i LALR
Przykład Przykład
Kanoniczna tablica analizatora
stan akcja przejście
Porównajmy stany s3 i s6, s4 i s7, oraz s8 i s9. Poszczególne pary
c d $ S C
mają te same jądra sytuacji (różnią się one tylko podglądanym
s0 s3 s4 s1 s2
symbolem).
s1 acc
s2 s6 s7 s5
s3 s3 s4 s8 Czy połączenie stanów może spowodować konflikt?
s4 r3 r3
Tak. Jest to jednak mało prawdopodobne dla błędu
s5 r1
przesunięcie/redukcja. Może natomiast zajść błąd redukcja/redukcja.
s6 s6 s7 s9
Stąd nie wszystkie gramatyki LR(1) są gramatykami LALR(1).
s7 r3
s8 r2 r2
s9 r2
Maciek Gębala Gramatyki SLR, LR(1) i LALR Maciek Gębala Gramatyki SLR, LR(1) i LALR
Przykład powstania konfliktu Metoda budowania tablic LALR
S S, S aAd|bBd|aBe|bAe, A c, B c
1
Zbuduj C = {I0, . . . , In}  rodzinę zbiorów sytuacji LR(1).
2
Dla każdego jądra zbiorów sytuacji znajdz
wszystkie zbiory o tym
samym jądrze i zastąp je przez ich sumę.
Tworząc zbiory sytuacji otrzymamy m.in. {[A c�, d], [B c�, e]}
i {[A c�, e], [B c�, d]}. Żaden z tych zbiorów nie wywołuje 3
Niech C = {J0, . . . , Jm}. Utwórz na podstawie tego zbioru
konfliktów.
tablicę akcji i przejść. Jeśli nastąpił konflikt  przerwij (uznaj, że
gramatyka nie jest typu LALR(1)).
Ich suma {[A c�, d/e], [B c�, d/e]} wywołuje konflikt.
Maciek Gębala Gramatyki SLR, LR(1) i LALR Maciek Gębala Gramatyki SLR, LR(1) i LALR
Przykład Różnice w działaniu LR(1) i LALR(1)
Tablica analizatora LALR(1)
stan akcja przejście
Dla poprawnych danych obie metody działają identycznie dając to
c d $ S C
samo wyprowadzenie.
s0 s36 s47 s1 s2
s1 acc
Dla niepoprawnych wejść analiza LALR(1) może wykonać pewne
s2 s36 s47 s5
redukcje po zgłoszeniu błędu przez analizę LR(1). Ale analiza
s36 s36 s47 s89
LALR(1) nie wykona już żadnego przesunięcia.
s47 r3 r3 r3
s5 r1
s89 r2 r2 r2
Maciek Gębala Gramatyki SLR, LR(1) i LALR Maciek Gębala Gramatyki SLR, LR(1) i LALR
Przykład Obsługa błędów w analizie LR
Kanoniczny analizator LR przed zgłoszeniem błędu nigdy nie wykona
żadnej redukcji. Analizatory SLR i LALR mogą wykonać pewną liczbę
S S S CC C cC|d
redukcji ale nie przesuną na stos błędnego symbolu wejściowego.
Słowo: ccd
Tryb paniki
LR(1) odłoży na stosie s0cs3cs3ds4 i widząc $ zgłosi błąd.
Przeglądamy stos w dół aż napotkamy stan s z przejściem dla
pewnego nieterminala A. Następnie wyrzucamy z wejścia symbole aż
LALR(1) odłoży na stosie s0cs36cs36ds47 i widząc $ dokona
znajdziemy symbol a który legalnie może występować po A.
redukcji C d i zmieni stos na s0cs36cs36Cs89.
Odkładamy na stos przejście[s, A] i kontynuujemy analizę.
Teraz wykona redukcję C cC i otrzyma s0cs36Cs89.
Następna redukcja C cC i otrzyma s0Cs2. Uzupełnienie tablicy analizatora o obsługę błędów
I dopiero teraz wykryje błąd. W puste miejsca tablicy wstawiamy odpowiednie akcje korygujące
stos i wejście.
Maciek Gębala Gramatyki SLR, LR(1) i LALR Maciek Gębala Gramatyki SLR, LR(1) i LALR
Analiza składniowa  podsumowanie
Rola analizatora składniowego.
Deterministyczne gramatyki bezkontekstowe.
Analiza zstępująca: gramatyki LL(k).
Analiza wstępująca: gramatyki operatorowe, SLR, LR i LALR.
Obsługa błędów.
Maciek Gębala Gramatyki SLR, LR(1) i LALR