LL gramatika je jakákoliv gramatika, z níž se dá udělat rozkladová tabulka pro LL parser. LL(k) parser se kouká při parsování věty na následujících k tokenů, aby věděl, co dál. Pokud takový parser může být použit pro nějakou gramatiku, aniž by se musel použít backtracking, jedná se o LL(k) gramatiku.

Aby se ze vstupní gramatiky dala udělat LL(1) gramatika – eliminace levé rekurze, levá faktorizace (eliminace překrývajících se množin FIRST, tj. "rozsekání" pravidel se stejným začátkem pravé strany na několik menších, už jednoznačných)

př: STAT => if EXP then STAT | if EXP then STAT else à STAT => if EXP then STAT ElsePart;  ElsePart => else STAT | e)

Nesmí být přítomna levá rekurze.

Nesmí dojít k first-follow (u neterminálu, který se přepisuje na "e") kolizi, first-first kolizi

Třídy jazyků LL(k)

L = Left to right -> vstupní text (soubor) čteme zleva doprava

L = Left parse -> vytváříme levý rozklad

K = při rozhodování mezi pravidly potřebujeme vidět nejvýše k znaků z nepřečtené části vstupu

Tzn.: LL(k) gramatika provádí deterministický rozbor čtením textu z Leva doprava, s použitím Levé derivace a prohlédnutí k dalších symbolů vstupního textu.

gramatika je typu LL(k), jestliže ji lze použít pro deterministickou syntaktickou analýzu metodou shora dolů (tj. vytváříme levý rozklad) a při rozhodování mezi pravidly potřebujeme znát nejvýše k symbolů ze vstupu.

jazyk je typu LL(k), pokud je generován některou LL(k) gramatikou

lze určit správné pravidlo aniž bychom předem potřebovali vidět nějaký znak na vstupu

každý neterminál musí mít jen jednu jedinou pravou stranu (jen jedno přepisovací pravidlo) 

neumožňuje rekurzi

prostě jen určují, jestli sekvence patří do jazyka nebo ne, žádné rozhodování není potřeba.

LL(0) gramatiky jsou nevhodné pro popis programovacích jazyků, protože zde není možná rekurze a pro každý neterminál existuje právě jedno pravidlo (důsledek faktu, že gramatika se nemůže rozhodnout podle následujícího vstupního symbolu), tudíž mohou generovat jen jazyk s jediným slovem.

Příklad:
G == id name lastname
id == [0-9]+
name == string
lastname == string
string == <unicode>+

pro danou gramatiku G se vystačí při rozhodování o výběru pravidla pro expanzi s informací o dopředu prohlíženém řetězci délky 1 -> proto LL(1) je gramatika silná

jednoduchá LL (1) gramatika je taková bezkontextová gramatika jestliže platí:

pravá strana každého pravidla začíná terminálním symbolem např. A -> aB

pokud mají 2 pravidla stejnou levou stranu, pak pravé strany začínají různými terminálními symboly např. A -> aB, A->bB

to znamená, že v každém políčku rozkladové tabulky bude právě jeden element

sdola (bottom-up) (vyžadují LR gramatiku, takže se netýkají této otázky)

Při hledání derivace začínáme počátečním symbolem a snažíme se dostat k hledanému slovu

Přesně určuje volbu pravidel při analýze a umožňuje jednoznačný postup při odvození

Gramatika, která je jednoznačná a lze ji takto analyzovat: LL gramatika

Využívá se zásobníkový automat

LL(k) označení gramatiky pro LL analýzu, číslo k určuje, kolik následujících symbolů na vstupu je nutné znát pro analýzu slova

LL(1): nejpoužívanější gramatika, stačí znát jeden následující symbol

Jde vlastně o variantu rekurzivního sestupu bez backtrackingu

LL(0): umožňuje jen jazyky s konečným počtem slov

LL gramatiky s k>1 lze převést na LL gramatiky s k = 1

