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ą 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) 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) 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 Mamy Wyrażenie → Wyrażenie '+' liczba Wyrażenie → liczba Lewostronną rekurencję da się przepisać jako prawostronną:
...
...
przepisujemy na
...
...
Lewostronna faktoryzacja 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 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łaby wcześniejszego if.
Parser rekurencyjny 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ż Parser LR Zbiory First i Follow
Bibliografia
Kategoria:Parsery