Wprowadzenie
Zstępująca analiza składniowa
Analiza składniowa jest drugą fazą kompilacji (po analizie
Języki formalne i techniki translacji - Wykład 7
leksykalnej).
Analiza składniowa przetwarza dane w postaci symboli
leksykalnych na drzewo wyprowadzenia pewnej gramatyki.
Maciek Gębala
Sprawdzanie kodu pod względem poprawności składni.
Gromadzenie dodatkowych informacji, np. w tablicy symboli,
potrzebnych dla dalszych kroków kompilacji.
3 kwietnia 2013
Maciek Gębala Zstępująca analiza składniowa Maciek Gębala Zstępująca analiza składniowa
Typy analizatorów składniowych Przykład niejednoznaczności
Rozważmy gramatykę dla prostych wyrażeń arytmetycznych
E E + E|E " E|E - E|E/E| - E|id
Zstępujące (top-down)  tworzenie drzewa wyprowadzenia od
Wez
my słowo id + id " id
góry.
Mamy dwa różne wyprowadzenia lewostronne
Wstępujące (bottom-up)  tworzenie drzewa wyprowadzenia od
liści w górę do korzenia.
E Ò! E + E Ò! id + E Ò! id + E " E
Metody te działają tylko dla pewnych podklas gramatyk
bezkontekstowych (jednoznaczne, deterministyczne).
Ò! id + id " E Ò! id + id " id
E Ò! E " E Ò! E + E " E Ò! id + E " E
Ò! id + id " E Ò! id + id " id
Gramatyka jest więc niejednoznaczna.
Maciek Gębala Zstępująca analiza składniowa Maciek Gębala Zstępująca analiza składniowa
Eliminowanie niejednoznaczności Eliminacja lewostronnej rekurencji
Niejednoznaczność można czasami wyeliminować.
Jak zmienić gramatykę
instr if wyr then instr
| if wyr then instr else instr Gramatyka jest lewostronnie rekurencyjna jeśli istnieje nieterminal A
taki, że istnieje wyprowadzenie A Ò!+ AÄ… dla pewnego Ä….
| inna
Metody zstępujące (up-down) nie dają się zastosować do takich
gramatyk.
Gramatyka jednoznaczna
instr p_instr|n_instr
Lewostronną rekurencję można wyeliminować.
p_instr if wyr then p_instr else p_instr
| inna
n_instr if wyr then instr
| if wyr then p_instr else instr
Porównaj wyprowadzenia dla if E1 then if E2 then I1 else I2
Maciek Gębala Zstępująca analiza składniowa Maciek Gębala Zstępująca analiza składniowa
Obsługa błędów Tryb paniki
W przypadku wystąpienia błędu wypisujemy go (czytelnie z podaniem
miejsca wystąpienia) i staramy się kontynuować przetwarzanie.
Sposób najprostszy w implementacji.
Po natrafieniu na błąd usuwamy kolejne symbole aż trafimy na
Strategie odzyskiwania kontroli taki który umożliwi nam ponowną synchronizację danych z
analizatorem (np. ograniczniki instrukcji).
tryb paniki
Mimo ominięcia pewnej liczby symboli metoda pozwala łatwo
poziom frazy
kontynuować pracę.
produkcje dla błędów
korekta globalna
Maciek Gębala Zstępująca analiza składniowa Maciek Gębala Zstępująca analiza składniowa
Poziom frazy Produkcje dla błędów
Po wykryciu błędu analizator stara się zmienić lokalnie wejście
Rozszerzamy gramatykę o produkcje generujące błędna
aby kontynuować analizę.
konstrukcje dla najczęstszych błędów.
Typowe zastosowania: zmiana niewłaściwego separatora,
Generujemy komunikat o błędzie w przypadku użycia produkcji
dodanie końcowego ogranicznika instrukcji.
dla błędu (ale nie przerywamy analizy, jest ona poprawna
względem tak poprawionej gramatyki).
W pewnych sytuacjach może to spowodować zapętlenie.
Maciek Gębala Zstępująca analiza składniowa Maciek Gębala Zstępująca analiza składniowa
Korekta globalna Analiza metodą zstępującą
"
Mamy ciąg tokenów (terminali) w " T i gramatykę
Staramy siÄ™ znalez
ć dla całego tekstu minimalną liczbę
G = (N, T , P, S).
poprawek, które spowodują, że tekst stanie się poprawny
Chcemy sprawdzić czy w " L(G)?
gramatycznie.
Szukamy lewostronnego wyprowadzenia dla w.
Metoda czasochłonna i nie zawsze poprawiająca w kierunku o
Budujemy drzewo wyprowadzenia dla w zaczynajÄ…c od korzenia
jaki chodziło w tekście wejściowym.
i tworząc wierzchołki w porządku preorder.
Maciek Gębala Zstępująca analiza składniowa Maciek Gębala Zstępująca analiza składniowa
Przykład Przykład
Wez
my napis w = cad i gramatykÄ™
Wez
my gramatykÄ™
S cAd
S aAd|aB
A ab|a
A b|c
Zaczynamy od symbolu poczÄ…tkowego, pierwszÄ… literÄ… w jest c
B ccd|ddc
wiÄ™c bierzemy produkcjÄ™ S cAd i wyprowadzamy S Ò! cAd
Pierwsza litera cAd jest zgodna z pierwszą literą w więc
Wez
my słowo w = accd
przechodzimy do symboli A i a. Możemy teraz użyć produkcji
S Ò! aAd
A ab i otrzymać ciąg cabd.
S Ò! aAd Ò! abd y
le, abd = accd, nawracamy

