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:

I dla wyrażenia 5 + 3 * 8 * 2 + 7 * 2 parsing przebiega następująco:

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 ${\displaystyle A\Rightarrow \alpha |\beta {:}}$

1. Z ${\displaystyle \alpha }$ i ${\displaystyle \beta }$ nie da się wyprowadzić tego samego symbolu terminalnego
2. Nie można jednocześnie wyprowadzić ciągu pustego z ${\displaystyle \alpha }$ i ${\displaystyle \beta }$
3. Jeżeli z ${\displaystyle \beta }$ da się wyprowadzić ciąg pusty, wówczas z ${\displaystyle \alpha }$ nie można wyprowadzić żadnego ciągu zaczynającego się od terminala należącego FOLLOW(A). Analogicznie w drugą stronę, gdy z ${\displaystyle \alpha }$ da się wyprowadzić ciąg pusty.

Te warunki są równoważne

1. ${\displaystyle FIRST(\alpha )}$ i ${\displaystyle FIRST(\beta )}$ muszą być zbiorami rozłącznymi
2. jeśli ${\displaystyle \epsilon \in FIRST(\beta )}$ wtedy ${\displaystyle FIRST(\alpha )}$ i ${\displaystyle FOLLOW(A)}$ muszą być zbiorami rozłącznymi i analogicznie gdy ${\displaystyle \epsilon \in FIRST(\alpha )}$ wtedy ${\displaystyle FIRST(\beta )}$ i ${\displaystyle FOLLOW(A)}$ 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):

1. eliminacja lewostronnej rekursji
2. lewostronna faktoryzacja

Eliminacja lewostronnej rekursji[edytuj | edytuj kod]

Mamy

• Wyrażenie → Wyrażenie '+' liczba
• Wyrażenie → liczba

Lewostronną rekurencję da się przepisać jako prawostronną:

• ${\displaystyle N\to N\alpha _{1}}$
• ...
• ${\displaystyle N\to N\alpha _{m}}$
• ${\displaystyle N\to \beta _{1}}$
• ...
• ${\displaystyle N\to \beta _{n}}$

przepisujemy na

• ${\displaystyle N\to \beta _{1}N'}$
• ...
• ${\displaystyle N\to \beta _{n}N'}$
• ${\displaystyle N'\to \alpha _{1}N'}$
• ...
• ${\displaystyle N'\to \alpha _{m}N'}$
• ${\displaystyle N'\to \epsilon }$

Lewostronna faktoryzacja[edytuj | edytuj kod]

Mamy

• Expr ${\displaystyle \to }$ number '+' Expr
• Expr ${\displaystyle \to }$ 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 ${\displaystyle \to }$ number PlusExpr
• PlusExpr ${\displaystyle \to }$ '+' Expr
• PlusExpr ${\displaystyle \to \epsilon }$

Gdy więcej niż dwie produkcje zaczynają się od tego samego:

• Expr ${\displaystyle \to }$ number '+' Expr
• Expr ${\displaystyle \to }$ number '-' Expr
• Expr ${\displaystyle \to }$ number

Zamieniamy na

• Expr ${\displaystyle \to }$ number PlusMinusExpr
• PlusMinusExpr ${\displaystyle \to }$ '+' Expr
• PlusMinusExpr ${\displaystyle \to }$ '-' Expr
• PlusMinusExpr ${\displaystyle \to \epsilon }$

Gramatyka niejednoznaczna[edytuj | edytuj kod]

Czasami niejednoznaczna definicja gramatyki jest konieczna jak w przypadku IF..THEN..ELSE:

• Stat ${\displaystyle \to }$ if Expr then Stat else Stat
• Stat ${\displaystyle \to }$ if Expr then Stat

Po lewostronnej faktoryzacji:

• Stat ${\displaystyle \to }$ if Expr then Stat ElseStat
• ElseStat ${\displaystyle \to }$ else Stat
• ElseStat ${\displaystyle \to \epsilon }$

Gramatyka jest niejednoznaczna dla ElseStat w przypadku napotkania symbolu else. Rozwiązujemy to przyjmując wybór zachłanny

• ElseStat ${\displaystyle \to }$ else Stat

bo w przeciwnym razie gdybyśmy wybrali ${\displaystyle \epsilon }$ 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]

• Parser LR
• Zbiory First i Follow

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.brak strony w książce