Existují přesné popisy, jak jednotlivá pravidla nahrazovat (přidávají se neterminály a pravidla se upravují, aby při analýze stačilo znát jeden další symbol)

LL parsery používají parsing shora dolů, zpracovávají vstup zleva doprava a konstruují nejlevější derivaci. Proto se také nazývá L (left-to-right) L(leftmost derivation). Občas se setkáváme s označením LL(k), kde k značí počet tokenů, které potřebujeme znát při rozhodování o průběhu další analýzy bez toho, aby bylo třeba používat backtracking (= prediktivní parser). Také se v této souvislosti používá pojem look-ahead. Prakticky do nedávné doby se tyto gramatiky příliš nepoužívaly, ovšem na počátku 90. let minulého století došlo ke změně přístupu.

Budeme se zabývat algoritmem syntaktické analýzy, který vytváří derivační strom analyzovaného řetězce směrem shora dolů. Základní princip syntaktické analýzy můžeme v tomto případě formulovat takto:

Je dána bezkontextová gramatika G= (N,T,P,S) a řetězec w = a1 a2 … an, který je větou z L(G). Pak existuje levá derivace

S = γ1 ⇒ γ2 ⇒ … ⇒ γn = w.

Vzhledem k tomu, že derivace je levá, má každá větná forma γi tvar:

γi = a1 a2 … aj Ai βi,

kde a1, a2 …, aj jsou terminální symboly, Ai je neterminální symbol, βi je řetězec terminálních a neterminálních symbolů. Přitom řetězec a1a2 … aj je předponou věty w, j ≥ 0.

Předpokládejme, že A → α1 | α2 | … | αn jsou všechna pravidla v P s neterminálním symbolem A na levé straně. Pak základní problém syntaktické analýzy metodou shora dolů spočívá v nalezení toho pravidla A → αk, jehož aplikací dostaneme z větné formy γi větnou formu γi + 1.

Pro výběr pravidla A → αk, je možno použít:

informaci o dosavadním průběhu (historii) analýzy,

informaci o dosud nepřečtené části vstupního řetězce (dopředu prohlíženém řetězci omezené délky).

Pokud tyto informace vždy stačí k jednoznačnému výběru pravidla A → αk, pak se gramatika G nazývá LL gramatika. Název je odvozen od toho, že při čtení vstupního řetězce zleva je vytvářen levý rozklad. Při syntaktické analýze LL gramatik jsou do zásobníku ukládány řetězce, které odpovídají levým větným formám nebo takovým jejich příponám, které vzniknou odejmutím předpony tvořené řetězcem terminálních symbolů.

Expanze – neterminální symbol na vrcholu zásobníku je nahrazen pravou stranou vybraného pravidla

Srovnání – terminální symbol na vrcholu zásobníku se ze zásobníku vyloučí, jestliže je shodný se symbolem, který byl ze vstupního řetězce přečten.

Přijetí – vstupní řetězec je přečten a zásobník je prázdný.

Chyba – ve všech ostatních případech.

Pokud pro danou gramatiku G vystačíme při rozhodování o výběru pravidla pro expanzi s informací o dopředu prohlíženém řetězci délky nejvýše k, pak se gramatika G nazývá silná LL(k) gramatika. Při analýze silných LL(k) gramatik jsou do zásobníku ukládány přímo symboly gramatiky a syntaktický analyzátor je řízen rozkladovou tabulkou.

Konstrukce jak top-down, tak bottom-up parserů používá dvě funkce, FIRST a FOLLOW, spojené s gramatikou G. Při parsování shora dolů nám FIRST a FOLLOW říkají, které přepisovací pravidlo uplatnit v závislosti na dalším vstupním symbolu. Během zotavení z chyby při panic módu mohou být množiny tokenů získané pomocí  FOLLOW použity jako synchronizační tokeny.

Popis LL gramatik a LL analyzátoru

Řešení kolizí: [link]
