Cursul 8
Analiza sintactic ascendent
Parser (Analizor de sintax) ascendent
general
Gramatici LR(k)
Definiie
Proprieti
Gramatici LR(0)
Teorema de caracterizare LR(0)
Automatul LR(0)
lfac Gh Grigoras 1
Parser (Analizor de sintax) ascendent
general
Intrare
a1 ai an #
Stiva
TABELA
ym CONTROL DE
PARSARE
ym-1
.
.
p1 p2
y0
Ieire
Gh. Grigoras 2
Configuraii
O configuraie ( #, u#, ) este interpretat n
felul urmtor:
# este coninutul stivei cu simbolul # la baza ei, iar
ultimul simbol din # este topul stivei.
u# este coninutul benzii de intrare, unde #
marcheaz sfritul cuvntului de analizat.
este coninutul benzii de ieire
C0 = {(#, w#, )|w T*} mulimea configuraiilor
iniiale.
Gh. Grigoras 3
Tranziii
Parserul ascendent ataat gramaticii G este
perechea (C0, ) unde C0 este mulimea
configuraiilor iniiale, iar este o relaie de tranziie
pe C definit prin:
(#, au#, ) (#a, u#, ) (tranziie de tip deplasare)
pentru orice *, a T, u T*, P*.
(#, u#, ) (#A, u#, r) dac r = A (tranziie
de tip reducere).
Configuraia (#S, #, ) unde , se numete
configuraie de acceptare.
Orice configuraie, diferit de cea de acceptare, care
nu este n relaia cu nici o alt configuraie,
spunem c este o configuraie eroare.
Parserele de acest fel se numesc parsere de
deplasare/reducere.
Gh. Grigoras 4
Exemplu
Fie gramatica S aSb| . Tranziiile sunt:
(#, u#, ) (#S, u#, 2), unde 2 este regula S
(#aSb, u#, ) (#S, u#, 1), unde 1 este regula S
aSb
(#, au#, ) (#a, u#, )
(#, bu#, ) (#b, u#, )
unde *, u T*, P*.
O succesiune de tranziii o vom numi calcul
Iat nite calcule pentru exemplul de mai sus:
(#, #, ) (#S, #, 2)
(#, aabb#, ) (#a, abb#, ) (#aa, bb, ) (#aaS, bb, #,
2)
(#aaSb, b#, 2) (#aS, b#, 21) (#aSb, #, 21) (#S, #,
211)
n cel de-al doilea calcul am fcut alegeri nedeterministe
ntre a aplica o tranziie de tip deplasare sau una de tip
reducere. De pild, are loc:
(#aa, bb#, ) (#aaS, bb#, 2) (reducere) dar i
(#aa, bb#, ) (#aab, b#, ) (deplasare)
Gh. Grigoras 5
Conflicte
Parserul descris funcioneaz nedeterminist din dou
motive:
Pentru orice configuraie de forma (#, au#, ) cu A P
exist cel puin dou configuraii urmtoare (relativ la relaia ) :
(#, au#, ) (#A, au#, r) ( reducere cu r = A
)
(#, au#, ) (#a, u#, ) (deplasare)
Este posibil ca pentru o configuraie de forma (#, u#, ) s
avem = 11 = 22 astfel ca A 1 P, B 2 P, nct au
loc:
(#11, u#, ) (#A, u#, r1) ( reducere cu r1 = A 1) i
(#22, u#, ) (#B, u#, r2) ( reducere cu r2 = A 2).
n primul caz spunem c avem de-a face cu un conflict
de deplasare/reducere, iar n cel de-al doilea caz avem
de-a face cu un conflict de6 reducere/reducere.
Gh. Grigoras
Corectitudine
Spunem c un cuvnt w T* este acceptat de
un parser ascendent dac exist mcar un
calcul de forma
(#, w#, ) + (#S, #, )
Pentru ca parserul descris n definiia 1 s fie
corect, trebuie ca el s accepte toate cuvintele
din L(G) i numai pe acestea.
Teorema Parserul ascendent general ataat unei
gramatici G este corect: pentru orice w T*, w
L(G) dac i numai dac n parser are loc
calculul (#, w#, ) + (#S, #, ).
Gh. Grigoras 7
Analiza sintactic LR
Gramatici LR(k): Left to right scanning of the
input, constructing a Rightmost derivation in
reverse, using k symbols lookahead
Definiie O gramatic G se numete gramatic
LR(k), k 0, dac pentru orice dou derivri de
forma:
S S dr* Au dr u = u
S S dr* Au dr u = v = v
pentru care k:u = k:v,
are loc: = , A = A, = .
Gh. Grigoras 8
Analiza sintactic LR
Teorema 1 Dac G este gramatic LR(k), k 0,
atunci G este neambigu.
Teorema 2 Orice gramatic LL(k) este gramatic
LR(k).
OBS. Exist gramatici LR(0) care nu sunt LL(k).
SA|B
A aAb | c
B aBbb | d
L(G) = {ancbn | n 0 } {andb2n | n 0 }. Pentru un
cuvnt care ncepe cu (cel puin) k simboluri a, nu
putem decide n manier LL(k) dac el aparine sau
nu limbajului.
Se constat c gramatica dat este LR(0).
Gh. Grigoras 9
Analiza sintactic LR
Un limbaj L este (n clasa) LR(k) dac exist o
gramatic LR(k) ce-l genereaz
Teorema 3 Orice limbaj LR(k) este limbaj de tip
2 determinist.
Teorema 4 Orice limbaj de tip 2 determinist este
limbaj LR(1).
Teorema 5 Pentru orice limbaj LR(k), k 1,
exist o gramatic LR(1) care genereaz acest
limbaj, adic LR(0) LR(1) = LR(k), k 1.
Gh. Grigoras 10
Gramatici LR(0) - Caracterizare
Definiie Fie G = (V, T, S, P) o gramatic
independent de context redus. S presupunem c
simbolul nu este n . Un articol pentru gramatica
G este o producie A n care s-a adugat
simbolul ntr-o anume poziie din . Notm un
articol prin A dac = . Un articol n care
este pe ultima poziie se numete articol complet.
Definiie Un prefix viabil pentru gramatica G este
orice prefix al unui cuvnt dac S dr* Au dr
u. Dac = 12 i = 1 spunem c articolul
A 12 este valid pentru prefixul viabil .
Gh. Grigoras 11
Exemplu S A, A aAa | bAb | c.
Articole: S A, S A, A aAa, A aAa,
A aAa, A aAa, A bAb, A bAb, A bAb,
A bAb, A c, A c.
Dac, n plus, avem i regula A , atunci singurul articol
corespunztor acesteia este articolul (complet) A .
Exemple de articole valide pentru prefixe viabile:
Prefixul Articole valide
viabil
Derivarea corespunztoare
ab A bAb S A aAa abAba
A aAa S A aAa abAba abaAaba
A bAb S A aAa abAba abbAbba
S A SA
A bAb S A bAb
A c SAc
Gh. Grigoras 12
Lema Fie G o gramatic i A 1B2 un articol
valid pentru prefixul viabil . Atunci, oricare ar fi
producia B , articolul B este valid pentru
.
Teorema ( caracterizare LR(0) ) Gramatica G
este gramatic LR(0) dac i numai dac, oricare
ar fi prefixul viabil , sunt ndeplinite condiiile:
1. nu exist dou articole complete valide pentru .
2. dac articolul A este valid pentru , nu exist
nici un articol B 1a2, a T, valid pentru .
Gh. Grigoras 13
Teorema Fie G = (V, T, S, P) o gramatic independent
de context. Mulimea prefixelor viabile pentru gramatica
G este limbaj regulat.
Demonstraie G este G la care se adaug S S.
M = (Q, , , q0, Q), unde:
Q este mulimea articolelor gramaticii G,
= V T, q0 = S S, : Q ( {}) 2Q
definit astfel:
(A B, ) = {B | B P}.
(A X, X) = { A X}, X .
(A a, ) = , a T.
(A X, Y) = , X,Y cu X Y.
Se arat c are loc:
A ^(q0, ) este prefix viabil i
A este valid pentru .
Gh. Grigoras 14
Exemplu S S, S aSa |bSb | c
S
S S S S
S aSa S c S bSb
a b
c
S aSa S bSb
S S c S
S aSa S bSb
a b
S aSa S bSb
Gh. Grigoras 15
Teorema ( caracterizare LR(0) ) Gramatica G este gramatic
LR(0) dac i numai dac, oricare ar fi prefixul viabil , sunt
ndeplinite condiiile:
1. nu exist dou articole complete valide pentru .
2. dac articolul A este valid pentru , nu exist nici un articol
B 1a2, a T, valid pentru .
Demonstraie
G este LR(0) i, prin reducere la absurd 1 sau 2 nu are loc
1, 2 au loc si prin reducere la absurd, G nu este LR(0): exist
*
S S dr Au
dr
u = u (1)
S S Au u = v
*
dr dr
(2)
i nu are loc: = , A = A, = .
Fr a restrnge generalitatea, presupunem c n (1) i (2)
avem ndeplinit condiia || = || ||.
lfac Gh Grigoras 16
Cazul 1: || ||. Schematic acest lucru arat astfel:
Rezult de aici c = 12, v = 2u, = 1 i 2
T*. Atunci, din (1) rezult c A este articol valid
pentru iar din (2) rezult c articolul A 12 este
valid de asemenea pentru . Asta contrazice 1 dac 2 =
respectiv 2 dac 2 . Aadar, n acest caz,
presupunerea c G nu este LR(0) este fals.
lfac Gh Grigoras 17
Cazul 2: ||>||. Din nou schematic condiia arat astfel:
u
Asta nseamn c = u1, v = u1u T* (|u1| 1). n
derivarea (2), punem n eviden prima form
propoziional care are prefixul ; aceasta exist
deoarece S nu are prefixul , iar u = v are prefixul .
Rezult c exist A1 11 este articol valid pentru
(iar din (1) rezult c A este valid de asemenea
pentru )....
lfac Gh Grigoras 18
Automatul LR(0)
Algoritmul 1 (procedura nchidere(t))
Intrare: Gramatica G = (V, T, S, P);
Mulimea t de articole din gramatica G;
Ieire: t = nchidere( t ) = {q Q | p t, q (p, ) } = (t, )
Metoda:
t = t ; flag = true;
while( flag ) {
flag = false;
for ( A B t ) {
for ( B P )
if ( B t ) {
t = t {B };
flag = true;
}//endif
}//endforB
}//endforA
}//endwhile
return t;
lfac Gh Grigoras 19
Automatul LR(0)
Algoritmul 2 Automatul LR(0)
Intrare: Gramatica G = (N, T, S, P) la care s-a adugat S S;
Ieire: Automatul determinist M = (T, , g, t0, T) echivalent cu M.
Metoda:
t0=nchidere(SS); T={t0}; marcat(t0)=false;
while(tT && !marcat(t)) { // marcat(t) = false
for( X ) { // = N T
t = ;
for( A X t )
t = t {B X | B X t};
if( t ){
t = nchidere( t );
if( t T ) {
T = T { t };
marcat( t ) = false;
}//endif
g(t, X) = t;
}//endif
}//endfor
}//endfor
marcat( t ) = true;
}// endwhile
lfac Gh Grigoras 20
Automatul LR(0)
Exemplu S S, S aSa | bSb | c
S S
S aSa S
S S
S bSb
S c
a
a b
c b
S aSa c S c c S bSb
S aSa S aSa
S bSb S bSb
b
S c S c
S a S
S aSa S bSb
a b
S aSa S bSb
lfac Gh Grigoras 21
Test LR(0)
Definiie Fie G o gramatic i M automatul LR(0) ataat
lui G. Spunem c o stare a lui M are un conflict
reducere/reducere dac ea conine dou articole
complete distincte A , B . Spunem c o stare a
lui M are un conflict deplasare/reducere dac ea
conine un articol complet A i un articol cu
terminal dup punct de forma B a. Spunem c o
stare este consistent dac ea nu conine conflicte i
este inconsistent n caz contrar.
Teorema Fie G o gramatic i M automatul su LR(0).
Gramatica G este LR(0) dac i numai dac automatul
M nu conine stri inconsistente
lfac Gh Grigoras 22
Automatul LR(0)
Exemplu S aAd | bAB A cA | c Bd
S S
S aAd S S S
S bAB
a b
S aAd A cA S bAB
A cA c A c c A cA
A c A cA S c
A c
c
A A
A
S bAB
S aAd A cA B d
d B d
S aAd S bAB B d
lfac Gh Grigoras 23