Parser LR

În informatică , un analizor LR este un analizor de jos în sus pentru gramaticile fără context , utilizat foarte frecvent în compilatoarele de limbaje de programare (și alte instrumente asociate). Un analizor LR își citește intrarea începând de la stânga ( L eft) spre dreapta, producând o derivare dreaptă ( R ightmost Derivation). Uneori, acest parser este denumit și "Parser LR ( k ) unde k se referă la numărul de simboluri citite (dar nu" consumate ") utilizate pentru a lua decizii de analiză. De obicei, k are valoarea 1 și este adesea omis. Un context gratuit gramatica se numește LR ( k ) dacă există un analizor LR ( k ) potrivit pentru aceasta.

În utilizarea obișnuită, atunci când faceți referire la un analizor LR înseamnă că vorbiți despre un anumit analizor capabil să recunoască un anumit limbaj într-o gramatică fără context. Cu toate acestea, nu este neobișnuit să ne referim la un analizor LR ca program care, având în vedere un tabel "ad hoc", este capabil să producă un număr mare de LR distincte.

Analiza LR are mai multe beneficii:

Mai multe limbaje de programare pot fi analizate folosind variante ale analizorului LR. Excepții notabile sunt C ++ și Perl .
Analizorul LR poate fi implementat extrem de eficient.
Dintre toate tipurile de analizori care își scanează intrarea de la stânga la dreapta, analizorul LR este cel care poate identifica cel mai rapid erorile sintactice (adică atunci când intrarea nu este conformă cu gramatica).

Crearea manuală a unui analizor LR este destul de dificilă; sunt de obicei create folosind generatoare de parser . În funcție de modul în care este generat tabelul de analiză, acești analizatori pot fi și analizori SLR sau LALR . Cu aceste tipuri de analizori aveți de-a face cu o mare varietate de gramatici augmentate; analizorul LALR, de exemplu, este capabil să recunoască un număr mai mare de gramatici decât un SLR. Celebrul Yacc produce parsere de tip LALR.

Arhitectura unui analizor LR

Analizorul constă din:

Un buffer de intrare, care vă permite să citiți următorul simbol din intrarea standard;
O stivă , care vă permite să memorați ce simboluri au fost citite;
Un tabel, împărțit în Table de acțiune (care vă permite să determinați ce acțiune să luați) și GoTo Table (care determină în ce stare nouă să vă deplasați sau ce regulă gramaticală să adoptați);

Încercând să explic cum funcționează cu un exemplu; ia în considerare următoarea gramatică:

(1) E → E * B

(2) E → E + B

(3) E → B

(4) B → 0

(5) B → 1

Tabelul de acțiuni și Mergeți

Cele două tabele de analiză LR (0) pentru această gramatică sunt:

	acțiune					mergi la
fost	*	+	0	1	$	ȘI	B.
0			s1	s2		3	4
1	r4	r4	r4	r4	r4
2	r5	r5	r5	r5	r5
3	s5	s6			acc
4	r3	r3	r3	r3	r3
5			s1	s2			7
6			s1	s2			8
7	r1	r1	r1	r1	r1
8	r2	r2	r2	r2	r2

În Tabelul de acțiuni , conținutul celulelor este determinat de starea analizorului și de un simbol terminal (inclusiv simbolul terminalului special $ care indică sfârșitul intrării) și poate conține trei tipuri de acțiuni:

shift , scris în forma 's n ' indică faptul că un simbol trebuie mutat și că următoarea stare este n
reduce , scris în forma „r m ” indică faptul că trebuie făcută o reducere prin aplicarea regulii m
accept , scris în forma „acc” și indică faptul că toate simbolurile au fost citite și șirul este conform gramaticii definite

În tabelul GoTo, pe de altă parte, valorile celulelor sunt determinate de starea analizorului și de simbolurile non-terminale; conținutul determină care va fi următoarea stare a analizorului dacă este recunoscut un non-terminal.

Algoritmul de analiză

Algoritmul de analiză LR funcționează după cum urmează:

