Curs9

S.Motogna- LFTC

Analizor sintactic SLR

• SLR=SimpleLR

• Observație:LR(0)– multe conflicte – dacă seține cont depredicție atunci se

elimină conflictul

=>1. Colecție canonică destări LR(0)– predicție delungime 02. Tabel și analiza secvenței – predicție delungime 1

S.Motogna- LFTC

Analiză sintactică LR(k):LR(0),SLR,LR(1),LALR

• definirea elementului deanaliză• construirea mulțimii destări• construirea tabelului deanaliză• Analiza secvenței debaza tranzițiilor între configurații

S.Motogna- LFTC

LR(0)LR(0)

Construcția tabelului SLRObsevații:1. Predicția =următorul simbol dinșirul deintrare =>FOLLOW

- vezi LL(1)2. Structura – LR(k):• Linii - stări• partedeacțiune +partedegoto

acțiune – câte ocoloană pentru fiecare predicție∈𝞢goto – câte ocoloană pentru fiecare simbol X∈N∪𝞢

S.Motogna- LFTC

Obs.(tabel LR(0)):• Dacă într-oanumită stares acțiunea este deacceptare,goto(s,X)=∅,∀X∈ N∪ Σ.• Dacă într-oanumită stares acțiunea este dereducere,atunci goto(s,X)=∅,∀X∈ N∪ Σ.

Tabel SLR

Acțiune GOTO

a1 … an B1 … Bm

s0s1…sk

S.Motogna- LFTC

a1,…,an∈𝞢B1,...,Bm∈Ns0,…,sk - stări

Reguli tabel SLR

1. dacă[A→α.β]∈ si șigoto(si,a)=sj atunciacțiune(si,a)=shift sj2. dacă[A→β.]∈ si șiA≠Sʹatunciacțiune(si,u)=reducel,undel-

numărulproducțieiA→β,∀u∈ FOLLOW(A)3. dacă[Sʹ→S.]∈ si atunciacțiune(si,$)=acc4. dacăgoto(si,X)=sj atuncigoto(si,X)=sj ,∀X∈N5. toatecelelaltevalori=eroare

S.Motogna- LFTC

Observații

1. Similaritate cuLR(0)

2. Ogramatică este detipSLRdacă tabelul SLRNU conține conflicte

S.Motogna- LFTC

Analiza secvenței debaza tranzițiilor între configurații

• INPUT:• Gramatica limbajului G’=(NU{S’},𝚺,PU{S’->S},S’)• Tabel deanaliză SLR• Secvența deanalizat w=a1…an

• OUTPUT:Dacă (w∈L(G)) atunci șir deproducții

altfel locația erorii

S.Motogna- LFTC

Configurații SLR≈LR(0)

(𝛼,𝛽,𝜋)

Unde:• 𝛼 =stiva delucru• 𝛽 =stiva deintrare• 𝜋 =banda deieșire (rezultat)

S.Motogna- LFTC

Configurația finală:($sacc,$, 𝜋)

Configurația inițială:($s0,w$,𝜀)

Tranziții1. Deplasaredacă actiune(sm,ai)=shift sj atunci

($s0x1 ...xmsm,ai ...an$, 𝜋)⊢ ($s0x1 ...xmsmaisj,ai+1 ...an$, 𝜋)2. Reduceredacă actiune(sm,ai)=reducet AND(t)A→xm−p+1 ...xm ANDgoto(sm−p,A)=sjatunci

($s0 ...xmsm,ai ...an$, 𝜋)⊢ ($s0 ...xm−psm−pAsj,ai ...an$,t 𝜋)3. Acceptaredacă actiune(sm,$)=acceptatunci ($sm,$,𝜋)=acc3. Eroare - altfel

S.Motogna- LFTC

head(𝛽)=predicția

Analizor sintactic LR(1)

1. definirea elementului deanaliză2. construirea mulțimii destări3. construirea tabelului deanaliză4. analiza secvenței debaza tranzițiilor între configurații

S.Motogna- LFTC

[A→𝜶.𝜷,u]

nucleu predicție

Construirea mulțimii destări LR(1)

• Alg ColCan_LR1• Funcția goto1• Alg Closure1

