LR(0) — Algoritm de jos în sus pentru analizarea gramaticilor fără context , unul dintre tipurile de LR .
LR(0) este rar folosit în practică datorită clasei înguste de gramatici analizate, dar este baza pentru algoritmii mai puternici SLR(1) și LALR(1) , cel din urmă având aplicații practice bogate.
Toți cei trei algoritmi menționați au aceeași fază de execuție pentru fluxul de intrare, diferind doar în faza de construire a tabelului de analiză pentru gramatică.
Această fază de execuție este foarte rapidă (timp liniar), capabilă să parseze toate limbajele LALR(1), adică aproape toate limbajele de programare utilizate. În plus, este capabil să genereze erori de sintaxă inteligibile de forma „un caracter neanalizat așa și așa într-o astfel de poziție” și, dacă există doar 1 operație de schimbare în întreaga linie a tabelului de analizare, de forma „ era de așteptat un astfel de personaj”.
Datorită complexității ridicate a construirii unui tabel de analiză pentru algoritmii LR(0), SLR(1) și LALR(1), se folosește de obicei un generator de parseri precum yacc , dacă trebuie să scrieți rapid un parser manual, utilizați metoda coborârii recursive sau LL(1 )
Să introducem conceptul de „lanț”. Aceasta este partea dreaptă a unei anumite reguli din gramatică și poziția în ea, de la 0 la N (lungimea părții drepte), poziția N înseamnă - dincolo de sfârșitul părții drepte a regulii. Notați lanțul R(K, L), unde K este numărul regulii și L este poziția din partea dreaptă.
Lanțul, unde L = lungimea laturii drepte a regulii K, se numește complet.
Să introducem conceptul de „simbol R(K, L)”, adică simbolul indicat de șir. Acesta este al L-lea caracter din partea dreaptă a regulii K. Șirul completat nu indică niciun caracter.
Să introducem conceptul de „un set de lanțuri inițiale pentru un nonterminal”. Pentru non-terminalul A, setul de lanțuri inițiale include:
Să introducem conceptul de „stat” ca un set de lanțuri.
Să introducem conceptul de „stare inițială” ca un set de lanțuri inițiale ale simbolului E, începutul gramaticii.
Să introducem conceptul de „schift” ca o tranziție de la stare la stare sub acțiunea unui simbol (non-terminal sau terminal). Noua stare este construită din starea veche atunci când treceți de-a lungul simbolului A, după cum urmează:
Se spune că o schimbare este imposibilă dacă rezultatul este un set gol.
Pentru gramatică, se construiește o stare inițială.
În plus, pentru toate terminalele și non-terminale, sunt construite toate stările posibile (seturile de lanțuri) obținute prin trecerea de la stările cunoscute anterior. Acest lucru elimină stările duplicate.
În continuare, se construiește un tabel de analiză, pe verticală - numere de stare (0 - stare inițială), pe orizontală - simboluri (terminale, non-terminale și simbolul „sfârșitul fluxului”).
Schimbările sunt introduse în tabel după cum urmează: dacă este posibilă o schimbare pentru simbolul C și starea S, atunci valoarea „deplasare la starea cursei S” (obținută ca urmare a deplasării) este introdusă în celulă ( S, C).
În continuare, începutul gramaticii S → E este înlocuit, iar pentru noul început S, se introduce în celulă valoarea „finalizarea cu succes a parsării” (S, sfârșitul fluxului).
În plus, acțiunile de reducere (reducere) sunt introduse în tabel, numai pentru terminale, după cum urmează: dacă există un lanț finalizat în starea S, atunci valoarea „reducere conform regulii R, partea dreaptă a lungimii lui N. caractere” este introdus în toate celulele (S, terminal), obținem un C non-terminal din partea stângă a regulii."
O încercare de a insera o distribuție într-o celulă de tabel deja ocupată (de exemplu, în cazul a două lanțuri complete în stare) se numește conflict shift-cast sau conflict cast-cast. În acest caz, construirea unui parser LR(0) nu este posibilă, dar poate fi posibilă construirea folosind algoritmul SLR(1) sau LALR(1) ceva mai complex, care diferă doar prin modul în care sunt introduse turnările în masa.
Se folosește stiva de analizor, unde sunt situate fluxurile de numere de stare, de intrare (terminale și sfârșitul fluxului) și de ieșire (numerele regulilor).
0 este împins mai întâi pe stivă.
În plus, până când se primește o eroare de sintaxă sau finalizarea cu succes a analizei: