Parser LL toparser czytający tekst od lewej do prawej i produkujący lewostronne wyprowadzeniemetodą zstępującą. Popularne rodzaje parserów LL to parsery sterowanetablicą irekurencyjne.

Parsery klasyLL(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 szczyciestosu 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 odk 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 prostagramatyka 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 przypadkuk 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:

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 ϵ\in FIRST(\beta )}$ wtedy${\displaystyle FIRST(\alpha )}$ i${\displaystyle FOLLOW(A)}$ muszą być zbiorami rozłącznymi i analogicznie gdy${\displaystyle ϵ\in FIRST(\alpha )}$ wtedy${\displaystyle FIRST(\beta )}$ i${\displaystyle FOLLOW(A)}$ muszą być zbiorami rozłącznymi

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

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}^{\prime }}$
• ...
• ${\displaystyle N\to {\beta }_n{N}^{\prime }}$
• ${\displaystyle N^{\prime }\to {\alpha }_1{N}^{\prime }}$
• ...
• ${\displaystyle N^{\prime }\to {\alpha }_m{N}^{\prime }}$
• ${\displaystyle N^{\prime }\to ϵ}$

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 ϵ}$

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 ϵ}$

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 lewostronnejfaktoryzacji:

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

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 ϵ}$ mógłaby zostać część else, która nie miała by wcześniejszego if.

Parsery LL można też łatwo pisać ręcznie, za pomocą zestawu wzajemnie wywołujących się funkcji.

znaknastępny_znak;/* zmienna globalna */voidparsujWyrażenie(){if(następny_znak==liczba){parsujIloczyn();parsujOpcjonalnePlusWyrażenie();}else{błąd();}}voidparsujIloczyn(){if(następny_znak==liczba){następny_znak=odczytaj_znak();parsujOpcjonalneRazyIloczyn();}else{błąd();}}voidparsujOpcjonalnePlusWyrażenie(){if(następny_znak=='+'){następny_znak=odczytaj_znak();parsujWyrażenie();}elseif(następny_znak==KONIEC_PLIKU){/* pusty ciąg znaków */}else{błąd();}}voidparsujOpcjonalneRazyIloczyn(){if(następny_znak=='*'){następny_znak=odczytaj_znak();parsujIloczyn();}elseif(następny_znak=='+'||następny_znak==KONIEC_PLIKU){/* pusty ciąg znaków */}else{błąd();}}voidparsuj(){następny_znak=odczytaj_znak();parsujWyrażenie();if(następny_znak!=KONIEC_PLIKU)błąd();}

• Parser LR
• Zbiory First i Follow

• Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman: Kompilatory. Reguły, metody i narzędzia. Warszawa: WNT, 2002.ISBN 83-204-2656-1. Brak numerów stron w książce

• Parsery

• Szablon cytowania książki – brak numeru strony