S.Motogna- LFTC

Algoritm ColCan_LR(1)Algoritmul 3.12 Col stariLR1

INPUT: G’- gramatica ımbogatitaOUTPUT: C - colectia canonica de stariC1

:= ;;s0

:= closure({[S0 ! .S, $]})C1

:= C1

[ {s0

};repeat

for 8s 2 C1

dofor 8X 2 N [ ß do

T:=goto(s, X);if T 6= ; and T /2 C

1

thenC1

= C1

[ Tend if

end forend for

until C1

nu se mai modifica

Exemplul 3.7. Fie gramatica G = ({S0, S,A}, {a, b}, P, S0) unde produc-tiile sunt:

S0 ! SS ! AAA ! aAA ! b

pentru care dorim sa calculam colectia de stari. Vom avea nevoie devaloarea functiei FIRST pentru neterminalul A. Se observa usor caFIRST (A) = {a, b}.

s0

= closure({[S0 ! .S, $]}) = {[S0 ! .S, $], [S ! .AA, $], [A ! .aA, a],[A ! .aA, b], [A ! .b, a], [A ! .b, b]}

Sa analizam constructia starii s0

, pentru a ıntelege mecanismul de cal-cul al predictiilor din starile LR(1). Initializam colectia cu [S0 ! .S, $].Avem un element de analiza cu punct ınaintea neterminalului S, deci vomadauga elementul [S ! .AA, u], unde u se calculeaza ca fiind FIRST ($)(dupa S ın partea dreapta a productiei S0 ! S nu mai avem nimic, iarpredictia ın respectivul element de analiza este $).

Luam acum ın considerare elementul de analiza [S ! .AA, $]. Avempunct ınaintea lui A, deci vom adauga elemente de analiza corespunzatoare

81

S.Motogna- LFTC

Funcția goto1

goto1:P(ℰ0)× (N∪ Σ)→P(ℰ0)undeℰ0=mulțimeadeelementeLR(0)

goto1(s,X)=closure({[A→αX.β,u]|[A→α.Xβ,u]∈ s})

S.Motogna- LFTC

Algoritm Closure

S.Motogna- LFTC

• [A→α.Bβ,u]valabil pentru prefixul viabil γα=>

• [B→.δ,ceva]∈P=>

=>[B→.δ,b]valabil pentru prefixul viabil γα,∀b∊ FIRST(𝛽u)

Analizoarele sintactice LR(k) lucreaza cu gramatica ımbogatita: G =(N [ {S0}, ß, P [ {S0 ! S}, S0), S0 /2 N , pentru a evita ca simbolul destart S sa apara ın partea dreapta a unei productii. Se observa ca celedoua gramatici sunt echivalente (genereaza acelasi limbaj) si ın aceastanoua gramatica S0 nu apare ın partea dreapta a nici unei productii.

Definitia 3.4. [Ser87] O gramatica G = (N, ß, P, S) este de tip LR(k)pentru k ∏ 0 daca din:

1. S0 §)dr ÆAw )dr ÆØw;

2. S0 §)dr ∞Bx)dr ÆØy;

3. FIRSTk(w) = FIRSTk(y)

rezulta ca Æ = Ø, A = B, x = y.

Pornind de la definitia elementului de analiza sa consideram un cazparticular [A ! ÆØ., u]. Semnificatia acestui element de analiza este caÆØ a fost deja detectat ın arbore si astfel s-ar putea reduce subarborelecu frontul ÆØ la neterminalul A. Astfel, am determinat cand (ın ce starea automatului push-down) se poate face reducerea si care este mansa.Deci, cand se ajunge ıntr-o stare ce contine element de analiza de forma[A ! ÆØ., u] actiunea va fi de reducere, altfel va fi deplasare. Deoarecestarea automatului decide actiunea, ea va fi de asemenea depusa ın stivade lucru. Configuratia stivei va fi:

$sinitX1

s1

. . . Xmsm

unde Xm este simbolul din varful stivei, iar sm este starea curenta a au-tomatului. Cele doua elemente ımpreuna cu predictia de lungime k vordetermina comportamentul analizorului, caracterizat prin:

• actiunea care se va efectua si

• tranzitia ın alta stare.

De aceea tabelele de analiza LR(k) au doua componente: de actiune side deplasare, numita ”goto“.

Care sunt si cum se determina aceste stari? Pentru a raspunde saconsideram elementul de analiza [A ! Æ.BØ, u] care, conform definitiei,implica:

S§)dr ∞Aw )dr ∞ÆBØw si