Druga litera się zgadza więc sprawdzamy trzecią. Niestety mamy
S Ò! aAd Ò! acd y
le, acd = accd, nawracamy

d i b czyli z
le. Musimy wrócić do A i poszukać alternatywnego
S Ò! aB
wyprowadzenia.
S Ò! aB Ò! accd OK
Używamy produkcji A a i tym razem jest dobrze.
UzyskaliÅ›my wyprowadzenie: S Ò! cAd Ò! cad.
Maciek Gębala Zstępująca analiza składniowa Maciek Gębala Zstępująca analiza składniowa
Faktoryzacja lewostronna Algorytm lewostronnej faktoryzacji gramatyki
Dla każdego nieterminala A znajdz
najdłuższy prefiks ą wspólny
dla co najmniej dwóch prawych stron A-produkcji.
Kiedy nie jest jasne na podstawie pierwszego symbolu, którą
JeÅ›li Ä… = µ to zamieÅ„ produkcje

produkcję wybrać do rozwinięcia nieterminala, przekształcamy te
produkcje tak aby decyzję podjąć póz
niej.
A Ä…²1| . . . |Ä…²n|Å‚1| . . . |Å‚m
na produkcje
Przykład
instr if wyr then instr else instr|if wyr then instr
A Ä…B|Å‚1| . . . |Å‚m
instr if wyr then instr koniec
B ²1| . . . |²n
koniec else instr|µ
gdzie B jest nowym dodatkowym nieterminalem.
Transformację powtarzamy dopóki zmienia ona gramatykę.
Maciek Gębala Zstępująca analiza składniowa Maciek Gębala Zstępująca analiza składniowa
Analizatory przewidujące Przykład
Wez
my gramatykÄ™
E E+T |T
T T "F |F
Często uważnie tworząc gramatykę, usuwając w niej lewostronną
F (E)|id
rekurencję i wykonując lewostronną faktoryzację możemy uzyskać
gramatykę, która przy wyprowadzeniu nie potrzebuje nawrotów.
Eliminujemy lewostronnÄ… rekurencjÄ™
E TG
Wyprowadzenie w takiej gramatyce może być łatwo sprawdzane
G +TG|µ
prostym, deterministycznym automatem ze stosem.
T FV
V "FV |µ
F (E)|id
Gramatyka nie potrzebuje lewostronnej faktoryzacji.
Maciek Gębala Zstępująca analiza składniowa Maciek Gębala Zstępująca analiza składniowa
Działanie analizatora przewidującego na id + id " id Zbiory FIRST i FOLLOW
Stos Wejście Wyjście
FIRST pomaga wybrać produkcję którą możemy użyć do
$E id + id " id$
wyprowadzania napisu.
$GT id + id " id$ E TG
$GVF id + id " id$ T FV
FIRST (Ä…) = {x " T : "² Ä… Ò!" x²}
$GV +id " id$ F id
$G +id " id$ V µ
FOLLOW pomaga synchronizować symbole podczas
$GT id " id$ G +TG
odzyskiwania kontroli w trybie paniki.
$GVF id " id$ T FV
$GV "id$ F id
FOLLOW (A) = {x " T : "Ä…"² S Ò!" Ä…Ax²}
$GVF id$ V "FV
Na podstawie tych funkcji generujemy tablicÄ™ analizatora
$GV $ F id
przewidującego która dla nieterminala A i terminala a wyznacza
$G $ V µ
którą produkcję możemy użyć.
$ $ G µ
Maciek Gębala Zstępująca analiza składniowa Maciek Gębala Zstępująca analiza składniowa
Wyznaczanie FIRST (X ) Wyznaczanie FOLLOW (A)
Dla wszystkich symboli X z gramatyki G tworzymy zbiory FIRST
według następujących reguł
Dla wszystkich nieterminali A FOLLOW (A) tworzymy według
1
Jeśli X jest terminalem to FIRST (X ) = {X }.
następujących reguł
2
JeÅ›li X µ jest produkcjÄ… to do FIRST (X) dodajemy µ.
1
Dla symbolu poczÄ…tkowego S do FOLLOW (S) dodajemy $.
3
Jeśli X jest nieterminalem i X Y1Y2 . . . Yk to a dodajemy do
2
JeÅ›li mamy produkcjÄ™ A Ä…B² to do FOLLOW (B) dodajemy
FIRST (X ) jeżeli istnieje i takie, że a " FIRST (Yi) oraz
wszystkie symbole z FIRST (²) poza µ.
µ " FIRST (Yj) dla każdego j < i. µ " FIRST (X ) jeÅ›li należy do
3
JeÅ›li mamy produkcjÄ™ A Ä…B albo produkcjÄ™ A Ä…B², gdzie
wszystkich FIRST (Yi)
µ " FIRST (²) to do FOLLOW (B) dodajemy wszystkie symbole z
Ponadto
FOLLOW (A).
FIRST (X Ä…) = FIRST (X ) gdy µ " FIRST (X )
/
FIRST (X Ä…) = FIRST (X ) *" FIRST (Ä…) gdy µ " FIRST (X)
Maciek Gębala Zstępująca analiza składniowa Maciek Gębala Zstępująca analiza składniowa
Przykład Budowa tablic analizatora przewidującego
FIRST (E) = FIRST (T ) = FIRST (F ) = {(, id}
Dla każdej produkcji A ą
FIRST (G) = {+, µ}
1
dla każdego a " T jeśli a " FIRST (ą) to wpisz A ą do M[A, a].
FIRST (V ) = {", µ}
2
jeÅ›li µ " FIRST (Ä…) to dla każdego b " FOLLOW (A) wpisz A Ä…
FOLLOW (E) = FOLLOW (G) = {), $}
do M[A, b].
FOLLOW (T ) = FOLLOW (V ) = {+, ), $}
FOLLOW (F ) = {+, ", ), $}
Maciek Gębala Zstępująca analiza składniowa Maciek Gębala Zstępująca analiza składniowa
Przykład
id + " ( ) $
E TG TG
G +TG µ µ
T FV FV
V µ "FV µ µ
F id (E)
Maciek Gębala Zstępująca analiza składniowa