SLR(1)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 1 december 2014; verifiering kräver 1 redigering .

SLR(1) är en nedifrån och upp-parsningsalgoritm.

Det är en förlängning av LR(0) -algoritmen . I vissa fall fungerar det när det inte är möjligt att bygga en LR(0)-tolkningstabell för en given grammatik på grund av skift-cast eller cast-cast-konflikter. Således är klassen av grammatiker analyserade enligt SLR(1) (cr. "SLR(1)-grammars") bredare än klassen av LR(0)-grammars.

Själva analysalgoritmen (exekverar analysatorn enligt ingångsströmmen) är densamma för både SLR(1) och LR(0) — och, mer allmänt, för LALR(1) . Endast algoritmerna för att konstruera analystabellen genom grammatik i processen att generera analysatorn skiljer sig åt.

Beskrivning

För varje icke-terminal A i grammatiken genereras en uppsättning terminaler First(A), definierade enligt följande:

om grammatiken har en regel med ett A på vänster sida och en höger sida som börjar med en terminal, då är den terminalen i First(A)
om grammatiken har en regel med ett A på vänster sida och en höger sida som börjar med en icke-terminal (betecknad B), så är First(B) strikt inkluderad i First(A)
inga andra terminaler ingår i First(A)

Samma uppsättningar används för att konstruera LL(1)-analysatorn.

Vidare, baserat på First(A)-uppsättningarna, genereras Follow(A)-uppsättningarna, definierade enligt följande

om grammatiken har en regel där ett A inte förekommer i den sista positionen och följs av en terminal, så ingår terminalen i Follow(A).
om grammatiken har en regel där A inte förekommer i den sista positionen, och den följs av en icke-terminal (betecknad med B), är First(B) strikt inkluderad i Follow(A)
om grammatiken har en regel där A förekommer i den sista positionen, så är Följ(C) strikt inkluderad i Följ(A), där C är den vänstra sidan av regeln.
inga andra terminaler ingår i Follow(A)

(det är möjligt att generalisera dessa villkor för fallet med förekomsten av regler B -> null)

Därefter genereras analystabellen, som för LR(0), med en skillnad när cast-åtgärderna matas in. Casten för tillståndet S och ingångssymbolen C tabelleras endast om det finns en sträng i S som matchar hela högra sidan av regeln, och det icke-terminala N från vänster sida av regeln uppfyller villkoret "C är i Follow( N)".

Detta resulterar i färre försök för SLR(1) att sätta en "cast" i analystabellscellen, 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 tolkas av LR(0) ) parserbar.

Praktisk tillämpning

Det har den nästan inte (förutom för utbildning) på grund av den smala klassen av grammatik som analyseras. En praktisk tillämpning är LALR(1), som är en generalisering av SLR(1).

Aritmetiska uttryck med unära och binära operatorer och parenteser tolkas med hjälp av SLR(1)

Se även