u = FIRSTk(w) valabil pentru prefixul viabil ∞Æ.Daca ın gramatica exista o productie B ! ± atunci elementul de analiza

[B ! .±, u] are, de asemenea, u valid pentru prefixul viabil ∞Æ:

67

Analizoarele sintactice LR(k) lucreaza cu gramatica ımbogatita: G =(N [ {S0}, ß, P [ {S0 ! S}, S0), S0 /2 N , pentru a evita ca simbolul destart S sa apara ın partea dreapta a unei productii. Se observa ca celedoua gramatici sunt echivalente (genereaza acelasi limbaj) si ın aceastanoua gramatica S0 nu apare ın partea dreapta a nici unei productii.

Definitia 3.4. [Ser87] O gramatica G = (N, ß, P, S) este de tip LR(k)pentru k ∏ 0 daca din:

1. S0 §)dr ÆAw )dr ÆØw;

2. S0 §)dr ∞Bx)dr ÆØy;

3. FIRSTk(w) = FIRSTk(y)

rezulta ca Æ = Ø, A = B, x = y.

Pornind de la definitia elementului de analiza sa consideram un cazparticular [A ! ÆØ., u]. Semnificatia acestui element de analiza este caÆØ a fost deja detectat ın arbore si astfel s-ar putea reduce subarborelecu frontul ÆØ la neterminalul A. Astfel, am determinat cand (ın ce starea automatului push-down) se poate face reducerea si care este mansa.Deci, cand se ajunge ıntr-o stare ce contine element de analiza de forma[A ! ÆØ., u] actiunea va fi de reducere, altfel va fi deplasare. Deoarecestarea automatului decide actiunea, ea va fi de asemenea depusa ın stivade lucru. Configuratia stivei va fi:

$sinitX1

s1

. . . Xmsm

unde Xm este simbolul din varful stivei, iar sm este starea curenta a au-tomatului. Cele doua elemente ımpreuna cu predictia de lungime k vordetermina comportamentul analizorului, caracterizat prin:

• actiunea care se va efectua si

• tranzitia ın alta stare.

De aceea tabelele de analiza LR(k) au doua componente: de actiune side deplasare, numita ”goto“.

Care sunt si cum se determina aceste stari? Pentru a raspunde saconsideram elementul de analiza [A ! Æ.BØ, u] care, conform definitiei,implica:

S§)dr ∞Aw )dr ∞ÆBØw si

u = FIRSTk(w) valabil pentru prefixul viabil ∞Æ.Daca ın gramatica exista o productie B ! ± atunci elementul de analiza

[B ! .±, u] are, de asemenea, u valid pentru prefixul viabil ∞Æ:

67

S§) ∞Aw )dr ∞ÆBØw )dr ∞ƱØw.

Aceasta observatie sugereaza faptul ca elementele de analiza cores-punzatoare unui acelasi prefix viabil ar trebui grupate ıntr-o multime si caaceasta multime caracterizeaza un pas al analizei, deci va forma o stare.Multimea care va contine toate elementele de analiza corespunzatoare unuiprefix viabil va forma o stare a automatului.

Starea initiala este cea care corespunde prefixului vid (ınca nu s-a cititnimic de pe banda de intrare), deci va contine elementul de analiza [S0 !.S, u]. Starea finala, corespunzatoare acceptarii unei secvente, va trebuisa contina elementul de analiza [S0 ! S., $] pentru a impune o actiune dereducere la S0, iar predictia este vida, adica la radacina arborelui, ceea cecorespunde construirii complete a arborelui de analiza sintactica.

Toate analizoarele sintactice LR au aceste caracteristici generale. Mo-dul de calcul al starilor automatului si constructia tabelului de analiza vorfi particularizate pentru diferite tipuri de analizoare LR, si anume: LR(0),SLR, LR(1), LALR.

