Parser LL
Parser LL to parser czytający tekst od lewej do prawej i produkujący lewostronne wyprowadzenie metodą zstępującą. Popularne rodzaje parserów LL to parsery sterowane tablicą i rekurencyjne.
Parser sterowany tablicą
[edytuj | edytuj kod]Parsery klasy LL(k) parsują znak po znaku, utrzymując stos zawierający „spodziewane symbole”. Na początku znajdują się tam symbol startowy i znak końca pliku. Jeśli na szczycie stosu jest ten sam symbol terminalny, jaki aktualne znajduje się na wejściu, usuwa się go ze szczytu stosu i przesuwa strumień wejściowy na kolejny znak. Jeśli inny symbol terminalny zwraca się błąd. Jeśli występuje tam jakiś symbol nieterminalny, to zdejmuje się go i zależnie od tego symbolu oraz od k kolejnych znaków wejścia, umieszcza na stosie odpowiedni zestaw symboli.
LL(1) jest bardzo ubogą klasą (jednak w wielu przypadkach wystarczająca), np. tak prosta gramatyka jak:
- Wyrażenie → liczba '+' Wyrażenie
- Wyrażenie → liczba
już do niej nie należy, ponieważ spodziewając się Wyrażenia i widząc liczbę, nie wiemy czy zamienić ją na stosie na liczba czy liczba '+' Wyrażenie.
Na szczęście można przepisać tę gramatykę na równoważną gramatykę LL(1):
- Wyrażenie → liczba OpcjonalnePlusWyrażenie
- OpcjonalnePlusWyrażenie → ε
- OpcjonalnePlusWyrażenie → '+' Wyrażenie
Zbudujmy tablicę parsingu dla gramatyki:
- Wyrażenie → Iloczyn '+' Wyrażenie
- Wyrażenie → Iloczyn
- Iloczyn → liczba '*' Iloczyn
- Iloczyn → liczba
Najpierw musimy przepisać ją do równoważnej gramatyki LL(k) (w tym przypadku k jest równe 1):
- Wyrażenie → Iloczyn OpcjonalnePlusWyrażenie
- OpcjonalnePlusWyrażenie → ε
- OpcjonalnePlusWyrażenie → '+' Wyrażenie
- Iloczyn → liczba OpcjonalneRazyIloczyn
- OpcjonalneRazyIloczyn → ε
- OpcjonalneRazyIloczyn → '*' Iloczyn
Tablica parsingu to:
liczba | + | * | koniec | |
Wyrażenie | Iloczyn OpcjonalnePlusWyrażenie | błąd | błąd | błąd |
OpcjonalnePlusWyrażenie | błąd | + Wyrażenie | błąd | ε |
Iloczyn | liczba OpcjonalneRazyIloczyn | błąd | błąd | błąd |
OpcjonalneRazyIloczyn | błąd | ε | * Iloczyn | ε |
I dla wyrażenia 5 + 3 * 8 * 2 + 7 * 2 parsing przebiega następująco:
Stos | Wejście |
---|---|
Wyrażenie koniec | liczba + liczba * liczba * liczba + liczba * liczba koniec |
Iloczyn OpcjonalnePlusWyrażenie koniec | liczba + liczba * liczba * liczba + liczba * liczba koniec |
liczba OpcjonalneRazyIloczyn OpcjonalnePlusWyrażenie koniec | liczba + liczba * liczba * liczba + liczba * liczba koniec |
OpcjonalneRazyIloczyn OpcjonalnePlusWyrażenie koniec | + liczba * liczba * liczba + liczba * liczba koniec |
OpcjonalnePlusWyrażenie koniec | + liczba * liczba * liczba + liczba * liczba koniec |
+ Wyrażenie koniec | + liczba * liczba * liczba + liczba * liczba koniec |
Wyrażenie koniec | liczba * liczba * liczba + liczba * liczba koniec |
Iloczyn OpcjonalnePlusWyrażenie koniec | liczba * liczba * liczba + liczba * liczba koniec |
liczba OpcjonalneRazyIloczyn OpcjonalnePlusWyrażenie koniec | liczba * liczba * liczba + liczba * liczba koniec |
OpcjonalneRazyIloczyn OpcjonalnePlusWyrażenie koniec | * liczba * liczba + liczba * liczba koniec |
* Iloczyn OpcjonalnePlusWyrażenie koniec | * liczba * liczba + liczba * liczba koniec |
Iloczyn OpcjonalnePlusWyrażenie koniec | liczba * liczba + liczba * liczba koniec |
liczba OpcjonalneRazyIloczyn OpcjonalnePlusWyrażenie koniec | liczba * liczba + liczba * liczba koniec |
OpcjonalneRazyIloczyn OpcjonalnePlusWyrażenie koniec | * liczba + liczba * liczba koniec |
* Iloczyn OpcjonalnePlusWyrażenie koniec | * liczba + liczba * liczba koniec |
Iloczyn OpcjonalnePlusWyrażenie koniec | liczba + liczba * liczba koniec |
liczba OpcjonalneRazyIloczyn OpcjonalnePlusWyrażenie koniec | liczba + liczba * liczba koniec |
OpcjonalneRazyIloczyn OpcjonalnePlusWyrażenie koniec | + liczba * liczba koniec |
OpcjonalnePlusWyrażenie koniec | + liczba * liczba koniec |
+ Wyrażenie koniec | + liczba * liczba koniec |
Wyrażenie koniec | liczba * liczba koniec |
Iloczyn OpcjonalneRazyWyrażenie koniec | liczba * liczba koniec koniec |
liczba OpcjonalneRazyIloczyn OpcjonalneRazyWyrażenie koniec | liczba * liczba koniec |
OpcjonalneRazyIloczyn OpcjonalneRazyWyrażenie koniec | * liczba koniec |
* Iloczyn OpcjonalneRazyWyrażenie koniec | * liczba koniec |
Iloczyn OpcjonalneRazyWyrażenie koniec | liczba koniec |
liczba OpcjonalneRazyIloczyn OpcjonalneRazyWyrażenie koniec | liczba koniec |
OpcjonalneRazyIloczyn OpcjonalneRazyWyrażenie koniec | koniec |
OpcjonalneRazyWyrażenie koniec | koniec |
koniec | koniec |
Warunek LL(1)
[edytuj | edytuj kod]Aby gramatyka była klasy LL(1) dla każdego symbolu nieterminalnego, produkcja powinna być rozpoznawana i wybierana już po podejrzeniu jednego symbolu terminalnego. Oznacza to, że dla każdej pary produkcji dla jednego symbolu nieterminalnego
- Z i nie da się wyprowadzić tego samego symbolu terminalnego
- Nie można jednocześnie wyprowadzić ciągu pustego z i
- Jeżeli z da się wyprowadzić ciąg pusty, wówczas z nie można wyprowadzić żadnego ciągu zaczynającego się od terminala należącego FOLLOW(A). Analogicznie w drugą stronę, gdy z da się wyprowadzić ciąg pusty.
Te warunki są równoważne
- i muszą być zbiorami rozłącznymi
- jeśli wtedy i muszą być zbiorami rozłącznymi i analogicznie gdy wtedy i muszą być zbiorami rozłącznymi
Transformacja do LL(1)
[edytuj | edytuj kod]Aby gramatyka dała się przekształcić do LL(1) musi być jednoznaczna, jednak nie każda jednoznaczna da się przekształcić. Mamy dwie transformacje, które dają szansę, że dostaniemy gramatykę LL(1):
- eliminacja lewostronnej rekursji
- lewostronna faktoryzacja
Eliminacja lewostronnej rekursji
[edytuj | edytuj kod]Mamy
- Wyrażenie → Wyrażenie '+' liczba
- Wyrażenie → liczba
Lewostronną rekurencję da się przepisać jako prawostronną:
- ...
- ...
przepisujemy na
- ...
- ...
Lewostronna faktoryzacja
[edytuj | edytuj kod]Mamy
- Expr number '+' Expr
- Expr number
Patrzymy ile pierwszych symboli (terminalnych i nieterminalnych) jest identycznych. Tu mamy tylko jeden symbol – number. Prawą stronę zamieniamy na nowy symbol: nazwijmy go PlusExpr
- Expr number PlusExpr
- PlusExpr '+' Expr
- PlusExpr
Gdy więcej niż dwie produkcje zaczynają się od tego samego:
- Expr number '+' Expr
- Expr number '-' Expr
- Expr number
Zamieniamy na
- Expr number PlusMinusExpr
- PlusMinusExpr '+' Expr
- PlusMinusExpr '-' Expr
- PlusMinusExpr
Gramatyka niejednoznaczna
[edytuj | edytuj kod]Czasami niejednoznaczna definicja gramatyki jest konieczna jak w przypadku IF..THEN..ELSE:
- Stat if Expr then Stat else Stat
- Stat if Expr then Stat
Po lewostronnej faktoryzacji:
- Stat if Expr then Stat ElseStat
- ElseStat else Stat
- ElseStat
Gramatyka jest niejednoznaczna dla ElseStat w przypadku napotkania symbolu else. Rozwiązujemy to przyjmując wybór zachłanny
- ElseStat else Stat
bo w przeciwnym razie gdybyśmy wybrali mógłaby zostać część else, która nie miała by wcześniejszego if.
Parser rekurencyjny
[edytuj | edytuj kod]Parsery LL można też łatwo pisać ręcznie, za pomocą zestawu wzajemnie wywołujących się funkcji.
znak następny_znak; /* zmienna globalna */
void parsujWyrażenie() {
if (następny_znak == liczba)
{
parsujIloczyn();
parsujOpcjonalnePlusWyrażenie();
} else {
błąd();
}
}
void parsujIloczyn() {
if (następny_znak == liczba)
{
następny_znak = odczytaj_znak();
parsujOpcjonalneRazyIloczyn();
} else {
błąd();
}
}
void parsujOpcjonalnePlusWyrażenie() {
if (następny_znak == '+')
{
następny_znak = odczytaj_znak();
parsujWyrażenie();
} else if (następny_znak == KONIEC_PLIKU) {
/* pusty ciąg znaków */
} else {
błąd();
}
}
void parsujOpcjonalneRazyIloczyn() {
if (następny_znak == '*')
{
następny_znak = odczytaj_znak();
parsujIloczyn();
} else if (następny_znak == '+' || następny_znak == KONIEC_PLIKU){
/* pusty ciąg znaków */
} else {
błąd();
}
}
void parsuj()
{
następny_znak = odczytaj_znak();
parsujWyrażenie();
if (następny_znak != KONIEC_PLIKU)
błąd();
}
Zobacz też
[edytuj | edytuj kod]Bibliografia
[edytuj | edytuj kod]- Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman: Kompilatory. Reguły, metody i narzędzia. Warszawa: WNT, 2002. ISBN 83-204-2656-1.