Parser SLR

În informatică , un analizor SLR este un analizor LR care recunoaște tabelele de analiză generate ca pentru un analizor LR (0), dar care efectuează o reducere cu regula gramatică A → w numai dacă următorul simbol de intrare este în setul următor . Acest analizor poate evita unele conflicte de reducere a schimbării și reducere-reducere și, prin urmare, poate funcționa cu un număr mai mare de gramatici. Cu toate acestea, nu poate analiza toate gramaticile fără context, așa cum o poate face un analizor LR (1). O gramatică care este recunoscută corect de un analizor SLR se numește gramatică SLR .

Exemplu

Următoarea gramatică poate fi recunoscută de un analizor SLR, dar nu de un analizor LR (0):

(1) E → 1 E

(2) E → 1

Construirea tabelului de acțiune și a tabelului Goto ca pentru un analizor LR (0) ar da următorul set de articole și tabele:

Set de articole 0

S → • E

+ E → • 1 E

+ E → • 1

Set de articole 1

E → 1 • E

E → 1 •

+ E → • 1 E

+ E → • 1

Set de articole 2

S → E •

Set de articole 3

E → 1 E •

Acțiunile și trecerea la tabele:

	acțiune		mergi la
fost	1	$	ȘI
0	s1		2
1	s1 / r2	r2	3
2		acc
3	r1	r1

După cum puteți vedea, există un conflict de reducere a schimbării pentru starea 1 și terminalul '1'. Cu toate acestea, următorul set de E este {$}, deci acțiunile de reducere r1 și r2 se aplică doar coloanei $. Rezultatul este următorul tabel fără conflicte:

	acțiune		mergi la
fost	1	$	ȘI
0	s1		2
1	s1	r2	3
2		acc
3		r1

Algoritm

 1 Inițializați bateria cu S
2 Citiți simbolul din intrare
3 În timp ce (adevărat), faceți:
3.1 dacă Acțiune (sus (stivă), intrare) = S
         NS <- Mergeți (sus (stivă), intrare)
         împingeți NS
         Citiți următorul simbol
3.2 altfel dacă Acțiune (sus (stivă), intrare) = Rk
         ieșire k
         face pop | RHS | de producție k din stivă
         NS <- Mergeți (sus (stivă), LHS_k)
         împingeți NS
3.3 altfel dacă Acțiune (sus (stivă), intrare) = A
         ieșire corectă, returnare
    altceva
         ieșire nevalidă, returnare

linkuri externe

Simulator de analiză Acest simulator este conceput pentru a ajuta elevul să înțeleagă în toată simplitatea diferiții pași pentru construirea tabelelor SLR de analiză. Util pentru cei care doresc să practice pe această temă