Conținutul stivei este setat la [ 0 ]. Starea actuală ar trebui să fie întotdeauna starea superioară a stivei.
Având în vedere starea curentă și terminalul curent din fluxul de intrare, se efectuează acțiunea prezentă în tabelul de acțiuni. Există patru cazuri posibile:
- o schimbare s n :
  - terminalul curent este eliminat din fluxul de intrare
  - starea n este inserată în stivă și devine starea curentă,
- o reducere r m :
  - numărul m este scris în fluxul de ieșire,
  - pentru fiecare simbol din dreapta regulii m o stare este eliminată din teanc e
  - definit cu $S.$ ${\ displaystyle S}$ $S.$ următoarea stare din partea de sus a stivei și NT caracterul non-terminal din partea stângă a numărului de regulă m ; spune-te atunci $S_{1}$ ${\ displaystyle S_ {1}}$ $S_1$ starea care se află în tabelul Goto la starea $S.$ ${\ displaystyle S}$ $S.$ (index rând) și NT non-terminal (index coloană). În acest moment se introduce starea $S_{1}$ ${\ displaystyle S_ {1}}$ $S_1$ deasupra grămezii.
- un accept: șirul este acceptat
- nicio acțiune: este raportată o eroare de sintaxă
Pasul anterior se repetă până când șirul este acceptat sau se raportează o eroare de sintaxă

Algoritmul poate fi mai bine exprimat cu un șir de exemplu: 1 + 1. Tabelul de mai jos ilustrează fiecare etapă realizată de proces, starea de referință este elementul din partea de sus a stivei (adică cel mai îndepărtat la dreapta) și acțiunea care trebuie întreprinsă va fi cea determinată de tabelul de acțiuni definit mai sus. De asemenea, rețineți că simbolul $ este inserat la sfârșitul șirului pentru a semnaliza sfârșitul intrării.

Stat	Flux de intrare	Flux de ieșire	Grămadă	Acțiunea următoare
0	1 + 1 $		[0]	Shift 2
2	+ 1 $		[0,2]	Reduceți 5
4	+ 1 $	5	[0,4]	Reduceți 3
3	+ 1 $	5.3	[0,3]	Shift 6
6	1 $	5.3	[0,3,6]	Shift 2
2	$	5.3	[0,3,6,2]	Reduceți 5
8	$	5.3.5	[0,3,6,8]	Reduceți 2
3	$	5.3.5.2	[0 3]	Accept

Când începe analiza, acesta va fi la starea inițială 0 și cu următoarea stivă:

[ 0 ]

Primul terminal pe care analizorul îl recunoaște este „1” și, conform tabelului de acțiuni, puteți trece la starea 2 cu Stack, care este după cum urmează:

[ 0 '1' 2 ]

Capul stivei este partea cea mai dreaptă (pentru comoditate afișăm și simbolul, terminalul sau non-terminalul, de exemplu „1” sau B, care a „provocat” trecerea la următoarea stare, chiar dacă acest simbol nu aparțin stivei ).

În starea 2, tabelul de acțiuni spune că pentru orice terminal se află în intrare ar trebui să facem o reducere cu regula gramaticală 5. Dacă tabelul a fost creat corect, aceasta înseamnă că analizorul a recunoscut corect partea dreaptă a regulii 5, pe care această este tocmai cazul nostru. Puteți scrie „5” în fluxul de ieșire, efectuați „pop” -ul stării pe stivă și apoi o „apăsare” pe teancul stării indicate de tabelul de trecere cu 0 și B, adică 4. Rezultatul stiva va fi:

[ 0 B 4 ]

Cu toate acestea, starea 4 a tabelului de acțiuni indică faptul că ar trebui să facem o reducere cu regula nr. 3. Scriem apoi 3 în fluxul de ieșire, facem un „pop” suplimentar pe stivă și găsim noua stare în tabelul de trecere, indicat cu 0 și E sau 3. În consecință:

[ 0 ȘI 3 ]

Următorul terminal pe care analizorul îl recunoaște este „+” și urmând tabelul de acțiuni, va trebui să treceți la starea 6:

