Cap II. Analiza sintactică [605405]

Cap II. Analiza sintactică

Analiza sintactică este o etapa a procesului de compilare care are următoarele două cauze
principale:
• Determina daca un cuvânt specificat aparține sau nu limbajului, atunci presupunem ca
cuvâ ntul este corect din punct de vedere sintactic. În particular limbajul poate fi caracterizat
de o gramatica generativa de tip Chomsky ¸ deci termenul de analiza sintactică trebuie
înteles în sensul teoriei limbajelor formale. Mai mentionam ca prin cuvant în telegem orice
structura constituita cu simbolurile acceptate de limbaj,ˆın particular unˆıntreg program, dar
de obicei ne vom mărgini la anumite entităti, de exemplu, o linie sau un rand.
• Stabileste .derivarea(arborele de derivare)corespunzator cuvantul ui. Odata cu aceasta
operatie sunt degajate anumite structuri pentru care se poate genera cod intermediar,
structuri pe care le vom numi unitati sintactice.
Pe langa˘ aceste obiective principale se mai efectuaza ¸si alte operatii, de exemplu, analiza
¸si tratarea erorilor, prelucrarea tabelelor, etc. Rezultatul analizei sintactice va fi un fisier care
contine derivarile (arborii de derivare) corespunzatoare unitatilor sintactice ˆın care este
descompus programul: expresii aritmetice, declaratii, etc. Acest fis ier este utilizat ˆın faza de
generare a formatului intermediar. ˆIn mod curent ˆınsa˘, generatoarele de format
intermediar sunt ni¸ste rutine, apelate de analizorul sintactic, astfel ˆıncaˆt formatul
intermediar se obtine succesiv. Teoretic,
problemaanali zeisintacticeesterezolvata˘deautomatelecorespunz˘atoare diverselor tipuri de
limbaje; aceasta cale conduce ˆınsa˘ la algoritmi cu complexitate mare (numar mare de stari,
functie de tranziție conmplexa, etc.).
II.1 Algoritmul general Top -Down de analiza sin tactica

Algoritmul general de analiza top -down are un principiu foarte simplu: se aplica ın mod
sistematic regulile de generare,incepand cu simbolul de start ,ın cazul unui esec se revine ın
sus ¸si se ıncearca o alta regula. Regulile se aplica ın ordinea ın care sunt scrise ın
gramatica, fara sa existe o anumita ordine preferentiala de scriere, ıntrucat natura
algoritmului nu permite nici un fel de ierarhizare a regulilor din punctul de vedere al
frecventei de utilizare .
Pentru descrierea riguroasa a aces tui algoritm am urmat modelul din cartea lui D. Gries,”
Compiler construction for digital compters”. Fie G = (VN,VT,x0,P) o gramatica de tipul 2 ¸si p
∈ V∗ T . Ne intereseaza urmatoarele doua probleme:

(a) p∈L(G)?,

(b) Daca p ∈L(G) atunci sa se determine derivarea x0 ⇒p. Consideram toate regulile care au
X0 ın stanga:
x0 →x11 …x1n1|x21 …x2n2|…|xp1 …xpnp
Initial x0 devine activ ¸si alege prima regula x0 → x11 …x1n1. Daca aceasta alegere este
corecta trebuie sa avem x0 ⇒ x11 …x1n1 ∗ ⇒p ¸si ın conformitate cu lema de localizare a
gramaticilor de tipul 2, cuvantul p se poate descompune ın forma p = p1p2 …pn1, unde x1j ∗
⇒pj, j = 1,…n1.Simbolul x0 ıl activeaza pe x11 ¸si ıi cere sa gaseasca derivarea x11 ∗ ⇒p1;
daca x1 1 reuseste, transmite lui x0 succes. Simbolul x0 ıl dezactiveaza pe x11,ıl activeaza
pe x12 ¸si ıi cere sa gaseasca derivarea x12 ∗ ⇒p2, etc. Daca toate simbolurile activate de
x0 transmit succes, constructia este terminata. Sa presupunem ca x1j transmite esec; atunci
x0 ıl dezactiveaza pe x1j, ıl reactiveaza pe x1j−1 caruia ıi transmite: Mi -ai dat o derivare, dar
aceasta nu este buna,ıncearca alta. Daca x1j−1 reuseste, procesul se continua spre
dreapta; daca nu, atunci x0 ıl dezactiveaza pe x1j−1, ıl react iveaza pe x1j−2 caruia ıi cere o
alta derivare. Procesul se continua ın acest mod fie spre dreapta, fie spre stanga. Daca se
ajunge la x11 ¸si acesta nu reuseste sa gasasca o alta derivare, x0 decide ca prima regula
aleasa nu este buna ¸si incearca cu urmato area regula, adica
x0 →x21 …x2n2, ¸s. a. m. d.
Observatii
• Fiecare simbol devenit activ, procedeaza exact ca ¸si parintele sau, alege prima regula,
activeaza primul simbol, etc.
• Nu se cunoaste anticipat descompunerea p = p1p2 …pn1. Deci x1j transmite succes daca
reuseste sa gaseasca o derivare x1j ∗ ⇒pj, unde pj este unsubcuvant oarecare al lui p, cu
singura conditie ca p1j sa ınceapa din punctul unde s -a terminat p1j−1. De exemplu, daca p
= i1i2 …i8 … ¸si p1 = i1i2i3i4, p2 = i5i6 , atunci x13 trebuie sa gaseasca o derivare de forma
x13 ∗ ⇒i7i8 ….ˆ In particular, daca x1j ∈ VT decizia de succes sau esec depinde de faptul
daca x1j coincide sau nu cu simbolul din p care urmeaza (ˆIn exempl ul de mai sus, daca x13
coincide sau nu cu i7).
• Cand se reactiveaza un simbol si i se cere o noua derivare, acesta reactiveaza ultimul
simbol fiu ¸si ıi cere acelasi lucru.

