Analiza redukujÄ…ca
Analiza wstępująca. Gramatyki LR(k)
Analiza redukująca buduje drzewo wyprowadzenia dla wejścia,
zaczynając od liści (od dołu) i przechodząc w górę, aż do korzenia
Języki formalne i techniki translacji - Wykład 9
(do góry). W każdym kroku redukcji pewien podciąg pasujący do
prawej strony produkcji jest zastępowany symbolem z lewej strony tej
produkcji. Jeśli podciągi wybieramy prawidłowo to otrzymujemy
Maciek Gębala
prawostronne wyprowadzenie.
Metoda pierwszeństwa operatorów.
17 kwietnia 2013
Analiza LR.
Maciek Gębala Analiza wstępująca. Gramatyki LR(k) Maciek Gębala Analiza wstępująca. Gramatyki LR(k)
Przykład Uchwyty
Wez
my gramatykÄ™
S aABe
Uchwyt Å‚ to produkcja A ² i pozycja w Å‚, na której znajduje siÄ™
A Abc|b
ciÄ…g symboli ², który po zastÄ…pieniu przez A da nam ciÄ…g
B d
poprzedzajÄ…cy Å‚ w wyprowadzeniu prawostronnym.
Wez
my słowo abbcde.
JeÅ›li S Ò!" Ä…Aw Ò! Ä…²w, to A ² na pozycji po Ä… jest
Pierwszym symbolem który możemy zredukować jest b
uchwytem Ä…²w.
i otrzymujemy aAbcde.
CiÄ…g symboli po prawej stronie uchwytu zawiera tylko terminale.
Teraz możemy zredukować Abc i otrzymujemy aAde.
Jeśli gramatyka jest jednoznaczna to w trakcie redukcji mamy
Teraz d i aABe.
zawsze tylko jeden uchwyt.
StÄ…d mamy prawostronne wyprowadzenie
S Ò! aABe Ò! aAde Ò! aAbcde Ò! abbcde
Maciek Gębala Analiza wstępująca. Gramatyki LR(k) Maciek Gębala Analiza wstępująca. Gramatyki LR(k)
Przykład - Shift-Reduce-Parsing Parsowanie z użyciem stosu
E E + E | E " E | (E) | id
Stos używamy do pamiętania symboli z gramatyki. Uchwyt jest
SÅ‚owo id1 + id2 " id3.
zawsze na szczycie stosu.
Wyprowadzenie prawostronne
Stos input czynność
E Ò! E + E Ò! E + E " E
$ id1 + id2 " id3$ shift
Ò! E + E " id3 Ò! E + id2 " id3 Ò! id1 + id2 " id3
$id1 +id2 " id3$ redukcja przez E id
$E +id2 " id3$ shift
Redukcja
$E+ id2 " id3$ shift
$E + id2 "id3$ redukcja przez E id
SÅ‚owo Uchwyt Produkcja do redukcji
$E + E "id3$ shift
id1 + id2 " id3 id1 E id
$E + E" id3$ shift
E + id2 " id3 id2 E id
$E + E " id3 $ redukcja przez E id
E + E " id3 id3 E id
$E + E " E $ redukcja przez E E " E
E + E " E E " E E E " E
$E + E $ redukcja przez E E + E
E + E E + E E E + E
$E $ Accept
E
Maciek Gębala Analiza wstępująca. Gramatyki LR(k) Maciek Gębala Analiza wstępująca. Gramatyki LR(k)
Problemy w trakcie analizy Gramatyki operatorowe
Gramatyka jest operatorowa jeśli żadna prawa strona produkcji nie
zawiera dwóch sąsiednich nieterminali.
Konflikt przesunięcie/redukcja  mimo znajomości całego stosu
Gramatyka nie-operatorowa
i następnego symbolu wejściowego nie można zdecydować, czy
wykonać przesunięcie czy redukcję.
E EAE | id
Konflikt redukcja/redukcja  możemy wykonać kilka możliwych
redukcji.
A + | - | " | /
Równoważna gramatyka operatorowa
E E + E | E - E | E " E | E/E | id
Maciek Gębala Analiza wstępująca. Gramatyki LR(k) Maciek Gębala Analiza wstępująca. Gramatyki LR(k)
Priorytety operatorów Analiza dla gramatyki operatorowej
Między pewnymi parami terminali definiujemy trzy rozłączne relacje
a b a ma mniejszy priorytet niż b
.
a = b a ma taki sam priorytet jak b
Wez
my słowo do wyprowadzenia $ id + id " id $
a b a ma większy priorytet niż b
Wstawmy relacje między terminale $ id + id " id $
$ E + E " E $
Przykład relacji operatorów
(ignoruj znaki nieterminalne)
+ - " / id $
$ + " $
+
$ + $
-
$$
"
/
id
$
Maciek Gębala Analiza wstępująca. Gramatyki LR(k) Maciek Gębala Analiza wstępująca. Gramatyki LR(k)
. .
Obliczanie relacji , = i Obliczanie relacji , = i
Dla każdej produkcji A x1 . . . xk
Zbiór LEADING(A) (pierwsze terminale wyprowadzane z A).
1 .
a " LEADING(A) jeÅ›li mamy produkcjÄ™ A Ba² lub A a².
1
Jeśli xi i xi+1 są terminalami to xi = xi+1.
2
Jeśli istnieje produkcja A Bą i a " LEADING(B) to
.
2
Jeśli xi i xi+2 są terminalami a xi+1 nieterminalem to xi = xi+2.
a " LEADING(A).
3 3
Dla wszystkich nieterminali liczymy 1 i powtarzamy 2 aż nic się nie Jeśli xi jest terminalem a xi+1 nieterminalem to dla każdego
zmienia.
a " LEADING(xi+1) mamy xi a.
4
Analogicznie TRAILING(A) (ostatnie terminale wyprowadzane
Jeśli xi jest nieterminalem a xi+1 terminalem to dla każdego
z A).
a " TRAILING(xi) mamy a xi+1.
Maciek Gębala Analiza wstępująca. Gramatyki LR(k) Maciek Gębala Analiza wstępująca. Gramatyki LR(k)
Uproszczenie Algorytm analizy metodą pierwszeństwa operatorów
Dla każdego terminala a definiujemy f (a), g(a) " N tak aby
f (a) < g(b) Ð!Ò! a b
Wejście: Tekst wejściowy w i tablica relacji priorytetów.
.
f (a) = g(b) Ð!Ò! a = b
Wyjście: Jeśli w jest poprawny to poprawny ciąg produkcji
f (a) > g(b) Ð!Ò! a b
prawostronnego wyprowadzenia, w p.p. informacje o błędzie.
Nieterminale są ignorowane w porównaniach operacjach na
Przykład stosie a wykorzystywane w redukcjach.
+ - " / id $
f 2 2 4 4 6 0
g 1 1 3 3 5 0
Maciek Gębala Analiza wstępująca. Gramatyki LR(k) Maciek Gębala Analiza wstępująca. Gramatyki LR(k)
Algorytm analizy metodą pierwszeństwa operatorów Analiza LR(k)
top(stack) = $ and first(in) = $
Wejście przeglądamy od lewej do prawej (L).
ACCEPT
Otrzymujemy wyprowadzenie prawostronne (R).
.
k - ilość symboli wejścia potrzebnych do podjęcia decyzji. Jeśli
top(stack) first(in) or top(stack) = first(in)
k = 1 to jest często pomijane.
przenieÅ› first(in) na stack
!(top(stack) first(in)) error() Prawie wszystkie języki programowania można opisać gramatyką
bezkontekstowÄ… typu LR(1).
top(stack) first(in) /* redukcja */
pop(stack)
Maciek Gębala Analiza wstępująca. Gramatyki LR(k) Maciek Gębala Analiza wstępująca. Gramatyki LR(k)
Algorytm analizy LR Tablica analizatora
Tablica składa się z dwóch części: akcji i przejść.
Na podstawie s - stanu z wierzchołka stosu i a symbolu na
wejściu wykonujemy akcja[s, a]
1
przesuń, na stos a i s = akcja[s, a],
Analizator LR składa się z wejścia, wyjścia, stosu, programu
2
redukuj zgodnie z produkcjÄ… A ², na stos A i stan wyliczony
sterujÄ…cego i tablicy analizatora.
przez przejście,
Na stosie zapamiętywane są symbole z gramatyki i specjalne
3
akceptuj,
symbole zwane stanami. 4
błąd.
Symbole stanu podsumowujÄ… informacjÄ™ zawarte na stosie po
Konfiguracja analizatora LR to zawartość stosu
nim.
i nieprzetworzone wejście
Symbol stanu i aktualny symbol wejściowy są używane do
(s0X1s1X2s2 . . . Xmsm, aiai+1 . . . an$)
podejmowania decyzji na podstawie tablicy analizatora.
i odpowiada prawostronnej formie wyprowadzenia
X1X2 . . . Xmaiai+1 . . . an
Maciek Gębala Analiza wstępująca. Gramatyki LR(k) Maciek Gębala Analiza wstępująca. Gramatyki LR(k)
Działanie analizatora LR Przykład
Gramatyka
1 E E + T (1) | T (2)
akcja[sm, ai] = shift s (s0X1s1X2s2 . . . Xmsm, aiai+1 . . . an$)
(s0X1s1X2s2 . . . Xmsmais, ai+1 . . . an$) T T " F (3) | F (4)
2
akcja[sm, ai] = A ² (s0X1s1X2s2 . . . Xmsm, aiai+1 . . . an$)
F (E) (5) | ID (6)
(s0X1s1X2s2 . . . Xm-r sm-r As, aiai+1 . . . an$),
gdzie s = przejÅ›cie[sm-r , A] i ² = Xm-r+1 . . . Xm (r = |²|).
3
akcja[sm, ai] = accept  koniec analizy.
Akcje kodujemy następująco:
4
akcja[sm, ai] = error  wykryto błąd.
1
si  przesunięcie i, wstawiamy na stos stan si,
2
rj  redukcja według produkcji o numerze j
3
acc  akceptacja,
4
puste miejsce oznacza błąd.
Maciek Gębala Analiza wstępująca. Gramatyki LR(k) Maciek Gębala Analiza wstępująca. Gramatyki LR(k)
Przykład - Tablica analizatora Przykład
stos wejście akcja
stan akcja przejście
s0 id + id " id$ s5
id + " ( ) $ E T F
s0ids5 +id " id$ r6 (F id), p[s0, F ] = s3
s0 s5 s4 s1 s2 s3
s0F s3 +id " id$ r4 (T F ), p[s0, T ] = s2
s1 s6 acc
s0T s2 +id " id$ r2 (E T ), p[s0, E] = s1
s2 r2 s7 r2 r2
s0Es1 +id " id$ s6
s3 r4 r4 r4 r4
s0Es1+s6 id " id$ s5
s4 s5 s4 s8 s2 s3 s0Es1+s6ids5 "id$ r6 (F id), p[s6, F ] = s3
s0Es1+s6F s3 "id$ r4 (T F ), p[s6, T ] = s9
s5 r6 r6 r6 r6
s0Es1+s6T s9 "id$ s7
s6 s5 s4 s9 s3
s0Es1+s6T s9"s7 id$ s5
s7 s5 s4 s10
s0Es1+s6T s9"s7ids5 $ r6 (F id), p[s7, F ] = s10
s8 s6 s11
s0Es1+s6T s9"s7F s10 $ r3 (T T " F ), p[s6, T ] = s9
s9 r1 s7 r1 r1
s0Es1+s6T s9 $ r1 (E E + T ), p[s0, E] = s1
s10 r3 r3 r3 r3
s0Es1 $ acc
s11 r5 r5 r5 r5
Maciek Gębala Analiza wstępująca. Gramatyki LR(k) Maciek Gębala Analiza wstępująca. Gramatyki LR(k)
Budowanie tablic analizatorów Generatory analizatorów LR - Bison (Yacc)
Bison dla zadanej specyfikacji generuje kod z
ródłowy analizatora
składniowego.
Aby zbudować analizator typu LR wystarczy zbudować tablicę
Program Bison w łatwy sposób może współpracować z
analizatora dla podanej gramatyki.
generatorem analizatorów leksykalnych Flex.
Rozpatrzymy trzy metody (typy), od najprostszego i najsłabszego
Program generuje analizator redukujÄ…cy LALR.
1
SLR  prosty LR; Nieterminal lewej strony pierwszej produkcji jest domyślnie
2
kanoniczny LR;
symbolem startowym.
3
LALR  podglÄ…dajÄ…ce LR.
W razie konfliktu redukcja/redukcja wybierana jest akcja
Budowa poszczególnych analizatorów na kolejnych wykładach.
wynikająca z kolejności zapisu.
W razie konfliktu redukcja/przesunięcie wybierane jest
przesunięcie.
Maciek Gębala Analiza wstępująca. Gramatyki LR(k) Maciek Gębala Analiza wstępująca. Gramatyki LR(k)
Bison - plik specyfikacji Współpraca z LEX-em
Funkcja parsujÄ…ca .
Funkcja zwracająca błędy .
Parser korzysta z funkcji do czytania tokenów którą
można napisać samemu lub skorzystać z LEX-a.
Plik specyfikacji składa się z trzech sekcji (rozdzielonych ):
1
sekcja definicji,
Tokeny użyte w parserze mogą być wyeksportowane do pliku
2
sekcja reguł przetwarzania,
nagłówkowego.
3
sekcja podprogramów.
Również wartość tokena może być przeniesiona do parsera 
W sekcji definicji definiujemy tokeny (terminale) używane w
zmienna globalna . Domyślny typ to ale można
gramatyce.
zmienić na kilka typów posługując się unią i deklaracjami typów.
Reguła przetwarzania składa się z produkcji i operacji (w języku
C).
Maciek Gębala Analiza wstępująca. Gramatyki LR(k) Maciek Gębala Analiza wstępująca. Gramatyki LR(k)
Przykład
Gramatyka
E E or T | T
T T and F | F
F not F | (F ) | true | false
Pliki
Maciek Gębala Analiza wstępująca. Gramatyki LR(k)