Viz také LL(1)
LL parser ( LL parser ) je analyzátor shora dolů v informatice pro podmnožinu bezkontextových gramatik známých jako LL gramatiky . Ne všechny bezkontextové gramatiky jsou však gramatiky LL.
Písmena L ve výrazu "LL parser" znamenají, že vstupní řetězec je analyzován zleva doprava a zároveň je vytvořena jeho levá derivace .
Analyzátor LL se nazývá analyzátor LL(k), pokud tento analyzátor při analýze vstupního toku používá dopředný dotaz pro k tokenů (tokenů). Gramatika, která může být rozpoznána analyzátorem LL(k) bez zpětného sledování, se nazývá gramatika LL(k). Jazyk, který může být reprezentován jako LL(k)-gramatika, se nazývá LL(k)o-jazyk. Existují LL(k+n)-jazyky, které nejsou LL(k)-jazyky.
Následuje popis analyzátoru, který je založen na konstrukci tabulek; alternativou je rekurzivní sestupný analyzátor, který se obvykle píše ručně (i když existují výjimky, jako je generátor analyzátoru ANTLR pro gramatiky LL(*)).
Gramatiky LL(1) jsou velmi běžné, protože jejich odpovídající analyzátory LL sledují proud pouze o jeden znak dopředu, když se rozhodují, které gramatické pravidlo použít. Jazyky založené na gramatikách s velkými hodnotami k byly tradičně považovány za obtížně rozpoznatelné, ačkoli s rozšířeným používáním generátorů analyzátorů, které podporují gramatiky LL(k) s libovolným k, tato poznámka již není relevantní.
Analyzátor LL se nazývá analyzátor LL(*), pokud neexistuje žádné striktní omezení na k a analyzátor dokáže rozpoznat jazyk, pokud tokeny patří do nějaké pravidelné množiny (například pomocí deterministických konečných automatů ).
Mezi tzv. „evropskou školou“ jazykové konstrukce, která je založena na gramatikách LL, a „americkou školou“, která preferuje gramatiky LR, existují rozpory. Takové rozpory jsou způsobeny tradicemi výuky a podrobnostmi popisu různých metod a nástrojů v konkrétních učebnicích; ovlivněn také N. Wirthem z ETHZ , jehož výzkum popisuje různé metody optimalizace LL(1) resolverů a kompilátorů.
Analyzátor je navržen tak, aby vyřešil problém, zda řetězec patří do dané gramatiky, a pokud ano, vytvořil výstupní strom.
Parser se skládá z:
V řádcích tabulky jsou symboly obchodní abecedy a ve sloupcích symboly koncové abecedy.
Při zahájení analýzy již zásobník obsahuje dva znaky:
[S, $]Kde '$' je speciální terminál používaný k označení konce zásobníku a 'S' je axiom gramatiky. Analyzátor se pokusí pomocí gramatických pravidel nahradit axiom na zásobníku řetězcem znaků podobným řetězci na vstupní pásce a poté pásku kompletně přečíst a vyprázdnit zásobník.
Chcete-li vysvětlit, jak funguje analyzátor LL, zvažte následující gramatiku:
A pojďme analyzovat analýzu na příkladu řetězce:
(1+1)Tabulka analýzy pro tuto gramatiku vypadá takto:
| ( | ) | jeden | + | $ | |
| S | 2 | — | jeden | - | - |
| F | — | — | 3 | - | - |
K dispozici je také sloupec pro speciální terminál označený $, který se používá k označení konce vstupního proudu. Čísla (tučně) v buňkách označují čísla výše uvedených pravidel.
Analyzátor se podívá na první znak '(' ze vstupního proudu, v tu chvíli je znak 'S' na vrcholu zásobníku, na průsečíku těchto hodnot v tabulce analýzy je pravidlo z gramatiky V tomto příkladu se jedná o pravidlo číslo 2, které nařizuje nahradit v zásobníku znak 'S' v řetězci '(S + F)' Stav zásobníku po použití tohoto pravidla je:
[ (, S, +, F, ), $ ]V dalším kroku analyzátor přečte znak '(' ze vstupního toku. Protože je v horní části zásobníku podobný znak '(', je tento znak přečten z pásky a odstraněn ze zásobníku. Stav zásobník po použití tohoto pravidla je:
[S, +, F, ), $]Další na pásce je symbol '1' a v horní části zásobníku 'S', v průsečíku těchto symbolů v tabulce, je pravidlo 1. Po aplikaci tohoto pravidla podle tabulky analyzátor aplikuje pravidlo 3. Stav zásobníku po použití pravidel:
[ F, +, F, ), $ ] [ 1, +, F, ), $ ]Dále analyzátor přečte '1' a '+' ze vstupního toku, a protože odpovídají dalším dvěma prvkům v zásobníku, také je ze zásobníku odstraní. Výsledkem je, že zásobník vypadá takto:
[ F, ), $ ]V následujících třech krocích se znak 'F' na zásobníku změní na '1', poté budou znaky '1' a ')' přečteny z pásky a odstraněny ze zásobníku. V důsledku toho bude symbol '$' v horní části zásobníku a na pásce, podle definice to znamená úspěšnou analýzu řetězce.
V tomto případě analyzátor oznámí úspěch a vrátí seznam pravidel, která byla použita během procesu odvození:
[2, 1, 3, 3]Tato pravidla jsou skutečně nejlevější závěr:
S → (S + F) → (F + F) → (1 + F) → (1 + 1)Jak můžete vidět z příkladu, analyzátor dělá tři různé věci v závislosti na tom, zda je v horní části zásobníku neterminál, terminál nebo speciální znak $:
Tyto kroky se opakují, dokud nedojde k zastavení. Po zastavení nám přijde buď chybové hlášení, nebo hlášení, že řetěz byl úspěšně rozpoznán.
Aby bylo možné naplnit tabulku analýzy, je nutné určit, jaké gramatické pravidlo by měl syntaktický analyzátor zvolit, pokud je neterminál A na vrcholu zásobníku a znak a je ve vstupním proudu. Je snadné vidět, že takové pravidlo musí být ve tvaru A → w a že jazyk odpovídající w musí mít alespoň jeden řádek začínající a . Za tímto účelem definujeme První množinu w , zde zapsanou jako Fi(w) , jako množinu terminálů, které lze nalézt na začátku libovolného řádku v w , a ε, pokud prázdný řádek patří také w . Pokud máme gramatiku s pravidly A 1 → w 1 , …, A n → w n , lze vypočítat Fi(w i ) a Fi( Ai ) pro každé pravidlo takto:
Bohužel první sady nestačí k sestavení tabulky analýzy. Je to proto, že pravá strana w pravidla by mohla být nakonec přetypována na prázdný řetězec. Analyzátor tedy musí také použít pravidlo A → w , pokud je ε ve Fi(w) a ve vstupním proudu znak, který může následovat A . Proto je také nutné zkonstruovat Další množinu A (zde zapsanou jako Fo(A) ), která je definována jako množina terminálů a tak, že existuje řetězec znaků αAaβ , který lze získat z počátečního znaku. Výpočet následujících sad pro neterminály v gramatice lze provést následovně:
Nyní můžete přesně definovat, která pravidla budou obsažena v tabulce analýzy. Pokud T[A, a] označuje záznam v tabulce pro neterminál A a terminál a , pak
T[A,a] obsahuje pravidlo A → w právě tehdy, když:
Pokud tabulka neobsahuje více než jedno pravidlo v každé buňce, pak bude analyzátor schopen jednoznačně určit, které pravidlo musí být použito v každém kroku analýzy. V tomto případě se gramatika nazývá gramatika LL(1) .
Velikost tabulky analýzy má v nejhorším případě exponenciální složitost jako funkci k . Po vydání Compiler Construction Toolkit (PCCTS, nyní známý jako ANTLR ) kolem roku 1992 se však ukázalo, že velikost tabulky analýzy pro většinu programovacích jazyků nemá tendenci exponenciálně narůstat, protože není nejhorší. případ. Kromě toho bylo v určitých případech dokonce možné vytvořit LL( * )-analyzátory. Navzdory tomu však tradiční generátory syntaktických analyzátorů, jako je yacc / GNU bison , používají tabulky analýzy LALR( 1 ) k vytvoření omezeného analyzátoru LR .
Moderní generátory syntaktických analyzátorů pro gramatiky LL s multireléovou anticipací zahrnují:
| Formální jazyky a formální gramatiky | |
|---|---|
| Obecné pojmy | |
| Typ 0 | |
| Typ 1 |
|
| Typ 2 | |
| Typ 3 | |
| rozebrat | |