II.2 Analiza LL(1)
In teoria limbajelor formale o gramatica LL este o gramatica de context care poate fi
analizată de un analizor LL care analizează intrarea de la stânga la dreapta și construiește o
derivație din stânga a propoziției .
Spunem că o gramatică este LL (k) dacă pentru fiecare simbol non -terminal a și fiecare
pereche de reguli A :: = α | β avem :

[ k (α) O k Follow k (A)] Ω [First k (β) O k Follow k (A)] = multimea vida .
Ideea este că, dacă privim înainte k pozitii, putem decide regula potrivita, regula A :: = a sau
regula A :: = b.
Data fiind k≥0 ,o gramatica fara context G=(V,£,R,S) este o gramatica de tipul LL(k) daca :
• pentru fiecare șir de simbol terminal w apartine lu £* pana la k simboluri,
• pentru fiecare simbol nonterminal A apartine lui V ,sau
• pentru fiecare șir de simbol terminal w 1 apartine lu £*
Exista cel mult o regula r care apartine lu R , astfel încât pentru niște șiruri de simboluri
terminale w 2 , w3 care partin lu £* ,
• Sirul w 1Aw 3 poate fi derivat din simbolul de start S,
• W2 poate fi derivat din A dupa aplicarea reguli r,si
• Primul k simbol din w,si din w2 w3 sunt de acord.
Informal ,cand a fost derivat un parser w1Aw3 , cu A cel mai din stanga si cu terminalul
w deja consumat de la intrare si atunci uitandu -se la w1 și cu privire la următoarele simboluri
k ale intrării curente, parserul poat e identifica cu certitudine regula de producție r pentru A.
O gramatica pentru care alegerea regulii de aplicat este unic determinata de urmatorul
simbol terminal din sirul de analizat se numeste gramatica LL(1) (Left to right parsing,
Left most derivation , 1 symbol look a head). ˆIn multe cazuri exista posibilitatea de a
transforma gramatica ıntr -una echivalenta de tip LL(1).
Definitie : Fie G = (VN , VT , S,P) o gramatica independenta de context. G se zice de tip
LL(k) daca ¸si numai daca oricare ar fi do ua derivari extrem stangi
S ∗⇒uXv ⇒ uαv ∗⇒uγ
S ∗⇒uXv ⇒ uβv ∗⇒uν unde X → α ∈ P, X → β ∈ P, γ, ν ∈ V + T
din γ k = ν k rezulta α = β (notatia γ k ˆınseamna primele k simboluri din sirul γ).
Pentru k = 1 se obtine cazul gramaticilor din sectiunile precedente. Restrictia asupra
numarului de simboluri citite ˆın avans restrange drastic multimea limbajelor ce por fi
analizate cu astfel de gramatici. Un inconvenient major pentru k > 1 este cresterea
exponentiala a dime nsiunii tabelei de predictie (cate o intrare ˆın tabel pentru fiecare
combinatie de k simboluri. O varianta mai eficienta de analiza se obtine cu gramatici LR(1)
(Left to right parsing, Rightmost derivation, 1 symbol lookahead).

II.3 Analiza sintactica Bo ttom Up bazata pe precedent simpla.

Fie G = (VN , VT , x0,P) o gramatica de tipul doi ¸si p ∈ L(G) o forma propozitionala, adica
un cuvant peste alfabetul general VG astfel ˆıncat x0 ∗⇒p. Vom nota cu Ax0,p arborele de
derivare care are radacina x0 ¸si fro ntiera p.
Definitia 1. Vom spune ca f este o fraza simpla a lui p daca f este un subcuvant al lui p ¸si ˆın
plus:
• ∃x ∈ VN , cu x → f ∈ P;
• Ax,f ⊂ Ax0,p.
Definitia 2. Fraza simpla cea mai din stanga poarta denumirea de fraza simpla stanga. Vom
nota fraza simpla stanga corespunzatoare lui p cu fp ˆın exemplul nostru, fp = T ∗ F. Dupa
cum vom vedea ˆın continuare, fraza simpla stanga are un rol important ˆın algoritmii de
analiza sintactica bottom -up.
II.3 Analiza RL(1)
O varianta mai eficienta de analiza se obtine cu gramatici LR(1) (Left to right
parsing, Rightmost derivation, 1 symbol lookahead).
Teorema 1
◦ Dacă G este gramatică LR(k), k≥0, atunci G este neambiguă.
Un limbaj L este (în clasa)
ℒℛ(k) dacă există o gramatică LR(k) care îl generează
Teorema 2 ◦ Orice limbaj ℒℛ(k)
este limbaj de tip 2 determinist.
Teorema 3 ◦ Orice limbaj de tip 2 determinist este limbaj
LR(1).
Teorema 4 ◦ Pentru orice limbaj ℒℛ(k), k≥1, există o gramatică LR(1) care
generează acest limbaj, adică LR(0) ⊂ LR(1) = LR(k), k≥1.