Prezentarea fiecarui analizor va urma pasii:

• prezentarea elementului de analiza;

• construirea multimii de stari;

• construirea tabelului de analiza;

• functionarea analizorului.

3.3.2. Analizor sintactic LR(0)

Elementul de analiza LR(0) are forma [A ! Æ.Ø] (predictia fiindvida, ea dispare din elementul de analiza), ceea ce ınseamna ca vom aplicaprincipiile analizei sintactice LR de determinare a mansei, deplasare sireducere, dar fara sa tinem seama de predictie (de ce simbol urmeaza pebanda de intrare).

Constructia multimii de stari: Dupa cum am mai precizat o stareeste o multime care contine toate elementele de analiza corespunzatoareunui prefix viabil. Vom nota cu E

0

multimea elementelor de analiza LR(0).Vom folosi o functie de ınchidere pentru a construi aceasta multime[ASU86]:

closure : P(E0

)! P(E0

)care are urmatoarele doua proprietati importante, pe baza carora vomelabora algoritmul 3.8:

1. I 2 P(E0

), I µ closure(I)

68

Algoritm Closure1

1. C 2 closure(C).

2. Consideram elementul de analiza [A ! Æ.BØ, a], care are urmatoareasemnificatie:S

§)dr ∞Aw )dr ∞ÆBØw si a = FIRSTk(w)valabil pentru prefixul viabil ∞Æ. Vom folosi o productie pentru Bın derivarile ulterioare, fie ea B ! ± si vom obtine:S

§)dr ∞Aw )dr ∞ÆBØw )dr ∞ƱØw

astfel ca elementul de analiza [B ! .±, ?] va fi valabil pentru prefixulviabil ∞Æ. Care este predictia corespunzatoare acestul element deanaliza? Primul simbol care urmeaza dupa ± ın forma propozitionalasi anume FIRST (Øw). Dar ın acest sir de derivari s-a presupus dejaca FIRST (w) = a, obtinand predictia FIRST (Øa). Deci, vom aveaurmatoarea regula de calcul pentru closure, aplicata ın algoritmul3.11:8[A ! Æ.BØ, a] 2 closure(C),8B ! ± 2 P, [B ! .±, b] 2 closure(C)pentru 8b 2 FIRST (Øa)

Algoritmul 3.11 ClosureLR1INPUT: I-element de analiza; G’- gramatica ımbogatita;

