SLR(1)

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 1 decembrie 2014; verificarea necesită 1 editare .

SLR(1) este un algoritm de parsare de jos în sus.

Este o extensie a algoritmului LR(0) . În unele cazuri, funcționează atunci când construirea unui tabel de analiză LR(0) pentru o anumită gramatică nu este posibilă din cauza conflictelor shift-cast sau cast-cast. Astfel, clasa de gramatici analizate conform SLR(1) (cr. „SLR(1)-gramatici”) este mai largă decât clasa LR(0)-gramatici.

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

Descriere

Pentru fiecare non-terminal A din gramatică, este generat un set de terminale First(A), definite după cum urmează:

dacă gramatica are o regulă cu un A pe partea stângă și o parte dreaptă care începe cu un terminal, atunci acel terminal este în primul (A)
dacă gramatica are o regulă cu un A pe partea stângă și o parte dreaptă care începe cu un non-terminal (notat B), atunci First (B) este strict inclus în First (A)
nu sunt incluse alte terminale în First(A)

Aceleași seturi sunt folosite pentru a construi analizorul LL(1).

În plus, pe baza setului First(A), se generează seturile Follow(A), definite după cum urmează

dacă gramatica are o regulă în care un A nu apare în ultima poziție și este urmat de un terminal, atunci terminalul este inclus în Follow(A).
dacă gramatica are o regulă în care A apare nu în ultima poziție și este urmată de un non-terminal (notat cu B), atunci First(B) este inclus strict în Follow(A)
dacă gramatica are o regulă în care A apare în ultima poziție, atunci Follow(C) este inclus strict în Follow(A), unde C este partea stângă a regulii.
niciun alt terminal nu este inclus în Follow(A)

(este posibil sa se generalizeze aceste conditii pentru cazul prezentei regulilor B -> nul)

Apoi, tabelul de analiză este generat, ca și pentru LR(0), cu o diferență când sunt introduse acțiunile de cast. Distribuția pentru starea S și simbolul de intrare C este tabelată numai dacă există un șir în S care se potrivește cu toată partea dreaptă a regulii, iar nonterminalul N din partea stângă a regulii satisface condiția „C este în Urmărire( N)".

Acest lucru are ca rezultat mai puține încercări pentru SLR(1) de a pune o „transformare” în celula tabelului de analiză, ceea ce reduce riscul de conflicte cu turnări, uneori scăpând complet de ele și face o gramatică care nu este analizată de LR(0). ) analizabil.

Aplicație practică

Aproape că nu are (cu excepția educațională) din cauza clasei înguste de gramatici care sunt analizate. O aplicație practică este LALR(1), care este o generalizare a SLR(1).

Expresiile aritmetice cu operatori unari și binari și paranteze sunt analizate folosind SLR(1)

Vezi și