[ 0 E 3 '+' 6 ]

Se poate vedea cum stiva construită până acum poate fi văzută ca povestea unui automat cu stare finită care tocmai a citit un E non-terminal urmat de un terminal '+'. Tabelul de tranziție al acestei automatizări este definit de acțiunile „shift” ale tabelului de acțiuni și acțiunile de mutare din tabelul gogo.

Următorul terminal este acum „1”, ceea ce înseamnă că trebuie efectuat un „shift and go” la starea 2:

[ 0 E 3 '+' 6 '1' 2 ]

După cum s-a făcut, simbolul „1” este redus la B cu stiva formată după cum urmează:

[ 0 E 3 '+' 6 B 8 ]

Se poate vedea din nou cum stiva corespunde acum unei liste de stări ale unui automat de stare finită care a citit un E non-terminal, urmat de un '+' și un non-terminal B. În starea 8 vom efectua întotdeauna un reducere cu regula 2. Observați că cele 3 stări ale stivei corespund acum celor 3 simboluri din partea dreaptă a regulii 2.

[ 0 ȘI 3 ]

În cele din urmă, se citește simbolul „$” care, urmând regulile tabelului de acțiuni (a cărui stare curentă este a treia), analizorul acceptă șirul de intrare. Numerele de regulă care au fost scrise în fluxurile de ieșire vor fi [5, 3, 5, 2], care este efectiv o derivare a mâinii drepte a șirului invers „1 + 1”.

Construirea unui tabel de analiză LR (0)

Articol

Construcția acestor tabele de analiză se bazează pe notația articolelor LR (0) care sunt reguli gramaticale cu o perioadă specială adăugată în poziții precise pe partea dreaptă. De exemplu, regula E → E + B are următoarele patru obiecte corespunzătoare:

E → • E + B

E → E • + B

E → E + • B

E → E + B •

Regulile sub forma A → ε au un singur element A → •. Aceste reguli vor fi utilizate pentru a indica starea analizatorului. Elementul E → E • + B, de exemplu, indică faptul că analizorul a recunoscut un șir corespunzător lui E în fluxul de intrare și acum așteaptă să citească un „+” urmat de un alt șir, corespunzător lui B.

Seturi de articole

De obicei, nu este posibil să se caracterizeze starea analizorului cu un singur articol, deoarece nu este posibil să se știe în prealabil ce reguli vor fi utilizate pentru reducere. De exemplu, dacă există deja o regulă de formă E → E * B, atunci elementele E → E • + B și E → E • * B vor fi aplicate ambele după ce șirul corespunzător lui E a fost citit. În consecință, va trebui să caracterizăm stările analizorului printr-un set de itemi, în cazul nostru setul va fi format din {E → E • + B, E → E • * B}.

Închiderea seturilor de articole

Un element cu un punct în fața unui non-terminal, cum ar fi E → E + • B, indică faptul că parserul așteaptă să primească un non-terminal B. Pentru a se asigura că setul de obiecte conține toate regulile posibile pe care analizorul le are s-ar putea găsi în timpul executării lucrării sale, trebuie să includă toți termenii care descriu modul în care B în sine trebuie analizat. Aceasta înseamnă că, dacă există o regulă precum B → 1 și B → 0, atunci setul de itemi trebuie să includă și itemi B → • 1 și B → • 0. În general, acest lucru poate fi formulat după cum urmează:

Dacă există un element în forma A → v • Bw într-un set de itemi și în gramatică există o regulă în forma B → w ', atunci elementul B → • w' trebuie să fie și în setul de itemi.

Fiecare set de articole poate fi extins pentru a îndeplini următoarea regulă: Pur și simplu continuați să adăugați articolele corespunzătoare până când au fost luate în considerare toate non-terminalele precedate de puncte. Extensia minimă se numește închiderea unui set de articole și se scrie clos ( I ) unde I este un set de articole. Acest set de articole închise va fi luat ca stări de analiză, deși numai cele care sunt de fapt accesibile din starea inițială vor fi incluse în tabel.

