LALR (1) (LA från engelska lookahead - förhandsvisning) - nedifrån- och -upp- parsningsalgoritm .
Det är en förlängning av SLR(1) -algoritmen . I vissa fall fungerar det när det inte är möjligt att bygga en SLR(1) parsetabell för en given grammatik på grund av konflikter mellan skift-minska eller reducera-minska. Således är klassen av grammatiker som analyseras av LALR(1) bredare än klassen för SLR(1)-grammatik.
Parsningsalgoritmen (utförande av analysatorn enligt ingångsströmmen) är densamma för både LALR(1) och SLR(1) och är bredare än för LR(0) . Endast algoritmerna för att konstruera analystabellen genom grammatik i processen att generera analysatorn skiljer sig åt.
Låt det finnas en grammatik som inte analyseras på grund av skift-minska eller vik-minska konflikter med hjälp av SLR(1)-algoritmen.
I det här fallet omvandlas grammatiken enligt följande:
För den transformerade grammatiken (den är isomorf till den ursprungliga) görs ett försök att bygga en SLR(1) parsetabell.
Handlingen är baserad på det faktum att Follow(A) är föreningen av alla Follow(Ak). I varje specifikt tillstånd har den nya grammatiken inte längre A, utan en av Ak, det vill säga Follow-uppsättningen för detta tillstånd har färre element än för A i den ursprungliga grammatiken.
Detta resulterar i färre försök för LALR(1) att lägga en "cast" i en cell i analystabellen, vilket minskar risken för konflikter med casts, ibland att bli av med dem helt och hållet, och gör en grammatik som inte analyseras av SLR (1) analyserad efter transformationer.
Uppsättningen Follow(Ak) kallas lookahead-uppsättningen för A och k:te möte i reglerna, därav namnet på algoritmen.
Skift-reducera och fold-reduce-konflikter kan finnas kvar efter LALR(1) grammatiktransformationen. Detta betyder att en fullständig LR(1)-parser behövs för denna grammatik, som är mycket mer komplex (LR(0)/SLR(1)/LALR(1)-algoritmerna behåller absolut ingen information om den redan analyserade delen av indataströmmen, medan som full LR(1) gör, och därför svårare), men kan analysera vilken kontextfri entydig grammatik som helst.
Enligt viss information (specificera!) kan alla LL(1) -grammatiker konverteras till en form som tolkas av LALR(1).
Används i parsergeneratorn yacc och dess derivator, såsom GNU bison.
Majoriteten av faktiskt använda programmeringsspråk har LALR(1)-grammatik, det vill säga den här typen av tolkar räcker för att tolka de flesta av de verkligen använda språken.
GNU C-kompilatorn använder yacc för att bygga parsern. Kanske (närvaron av strängen grammar.y och yacc i kroppen av den körbara modulen), Microsoft gör samma sak för att bygga sin C-kompilator .