LALR (1) (LA angol lookahead - előnézet) - alulról felfelé irányuló elemzési algoritmus .
Ez az SLR(1) algoritmus kiterjesztése . Egyes esetekben működik, amikor egy SLR(1) elemző tábla felépítése egy adott nyelvtanhoz nem lehetséges a shift-reduce vagy a reduction-reduction konfliktusok miatt. Így az LALR(1) által elemzett nyelvtanok osztálya szélesebb, mint az SLR(1) nyelvtanok osztálya.
Az elemzési algoritmus (az analizátor végrehajtása a bemeneti adatfolyam szerint) ugyanaz LALR(1) és SLR(1) esetén, és szélesebb, mint az LR(0) esetében . Csak azok az algoritmusok különböznek egymástól, amelyek az elemző táblát a nyelvtan alapján állítják össze az analizátor előállítása során.
Legyen olyan nyelvtan, amelyet az SLR(1) algoritmussal eltolás-kicsinyítés vagy hajtás-kicsinyítés ütközések miatt nem elemeznek.
Ebben az esetben a nyelvtan a következőképpen alakul:
A transzformált nyelvtanhoz (ez izomorf az eredetivel) egy SLR(1) elemző tábla létrehozására teszünk kísérletet.
Az akció azon a tényen alapul, hogy a Follow(A) az összes Follow(Ak) egyesülése. Az egyes állapotokban az új nyelvtanban már nem A, hanem az Ak egyike van, vagyis az ehhez az állapothoz tartozó Follow halmaznak kevesebb eleme van, mint az eredeti nyelvtanban A-nak.
Ez azt eredményezi, hogy az LALR(1) kevesebb kísérletet tesz arra, hogy "cast"-ot helyezzen el az elemző tábla cellájában, ami csökkenti a castokkal való ütközések kockázatát, néha teljesen megszabadul tőlük, és olyan nyelvtant készít, amelyet az SLR nem értelmez. (1) transzformációk után értelmezve.
A Follow(Ak) halmazt az A és a k-edik találkozásra vonatkozó előretekintési halmaznak nevezzük a szabályokban, innen ered az algoritmus neve is.
Eltolás-kicsinyítés és hajtás-kicsinyítés ütközések maradhatnak a LALR(1) nyelvtani átalakítás után. Ez azt jelenti, hogy ehhez a nyelvtanhoz egy teljes LR(1) elemző szükséges, ami sokkal összetettebb (az LR(0)/SLR(1)/LALR(1) algoritmusok nem őriznek meg semmilyen információt a már elemzett részről. a bemeneti adatfolyam, bár a teljes LR(1)-hez hasonlóan, és ezért nehezebb), de bármilyen kontextusmentes, egyértelmű nyelvtant képes elemezni.
Egyes információk szerint (add meg!) minden LL(1) nyelvtan átalakítható LALR(1) által elemzett formává.
A yacc elemző generátorban és származékaiban, például a GNU bisonban használják.
A ténylegesen használt programozási nyelvek többsége rendelkezik LALR(1)-grammatikával, vagyis ez a fajta értelmező elegendő a valóban használt nyelvek többségének elemzéséhez.
A GNU C fordító yacc-ot használ az értelmező felépítéséhez. Talán (a grammar.y és a yacc karakterlánc jelenléte a végrehajtható modul törzsében) a Microsoft ugyanezt teszi a C fordító elkészítésekor .