LALR(1)

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 23 martie 2019; verificările necesită 2 modificări .

LALR (1) (LA din engleză lookahead - previzualizare) - algoritm de analiză de jos în sus .

Este o extensie a algoritmului SLR(1) . În unele cazuri, funcționează atunci când construirea unui tabel de analiză SLR(1) pentru o anumită gramatică nu este posibilă din cauza conflictelor de schimbare-reducere sau reducere-reducere. Astfel, clasa de gramatici analizată de LALR(1) este mai largă decât clasa de gramatici SLR(1).

Algoritmul de analiză (execuția analizorului în funcție de fluxul de intrare) este același atât pentru LALR(1) cât și pentru SLR(1) și este mai larg decât pentru LR(0) . Diferă doar algoritmii pentru construirea tabelului de analizare prin gramatică în procesul de generare a analizorului.

Descriere

Să existe o gramatică care nu este analizată din cauza conflictelor shift-reduce sau fold-reduce folosind algoritmul SLR(1).

În acest caz, gramatica se transformă după cum urmează:

se caută neterminalul pe care s-a originat circumvoluția care a provocat conflictul. Să-i spunem A.
sunt introduse noi non-terminale A1, A2, …, An, câte unul pentru fiecare apariție a lui A în partea dreaptă a regulilor.
peste tot în părțile corecte ale regulilor, A este înlocuit cu Ak corespunzătoare.
setul de reguli cu A în stânga se repetă de n ori pentru fiecare Ak.
regulile cu un A pe partea stângă sunt eliminate, eliminând astfel A din gramatică în întregime.

Pentru gramatica transformată (este izomorfă cu cea originală), se încearcă construirea unui tabel de analiză SLR(1).

Acțiunea se bazează pe faptul că Follow(A) este uniunea tuturor Follow(Ak). În fiecare stare specifică, noua gramatică nu mai are A, ci una din Ak, adică setul Follow pentru această stare are mai puține elemente decât pentru A în gramatica originală.

Acest lucru are ca rezultat mai puține încercări pentru LALR(1) de a pune o „transformare” într-o celulă din tabelul de analiză, ceea ce reduce riscul de conflicte cu distribuții, uneori scăpând complet de ele și face o gramatică care nu este analizată de SLR. (1) analizat după transformări.

Setul Follow(Ak) se numește setul de anticipare pentru întâlnirea A și k-a din reguli, de unde și numele algoritmului.

LALR(1) și LR(1) complet

Conflictele Shift-reduce și fold-reduce pot rămâne după transformarea gramaticală LALR(1). Aceasta înseamnă că este necesar un parser LR(1) complet pentru această gramatică, care este mult mai complexă (algoritmii LR(0)/SLR(1)/LALR(1) nu rețin absolut nicio informație despre partea deja analizată a fluxul de intrare, în timp ce face LR(1) complet și, prin urmare, mai dificil), dar poate analiza orice gramatică fără ambiguitate fără context.

Conform unor informații (specificați!), toate gramaticile LL(1) pot fi convertite într-o formă analizată de LALR(1).

Aplicație practică

Folosit în generatorul de analizoare yacc și derivatele sale, cum ar fi GNU Bison.

Majoritatea limbajelor de programare utilizate efectiv au LALR(1)-gramatici, adică acest tip de parsere este suficient pentru a analiza majoritatea limbajelor utilizate cu adevărat.

Compilatorul GNU C folosește yacc pentru a construi parserul. Poate (prezența șirului grammar.y și yacc în corpul modulului executabil), Microsoft face același lucru pentru a-și construi compilatorul C.