Gramatică mărită

Înainte de a începe să se determine tranzițiile între diferite stări, gramatica este întotdeauna mărită cu următoarea regulă suplimentară:

(0) S → E

unde S este un nou simbol de pornire și E cel vechi. Analizatorul va folosi această regulă pentru a reduce exact momentul în care a acceptat șirul de intrare.

Să luăm ca exemplu gramatica văzută mai sus:

(0) S → E

(1) E → E * B

(2) E → E + B

(3) E → B

(4) B → 0

(5) B → 1

Prin această gramatică mărită se va determina setul de itemi și tranzițiile dintre ele.

Găsiți seturile de articole accesibile și tranzițiile dintre ele

Primul pas în construcția tabelelor este determinarea tranzițiilor dintre seturile de articole închise . Aceste tranziții vor fi determinate ca și cum am fi luat în considerare un automat cu stare finită care poate citi atât terminal cât și non-terminal. Începutul stării acestui automat este întotdeauna închiderea primului element al regulii adăugate, adică S → • E:

Set de articole 0

S → • E

+ E → • E * B

+ E → • E + B

+ E → • B

+ B → • 0

+ B → • 1

„+” Din partea de sus a elementului indică faptul că articolele care au fost adăugate la închidere . Elementele originale fără un „+” în față se numesc nuclee ale setului de articole.

Pornind de la starea inițială (S0), toate stările la care se poate ajunge din această stare sunt acum determinate. Tranzițiile posibile pentru un set de elemente pot fi găsite uitându-se la simbolurile (atât terminale, cât și nu) prezente în dreapta punctului; în cazul setului de articole 0 acestea sunt terminalele „0” și „1” și non-terminale E și B. Pentru a găsi setul de articole către care conduce un simbol „x” din starea curentă, urmați această procedură:

Luați setul S al tuturor elementelor din setul curent, unde există un punct în fața unui simbol x .
Pentru fiecare articol din S , punctul din dreapta lui x se mișcă.
Setul de articole rezultat se închide.

Pentru terminalul '0' rezultă:

Set de articole 1

B → 0 •

și pentru terminalul '1' în:

Set de articole 2

B → 1 •

și pentru E non-terminal în:

Set de articole 3

S → E •

E → E • * B

E → E • + B

și pentru B non-terminal în:

Set de articole 4

E → B •

Rețineți că în toate închiderea nu se adaugă elemente noi. Aceasta continuă procesul până când nu sunt găsite elemente noi în set. Pentru setul de elemente 1, 2 și 4 nu va exista nicio tranziție până când punctul nu se află în fața oricărui simbol. Pentru setul de articole 3 rețineți că punctul se află în fața terminalelor „*” și „+”. Pentru „*” tranziția merge la:

Set de articole 5

E → E * • B

+ B → • 0

+ B → • 1

iar pentru „+” tranziția merge la:

Set de articole 6

E → E + • B

+ B → • 0

+ B → • 1

Pentru elementele din setul 5 trebuie luate în considerare terminalele „0” și „1” și non-terminalul B. Pentru terminale se remarcă faptul că închiderea rezultată a setului de elemente este aceeași cu cele deja găsite anterior: respectiv și 2. Pentru non-terminal B, tranziția va fi:

Set de articole 7

E → E * B •

Pentru setul de elemente 6 trebuie să luăm în considerare și terminalele „0” și „1” și non-terminalul B. Ca și mai înainte, setul de elemente rezultat este egal cu setul 1 și 2. Pentru non-terminalul B tranziția se face în:

Set de articole 8

E → E + B •

Am ajuns la ultimul set de articole care nu mai au niciun simbol după punct și, prin urmare, nu sunt adăugate elemente noi și lucrarea este finalizată. Tabelul de tranziție pentru automat va fi acum după cum urmează:

Set de articole	*	+	0	1	ȘI	B.
0			1	2	3	4
1
2
3	5	6
4
5			1	2		7
6			1	2		8
7
8

Construcția tabelei de acțiune și a merge

