LALR (1) (LA z anglického lookahead - náhled) - algoritmus analýzy zdola nahoru .
Jedná se o rozšíření algoritmu SLR(1) . V některých případech to funguje, když sestavení tabulky analýzy SLR(1) pro danou gramatiku není možné kvůli konfliktům shift-reduce nebo reduction-reduce. Třída gramatik analyzovaných pomocí LALR(1) je tedy širší než třída gramatik SLR(1).
Algoritmus analýzy (provádění analyzátoru podle vstupního toku) je stejný pro LALR(1) i SLR(1) a je širší než pro LR(0) . Liší se pouze algoritmy pro konstrukci tabulky analýzy podle gramatiky v procesu generování analyzátoru.
Nechť existuje gramatika, která není analyzována kvůli konfliktům shift-reduce nebo fold-reduce pomocí algoritmu SLR(1).
V tomto případě je gramatika transformována takto:
Pro transformovanou gramatiku (je izomorfní s původní) je učiněn pokus sestavit tabulku analýzy SLR(1).
Akce je založena na skutečnosti, že Follow(A) je spojením všech Follow(Ak). V každém konkrétním stavu nová gramatika již nemá A, ale jeden z Ak, to znamená, že sada Follow pro tento stav má méně prvků než pro A v původní gramatice.
To má za následek méně pokusů pro LALR(1) vložit "obsazení" do buňky v tabulce analýzy, což snižuje riziko konfliktů s přetypováním, někdy se jich úplně zbaví a vytvoří gramatiku, kterou SLR neanalyzuje. (1) analyzován po transformacích.
Množina Follow(Ak) se v pravidlech nazývá předběžná množina pro A a k-té setkání, odtud název algoritmu.
Po transformaci gramatiky LALR(1) mohou zůstat konflikty Shift-reduce a fold-reduce. To znamená, že pro tuto gramatiku je zapotřebí úplný analyzátor LR(1), který je mnohem složitější (algoritmy LR(0)/SLR(1)/LALR(1) neuchovávají absolutně žádné informace o již analyzované části vstupní tok, zatímco jako plný LR(1) to dělá, a proto obtížnější), ale dokáže analyzovat jakoukoli bezkontextovou jednoznačnou gramatiku.
Podle některých informací (upřesněte!) lze všechny gramatiky LL(1) převést do formy analyzované pomocí LALR(1).
Používá se v generátoru analyzátoru yacc a jeho derivátech, jako je GNU bison.
Většina skutečně používaných programovacích jazyků má gramatiku LALR(1), to znamená, že tento typ parserů stačí k analýze většiny skutečně používaných jazyků.
Kompilátor GNU C používá k sestavení analyzátoru yacc. Možná (přítomnost řetězců gramatika.y a yacc v těle spustitelného modulu) dělá Microsoft totéž při sestavování svého kompilátoru C .