LR parser ( eng. LR parser ) este un parser pentru codurile sursă ale programelor scrise într-un limbaj de programare care citește fluxul de intrare de la stânga (stânga ) la dreapta și produce cea mai dreaptă ( dreapta ) producție a unei gramatici fără context. . Este folosit și termenul LR( k )-analizor , unde k exprimă numărul de caractere de previzualizare necitite din fluxul de intrare, pe baza cărora se iau deciziile în timpul analizei. De obicei , k este 1 și este adesea omis.
Sintaxa multor limbaje de programare poate fi definită printr-o gramatică care este LR(1) sau apropiată acesteia și, din acest motiv, analizatorii LR sunt adesea folosiți de către compilatori pentru a efectua parsarea codului sursă.
De obicei, se face referire la un parser în legătură cu numele limbii al cărei cod sursă îl analizează, de exemplu, „Parser C++” parsează codul sursă C++ .
Un parser LR poate fi generat dintr-o gramatică fără context de un program numit generator de parser sau poate fi scris manual de un programator. O gramatică fără context este clasificată ca LR( k ) dacă există un parser LR( k ) pentru ea, așa cum este determinat de generatorul de parser.
Se spune că analizatorul LR este o analiză de jos în sus , deoarece încearcă să deducă producția de nivel superior a gramaticii prin construirea acesteia din frunze .
Un limbaj determinist fără context este un limbaj pentru care există un fel de gramatică LR( k ). Fiecare gramatică LR( k ) poate fi convertită automat într-o gramatică LR( 1 ) pentru aceeași limbă, în timp ce gramaticile LR( 0 ) pentru unele limbi pot să nu existe. Limbile LR( 0 ) sunt propriul lor subset de limbi deterministe.
Un parser LR se bazează pe un algoritm condus de un tabel de analiză , o structură de date care conține sintaxa limbajului analizat. Deci, termenul LR parser se referă de fapt la o clasă de analizoare care pot analiza aproape orice limbaj de programare pentru care este furnizat un tabel de analizare. Tabelul de analiză este generat de generatorul de analiză.
Analiza LR poate fi generalizată ca o analiză arbitrară a unui limbaj fără context, fără pierderi de performanță, chiar și pentru gramaticile LR(k). Acest lucru se datorează faptului că majoritatea limbajelor de programare pot fi exprimate cu o gramatică LR( k ), unde k este o constantă mică (de obicei 1). Rețineți că analizarea gramaticilor non-LR(k) este cu un ordin de mărime mai lentă (cubică în loc de pătratică în ceea ce privește dimensiunea fluxului de intrare).
Analiza LR poate fi aplicată în mai multe limbi decât analiza LL și este, de asemenea, mai bună la raportarea erorilor, ceea ce înseamnă că detectează cât mai devreme posibil erorile de sintaxă în care intrarea nu se potrivește cu gramatica. În schimb, analizatorii LL(k) (sau mai rău, chiar și LL(*)) pot întârzia detectarea unei erori în altă ramură a gramaticii din cauza rollback-ului, făcând adesea dificilă localizarea unei erori în locurile prefixelor lungi comune.
Analizatorii LR sunt dificil de creat manual și sunt de obicei creați de un generator de analizatori sau un compilator de compilatori . În funcție de modul în care a fost creat tabelul de analiză, acești analizatori pot fi numiți analizoare simple LR (SLR), analizoare LR anticipate (LALR) sau analizoare LR canonice . Analizoarele LALR au o putere de recunoaștere semnificativ mai mare decât analizoarele SLR . În același timp, tabelele pentru analiza SLR au aceeași dimensiune ca și pentru analiza LALR, astfel încât analiza SLR nu mai este utilizată. Analizoarele LR canonice au o putere de recunoaștere puțin mai mare decât parsetoarele LALR, dar necesită mult mai multă memorie de tabel, așa că sunt rareori utilizate. .
| Limbi formale și gramatici formale | |
|---|---|
| Concepte generale | |
| Tip 0 | |
| Tipul 1 |
|
| Tip 2 | |
| Tip 3 | |
| analizare | |