Din acest tabel și din setul de elemente tocmai obținute, tabelele pot fi construite după cum urmează:

Coloanele non-terminale sunt copiate în tabelul Goto
Coloanele terminalelor sunt copiate în tabelul de acțiuni ca acțiunile de deplasare
O coloană suplimentară pentru simbolul $ (sfârșitul intrării) este adăugată în tabelul de acțiuni care conține acc pentru fiecare set de elemente care conțin S → E •.
Dacă un set de itemi i conține un articol de forma A → w • și A → w este regula m cu m > 0 atunci rândul pentru starea i din tabelul de acțiuni este completat complet cu acțiunea care indică reducerea r m .

Versiuni mai puternice ale analizei LR

Rețineți că numai pasul 4 din procedurile descrise mai sus produce o acțiune de reducere și, prin urmare, toate acțiunile de reducere trebuie să ocupe un întreg rând al tabelului. Acest lucru se datorează faptului că un analizor LR (0) nu se uită la următorul simbol pentru a decide ce reducere să efectueze. O gramatică care trebuie să caute mai departe pentru a rezolva dezambiguitățile reducerilor necesită ca tabelul să indice acțiuni diferite în funcție de jetoanele de intrare ulterioare.

Îmbunătățirile procedurii de construire a unei tabele LR (0) (cum ar fi parserele SLR și LALR) pot crea acțiuni de reducere care nu ocupă întregul rând. Ca rezultat, ei sunt capabili să analizeze mai multe gramatici decât analizatorii LR (0).

Conflicte în tabelele construite

Cu toate acestea, se poate întâmpla ca atunci când o acțiune de reducere este adăugată la tabelul de acțiuni, celula relativă este deja ocupată de o acțiune. Când se întâmplă acest lucru, înseamnă pur și simplu că nu este o gramatică LR (0). Dacă conținutul precedent al celulei este o schimbare, se numește conflict de reducere a schimbării ; dacă este o acțiune de reducere diferită, vorbim despre un conflict de reducere-reducere .

Un exemplu de gramatică non-LR (0) cu conflict de schimbare-schimbare este:

(1) E → 1 E

(2) E → 1

Un set de articole găsite este:

Set de articole 1

E → 1 • E

E → 1 •

+ E → • 1 E

+ E → • 1

Există un conflict de reducere a schimbării în acest set de elemente, deoarece în celula tabelului de acțiuni pentru acest set de elemente și terminalul '1' există atât o acțiune de schimbare la starea 1, cât și o acțiune de reducere cu regula 2.

Un alt exemplu de gramatică non-LR (0) cu conflict de reducere-reducere este:

(1) E → A 1

(2) E → B 2

(3) A → 1

(4) B → 1

În acest caz, obținem următorul set de articole

Set de articole 1

A → 1 •

B → 1 •

Există un conflict de reducere-reducere în acest set de elemente, deoarece celulele tabelului de acțiuni pentru acest set de articole vor fi atât pentru regula 3, cât și pentru regula 4.

Ambele exemple de mai sus pot fi rezolvate lăsând analizorul să folosească următorul set (vezi analizorul LL ) al unui non-terminal A pentru a decide dacă se folosește o regulă A pentru o reducere; regula A → w va fi utilizată pentru o reducere dacă următorul simbol din fluxul de intrare se află în următorul set de A. Această soluție se numește analizor LR simplu .

Câteva exemple cu LR (0)

 E-> E + T / T
   T-> T * F / F
   F-> id

S-> AA
   A-> aA / b

Bibliografie

Compilatoare: Principii, tehnici și instrumente , Aho, Sethi, Ullman, Addison-Wesley , 1986. ISBN 0-201-10088-6
Internele unui analizor LALR (1) generat de GNU Bison , pe cs.uic.edu . Adus la 22 decembrie 2006 (arhivat din original la 26 noiembrie 2006) .

Elemente conexe

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 de analiză LR. Util pentru cei care doresc să practice pe această temă

Portal IT : accesați intrările Wikipedia care se ocupă cu IT