LR parser ( eng. LR parser ) är en parser för källkoderna för program skrivna i något programmeringsspråk som läser ingångsströmmen från vänster (vänster ) till höger och producerar produktionen längst till höger ( höger ) av en kontextfri grammatik . Termen LR( k )-analysator används också , där k uttrycker antalet olästa förhandstecken i inmatningsströmmen, på basis av vilka beslut fattas under analysen. Vanligtvis är k 1 och utelämnas ofta.
Syntaxen för många programmeringsspråk kan definieras av en grammatik som är LR(1) eller nära den, och av denna anledning används LR-parsers ofta av kompilatorer för att utföra källkodsanalys.
Vanligtvis hänvisas till en parser i relation till namnet på språket vars källkod den analyserar, till exempel "C++ parser" analyserar C++ källkod .
En LR-parser kan genereras från en kontextfri grammatik av ett program som kallas en parsergenerator , eller så kan den skrivas för hand av en programmerare. En kontextfri grammatik klassificeras som LR( k ) om det finns en LR( k )-parser för den, som bestäms av parsergeneratorn.
LR-parsern sägs vara nedifrån och upp-parsning eftersom den försöker sluta sig till produktionen av grammatiken på toppnivån genom att bygga den av löv .
Ett deterministiskt sammanhangsfritt språk är ett språk för vilket det finns någon form av LR( k )-grammatik. Varje LR( k ) grammatik kan automatiskt konverteras till en LR( 1 ) grammatik för samma språk, medan LR( 0 ) grammatik för vissa språk kanske inte existerar. LR( 0 )-språk är deras egen delmängd av deterministiska.
En LR-parser baseras på en algoritm som drivs av en analystabell , en datastruktur som innehåller syntaxen för det analyserade språket. Så termen LR-parser hänvisar faktiskt till en klass av parsare som kan analysera nästan vilket programmeringsspråk som helst för vilket en analystabell tillhandahålls. Analystabellen genereras av parsergeneratorn.
LR-tolkning kan generaliseras som godtycklig analys av ett sammanhangsfritt språk utan prestandaförlust, även för LR(k)-grammatik. Detta beror på att de flesta programmeringsspråk kan uttryckas med en LR( k ) grammatik, där k är en liten konstant (vanligtvis 1). Observera att att tolka icke-LR(k) grammatik är en storleksordning långsammare (kubisk istället för kvadratisk när det gäller storlek på ingångsström).
LR-parsning kan appliceras på fler språk än LL-parsing och är också bättre på felrapportering, vilket innebär att den upptäcker syntaxfel där inmatningen inte matchar grammatiken så tidigt som möjligt. Däremot kan LL(k) (eller ännu värre, till och med LL(*))-tolkare fördröja upptäckten av ett fel till en annan gren av grammatiken på grund av återställning, vilket ofta gör det svårt att lokalisera ett fel på platser med vanliga långa prefix.
LR-parsers är svåra att skapa för hand och skapas vanligtvis av en parsergenerator eller kompilatorkompilator . Beroende på hur tolktabellen skapades kan dessa tolkar kallas enkla LR-parsers (SLR), lookahead LR-parsers (LALR) eller kanoniska LR-parsers . LALR-parsrar har betydligt större igenkänningskraft än SLR-parsrar . Samtidigt har tabeller för SLR-analys samma storlek som för LALR-analys, så SLR-analys används inte längre. Kanoniska LR-parsrar har något mer igenkänningskraft än LALR-parsrar, men kräver mycket mer tabellminne, så de används sällan. .
| Formella språk och formella grammatiker | |
|---|---|
| Allmänna begrepp | |
| Typ 0 | |
| Typ 1 |
|
| Typ 2 | |
| Typ 3 |
|
| analysera | |