FIRST (X),8X 2 N [ ß;OUTPUT: C

1

= closure(I);C

1

:= {I};repeat

for 8[A! Æ.BØ, a] 2 C1

dofor 8B ! ∞ 2 P do

for 8b 2 FIRST (Øa) doif [B ! .∞, b] /2 C

1

thenC

1

= C1

[ [B ! .∞, b]end if

end forend for

end foruntil C

1

nu se mai modifica

Definitia functiei goto se actualizeaza ın:

goto(s,X) = closure({[A ! ÆX.Ø, a]|[A! Æ.XØ, a] 2 s}).

Pentru calculul colectiei canonice de stari LR(1) modificam algoritmulcorespunzator de la LR(0) (algoritmul 3.9), obtinand algoritmul 3.12.

80

S.Motogna- LFTC

Construcție tabel LR(1)

• Structura – SLR• Reguli:1. dacă[A→α.β,u]∈ si șigoto(si,a)=sj atunciacțiune(si,a)=shift sj2. dacă[A→β.,u]∈ si șiA≠Sʹatunciacțiune(si,u)=reducel,undel-

numărulproducțieiA→β3. dacă[Sʹ→S.,$]∈ si atunciacțiune(si,$)=acc4. dacăgoto(si,X)=sj atuncigoto(si,X)=sj ,∀X∈N5. toatecelelaltevalori=eroare

S.Motogna- LFTC

Observații

1. Ogramatică este detipLR(1)dacă tabelul deanaliză LR(1)nuconține conflicte

2. Număr destări – crește semnificativ

S.Motogna- LFTC

Analiza secvenței debaza tranzițiilor între configurații

• INPUT:• Gramatica limbajului G’=(NU{S’},𝚺,PU{S’->S},S’)• Tabel deanaliză LR(1)• Secvența deanalizat w=a1…an

• OUTPUT:Dacă (w∈L(G)) atunci șir deproducții

altfel locația erorii

S.Motogna- LFTC

Configurații LR(1)

(𝛼,𝛽,𝜋)

Unde:• 𝛼 =stiva delucru• 𝛽 =stiva deintrare• 𝜋 =banda deieșire (rezultat)

S.Motogna- LFTC

Configurația finală:($sacc,$, 𝜋)

Configurația inițială:($s0,w$,𝜀)

Tranziții1. Deplasaredacă actiune(sm,ai)=shift sj atunci

($s0x1 ...xmsm,ai ...an$, 𝜋)⊢ ($s0x1 ...xmsmaisj,ai+1 ...an$, 𝜋)2. Reduceredacă actiune(sm,ai)=reducet AND(t)A→xm−p+1 ...xm ANDgoto(sm−p,A)=sjatunci

($s0 ...xmsm,ai ...an$, 𝜋)⊢ ($s0 ...xm−psm−pAsj,ai ...an$,t 𝜋)3. Acceptaredacă actiune(sm,$)=acceptatunci ($sm,$,𝜋)=acc3. Eroare - altfel

S.Motogna- LFTC

head(𝛽)=predicția

Analizor sintactic LALR

• LALR=LookAheadLR(1)

• Dece?

S.Motogna- LFTC

Principiul LALR

• Unificarea stărilor careauacelași nucleu,cuconservarea tuturorpredicțiilor,cucondiția să nusecreeze conflict

[A→α.β,u]∈ si=>[A→α.β,u/v]∈ si,j

[A→α.β,v]∈ sj

S.Motogna- LFTC

Analiză sintactică LALR

• Cași LR(1)• Număr destări LALR=număr destări SLR/LR(0)

S.Motogna- LFTC

Analizoare sintactice LR(k)• LR(0):

• elementele deanaliză nuiau în considerare predicția• reducerea poate fiefectuată doar în stări singulare (careconțin unsingur elementdeanaliză)

• segenerează multe conflicte.• SLR:

• folosește aceleași elemente deanaliză cași LR(0)• lareducere seia în considerare predicția• seelimina unele cazuri deconflictcareapăreau laLR(0).

• LR(1):• algoritm performantdeconstruire astărilor• segenerează conflicte puține,• segenerează prea multe stări.

• LALR:• unifică stările LR(1)corespunzătoare aceluiași nucleu• este cel mai desfolosit algoritm

S.Motogna- LFTC

Analiza sintactică - recapitulare

Descendent AscendentRecursiv a.s.descendentcu

reveniria.s.ascendent cureveniri

Liniar LL(1) LR(0),SLR,LR(1),LALR

S.Motogna- LFTC

Analiza sintactică - recapitulare

• familia analizoarelor sintactice LR(k), daca dorim o analiza sintacticaascendenta.

Un aspect important pe care trebuie sa ıl luam ın considerare este legatde restrictiile impuse de metoda de analiza asupra gramaticii limbajului.Eliminarea conflictelor nu este ıntotdeauna usor de realizat si de aceea sedoreste evitarea lor. Cea mai putin restrictiva clasa este cea a gramaticilorLR(1), dar analizorul sintactic are alte dezavantaje, asupra carora vomreveni. Figura 3.4 ilustreaza incluziunea dintre tipurile de gramatici luateın considerare ın analiza sintactica. Se observa ca nu exista o corelatieevidenta ıntre gramatici LL(1) si gramaticile LR(k), o gramatica LL(1)poate sa fie LR(1), LALR, SLR sau chiar LR(0), dar orice gramatica LL(1)este LR(1).

LR(0)

SLR

LALR(1)

LR(1)

LL(1)

Figura 3.5: Relatia dintre diferite clase de gramatici ın functie de metodade analiza sintactica

Diferentele importante dintre cele doua mari clase de analizoare sintac-tice se pot sintetiza ın modul de construire al arborelui, tipul de derivarifolosite si semnificatia tabelelor de analiza, dupa cum se observa si ın ta-belul urmator.

91

S.Motogna- LFTC