Limbaje Formale si Tehnici de Compilare

Limbaje Formale si Tehnici de Compilare

Dragan Mircea

April 19, 2006

1

P R E F A T AMaterialul prezentat constituie notele de curs tinute studentilor din primii

doi ani la Sectia Informatica a Facultatii de Matematica si Informatica de laUniversitatea de Vest Timisoara.

In primul capitol, Introducere se trec ın revista notiunile fundamentale dinteoria limbajelor formale si se prezinta problema generala a compilarii.

Capitolul al doilea, Limbaje regulate si analiza lexicala, prezinta chestiunileteoretice fundamentale privind teoria automatelor si echivalenta cu limbajele detipul trei, proprietati speciale si mecanisme echivalente cu automatele finite. Suntprezentate de asemenea si principiile analizei lexicale, finalizate cu realizarea unuianalizor lexical.

Capitolul al treilea, Limbaje independente de context este dedicat studiuluiteoretic al mecanismelor de generare si de recunoastere a limbajelor de tipuldoi. Sunt prezentate formele normale ale gramaticilor independente de contextsi cateva proprietati speciale.

Capitolul patru, Analiza sintactica este dedicat prezentarii principiilor gen-erale de analiza sintactica si a algoritmilor specializati de analiza. Pentru fiecaretip de algoritm analizat s-au considerat exemple practice de aplicare.

Capitolul al cincilea, Sinteza programelor trateaza formele intermediare uzualepentru traducerea programelor si generarea codului obiect pornind de la for-matul intermediar. Pentru cazul expresiilor aritmetice sunt prezentati si algoritmidirecti de generarea a formatului intermediar, ımpreuna cu proceduri standardde optimizare a codului generat.

Ultimul capitol, Masina Turing prezinta succint mecanismul formal ce de-fineste modelul de calculabilitate.

La sfarsitul fiecarui capitol sunt date cateva exercitii (nerezolvate), aplicatiidirecte la chestiunile teoretice prezentate. Acestea pot fi parcurse ın cadrul orelorde seminar si laborator.

In expunerea algoritmilor s-a folosit un limbaj mai putin rigid, fara prea multereguli stricte. In general s-a urmarit descrierea cat mai simpla a structurilor careapar ın text.

Cuprins

1 Introducere 5

1.1 Limbaje formale . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2 Gramatici generative de tip Chomsky . . . . . . . . . . . . . . . . 8

1.3 Ierarhia Chomsky . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.4 Traducerea programelor . . . . . . . . . . . . . . . . . . . . . . . 17

1.5 Probleme propuse . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2 Limbaje Regulate si Analiza Lexicala 23

2.1 Automate finite si limbaje regulate . . . . . . . . . . . . . . . . . 23

2.2 Proprietati speciale ale limbajelor regulate . . . . . . . . . . . . . 29

2.3 Expresii regulate si sisteme tranzitionale . . . . . . . . . . . . . . 34

2.4 Analiza lexicala . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37


3 Limbaje Independente de Context 51

3.1 Arbori de derivare . . . . . . . . . . . . . . . . . . . . . . . . . . 51

3.2 Ambiguitate ın familia L2. . . . . . . . . . . . . . . . . . . . . . . 54

3.3 Forme normale pentru gramatici de tipul 2 . . . . . . . . . . . . . 56

3.4 Lema Bar–Hillel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

3.5 Automate push-down (APD) . . . . . . . . . . . . . . . . . . . . . 65

3.6 Automate push–down deterministe . . . . . . . . . . . . . . . . . 73


4 Analiza Sintactica 79

4.1 Algoritmi TOP-DOWN . . . . . . . . . . . . . . . . . . . . . . . . 80

4.1.1 Algoritmul general de analiza top-down . . . . . . . . . . . 80

4.1.2 Analiza top-down fara reveniri . . . . . . . . . . . . . . . . 81

4.1.3 Programarea unui analizor sintactic. Studiu de caz . . . . 84

4.2 Algoritmi BOTTOM-UP . . . . . . . . . . . . . . . . . . . . . . . 90

4.2.1 Gramatici cu precedenta simpla . . . . . . . . . . . . . . . 90

4.2.2 Relatii de precedenta . . . . . . . . . . . . . . . . . . . . . 92

4.2.3 Proprietati ale gramaticilor cu precedenta simpla . . . . . 93

3

4 CUPRINS

4.2.4 Determinarea relatiilor de precedenta pentru gramatici cuprecedenta simpla . . . . . . . . . . . . . . . . . . . . . . . 95

4.2.5 Studiu de caz . . . . . . . . . . . . . . . . . . . . . . . . . 954.2.6 Gramatici operatoriale . . . . . . . . . . . . . . . . . . . . 974.2.7 Gramatici operatoriale . . . . . . . . . . . . . . . . . . . . 1004.2.8 Determinarea relatiilor de precedenta pentru gramatici op-

eratoriale . . . . . . . . . . . . . . . . . . . . . . . . . . . 1034.2.9 Studiu de caz . . . . . . . . . . . . . . . . . . . . . . . . . 104

5 Sinteza Programelor 1075.1 Forme interne ale programelor . . . . . . . . . . . . . . . . . . . . 107

5.1.1 Tabelele compilatorului . . . . . . . . . . . . . . . . . . . . 1075.1.2 Cvadruple si triplete . . . . . . . . . . . . . . . . . . . . . 109

5.2 Generarea formatului intermediar . . . . . . . . . . . . . . . . . . 1145.2.1 Generarea cvadruplelor . . . . . . . . . . . . . . . . . . . . 1155.2.2 Generarea tripletelor . . . . . . . . . . . . . . . . . . . . . 1175.2.3 Generarea sirului polonez . . . . . . . . . . . . . . . . . . 118

5.3 Generarea formatului intermediar pentru instructii clasice . . . . . 1215.3.1 Instructiunea de atribuire . . . . . . . . . . . . . . . . . . 1215.3.2 Instructiunea If . . . . . . . . . . . . . . . . . . . . . . . . 1215.3.3 Variabile indexate . . . . . . . . . . . . . . . . . . . . . . . 121

6 Masina Turing 1236.1 Limbaje de tipul zero . . . . . . . . . . . . . . . . . . . . . . . . . 1236.2 Masina Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

Capitolul 1

Introducere

1.1 Limbaje formale

Notiunea generala de limbaj. Se numeste alfabet sau vocabular orice multimefinita si nevida. Elementele unui alfabet V le vom numi simboluri (sau litere,caractere, variabile).

Definitie 1.1 Un cuvant peste un alfabet V este o secventa p = a1a2 . . . an, ai ∈V, i = 1, . . . , n.

Numarul n, deci numarul simbolurilor cuvantului p, se numeste lungimea cuvantuluisi va fi notat cu |p| sau l(p). Vom considera si cuvantul vid λ sau e, care nu continenici un simbol; evident |λ| = 0.

Notiunea de cuvant este fundamentala ın teoria limbajelor formale sau ın altedomenii ale informaticii; termeni sinonimi utilizati ın literatura sunt propozitie,fraza sau sir. Sa observam ca nu exista o similitudine foarte buna ıntre notiunilede ”alfabet”, ”cuvant”, etc. din teoria limbajelor formale si notiunile core-spunzatoare din lingvistica.

Multimea tuturor cuvintelor peste un alfabet V o notam cu V +. Aceastamultime ımpreuna cu cuvantul vid va fi notata cu V ∗. In general, vom utilizalitere mari de la sfarsitul alfabetului pentru notarea diverselor alfabete, U, V,W,etc.; litere de la ınceputul alfabetului (mari sau mici) pentru notarea simbolurilor,A,B, C, . . . , a, b, c, . . . , i, j, . . . (uneori cifre 0,1,2,...); pentru notarea cuvintelorvom utiliza litere mici de la sfarsitul alfabetului, p, q, r, s, t, u, v, w, x, y, z, etc.(aceasta conventie de notare nu va fi absoluta).

Fie p = a1 . . . an, q = b1 . . . bm . Definim pe multimea V ∗ operatia de con-catenare sau juxtapunere prin pq = a1 . . . anb1 . . . bm.

Se poate verifica usor ca aceasta operatie este asociativa. Prin urmare,multimea V + ınzestrata cu aceasta operatie este un semigrup (semigrupul liberpeste V ). Multimea V ∗ cu aceiasi operatie este un semigrup cu unitate, deci unmonoid, unitatea fiind cuvantul vid (monoidul liber peste V ). Structura are si

5

6 CAPITOLUL 1. INTRODUCERE

proprietatea de simplificare la stanga si la dreapta, adica:

ua = ub⇒a = b, respectiv, au = bu⇒a = b, ∀a, b, u ∈ V ∗

Fie din nou p, q ∈ V ∗. Vom spune ca q este un subcuvat sau un infix (propriu)al lui p daca p = uqv, u, v ∈ V ∗ (u, v ∈ V +); q este prefix (propriu) al lui p dacap = qv, v ∈ V ∗(v ∈ V +); q este sufix (propriu) al lui p daca p = uq, u ∈ V ∗(u ∈V +).

Definitie 1.2 Un limbaj L peste alfabetul V este o parte a multimii tuturorcuvintelor peste V , deci L ⊆ V ∗.

Sa observam ca V ∗ (sau V +) este ıntotdeauna o multime infinita (evidentnumarabila); ın aceasta acceptiune generala, un limbaj poate sa fie o multimefinita sau infinita, uneori chiar vida.

Exemplu. Fie V = {0, 1}. Avem

V + = {0, 1, 00, 01, 10, 000, . . .},

V ∗ = {λ, 0, 1, 00, 01, 10, 000, . . .}.Limbaje peste alfabetul V sunt de exemplu multimile

L1 = {λ, 00, 11},

L2 = {1, 11, 111, . . .} = {1n|n ≥ 1}.Observatie. Notatia an, unde a este un simbol al unui alfabet, ınseamna

cuvatul constituit din n simboluri a, adica aa . . . a︸︷︷︸. In particular a0 = λ.

Operatii cu limbaje Limbajele fiind multimi se pot efectua cu limbaje ope-ratiile obisnuite cu multimi: reuniune, intersectie, diferenta, complementariere(fata de V ∗). Exista si operatii specifice limbajelor.

In general, o operatie de n-aritate oarecare (cel mai adesea binara sau unara)pe multimea V ∗ defineste o operatie corespunzatoare pe multimea limbajelor.Astfel, daca

α : V ∗ −→ P(V ∗) si β : V ∗ × V ∗ −→ P(V ∗)

sunt doua operatii pe V ∗ (unara si respectiv binara) si L1, L2 sunt doua limbajepeste V , putem defini limbajele α(L1) respectiv β(L1, L2) prin

α(L1) =⋃

x∈L1

α(x), β(L1, L2) =⋃

x∈L1,y∈L2

β(x, y).

Exemple:

1.1. LIMBAJE FORMALE 7

1. Produsul (concatenarea) a doua limbaje definit prin

L1L2 = {pq|p ∈ L1, q ∈ L2}.Daca L1 = L2 = L vom nota LL = L2. Prin recurenta, se defineste Ln

astfelL0 = {λ}, Lk = Lk−1L, k ≥ 1.

2. Inchiderea (Kleene) a unui limbaj L este

L∗ =∞⋃

k=0

Lk.

3. Limbajul Sub(L). Fie V ∗ si Sub(x) multimea tuturor subcuvintelor lui x(evident Sub este o operatie unara pe V ∗). Daca L este un limbaj peste V ,putem defini limbajul

Sub(L) =⋃

x∈L

{Sub(x)}.

adica limbajul constituit din toate subcuvintele tututor cuvintelor lui L.Semnificatii analoage vor avea si limbajele Pref(L) si Suf(L).

4. Limbajul Mi(L). Fie x = a1 . . . an un cuvant peste alfabetul V . CuvantulMi(x) = an . . . a1 se numeste rasturnatul sau oglinditul lui x (Mi este pres-curtarea cuvantului englez mirror). Se mai noteaza Mi(x) = x. Avematunci si rasturnatul unui limbaj

Mi(L) =⋃

x∈L

{Mi(x)}.

5. Operatia de substitutie. Fie U si V doua alfabete si fie aplicatia s : V −→P(U∗). Extindem (prelungim) aceasta aplicatie la V ∗ prin

s(λ) = {λ}, s(xy) = s(x)s(y),∀x, y ∈ V ∗.

O astfel de prelungire se numeste canonica; ea pastreaza operatia de con-catenare, ın sensul ca daca p = xy, atunci s(p) = s(x)s(y) este concatenarealimbajelor s(x), s(y). Operatia de substitutie a limbajelor este data de

s(L) =⋃

x∈L

s(x).

Sa observam ca aceasta operatie transforma un limbaj peste un alfabet Vıntr-un limbaj peste un alfabet U si ca pastreaza operatia de concatenare.Daca card(a) < ∞,∀a ∈ V , vom spune ca substitutia este finita, iar dacacard(a) = 1,∀a ∈ V vom spune ca s este un homomorfism.

Operatiile reuniune, produs si ınchidere Kleene se mai numesc operatii reg-ulate asupra limbajelor.


1.2 Gramatici generative de tip Chomsky

Un limbaj peste un alfabet poate sa fie o multime finita sau infinita. Daca este omultime finita, el poate fi definit prin scrierea efectiva a cuvintelor limbajului. Incazul ın care este o multime infinita, el poate fi definit ın anumite cazuri punandın evidenta structura cuvintelor lui. De exemplu

L2 = {01, 0011, 000111, . . .} = {0n1n|n ≥ 1}.Exista doua procedee mai generale pentru definirea limbajelor:

1. Procedee generative, care permit generarea tuturor cuvintelor limbajului.Exista mai multe tipuri de mecanisme de generare a limbajelor, ıntre caregramaticile Chomsky, sisteme Lindenmayer,etc.

2. Procedee analitice, care determina daca un cuvant dat apartine sau nulimbajului. Sunt asa-numitele automate, automate finite, automate push-down, etc.

Un rol deosebit ın teoria limbajelor formale ıl au gramaticile Chomsky.Notiunea de gramatica Fie VN si VT doua alfabete disjuncte,VN ∩ VT = ∅numite respectiv alfabetul simbolurilor neterminale (VN) si alfabetul simbolurilorterminale (VT ). Notam VG = VN ∪ VT alfabetul general si P ⊂ V ∗

GVNV ∗G × V ∗

G

alfabetul regulilor.Multimea P va fi deci formata din perechi de forma (u, v), unde u = u′Au′′,

u′, u′′ ∈ V ∗G, A ∈ VN iar v ∈ V ∗

G, deci u si v sunt cuvinte peste VG, cu observatiaca u trebuie sa contina cel putin un simbol neterminal. Vom spune ca o astfelde pereche este o regula (productie, regula de generare, regula de rescriere) si ovom nota u → v (vom spune: u se transforma ın v). Apartenenta unei reguli laP o vom nota ın mod obisnuit (u → v) ∈ P , sau mai simplu, u → v ∈ P (nu vaexista confuzia cu faptul ca v este un element al lui P ).

Definitie 1.3 O gramatica este un sistem G = (VN , VT , X0, P ), unde VN estealfabetul simbolurilor neterminale, VT este alfabetul simbolurilor terminale, X0 ∈VN si se numeste simbol de start al gramaticii, iar P este multimea de reguli.

Observatie. Simbolurile alfabetului VN le vom nota ın general cu litere mariA,B,C, . . . , X, Y, Z (mai putin U, V, W ) iar cele ale alfabetului VT cu litere micide la ınceput a, b, c, . . . sau cu cifre 0, 1, 2, . . ..

Fie G o gramatica si p, q ∈ V ∗G. Vom spune ca p se deriveaza direct ın q

si vom scrie p ⇒G

q (sau mai simplu p⇒q) daca exista cuvintele r, s, u, v ∈ V ∗G

astfel ıncıt p = rus, q = rvs iar u → v ∈ P . Vom spune ca p′ se deriveaza ın p′′

(fara specificatia direct) daca exista p1, p2, . . . , pn n ≥ 1 astfel ıncat

p′ = p1 ⇒G

p2 ⇒G

. . . ⇒G

pn = p′′.

1.2. GRAMATICI GENERATIVE DE TIP CHOMSKY 9

Vom scrie p′ +⇒G

p′′ (sau p′ +⇒p′′ cand nu exista nici o confuzie) daca n > 1

si p′ ∗⇒G

p′′ (sau p′ ∗⇒p′′) daca n ≥ 1. Sirul de mai sus va fi numit derivare iar

numarul de derivari directe din sir ıl vom numi lungimea derivarii; se mai spuneca p′ deriva ın p′′.

Sa observam ca transformarile astfel definite ⇒,+⇒,

∗⇒ sunt relatii pe V ∗G.

Este clar ca relatia+⇒ este ınchiderea tranzitiva a relatiei ⇒, iar relatia

∗⇒ esteınchiderea tranzitiva si reflexiva a relatiei de transformare directa .

Definitie 1.4 . Limbajul generat de gramatica G este prin definitie multimea

L(G) = {p ∈ V ∗T , X0

∗⇒G

p}.

Observatie. Daca p ∈ V ∗G si X0

∗⇒G

p se spune ca p este o forma propozitionala

ın gramatica G.Exemple:

1. Fie G = (VN , VT , X0, P ), unde VN = {A}, VT = {0, 1}, X0 = A (evident)si P = {A → 0A1, A → 01}. O derivare ın aceasta gramatica este, deexemplu

A⇒0A1⇒00A11⇒000111 = 0313.

Este evident ca L(G) = {0n1n|n ≥ 1}.Observatie. In cazul ın care mai multe reguli au aceeasi parte stanga, levom scrie compact astfel u → v1|v2| . . . |vn, simbolul | avand sensul de sau;ın cazul nostru, A → 0A1|01.

2. G = (VN , VT , X0, P ), undeVN = {<propozitie>, <subiect>, <atribut>, <predicat>, <complement>,<substantiv>, <adjectiv>, <verb>, <articol>},VT = {o, orice, matrice, functie, derivabila, continua, este },X0 =<propozitie>,P = {<propozitie>→<subiect><atribut><predicat><complement>,<subiect>→<articol><substantiv>,<atribut>→<adjectiv>,<predicat>→<verb>,<complement>→<adjectiv>,<articol>→o|orice,<substantiv>→matrice|functie,<adjectiv>→derivabila|continua,<verb>→este.

Observatie. In acest exemplu, ”<propozitie>”, ”<subiect>”, etc., reprezintafiecare cate un simbol neterminal; de asemenea, ”o”, ”orice”, ”matrice”,


etc., reprezinta simboluri terminale. Se poate usor observa ca aceastagramatica genereaza propozitii simple de forma subiect-atribut-predicat-complement care exprima judecati asupra conceptelor de ”matrice” si ”functie”.De exemplu, se poate forma propozitia: ”orice functie derivabila este con-tinua”, care este din punct de vedere semantic corecta, precum si propozitia”orice functie continua este derivabila”, care, dupa cum se stie, este falsa.Evident, se pot genera si numeroase propozitii care nu au sens. Ceea ce neintereseaza ın acest moment este aspectul formal, deci din punct de vederesintactic toate aceste propozitii sunt corecte; semantic, unele propozitii potsa fie incorecte sau chiar sa nu aibe sens.

Sa mai observam ca o gramatica Chomsky este ın masura sa constituieun model matematic pentru sintaxa unei limbi, fara sa intereseze aspectelesemantice. Este ceea ce a ıncercat sa faca Naom Chomsky pentru limbaengleza ın lucrarile sale din anii ′50.

3. G = (VN , VT , X0, P ), undeVN = {<program>, <instructie>, <atribuire>, <if>, <expresie>, <termen>,<factor>, <variabila>, <index>},VT = {begin, end, if, then, stop, t, i, +, *, (, ), =, ,, ; },X0 =<program>P = {<program>→begin <linie> end<linie>→<linie>;<instructie> | <instructie><instructie>→<atribuire> | <if> | stop<atribuire>→<variabila>=<expresie><if>→if( <expresie>) then <atribuire><expresie>→<expresie> + <termen> | <termen><termen>→<termen> ∗ <factor> | <factor><factor>→(<expresie>)| <variabila><variabila>→t(<index>)|i<index>→<index>,<expresie> | <expresie>Gramatica din acest exemplu defineste un limbaj de programare simplu cutrei tipuri de instructii: atribuiri, if-then, stop. Expresiile aritmetice au nu-mai operatorii + si *; variabilele pot fi simple sau indexate (tablouri), iar itine loc de identificator sau constanta. Mentionam ca definirea ın acest moda unui limbaj, inclusiv utilizarea crosetelor pentru desemnarea simbolurilorneterminale, poarta adesea denumirea de notatie Backus Naur; ın acestmod s-a definit limbajul ALGOL60.

Tipuri de gramatici Dupa forma regulilor de generare, gramaticile Chomskyse ımpart ın mai multe tipuri; clasificarea obisnuita este urmatoarea:

• Gramatici de tipul 0; sunt gramatici fara restrictii asupra regulilor;

• Gramatici de tipul 1 (dependente de context); sunt gramatici care au regulide forma

1.2. GRAMATICI GENERATIVE DE TIP CHOMSKY 11

uAv → upv, u, p, v ∈ V ∗G, p 6= λ, A ∈ VN

sau A → λ si ın acest caz A nu apare ın dreapta vreunei reguli.Observatie. Evident, regulile de forma a doua au sens numai daca A estesimbolul de start.

• Gramaticile de tipul 2 (independente de context); sunt gramatici care aureguli de forma

A → p, A ∈ VN , p ∈ V ∗G.

• Gramaticile de tipul 3 (regulate); sunt gramatici care au reguli de forma{

A → BpC → q

sau

{A → pBC → q

cu A,B, C ∈ VN si p, q ∈ V ∗T .

Vom nota cu Lj, j = 0, 1, 2, 3 familiile de limbaje generate de gramaticilede tipurile j = 0, 1, 2, 3; vom avea astfel limbaje de tipul 0, limbaje de tipul 1(sau dependente de context) , limbaje de tipul 2 (sau independente de context)si limbaje de tipul 3 (sau regulate). Sa observam ca este importanta structuracuvintelor unui limbaj si nu modul ın care sunt notate simbolurile terminale. Deexemplu , limbajele

L′2 = {0n1n|n ≥ 1}, L′′2 = {anbn|n ≥ 1}sunt ın mod practic identice. Putem utiliza o unica notatie pentru afabetulsimbolurilor terminale , de exemplu , VT = {i1, . . . , in}. Clasificarea de maisus este fundamentala ın teoria limbajelor formale, ea a fost introdusa de NaomChomsky in 1958 si prin traditie noile clase de limbaje sunt raportate la aceastaclasificare. O alta clasificare este urmatoarea

• Gramatici de tipul 0; fara restrictii;

• Gramatici monotone (de tipul 1):

u → v, |u| ≤ |v|, u, v ∈ V ∗G;

• Gramatici dependente de context:

uAv → upv, u, p, v ∈ V ∗G, p 6= λ, A ∈ VN ;

• Gramatici independente de context (de tipul 2):

A → p, A ∈ VN , p ∈ V ∗G;


• Gramatici liniare:

A → uBv, A ∈ VN , B ∈ VN ∪ {λ} u, v ∈ V ∗T ;

• Gramatici (stang) drept liniare:

A → uB (A → Bv), A ∈ VN , B ∈ VN ∪ {λ} u, v ∈ V ∗T ;

• Gramatici regulate (de tipul 3); gramatici stang liniare sau gramatici dreptliniare.

Gramaticile monotone ca si cele dependente de context nu pot avea reguli cupartea dreapta vida. Se introduce urmatoarea conventie de completare: ıntr-o gramatica monotona sau dependenta de context se admite o regula de formaA → λ cu conditia ca A sa nu apara ın partea dreapta a vreunei reguli. Dupacum vom vedea , existenta sau inexistenta regulilor de forma A → λ, regulinumite de stergere, poate modifica esential puterea generativa a unei gramatici.O gramatica ın care nu avem astfel de reguli o vom numi gramatica λ−libera; deasemenea, un limbaj care nu contine cuvantul vid, ıl vom numi limbaj λ−liber.Sa mai observam ca existenta regulilor de stergere ıntr-o gramatica nu implica ınmod necesar existenta cuvantului vid ın limbajul generat.

Doua gramatici care genereaza acelasi limbaj se numesc echivalente.Gramaticile monotone si gramaticile dependente de context sunt echivalente;

de asemenea, gramaticile drept si stang liniare sunt echivalente, justificandu-seastfel clasa gramaticilor regulate.

1.3 Ierarhia Chomsky

Lemele care urmeaza vor avea o utilizare frecventa ın cele ce urmeaza.

Lema 1.1 (Lema de localizare a gramaticilor independente de context) Fie G ogramatica independenta de context si fie derivarea

x1 . . . xm∗⇒p, unde xj ∈ VG, j = 1,m , p ∈ V ∗

G.

Atunci exista p1, p2, . . . , pm ∈ V ∗G astfel ıncat

p = p1 . . . pm si xj∗⇒pj, j = 1,m.

Demonstratie. Procedam prin inductie asupra lungimii derivarii l.Daca l = 0 atunci p = x1 . . . xm si luam pj = xj.Presupunem ca proprietatea este adevarata pentru derivari de lungime l si

fie o derivare de lungime l + 1, x1 . . . xm∗⇒p. Punem ın evidenta ultima derivare

1.3. IERARHIA CHOMSKY 13

directa x1 . . . xm∗⇒q⇒p. Conform ipotezei inductive, q = q1 . . . qm si xj

∗⇒qj, j =1, . . . , m.

Fie apoi A → u regula care se aplica ın derivarea directa q⇒p si sa presupunemca A intra ın subcuvantul qk, deci qk = q′kAq′′k . Vom lua

pj =

{qj , j 6= k

q′kuq′′k , j = k

Este evident ca xj∗⇒pj, j 6= k, iar pentru j = k avem

xk∗⇒qk = q′kAq′′k⇒q′kuq′′k = pk.2

Vom pune ın evidenta ın continuare o proprietate asupra structurii regulilor gra-maticilor Chomsky. Partea dreapta a unei reguli, pentru toate tipurile de gra-matici, este un cuvant format din terminale sau neterminale. Este convenabilde multe ori ca partea dreapta a regulilor sa contina un singur tip de simboluri,terminale sau neterminale. Acest lucru este posibil fara modificarea tipului gra-maticii.

Lema 1.2 (Lema A → i) Fie G = (VN , VT , S, P ) o gramatica de tipul 2. Existao gramatica G′ echivalenta, de acelasi tip, cu proprietatea ca daca o regula areın partea dreapta un terminal, atunci ea este de forma A → i, A ∈ VN , i ∈ VT .

Demonstratie. Luam gramatica G′ de forma G′ = (VN′, VT

′, S, P ′) unde VN′ si

P ′ se construiesc astfel: VN ⊆ VN′ si includem ın P ′ toate regulile din P care

convin. Fie acum o regula din P care nu convine (punem ın evidenta aparitiaterminalelor din partea dreapta):

u → v1i1v2i2 . . . invn+1, ik ∈ VT , vk ∈ V ∗N .

Vom introduce ın P ′ urmatoarele reguli:

u → v1Xi1v2Xi2 . . . Xinvn+1, Xik → ik, k = 1, n ,

unde Xik sunt neterminale noi pe care le adaugam la VN′. Este evident ca G′

pastreaza tipul lui G si ca L(G′) = L(G)2.Observatie. Constructia din lema se poate extinde usor la gramatici de tipul

0, ınlocuind si terminalele din partea stanga a regulilor (u poate fi un sir arbitrarce contine minim un neterminal). Gramatica astfel obtinuta este echivalenta cucea initiala si pastreaza tipul.

Ierarhia Chomsky. Este evident ca L3 ⊂ L2 si ca L1 ⊂ L0, deoarece oriceregula a unei gramatici de tipul 3 respecta prescriptiile unei gramatici de tipul2; analog pentru familiile L1 si L0. Aparent, o regula de forma A → p (de tipul2) este un caz particular a unei reguli de forma uAv → upv (de tipul 1), pentru


u = v = λ; totusi, realitatea nu este aceasta, deoarece la tipul 2 de gramaticisunt permise reguli de stergere, pe cand la tipul 1 se impune conditia p 6= λ. Vomarata ca avem L2 ⊂ L1.

Sirul de incluziuni

L3 ⊂ L2 ⊂ L1 ⊂ L0

poarta denumirea de ierarhia Chomsky (vom arata pe parcursul acestui cursca incluziunile sunt stricte). Aceasta ierarhie caracterizeaza puterea generativaa celor patru tipuri de gramatici, aceasta putere fiind crescatoare de la 3 la 0.Orice alte mecanisme generative se raporteaza la aceasta ierarhie fundamentala.Vom demonstra mai ıntai urmatoarea lema.

Lema 1.3 (Lema eliminarii regulilor de stergere). Orice limbaj independent decontext λ-liber poate fi generat de o gramatica de tipul 2 fara reguli de stergere.

Demonstratie. Fie G = (VN , VT , X0, P ) o gramatica independenta de context siL(G) limbajul generat. Prin ipoteza λ 6∈ L(G). Definim prin recurenta sirul demultimi Uk astfel:

U1 = {X|X ∈ VN , X → λ ∈ P}Uk+1 = {X|X ∈ VN , X → p ∈ P, p ∈ U∗

k} ∪ Uk, k ≥ 1.

Sa observam ca sirul de multimi definite este crescator ın raport cu relatia deincluziune. Cum toate aceste multimi sunt incluse ın VN si VNeste finita, rezultaca exista o multime maximala Uf astfel astfel ıncat

U1 ⊆ U2 ⊆ · · · ⊆ Uf = Uf+1 = · · · .

Are loc de asemenea si implicatia X ∈ Uf ⇔ X∗⇒λ.

Vom ilustra aceasta implicatie cu un exemplu. Sa presupunem ca Uf = U3

si fie X ∈ U3. Atunci ın mod necesar trebuie sa avem X → p ∈ P , p ∈ U∗2 ; de

exemplu p = X1X2 si X1, X2 ∈ U2. In mod analog X1 → Y1Y2Y3, X2 → Z1Z2 siY1, Y2, Y3, Z1, Z2 ∈ U1, prin urmare Y1 → λ, Y2 → λ, Y3 → λ, Z1 → λ, Z2 → λ.Putem scrie derivarea

X⇒X1X2∗⇒Y1Y2Y3Z1Z2

∗⇒λ.

Definim acum urmatoarea gramatica independenta de context fara reguli destergere G′ = (VN , VT , X0, P

′) unde VN , VT , X0 sunt ca ın gramatica data, iar P ′

se construieste pornind de la P astfel. Fie X → p ∈ P, p 6= λ. Includem atunciın P ′ aceasta regula precum si toate regulile de forma X → pj, unde pj se obtinedin p lasand la o parte, ın toate modurile posibile, simbolurile din Uf (se exceptacazul pj = λ). De exemplu daca X → ABC ∈ P si A,B ∈ Uf , vom induce ın P ′

regulileX → ABC, X → BC, X → AC, X → C.

1.3. IERARHIA CHOMSKY 15

Sa observam ca ın acest fel multimea P a fost pe de o parte micsorata (au fostexcluse regulile de alegere), iar pe de alta parte ımbogatita cu eventualele noireguli. Sa mai obsevam ca G′ este independenta de context si ca nu continereguli de stergere.

Vom arata ca L(G) = L(G′).Mai ıntai, sa aratam ca L(G) ⊆ L(G′).

Fie p ∈ L(G), deci X0∗⇒G

p; vom arata ca X0∗⇒G′

p. Vom arata o implicatie

ceva mai generala, X∗⇒G

p implica X∗⇒G′

p, pentru orice X ∈ VN (relatia ceruta

se obtine pentru X = X0). Procedam prin inductie asupra lungimii derivarii l.Daca l = 1 avem

X ⇒G

p deci X → p ∈ P. Dar p 6= λ deci X → p ∈ P ′

adica X∗⇒G′

p.

Presupunem ca afirmatia este adevarata pentru l = n si luam o derivare culungimea l = n + 1. Punem ın evidenta prima derivare directa

X ⇒G

X1 . . . Xm∗⇒G

p

Conform lemei de localizare avem p = p1 . . . pm si Xj∗⇒G

pj, j = 1, . . . , m.

Unele din cuvintele pj pot sa fie vide; pentru precizarea ideilor sa presupunem cap2, p3, p5 = λ. Atunci pentru derivarile Xj

∗⇒G

pj, j 6= 2, 3, 5, care au lungimea

de cel mult n, conform ipotezei inductive avem Xj∗⇒G′

pj.

Pe de alta parte , pentru j = 2, 3, 5 avem X2∗⇒G

λ, X3∗⇒G

λ, X5∗⇒G

λ,

deci X2, X3, X5 ∈ Uf . Rezulta ca

X → X1X4X6 . . . Xm ∈ P ′

asa ıncat putem scrie

X ⇒G′

X1X4X6 . . . Xm∗⇒G′

p1p4p6 . . . pm = p.

Deci X∗⇒G′

p si luand X = X0 obtinem p ∈ L(G′). Prin urmare L(G) ⊆ L(G′).

Sa aratam acum incluziunea inversa , L(G′) ⊆ L(G).Fie p ∈ L(G), X0

∗⇒G′

p. Punem ın evidenta o derivare directa oarecare

X0∗⇒G′

u ⇒G′

v∗⇒G′

p.


Daca ın derivarea directa u ⇒G′

v se aplica o regula care exista si ın G, atunci

evident pasul respectiv poate fi facut si ın G. Sa presupunem ca se aplica o regulanou introdusa de exemplu X → BC, deci pasul respectiv va avea forma

u = u′Xu′′ ⇒G′

u′BCu′′ = v

Regula X → BC ∈ P ′ a provenit dintr-o regula din P , lasand la o parte simboluridin Uf , ın cazul nostru din X → ABC, lasandu-l la o parte pe A ∈ Uf . DeoareceA

∗⇒G

λ, avem

u = u′Xu′′ ⇒G

u′ABCu′′ ∗⇒G

u′ABCu′′ = v.

Prin urmare orice pas al derivarii considerate se poate obtine si ın gramatica G,deci X0

∗⇒G

p si p ∈ L(G), adica L(G′) ⊆ L(G)2.

Teorema 1.1 L2 ⊆ L1.

Demonstratie. Fie L ∈ L2 un limbaj independent de context si G o gramatica detipul 2 care ıl genereaza, adica L = L(G).

Presupunem ca λ ∈ L. Construim gramatica G′ ca ın lema precedenta; oricecuvant p 6= λ din L(G) se poate obtine ın G′ si invers , deci L(G′) = L(G)−{λ}.Consideram atunci o gramatica G′′ = (VN ∪ {X ′′

0 }, VT , X ′′0 , P ′ ∪ {X ′′

0 → λ,X ′′0 →

X0}). Evident L(G′′) = L(G). Toate regulile lui G′′ respecta tipul 1 (cu u =v = λ) si contine o singura regula de stergere X ′′

0 → λ iar X ′′0 nu apare ın partea

dreapta a vreunei reguli. Deci G′′ este de tipul 1 si orice limbaj independent decontext este inclus ın L1, adica L2 ⊆ L1.2

Fiind data o operatie binara notata cu ”•” pe o familie de limbaje L, vomspuna ca familia L este ınchisa la operatia ”•” daca L1, L2 ∈ L implica L1 •L2 ∈L. Definitia notiunii de ınchidere pentru operatii unare sau cu aritate oarecareeste analoaga. Relativ la proprietatile de ınchidere a familiilor din clasificareaChomsky mentionam urmatorul rezultat.

Teorema 1.2 Familiile Lj, j = 0, 1, 2, 3 sunt ınchise la operatiile regulate.

Demonstratie. Fie Gk = (VNk, VTk

, Sk, Pk), k = 1, 2 doua gramatici de acelasitip j, j = 0, 1, 2, 3. Putem presupune ca VN1 ∩ VN2 = ∅. Trebuie sa aratam calimbajele L(G1) ∪ L(G2), L(G1)L(G2), L(G1)

∗, sunt de acelasi tip j. In acestscop vom construi gramatici de tipul j care sa genereze le genereze. Vom indicafara demonstrtie modul de constructie al gramaticilor (pentru detalii vezi [?]):

Reuniune

1.4. TRADUCEREA PROGRAMELOR 17

j = 0, 1, 2, 3:

G = VN1 ∪ VN2 ∪ {S}, VT1 ∪ VT2 , P1 ∪ P2 ∪ {S → S1|S2}).

Produsj = 0, 1, 2:

G = VN1 ∪ VN2 ∪ {S}, VT1 ∪ VT2 , P1 ∪ P2 ∪ {S → S1S2}).

j = 3:G = VN1 ∪ VN2 ∪ {S}, VT1 ∪ VT2 , S1, P

′1 ∪ P2),

unde P ′1 se obtine din P1 prin ınlocuirea regulilor de forma A → p cu A → pS2.

Inchidere Kleenej = 0, 1:

G∗ = (VN ∪ {S∗, X}, VT , S∗, P ∪ {S∗ → λ|S|XS,Xi → Si|XSi, ∀i ∈ VT})

j = 2:

G∗ = (VN ∪ {S∗}, VT , S∗, P ∪ P prime ∪ {S∗ → S∗S|λ})

j = 3:

G∗ = (VN ∪ {S∗}, VT , S∗, P ∪ P prime ∪ {S∗ → S|λ})

1.4 Traducerea programelor

Un limbaj de programare este un limbaj care are drept scop descrierea unorprocese de prelucrare a anumitor date si a structurii acestora (ın unele cazuridescrierea structurii datelor este preponderenta), prelucrare care se realizeaza ıngeneral cu ajutorul unui sistem de calcul.

Exista ın prezent un numar mare de limbaje de programare de nivel ınalt sauevoluate care se caracterizeaza printr-o anumita naturalete, ın sensul ca descriereaprocesului de prelucrare cu ajutorul limbajului este apropiata de descrierea nat-urala a procesului respectiv precum si prin independenta unor astfel de limbajefata de sistemul de calcul. Dintre limbajele de acest tip cu o anumita raspandireın momentul de fata mentionam limbajele PASCAL, FORTRAN, C, JAVA, etc.

O alta clasa importanta de limbaje, sunt limbajele de asamblare, sau de nivelinferior, ale caror caracteristici depind de sistemul de calcul considerat. In gen-eral, fiecare sistem de calcul (sau tip de sistem de calcul), are propriul sau lim-baj de asamblare; de exemplu, limbajul de asamblare ale sistemelor de calculechipate cu procesoare de tip Intel Z-80 este denumit ın mod curent ASSEM-BLER. Instructiile unui limbaj de asamblare corespund cu operatiile simple ale


sistemului de calcul iar stocarea datelor ın memorie este realizata direct de uti-lizator la nivelul locatiilor elementare ale memoriei. Exista de asemenea anumitepseudo-instructii sau directive referitoare la alocarea memoriei, generarea datelor,segmentarea programelor, etc., precum si macroinstructii care permit generareaunor secvente tipice de program sau accesul la bibliotecile de subprograme.

In afara de limbajele evoluate si de limbajele de asamblare, exista numeroaselimbaje specializate, numite uneori si de comanda, care se refera la o anumita clasade aplicatii. Mentionam de exemplu limbajul pentru prelucrarea listelor LISP,limbajele utilizate ın cadrul softwarelui matematic (Mathematica, Maple, MAT-CAD, etc.) si multe altele. In general ınsa astfel de limbaje nu sunt consideratelimbaje de programare propriuzise.

Un program redactat ıntr-un limbaj de programare poarta denumirea de pro-gram sursa. Fiecare sistem de calcul, ın functie de particularitatile sale, posedaun anumit limbaj propriu, numit cod masina, acesta fiind singurul limbaj ıntelesde procesorul sistemului. Un astfel de limbaj depinde de structura instructiilorprocesorului, de setul de instructii, de posibilitatile de adresare, etc. Un pro-gram redactat ın limbajul cod masina al sistemului de calcul ıl numim programobiect.

Procesul de transformare al unui program sursa ın program obiect se numestecompilare sau translatare, uneori chiar traducere. De obicei termenul de com-pilare este utilizat numai ın cazul limbajelor evoluate, ın cazul limbajelor deasamblare fiind utilizat termenul de asamblare.

Compilarea (asamblarea) este efectuata de un program al sistemului numitcompilator (asamblor). De multe ori compilatoarele nu produc direct programobiect, ci un text intermediar apropiat de programul obiect, care ın urma unorprelucrari ulterioare devine program obiect. De exemplu, compilatoarele sis-temelor de operare DOS produc un text numit obiect (fisiere cu extensia obj)care ın urma unui proces numit editare de legaturi si a ıncarcarii ın memoriedevine program obiect propriuzis, numit program executabil (fisiere cu extensiaexe). Exista mai multe ratiuni pentru o astfel de tratare, ıntre care posibilitateacuplarii mai multor module de program realizate separat sau provenite din lim-baje sursa diferite, posibilitatea crearii unor biblioteci de programe ın formatulintermediar si utilizarea lor ın alte programe, etc.

Un program sursa poate de asemenea sa fie executat de catre sistemul decalcul direct, fara transformarea lui prealabila ın program obiect. In acest caz,programul sursa este prelucrat de un program al sistemului numit interpretor;acesta ıncarca succesiv instructiile programului sursa, le analizeaza din punctde vedere sintactic si semantic si dupa caz, le executa sau efectueaza anumiteoperatii auxiliare.

Procesul de compilare este un proces relativ complex si comporta operatii careau un anumit caracter de autonomie. Din aceste motive procesul de compilareeste de obicei descompus ın mai multe subprocese sau faze, fiecare faza fiind ooperatie coerenta, cu caracteristici bine definite. In principiu aceste faze sunt

1.4. TRADUCEREA PROGRAMELOR 19

Analiza Lexicala

Analiza sintactica

Generarea formatului intermediar

Generarea codului

Optimizarea codului

Tratarea erorilor

Prelucrarea tabelelor

Program Obiect

Program Sursa

Figura 1.1: Fazele compilarii

parcurse secvential (pot sa existe si anumite reveniri) iar programul sursa estetransformat succesiv ın formate intermediare. Se poate considera ca fiecare fazaprimeste de la faza precedenta un fisier cu programul prelucrat ıntr-un mod core-spunzator fazei respective, ıl prelucreaza si furnizeaza un fisier de iesire, iarasiıntr-un format bine precizat, fisier utilizat ın faza urmatoare. Exista cinci faze decompilare principale: analiza lexicala, analiza sintactica, generarea formatului in-termediar, generarea codului, optimizarea codului si doua faze auxiliare, tratareaerorilor si tratarea tabelelor (vezi figura 1.1).

Analiza lexicala are ca obiectiv principal determinarea unitatilor lexicale aleunui program, furnizarea codurilor acestora si detectarea eventualelor erori lex-icale. Pe langa aceste operatii de baza, la analiza lexicala se mai pot efectuaanumite operatii auxiliare precum: eliminarea blank-urilor (daca limbajul per-mite utilizarea fara restrictii a acestora), ignorarea comentariilor, diferite conver-siuni ale unor date (care se pot efectua la aceasta faza), completarea tabelelorcompilatorului.

Analiza sintactica determina unitatile sintactice ale programului (secventede text pentru care se poate genera format intermediar) si verifica programuldin punct de vedere sintactic. Este faza centrala a unui compilator, deseori toatecelelalte faze sunt rutine apelate de analizorul sintactic pe masura ce este posibilaefectuara unei parti din faza respectiva. Tot la analiza sintactica se definitiveaza


tabelele de informatii si se realizeaza prelucrarea erorilor sintactice.Faza de generare a formatului intermediar se refera la transformarea progra-

mului ıntr-o forma numita intermediara pornind de la care se poate, printr-oprocedura relativ simpla, sa se obtina programul obiect. Structura acestei fazedepinde de formatul intermediar ales de catre proiectant si de modalitatea deimplementare; uzual se folosesc cvadruple, triplete sau sirurile poloneze.

Generarea codului este o faza in care se realizeaza codul obiect corespunzatorprogramului. Practic ın aceasta faza se obtine programul ın limbaj de asamblarecorespunzator programului sursa redactat ıntr-un limbaj evoluat. In mod obisnuitgeneratorul de cod este constituit din rutinele generatoare de cod corespunzatoarediverselor unitati ale formatului intermediar.

In faza de optimizare a codului se realizeaza o anumita ımbunatatire a coduluiobiect astfel ıncat programul rezultat sa fie cat mai performant (ın privinta con-sumului de timp si memorie). Cele mai tipice exemple sunt eliminarea ıncarcarilorsi a memorarilor redundante sau optimizarea ciclurilor.

Fazele de Prelucrare a tabelelor si de Tratare a erorilor vor fi atinse numaipartial ın aceast curs. Facem ınsa mentiunea ca prelucrarea tabelelor poate saaiba o influenta importanta asupra performantelor unui compilator, ın mod spe-cial din punctul de vedere al timpului de executie (compilare) si ca tratareaerorilor are o anumita implicatie ın eliminarea erorilor sintactice.

1.5 Probleme propuse

1. Gasiti limbajul generat de gramatica G = (VN , VT , S, P ), precizand tipulgramaticii (cf. clasificarii Chomsky):

(a) VN = {S}; VT = {0, 1, 2};P = {S → 0S0|1S1|2S2|0}.

(b) VN = {S}; VT = {a, b};P = {S → aSb|ab}.

(c) VN = {S, A, B}; VT = {a, b, c};P = {S → abc|aAbc, Ab → bA, Ac → Bbcc, bB → Bb, aB →aaA|aa}.

(d) VN = {S, A, C}; VT = {+,−, 0, 1, . . . , 9};P = {S → A|+ A| − A, A → AC|C, C → 0|1| . . . |9}.

(e) VN = {S, A, B}; VT = {0, 1};P = {S → 0S|1A, A → 0B|1S|0, B → 0A|1B|1}.

(f) VN = {A}, VT = {a, b}, S = A, P = {A → aA|b};(g) VN = {x0}, VT = {A,B, . . . , Z}, S = x0, P = {x0 → x1D,

x1 → x2N, x2 → E};

1.5. PROBLEME PROPUSE 21

(h) VN = {A}, VT = {0, 1, 2}, S = A, P = {A → 0A0|1A1|2A2|λ};(i) VN = {S, A}, VT = {0, 1, . . . , 9, .},

P = {S → A.A,A → 0A|1A| . . . |9A|0|1| . . . |9};(j) VN = {S}, VT = {PCR, PDAR,UDMR},

P = {S → PCR|PDAR|UDMR};(k) VN = {A,B, C}, VT = {0, 1}, S = A, P = {A → 0A|1B|1,

B → 0C|1A,C → 0B|1C|0};(l) VN = {S, A,B,C}, VT = {0, 1, . . . , 9, +,−},

P = {S → +A| − A|A,A → 0A|1A| . . . |9A|0|1| . . . |9};(m) VN = {S}, VT = {(, )}, P = {S → S(S)S|λ};(n) VN = {E, T, F}, VT = {(, ), i, +, ∗}, S = E,

P = {E → E + T |T, T → T ∗ F |F, F → (E)|i};(o) VN = {S, A,B}, VT = {a, b, c}, P = {S → abc|aAbc,

Ab → bA,Ac → Bbcc, bB → Bb, aB → aaA|aa};(p) VN = {S, A,B,C,D,E}, VT = {a}, P = {S → ACaB,Ca → aaC,CB →

DB|E, aD → Da, AD → AC, aE → Ea,AE → λ};(q) VN = {S, A,B,C,D,E}, VT = {a, b}, P = {S → ABC,

AB → aAD|bAE,DC → BaC,EC → BbC, Da → aD,Db → bD, Ea →aE, Eb → bE, AB → λ,C → λ, aB → Ba, bB → Bb};

2. Precizati care dintre gramaticile precedente sunt echivalente.

3. Gasiti gramatici pentru generarea urmatoarelor limbaje:

(a) L = {λ};(b) L = ∅;(c) L = {0n|n ∈ N};(d) L = {a, ab, aab, ba, baa}.(e) L = {ancbn|n ≥ 1}.(f) L = {w ∈ {a, b, c}∗|w contine cc si se termina cu a}.(g) L = {BEGIN |END|IF |WHILE|UNTIL}.(h) L = {w ∈ {0, 1}∗| reprezentarea binara pe 8 biti a unui ıntreg }.(i) L = {anbn+3an+1|n ≥ 0}.(j) L = {w ∈ {a, b, c}∗|w ıncepe cu a si are maxim 4 litere }.(k) L = {aibjck|i, j, k > 0}.(l) L = {w ∈ {0, 1}∗|w multiplu de 8 }.

(m) L = { constante reale ın scrierea obisnuita cu punct zecimal pi.pz}.


(n) L = {aibjaibj};(o) L = {awbbw′|w, w′ ∈ {0, 1}∗};(p) L = {w ∈ {0, 1}∗|w contine maxim 2 de 0 };(q) L = {waw|w ∈ {0, 1}∗};(r) L = {w|w octet ce reprezinta un numar par };(s) L = {A, B, C, . . . , Z};

4. Construiti o gramatica ce contine reguli de stergere, dar genereaza un limbajλ-liber.

5. Folosind teorema sa se construiasca o gramatica independenta de context,fara reguli de stergere care genereaza limbajul de la punctul precedent.

Capitolul 2

Limbaje Regulate si AnalizaLexicala

2.1 Automate finite si limbaje regulate

Automate finite. Automatele finite sunt mecanisme pentru recunoasterea lim-bajelor de tipul 3 (regulate). Un automat finit (AF ) se compune dintr-o bandade intrare si un dispozitiv de comanda.

Pe banda de intrare sunt ınregistrate simboluri ale unui alfabet de intrare, con-stituind pe banda un cuvant p. La fiecare pas de functionare banda se deplaseazacu o pozitie spre stanga.

Dispozitivul de comanda poseda un dispozitiv de citire de pe banda; dispoz-itivul se afla permanent ıntr-o anumita stare interna, element al unei multimifinite de stari. Schema unui automat finit este redata ın figura 2.1.

Automatul finit functioneaza ın pasi discreti. Un pas de functionare constadin: dispozitivul de comanda citeste de pe banda de intrare simbolul aflat ındreptul dispozitivului de citire; ın functie de starea interna si de simbolul citit,automatul trece ıntr-o noua stare si muta banda cu o pozitie spre stanga. Au-tomatul ısi ınceteaza functionarea dupa ce s-a citit ultimul simbol ınregistrat pebanda; ın acest moment el se va afla ıntr-o anumita stare, care, dupa cum vomvedea, va juca un rol important ın recunoasterea cuvintelor.

Din punct de vedere matematic, un automat finit este un sistemAF = (Σ, I, f, s0, Σf ),

unde

Σ este alfabetul (multimea) de stari;

I este alfabetul de intrare;

f : Σ× I −→ P(Σ) este functia de evolutie;

s0 ∈ Σ este starea initiala;

Σf ⊆ Σ este multimea de stari finale.

23

24 CAPITOLUL 2. LIMBAJE REGULATE SI ANALIZA LEXICALA

i 1 i 2 i 3 ... i k ... i n-1 i n ...

Dispozitiv de citire

Dispozitiv de comanda s Î S

Banda de intrare

Figura 2.1: Reprezentarea schematica a unui automat finit

Daca pentru orice (s, i) ∈ Σ × I, avem |f(s, i)| ≤ 1 automatul se numestedeterminist; ın caz contrar se numeste nedeterminist.

Observatii:

1. Functionarea unui automat finit se poate bloca ın situatia ın care el se aflaın starea s, citeste de pe banda simbolul i si f(s, i) = ∅; evident ca ın acestcaz functionarea ın continuare nu mai este posibila.

2. In cazul unui automat determinist vom scrie f(s, i) = s′ (ın loc de f(s, i) ∈{s′}.

3. Definitia data este specifica teoriei limbajelor formale. O alta definitie (maigenerala) , ıntalnita ın teoria automatelor este urmatoarea: un automat finiteste un sistem AF = (Σ, I, O, f, g, s0, F ) unde, Σ, I, f, s0, F au semnificatiade mai sus, O este alfabetul de iesire iar g : Σ × I −→ P(O) este functiede iesire. Functionalitatea unui astfel de automat finit este analoaga cucea descrisa mai sus, cu deosebirea ca la fiecare pas automatul furnizeaza oiesire o ∈ g(s, i).

Prin diagrama de stari a unui automat finit ıntelegem un graf orientat care arenodurile etichetate cu starile s ∈ Σ iar arcele se construiesc astfel: nodurile s, s′

se unesc cu un arc orientat de la s la s′ daca exista i ∈ I astfel ıncat s′ ∈ f(s, i);arcul respectiv va fi notat cu i.

Exemplu AF = (Σ, I, f, s0, Σf ) unde Σ = {s0, s1, s2}, I = {i1, i2}, Σf = {s2},iar f este data de tabelul

s0 s1 s2

i1 {s1} {s2} {s0}i2 ∅ {s0, s1} {s0, s1}

2.1. AUTOMATE FINITE SI LIMBAJE REGULATE 25

s 0

s 2

s 1

i 1

i 1

i 2

i 2

i 2

i 2

Figura 2.2: Diagrama de stari

Diagrama de stari corespunzatoare este prezentata ın figura 2.2.

Functia de evolutie Functia f se prelungeste de la Σ× I la P(Σ)× I∗ decidefinim f ′ : P(Σ)× I∗ −→ P(Σ), astfel:

(a) f ′(s, λ) = {s}, ∀s ∈ Σ,

(b) f ′(∅, i) = ∅, ∀i ∈ I,

(c) f ′(Z, i) =⋃

s∈Z f(s, i), Z ∈ P(Σ), Z 6= ∅,(d) f ′(Z, pi) = f ′(f ′(Z, p), i).

Prin abuz de limbaj, vom folosi pentru noua functie tot notatia f .Sa observamca relatiile de mai sus constituie o definitie prin recurenta, corecta; fiind dat f ,putem defini mai ıntai toate valorile f(Z, i) (un numar finit, deoarece I este omultime finita), apoi f(Z, p) pentru |p| = 2, ın continuare f(Z, p) pentru |p| = 3,etc.

Proprietatile functiei f:

1. Daca Zk este o familie de parti a lui Σ, avem

f(⋃

k

Zk, i) =⋃

k

f(Zk, i)

Demonstratie. Utilizand (c) putem scrie

⋃

k

f(Zk, i) =⋃

k

(⋃

s∈Zk

f(s, i)) =⋃

s∈∪Zk

f(s, i) = f(⋃

k

Zk, i).2

2. f(Z, p) =⋃

s∈Z(f(s, p)), p ∈ I∗.Demonstratie. Prin inductie asupra lungimii lui p.

Pentru |p| = 1 avem f(Z, i) =⋃

s∈Z f(s, i), adica (c).

Presupunem ca relatia este adevarata pentru |p| = m si consideram un p astfel


ıncat |p| = m + 1, deci p = p′i, |p′| = m. Putem scrie

f(Z, p) = f(Z, p′i) = f(f(Z, p′), i) = f(⋃

s∈Z f(s, p′), i) ==

⋃s∈Z f(f(s, p′), i) =

⋃s∈Z f(s, p′i) =

⋃s∈Z f(s, p).

2

3. f(s, pq) = f(f(s, p), q), p, q ∈ I∗.Demonstratie. Inductie asupra lungimii lui q.

Daca |q| = 1, atunci q = i si relatia se reduce la (d).Presupunem ca proprietatea este adevarata pentru r si consideram |q| = r+1.

Deci q = q′i. Avem

f(s, pq) = f(s, pq′i) = f(f(s, pq′), i) = f(f(f(s, p), q′), i) == f(f(s, p), q′i) = f(f(s, p), q).

2

Limbaje regulate.

Definitie 2.1 Limbajul recunoscut de automatul finit AF = (Σ, I, f, s0, Σf ) este

L(AF ) = {p|p ∈ I∗, f(s0, p) ∩ Σf 6= ∅}

Deci p ∈ L(AF ) daca automatul aflandu-se ın starea initiala s0, dupa |p| paside functionare poate sa ajunga ıntr-o stare finala.

In cazul unui automat finit determinist limbajul recunoscut poate fi definitın modul urmator. Pentru fiecare s ∈ Σ definim functia fs : I∗ −→ P(Σ) prinfs(p) = f(s, p).

Atuncif(s0, p) ∩ Σf 6= ∅ ⇔ f(s0, p) = fs0(p) ∈ Σf ,

deciL(AF ) = {p|f(s0, p) ∩ Σf 6= ∅} = f−1

s0(Σf )

Limbajele recunoscute de automate finite le vom numi limbaje regulate; familiaacestor limbaje o vom nota cu R. Evident, familia limbajelor recunoscute deautomate finite deterministe, Rd, este o parte a lui R, Rd ⊆ R. Vom arata cacele doua familii coincid.

Teorema 2.1 Rd = R.

Demonstratie. Fie AF = (Σ, I, f, s0, Σf ) un automat finit (ın general nedetermin-ist). Construim urmatorul automat finit determinist AF ′ = (Σ′, I, f ′, {s0}, Σ′

f )unde Σ′ = P(Σ), f ′ = f (prelungirea la Σ×I∗ ), Σ′

f = {Z| Z ∈ P(Σ), Z∩Σf 6= ∅}.Evident, automatul AF ′ este determinist.Fie p ∈ L(AF ). Atunci f(s0, p) ∩ Σf 6= ∅ si f(s0, p) ∈ Σ′

f . Pe de alta parte,conform cu proprietatea 2 a functiei de evolutie, avem

f ′({s0}, p) = f(s0, p)

2.1. AUTOMATE FINITE SI LIMBAJE REGULATE 27

si deci f ′(s0, p) ∈ Σ′f , adica p ∈ L(AF ′) si L(AF ) ⊆ L(AF ′).

Pe o cale analoaga se arata ca L(AF ′) ⊆ L(AF ).2Observatie. Faptul ca un cuvant este recunoscut de un automat finit se poateverifica prin calcul direct sau pe diagrama de stari.

Exemplu. Consideram automatul din exemplul anterior (figura 2.2) si fiep = i1i2i1. Prin calcul direct:

f(s0, i1i2i1) = f(f(f(s0, i1), i2), i1) = f(f({s1}, i2), i1) == f({s0, s1}, i1) = f({s0}, i1) ∪ f({s1}, i1) = {s1} ∪ {s2}.

Astfel ca f(s0, i1i2i1) ∩ Σf = {s2} 6= ∅ si p ∈ L(AF ).Pe diagrama de stari exista traiectoriile:

s0i1−→s1

i2−→s0i1−→s1;

s0i1−→s1

i2−→s1i1−→s2;

A doua traiectorie ne duce ıntr-o stare finala, deci p ∈ L(AF ).Limbaje de tipul trei si limbaje regulate. Vom arata ın cele ce urmeaza ca

familia limbajelor de tipul 3 coincide cu familia limbajelor regulate. In prealabilvom pune ın evidenta o forma speciala a limbajelor de tipul 3, pe care convenimsa o numim forma normala.

Definitie 2.2 Vom spune ca o gramatica de tipul 3 este ın forma normala dacaare reguli de generare de forma

{A → iB,C → j,

unde A, B, C ∈ VN , i, j ∈ VT

sau regula de completare S → λ si ın acest caz S nu apare ın dreapta vreuneireguli.

Lema 2.1 Orice gramatica de tipul 3 admite o forma normala.

Demonstratie. Daca G = (VN , VT , S, P ) ∈ G3 este gramatica data, eliminam ınprimul rand λ-regulile (ca ın lema eliminarii regulilor de stergere) apoi construimgramatica G′ = (V ′

N , VT , S, P ′), unde V ′N si P ′ se definesc astfel: introducem ın

V ′N toate simbolurile din VN iar ın P ′ toate regulile din P care convin; fie acum

ın P o regula de formaA → pB, p = i1 . . . in

Vom introduce ın P ′ regulile:

A → i1Z1,Z1 → i2Z2,. . . ,Zn−1 → inB,


iar simbolurile Z1, . . . Zn−1 le includem in V ′N .

In cazul unei reguli de forma A → p cu |p| > 1 procedam analog, exceptand ul-tima regula nou introdusa care va avea forma Zn−1 → in. Sa mai facem observatiaca simbolurile Z1, . . . , Zn−1 le luam distincte pentru fiecare caz.

Se poate arata usor ca L(G) = L(G′).2

Teorema 2.2 Familia limbajelor de tipul 3 coincide cu familia limbajelor regu-late.

Demonstratie. Partea I: E ∈ L3 ⇒ E ∈ R.Fie E un limbaj de tipul 3 si G = (VN , VT , S, P ) gramatica care ıl genereaza;

putem presupune ca G este ın forma normala. Construim automatul finit AF =(Σ, I, f, s0, Σf ) unde Σ = VN ∪ {X} ( X simbol nou), I = VT , s0 = S si

Σf =

{{X, S} , pentru λ ∈ E{X} , pentru λ 6∈ E

Functia de evolutie este definita de:

daca A → iB ∈ P luam B ∈ f(A, i),daca C → j ∈ P luam X ∈ f(C, j),ın rest ∅

Observatie. Automatul astfel definit este ın general nedeterminist. De exemplu,daca A → 0B|0 atunci f(A, 0) = {B, X}.

Fie p ∈ L(G), p = i1 . . . in, deci S∗⇒p. Detaliat, aceasta derivare va avea

forma

(1) S⇒i1A1⇒i1i2A2⇒i1i2 . . . in−1An−1⇒i1i2 . . . in.

S-au aplicat regulile:

(2)

S → i1A1,A1 → i2A2,. . .An−1 → in.

In automat avem corespunzator:

(3) :

A1 ∈ f(S, i1),A2 ∈ f(A1, i2),. . .X ∈ f(An−1, in)

Putem scrie traiectoria

(4) Si1−→ A1

i2−→A2i3−→ . . .

in−→X ∈ Σf

2.2. PROPRIETATI SPECIALE ALE LIMBAJELOR REGULATE 29

Deci p ∈ L(AF ).Daca p = λ, atunci S⇒λ si S → λ ∈ P . Dar atunci λ ∈ L(AF ), caci

automatul este ın starea S si ramıne ın aceasta stare dupa ”citirea” lui λ; cumınsa ın acest caz S ∈ Σf rezulta ca si ın acest caz p ∈ L(AF ). In consecintaL(G) ⊆ L(AF ).

Fie acum p = i1 . . . in ∈ L(AF ); atunci avem traiectoria (4), relatiile (3),regulile de generare (2) si putem scrie derivarea (1), adica p ∈ L(G) si L(AF ) ⊆L(G).2Partea II E ∈ R ⇒E ∈ L3.

Vom indica numai modul de constructie a gramaticii. Fie AF = (Σ, I, f, s0, Σf )automatul finit care recunoaste limbajul E, pe care ıl presupunem determinist.Construim gramatica G = (Σ, I, s0, P ) unde multimea P este definita astfel

f(A, i) = B genereaza regula A → iB ∈ P ,ın plus daca B ∈ Σf se genereaza si regula A → i ∈ P .

Putem arata ca L(G) = L(AF ).2

2.2 Proprietati speciale ale limbajelor regulate

Caracterizarea algebrica a limbajelor regulate. Limbajele regulate, fiindparti din I∗, se pot caracteriza algebric, independent de mecanismele de generare(gramaticile de tipul 3) sau de cele de recunoastere (automatele finite).

Teorema 2.3 Fie E ⊂ I∗ un limbaj. Urmatoarele afirmatii sunt echivalente.(a) E ∈ R;(b) E este o reuniune de clase de echivalente a unei congruente de rang finit;(c) Urmatoarea congruenta

µ = {(p, q)|χE(r1pr2) = χE(r1qr2), ∀r1, r2 ∈ I∗},

unde χE este functia caracteristica a lui E, este de rang finit.

Demonstratie: Vom arata urmatoarele implicatii: (a) ⇒ (b), (b) ⇒ (c), (c) ⇒ (a).(a) ⇒ (b).Fie AF = (Σ, I, f, s0, Σf ) automatul finit care recunoaste limbajul E. Definim

pe I∗ relatia

ξ = {(p, q)|f(s, p) = f(s, q),∀s ∈ Σ}.Se poate vedea cu usurinta ca ξ este o relatie de echivalenta (reflexiva , simetrica, tranzitiva). In plus , daca r ∈ I∗ si (p, q) ∈ ξ, atunci (pr, qr) ∈ ξ si (rp, rq) ∈ ξ.De exemplu, prima apartenenta se deduce astfel

f(s, pr) = f(f(s, p), r) = f(f(s, q), r) = f(s, qr), etc.


Prin urmare ξ este o relatie de congruenta.Sa aratam ca aceasta congruenta este de rang finit, adica multimea cat I∗/ξ

este finita.Fie α : Σ −→ Σ o aplicatie oarecare si fie multimea

I∗(α) = {p|p ∈ I∗, f(s, p) = α(s),∀s ∈ Σ}.Sa observam ca daca α este functia identica atunci λ ∈ I∗(α). Deci nu toate

I∗(α) sunt vide; ın acest caz I∗(α) este o clasa de echivalenta. Intr-adevar, fiep ∈ I∗(α) ⊆ I∗ fixat si fie Cp clasa de echivalenta a lui p. Aratam ca Cp = I∗(α).Daca q ∈ I∗(α), atunci f(s, q) = α(s),∀s ∈ Σ, ceea ce ınseamna ca f(s, q) =f(s, p),∀s ∈ Σ, si deci (p, q) ∈ ξ adica q ∈ Cp si I∗(α) ⊆ Cp.

Invers daca q ∈ Cp atunci f(s, q) = f(s, p) = α(s),∀s ∈ Σ si q ∈ I∗(α),adica Cp ⊆ I∗(α). Aceasta ınseamna ca I∗(α) = Cp, adica I∗(α) este o clasa deechivalenta .

Intre multimea cat I∗/ξ si multimea functiilor definite pe Σ cu valori ın Σputem stabili urmatoarea corespondenta biunivoca: unei functii α : Σ −→ Σ ıicorespunde clasa de echivalenta I∗(α). Invers, fiind data o clasa de echivalenta C,luam p ∈ C (oarecare) si atasam lui C functia α(s) = f(s, p)∀s ∈ Σ. Tinand contca daca q ∈ C atunci f(s, p) = f(s, q), ∀s ∈ Σ, rezulta ca functia α nu depindede elementul p ales.

Dar multimea functiilor definite pe Σ cu valori ın Σ este finita, deci I∗/ξ estefinita, adica congruenta ξ este de rang finit.

Fie acum p ∈ L(AF ) si q astfel ca (p, q) ∈ ξ. Avem

f(s0, q) = f(s0, p) ∈ Σf ;

adica q ∈ L(AF ). Aceasta ınseamna ca odata cu elementul p, L(AF ) contineclasa de echivalenta a lui p. De aici rezulta ca L(AF ) este constituit dintr-unanumit numar de clase de echivalenta a lui ξ.2

(b)⇒(c)Fie ξ o congruenta de rang finit si E o reuniune de clase de echivalenta. Fie

apoi (p, q) ∈ ξ; aceasta ınseamna ca r1pr2 ∈ E ⇔ r1qr2 ∈ E, deci

χE(r1pr2) = χE(r1qr2),∀r1, r2 ∈ I∗.

Prin urmare, (p, q) ∈ µ. Orice clasa de echivalenta din I∗/ξ este inclusaıntr-o clasa de echivalenta din I∗/µ, asa ıncat card(I∗/µ) < card(I∗/ξ), adicacongruenta µ este de rang finit.2

(c)⇒ (a)Presupunem ca µ este o congruenta de rang finit; consideram automatul finit

AF = (I∗/µ, I, f, Cλ, Σf ), unde functia de evolutie f si multimea de stari finalesunt

f(Cp, i) = Cpi, Σf = {Cp|p ∈ E}.


Vom arata ca E = L(AF ). In primul rand sa observam ca f(Cp, q) = Cpq (sepoate arata prin inductie asupra lui |q|). Avem

p ∈ E ⇔ Cp ∈ Σf ⇔ f(Cλ, p) = Cλp = Cp ∈ Σf ⇔ p ∈ L(AF )

adica E = L(AF ) si E este un limbaj regulat.2

Corolar 2.4 Familia R este ınchisa la operatia de rasturnare.

Demonstratie. Fie E ∈ R si E rasturnatul lui E. Conform teoremei de carac-terizare, card(I∗/µE) < ∞. Avem

(p, q) ∈ µE ⇔ χE(r1pr2) = χE(r1qr2) ⇔

si

χE(r1pr2) = χ

E(r1qr2) ⇔ (p, q) ∈ µE

Cu alte cuvinte daca C este o clasa de echivalenta a lui µE atunci C (rasturnatul

lui C) este o clasa de echivalenta a lui µE. Aceasta ınseamna ca card(I∗/µE) =card(I∗/µE) < ∞ si conform aceleiasi teoreme de caracterizare E ∈ R.2

Observatie. Am vazut ca limbajele de tipul 3 pot fi definite de gramatici cureguli de doua categorii: drept liniare sau stang liniare. Este evident ca limbajelestang liniare sunt rasturnatele limbajelor drept liniare. Cum familia limbajelorregulate (drept liniare) este ınchisa la operatia de rasturnare, rezulta ca cele douafamilii de limbaje coincid.Inchiderea familiei L3 la operatiile Pref si complementariere.

Operatiile Pref si complementariere se definesc ın modul urmator

Pref(E) = {p|∃r ∈ I∗, pr ∈ E}, C(E) = I∗ \ E.

Teorema 2.5 Familia L3 este ınchisa la operatiile Pref si complementariere.

Demonstratie. Fie AF = (Σ, I, f, s0, Σf ) automatul finit care recunoaste limbajulE. Putem presupune ca AF este determinist.

Limbajul Pref(E). Construim automatul finit AF ′ = (Σ, I, f, s0, Σ′f ) unde

Σ′f = {s ∈ Σ|s = f(s0, q), q ∈ Pref(E)}.

Este evident ca Pref(E) ⊆ L(AF ′), caci daca q ∈ Pref(E) atunci s = f(s0, q) ∈Σ′

f conform definitiei lui Σ′f .

Sa aratam acum ca L(AF ′) ⊆ Pref(E). Fie r ∈ L(AF ′), atunci f(s0, q) ∈ Σ′f ,

deci exista q ∈ Pref(E) astfel ıncat f(s0, r) = f(s0, q). Cum q este prefixul unuicuvant din E, exista w ∈ I∗ astfel ıncat qw ∈ E, adica f(s0, q) ∈ Σf . Dar

f(s0, rw) = f(f(s0, r), w) = f(f(s0, q), w) = f(s0, qw) ∈ Σf ,


s 0

s 1 i 1

s j -1

s j = s k

s j +1 s k -1

i j i k +1 s k +1

s n -1 i n

s n

Figura 2.3: Traiectoria automatului finit

deci rw ∈ E si r ∈ Pref(E). Aceasta ınseamna ca L(AF ′) ⊆ Pref(E) si prinurmare Pref(E) = L(AF ′), adica Pref(E) este limbaj regulat.2

Limbajul C(E). Avem

C(E) = {p ∈ I∗|p 6∈ E} = {p ∈ I∗|f(s0, p) 6∈ Σf} = {p ∈ I∗, f(s0, p) ∈ C(Σf )}.

Prin urmare C(E) = L(AFc) unde AFc = (Σ, I, f, s0, C(Σf )}, adica C(E) esteun limbaj regulat.2Lema de pompare pentru limbaje regulate Sub aceasta denumire (sau lemauvw) este cunoscuta o proprietate a limbajelor regulate (ca si a altor familii delimbaje) care ne premite sa descompunem cuvintele suficient de lungi ale limba-jului ın forma uvw si sa multiplicam subcuvantul v de un numar arbitrar de ori,obtinand cuvinte care apartin de asemenea limbajului. Cu alte cuvinte, putemsa ”pompam” ın cuvantul dat o anumita parte a sa. Astfel de leme se utilizeazadeseori pentru a rezolva probleme de neapartenenta, adica pentru a arata ca unanumit limbaj nu apartine unei familii date de limbaje.

Lema 2.2 Fie E un limbaj regulat si AF = (Σ, I, f, s0, Σf ) automatul finit careıl recunoaste. Daca p ∈ E si |p| ≥ card(Σ) atunci p se descompune ın formap = uvw, v 6= λ si uvmw ∈ E, ∀m ∈ N .

Demonstratie. Fie p = i1 . . . in, n ≥ card(Σ); fie s0, s1, . . . , sn starile parcursede automat la citirea cuvantului p. Atunci, sj = f(sj−1, ij), j = 1, n, sn ∈ Σf .Exista ın mod necesar doua stari egale, sj = sk, j < k. Traiectoria va avea obucla (vezi figura 2.3).

Descompunem cuvantul p ın forma p = uvw unde u = i1 . . . ij, v = ij+1 . . . ik, w =ik+1 . . . in. Este clar ca v 6= λ, caci j < k. Pe de alta parte, putem parcurge traiec-toria facand de mai multe ori bucla, adica

f(s0, uvmw) = sn ∈ Σf .

Prin urmare uvmw ∈ E.2


Consecinta 2.3 Incluziunea L3 ⊆ L2 este stricta.

In adevar, fie limbajul L2 = {0n1n|n ≥ 1}. Stim ca acest limbaj este de tipul 2 sica poate fi generat de gramatica G = ({A}, {0, 1}, A, {A → 0A1|01}). Sa aratamca L2 nu este de tipul 3.

Sa presupunem ca L2 este de tipul 3 si fie AF = (Σ, I, f, s0, Σf ) automatulfinit care ıl recunoaste. Cum L2 contine cuvinte oricat de lungi, fie p ∈ L2

astfel ıncat p ≥ card(Σ). Conform lemei de pompare, p se descompune ın formap = uvw, v 6= λ si uvmw ∈ E. Putem avea una din situatiile:

(1) p = 0 . . . 0︸︷︷︸u

0 . . . 0︸︷︷︸v

0 . . . 01 . . . 1︸︷︷︸w

,

(2) p = 0 . . . 01 . . . 1︸︷︷︸u

1 . . . 1︸︷︷︸v

1 . . . 1︸︷︷︸w

,

(3) p = 0 . . . 0︸︷︷︸u

0 . . . 1︸︷︷︸v

1 . . . 1︸︷︷︸w

.

Primele doua cazuri nu pot avea loc deoarece multiplicandu-l pe v, numarul desimboluri 0 si 1 nu s-ar pastra egal. In al treilea caz, luand de exemplu, m = 2obtinem

p2 = 0 . . . 00 . . . 10 . . . 11 . . . 1 ∈ L2

ceea ce din nou nu este posibil, ıntrucat se contrazice structura cuvintelor lui L2.Prin urmare L2 nu este de tipul 3.2

Observatie. Este interesant de observat ca limbajele simple de forma lui L2

sunt semnificative pentru clasele din clasificarea Chomsky. Astfel

L1 = {an|n ≥ 1}, L1 ∈ L3;L2 = {anbn|n ≥ 1}, L2 ∈ L2, L2 6∈ L3;L3 = {anbncn|n ≥ 1}, L3 ∈ L1(?), L3 6∈ L2;

Ne-am putea astepta ca limbajul L3, un exemplu analog lui L2, sa fie de tip1, adica L3 ∈ L1, L3 6∈ L2. In adevar, se poate arata ca L3 6∈ L2, dar dupacunostinta autorului, aparenta L3 ∈ L1 este o problema deschisa.

Consecinta 2.4 Fie E un limbaj regulat si AF = (Σ, I, f, s0, Σf ) automatul finitcare ıl recunoaste. Atunci E este infinit daca si numai daca exista p ∈ E astfelıncat |p| ≥ card(Σ).

Daca limbajul este infinit, este clar ca exista p ∈ E cu |p| ≥ card(Σ). Invers, dacaexista p ∈ E cu |p| ≥ card(Σ) atunci p = uvw, v 6= λ si uvmw ∈ E, ∀m ∈ N ,deci limbajul este infinit.2


2.3 Expresii regulate si sisteme tranzitionale

Expresii regulate Fie V un alfabet. Expresiile regulate sunt cuvinte pestealfabetul V ∪ {•, ∗, |} ∪ {(, )} la care se adauga simbolul ∅, Simbolurile ”|”-sau,”•”-produs, ”∗”-ınchidere, le vom considera operatori. Expresiile regulate sedefinesc astfel:

(1) λ si ∅ sunt expresii regulate;(2) pentru orice a ∈ V , cuvantul a este o expresie regulata;(3) daca R si S sunt expresii regulate, atunci (R|S) (R • S) si (R∗) sunt

expresii regulate;(4) orice expresie regulata se obtine prin aplicarea de un numar finit de ori a

regulilor (1)-(3).Parantezele sunt utilizate pentru a pune ın evidenta ordinea de aplicare a oper-

atorilor. Pentru simplificarea scrierii vom considera ca operatorul ∗ are pondereacea mai mare, apoi operatorul • si | ponderea cea mai mica. Astfel parantezeleredundante pot fi eliminate. De exemplu, prin R|S∗ vom ıntelege (R|(S∗)).

Observatie. Expresiile regulate se pot defini cu ajutorul gramaticii G =({E}, V ∪ {|, •, ∗, (, )}, E, P ) unde

P = {E → (E|E) | (E • E) | (E∗) | a | λ | ∅}.Unei expresii regulate ıi putem asocia un anumit limbaj peste V ; vom spune

ca expresia regulata reprezinta (desemneaza, noteaza) acel limbaj. Modul ın careasociem un limbaj unei expresii regulate este

(1) λ reprezinta limbajul {λ};(1′) ∅ reprezinta limbajul ∅;(2) a reprezinta limbajul {a};(3) daca R si S sunt expresii regulate ce reprezinta limbajele

LR respectiv LS atunci(i) R|S reprezinta limbajul LR ∪ LS;(ii) R • S reprezinta limbajul LRLS;(iii) R∗ reprezinta limbajul (LR)∗.

Fie R, S, P trei expresii regulate si LR, LS, LP limbajele reprezentate. Avem :

L(R|S)|P = (LR ∪ LS) ∪ LP = LR ∪ (LS ∪ LP ) = LR|(S|P ),

ıntrucat operatia de reuniune este asociativa. Vom scrie (R|S)|P = R|(S|P ). Inmod analog se pot obtine si alte proprietati. De exemplu:

S|R = S|R,R|R = R,(R • S) • P = R • (S • P ),R • (S|P ) = (R • S)|(R • P ), etc.

2.3. EXPRESII REGULATE SI SISTEME TRANZITIONALE 35

In cazul ın care nu exista pericol de confuzie, vom nota cu L (fara indice) limbajulreprezentat de o anumita expresie regulata.

Exemple.

1. R = a∗; L =⋃∞

j=0{aj} = {λ, a, a2, . . .}.2. R = aa∗; L = a • {λ, a, a2, . . .} = {a, a2, a3 . . .}.3. R = (a|b)∗; L = (La ∪ Lb)

∗ = ({a} ∪ {b})∗ = {a, b}∗;{a, b}∗ = {λ}∪{a, b}1∪{a, b}2∪ . . . = {λ, a, b, aa, ab, ba, bb, . . .}, adica(a|b)∗ reprezinta multimea tuturor cuvintelor peste alfabetul {a, b}.4. R = a|ba∗; L = {a} ∪ {b} • {λ, a, a2, . . .} = {a, b, ba, ba2, . . .}.

Limbajele reprezentate de expresii regulate constituie o anumita familie de lim-baje; o vom nota cu Llr. Apare urmatoarea problema: care este pozitia acesteifamilii ın ierarhia Chomsky? Vom arata ca Llr coincide cu familia limbajelorregulate.

Sisteme tranzitionale

Definitie 2.3 Un sistem tranzitional este un sistem de formaST = (Σ, I, f, Σ0, Σf , δ)

unde:

Σ este o multime (finita) de stari;I este alfabetul de intrare;f : Σ× I −→ P(Σ) este functia de tranzitie;Σ0 ⊆ Σ este multimea de stari initiale;Σf ⊆ Σ este multimea de stari finale;δ ⊂ Σ× Σ este relatia de tranzitie .

Exemplu. Σ = {s0, s1, s2}, I = {0, 1}, Σ0 = {s0, s1}, Σf = {s2} iar functia sirelatia de tranzitie sunt date de:

f s0 s1 s2

0 {s1} {s2} {s0}1 ∅ {s0, s1} {s0, s2}

δ = {(s0, s1), (s2, s1)}.Ca si ın cazul unui automat finit putem construi diagrama de stari completata

cu relatia δ (arcele punctate). In cazul exemplului nostru diagrama de stari esteprezenta ın figura 2.4

Observatie: δ fiind o relatie, are sens δ∗ (ınchiderea tranzitiva si reflexiva).Fie i ∈ I∪{λ}; vom spune ca sistemul tranzitional evolueaza direct din starea

s′ ın starea s′′ daca:(1) i = λ si (s′, s′′) ∈ δ∗. Pe diagrama de stari vom avea o traiectorie punctata

de la starea s′ la starea s′′;

s′ −→ O −→ O −→ . . . −→ O −→ s′′.


s 0

s 2

s 1

0

0

1

1

0,1

1

Figura 2.4: Diagrama de stari a sistemului tranzitional

(2) i 6= λ si exista s1, s2 ∈ Σ astfel ıncat (s′, s1) ∈ δ∗, s2 ∈ f(s1, i) si (s2, s′′) ∈

δ∗. Pe diagrama de stari, putem ajunge din s′ ın s′′ pe o traiectorie punctata,apoi un pas pe un arc plin si din nou pe o traiectorie punctata.

s′ −→ O −→ . . . −→ s1i−→ s2 −→ O −→ . . . −→ s′′.

Vom scrie s′i

` s′′.Fie acum p = i1 . . . in. Vom spune ca sistemul evolueaza din starea s′ ın starea

s′′ daca exista s0, s1, . . . , sn astfel ıncat

s′ = s0

i1` s1

i2` . . .in` sn = s′′.

Vom scrie s′p

` s′′.

Definitie 2.4 Limbajul recunoscut de un sistem tranzitional ST este

L(ST ) = {p|p ∈ I∗, ∃s0 ∈ Σ0, s0

p

` s, s ∈ Σf}.Vom nota cu LST familia limbajelor recunoscute de sisteme tranzitionale. Este ev-ident ca orice automat finit este un sistem tranzitional particular ın care card(Σ0) =1 iar δ = ∅ (nu exista arce punctate). Prin urmare R ⊆ LST .

Teorema 2.6 R = LST .

Demonstratie. Evident, trebuie sa aratam incluziunea LST ⊆ R. Fie ST =(Σ, I, f, Σ0, Σf , δ) un sistem tranzitional. Construim automatul finit AF = (P(Σ), I, f ′, Σ0, Σ

′f )

unde

f ′(Z, i) = {s|∃s′ ∈ Z, s′i

` s},Σ′

f = {Z|Z ∩ Σf 6= ∅}.

2.4. ANALIZA LEXICALA 37

s 0 s 1 a

s 0 s 0 s 1 s 1

Figura 2.5: Sistemele tranzitionale ce recunosc limbajele λ, a, ∅.

Fie p = i1 . . . in ∈ L(ST ) si fie urmatoarea evolutie a sistemului tranzitional

s0

i1` s1

i2` . . .in` sn ∈ Σf .

Putem construi o traiectorie a lui AF de forma

Σ0i1−→ Z1

i2−→ . . .in−→ Zn,

unde Z1 = f ′(Σ0, i1), Zk = f ′(Zk−1, ik), k = 2, . . . , n. Sa observam ca s0 ∈Σ0 si ca daca sk−1 ∈ Zk−1, atunci conform definitiei functiei f ′, avem sk ∈f ′(Zk−1, ik) = Zk. Asftel, sk ∈ Zk, k = 1, . . . , n; pentru k = n avem sn ∈ Zn sicum sn ∈ Σf rezulta ca Zn ∩ Σf 6= ∅, adica Zn ∈ Σ′

f . Deci automatul ajungeıntr-o stare finala, p ∈ L(AF ) si L(ST ) ⊆ L(AF ).

Incluziunea inversa se arata ın mod analog.2Constructia sistemelor tranzitionale pentru expresii regulate. Fiind datao expresie regulata putem ıntotdeauna construi un sistem tranzitional care re-cunoaste limbajul reprezentat de expresia respectiva.

Constructia se face cu ajutorul diagramelor de stari.Sistemele tranzitionale (diagramele de stari) corespunzatoare expresiilor reg-

ulate λ, a si ∅ sunt prezentate ın figura 2.5.Daca R si S sunt expresii regulate si notam cu STR si STS sistemele tranzitionale

corespunzatoare, atunci sistemele tranzitionale pentru R|S, R • S si R∗ sunt re-date ın figura 2.6.

In acest mod putem construi succesiv (recurent) un sistem tranzitional core-spunzator unei expresii regulate.

Exemplu. Sistemul tranzitional corespunzator expresiei R = a|b•a∗ este redatın figura 2.7.

Consecinta Dandu-se o expresie regulata, putem construi sistemul tranziti-onal care recunoaste limbajul reprezentat de expresia respectiva. Cum oricelimbaj recunoscut de un sistem tranzitional este regulat, rezulta ca limbajelereprezentate de expresii regulate sunt limbaje regulate.

2.4 Analiza lexicala

Procesul de analiza lexicala este o faza a procesului de compilare ın care se deter-mina unitatile lexicale (cuvintele, atomii) ale unui program sursa, se furnizeaza


ST S

ST R

ST R ST L

ST R

Figura 2.6: Sistemele tranzitionale ce recunosc limbajele R|S, R • S si

a

a

b

Figura 2.7: Sistemul tranzitional corespunzator expresiei regulate


codurile interne ale acestora si se detecteaza eventualele erori lexicale. Analizorullexical mai poate efectua o serie de operatii auxiliare precum: eliminarea blank-urilor, ignorarea comentariilor, diferite conversiuni ale unor date, completareatabelelor compilatorului, gestiunea liniilor textului sursa.Unitati lexicale O unitate lexicala (Lexic = vocabular; totalitatea cuvintelorunei limbi) este o secventa din textul sursa care are o anumita unitate logica.Definitia riguroasa a unitatilor lexicale ale unui limbaj particular se da la definirealimbajului de programare respectiv. De obicei, ın majoritatea limbajelor de pro-gramare, unitatile lexicale sunt: cuvinte cheie, identificatori, constante, operatori,delimitatori. Din punctul de vedere al analizei lexicale si al modului de prelucrare,unitatile lexicale pot fi de doua categorii:

• Unitati lexicale simple, sunt unitati lexicale care nu comporta atribute su-plimentare, de exemplu, cuvintele cheie, operatorii;

• Unitati lexicale compuse (atributive), sunt unitati lexicale care comportaanumite atribute suplimentare, de exemplu, identificatorii si constantele.Atributele sunt informatii specifice, de exemplu, tipul identificatorului saual constantei (ıntreg, real, etc.). Este necesara specificarea tipului unuiidentificator sau al unei constante din startul programului deoarece struc-tura programului obiect sau reprezentarea interna a constantelor depindede acest tip.

Reprezentarea interna a unitatilor lexicale se face ın functie de categoria lor.Cele simple se reprezinta printr-un cod specific(numar ıntreg). Unitatile lexicalecompuse se reprezinta prin cod si informatii (de natura semantica) asupra sa.De obicei compilatoarele utilizeaza tabele pentru stocarea atributelor (tabel deconstante, tabel de variabile, tabel de etichete, etc.). In acest caz unitatea lexicalase reprezinta intern printr-un cod urmat de o referinta ıntr-un tabel. Informatiacontinuta de tabel ar putea fi pentru constante: cod, tip, valoare, iar pentruidentificatori: cod, tip, indicator de initializare.

Este posibil ca o clasa de unitati lexicale simple sa se reprezinte printr-uncod unic si un atribut pentru distingerea ın cadrul clasei. De exemplu, operatoriiaritmetici cu aceiasi prioritate au o tratare similara din punct de vedere al anal-izei sintactice. Lista unitatilor lexicale si definitia riguroasa a acestora se da laproiectarea compilatorului.

Un exemplu de unitati lexicale si coduri asociate ar putea fi cele din figura2.8.

Analizorul primeste textul sursa si produce sirul de unitati lexicale ın codifi-carea interna. De exemplu secventa de text sursa urmatoare:

{if (unu < 2) return 0;

a=33;

}


Unitate lexicala COD ATRIBUT Exemplu

if if = 1 - if, If, IFelse else = 2 - else ElSe

identificator ID = 3 referinta Nelu v tabelconstanta ıntreaga NUM = 4 referinta 4 -3 233

constanta reala FLOAT = 5 referinta 4.32 -3.233+ op = 6 1- op = 6 2× op = 6 3/ op = 6 4< opr = 7 1> opr = 7 2

<= opr = 7 3>= opr = 7 4( LPAR = 8 -) RPAR = 9 -{ LBRACE = 10 -} RBRACE = 11 -

Figura 2.8: Coduri asociate unitatilor lexicale


va produce sirul de unitati lexicaleLBRACE If LPAR [ID,22] [opr,1] [NUM, 40], RPAR RETURN [NUM, 42] SEMI[ID,24] opAssign [NUM,44] SEMI RBRACE.

In lista codurilor interne gasite atributul identificatorului este adresa relativadin tabela de identificatori, analog atributele constantelor numerice sunt adreserelative ın tabelele de constante.

Majoritatea limbajelor evoluate contin si secvente de text care nu sunt unitatilexicale, dar au actiuni specifice asociate . De exemplu:

comentarii /* text */

directive de preprocesare #include<stdio.h>

#define MAX 5.6

Inaintea analizei lexicale (sau ca subrutina) se preproceseaza textul si abiaapoi se introduce rezultatul ın analizorul lexical.Specificarea unitatilor lexicale Definirea riguroasa a unitatilor lexicale se facede catre proiectantul limbajului. O posibilitate de descriere este limbajul natural.De exemplu, pentru C si JAVA:

”Un identificator este o secventa de litere si cifre: primul caracter trebuie safie litera. Liniuta de subliniere conteaza ca litera. Literele mari si mici suntdiferite. Daca sirul de intrare a fost ımpartit ın unitati lexicale pana la un carac-ter dat, noua unitate lexicala se considera astfel ıncat sa includa cel mai lung sirde caractere ce poate constitui o unitate lexicala. Spatiile, taburile, newline si co-mentariile sunt ignorate cu exceptia cazului cand servesc la separarea unitatilorlexicale. Sunt necesare spatii albe pentru separarea identificatorilor, cuvintelorcheie si a constantelor.”

Orice limbaj rezonabil poate fi folosit pentru implementarea unui analizorlexical.

Unitatile lexicale se pot specifica cu ajutorul limbajelor regulate, deci folosindgramatici de tipul 3 sau expresii regulate ce noteaza limbajele. Ambele specificatiiconduc la construirea de automate finite echivalente, care se pot usor programa.In cele ce urmeaza, vom folosi ambele variante de specificare pentru un set uzualde unitati lexicale ıntalnit la majoritatea limbajelor evoluate.

Consideram gramatica regulata ce genereaza identificatori, constante ıntregi,cuvinte cheie, operatori relationali si aritmetici.

G :

< ul >→< id > | < num > | < cc > | < op > | < opr >< id >→ l < id1 > |l, < id1 >→ l < id1 > |c < id1 > |l|c< num >→ c < num > |c< cc >→ if |do|else|for< op >→ +| − | ∗ |/< opr >→< | <= | > | >=

,


unde l-litera, c-cifra.Pornind de la aceasta gramatica se poate construi una echivalenta ın forma

normala, apoi se extrage functia de evolutie a automatului finit deterministechivalent ce recunoaste unitatile lexicale.

Descrieri echivalente ale unitatilor lexicale cu ajutorul expresiilor regulate sunt

cuvinte cheie = if | do | else | for

identificatori = ( a|b|c|...z )( a|b|c|...z|0|1|...|9 )*

Numar = ( 0|1|...|9 )( 0|1|...|9 )*

Operatori aritmetici = + | - | * | /

Operatori relationali = < | <= | > | >=

Limbajul generat de gramatica precedenta se obtine prin suma expresiilorregulate. Mentionam ca exista programe specializate (Lex, Flex, JavaCC) cegenereaza un analizor lexical (ın C sau Java) pornind de la expresiile regulate.Sintaxa folosita ın scrierea expresiilor regulate este dependenta de programulfolosit.Programarea unui analizor lexical Realizarea efectiva a unui analizor revinela simularea functionarii unui automat finit. O varianta de programare esteatasarea unei secvente de program la fiecare stare a automatului. Daca stareanu este stare finala atunci secventa citeste urmatorul caracter din textul sursa sigaseste urmatorul arc din diagrama de stari. Depinzand de rezultatul cautariise transfera controlul altei stari sau se returneaza esec (posibila eroare lexicala).Daca starea este finala atunci se apeleaza secventa de returnare a codului unitatiilexicale si eventuala instalare a unitatii lexicale ın tabelele compilatorului.

Pentru simplificarea implementarii se cauta urmatoarea unitate lexicala prinıncercarea succesiva a diagramelor corespunzatoare fiecarei unitati lexicale (ıntr-o ordine prestabilita). Eroarea lexicala se semnaleaza doar atunci cand toateıncercarile se ıncheie cu esec.

De obicei textul sursa contine si secvente ce se pot descrie cu ajutorul expresi-ilor regulate, dar care nu sunt unitati lexicale (de exemplu comentariile). Acestesecvente nu vor genera cod lexical, dar au asociate diverse actiuni specifice. Pen-tru a evita aparitia unor caractere necunoscute in textul sursa se considera silimbajul ce consta din toate simbolurile ASCII. Astfel, indiferent de unde ıncepeanaliza textului, programul de analiza lexicala gaseste o potrivire cu o descriere.Spunem ca specificatia este completa.

Exista posibilitatea ca mai multe secvente cu aceeasi origine sa corespunda ladiferite descrieri ale unitatilor lexicale. Se considera unitate lexicala cel mai lungsir ce se potriveste unei descrieri (longest match rule). Daca sunt doua reguli


care se potrivesc la acelasi sir de lungime maxima atunci se considera o prioritateasupra descrierilor (rule priority).

De exemplu, in textul urmator,

i if if8

unitatile lexicale delimitate vor fi i–identificator, if–cuvant cheie, if8–identificator.Regula de prioritate se aplica pentru potrivirea lui if cu identificator si cuvantcheie, iar criteriul de lungime maxima pentru if8.

Pentru depistarea celei mai lungi potriviri, din punt de vedere al programariianalizorului, este suficient sa prevedem un pointer suplimentar pe caracterul cecorespunde ultimei stari finale atinse pe parcursul citirii.Studiu de caz. Se considera problema realizarii unui analizor lexical ce delim-iteaza ıntr-un text sursa cuvinte din limbajul ce contine identificatori, cuvintecheie (pentru simplificare folosim doar cuvantul cheie if), constante numerice(ıntregi fara semn). De asemenea se face salt peste spatiile albe si se ignora co-mentariile. Presupunem ca un comentariu ıncepe cu doua caractere slash si setermina cu newline. Orice caracter ce nu se potriveste descrierii este semnalat casi caracter ilegal in text.

Etapa I. Descriem secventele cu ajutorul expresiilor regulate

IF = "if"

ID = (a|b|c|...|z)(a|b|c|...|z|0|1|...|9)*

NUM = (0|1|...|9)(0|1|...|9)* = (0|1|...|9)+

WS = (\n|\t|" ")+

COMMENT = "//"(a|b|c|...|z|0|1|...|9|" ")*\n

ALL = a|b|...|z|0|...|9|\t| ... toate caracterele ASCII

Etapa II. Corespunzator expresiilor avem urmatoarele automate finite deter-ministe echivalente, prezentate ın figura 2.9 (starile au fost notate prin numereıntregi):

Etapa III. Se construieste sistemul tranzitional (vezi figura 2.10) ce re-cunoaste limbajul reuniune, adaugand o noua stare initiala (notata cu 1), pecare o conectam prin arce punctate (ce corespund λ-tranzitiilor). Constructiaprovine din legarea sistemelor tranzitionale ın paralel. S-au renumerotat starilesistemului tranzitional, asignand nume simbolice starilor finale.

Etapa III. Constructia automatului finit determinist general ce recunoastereuniunea limbajelor. Pentru aceasta sistemul tranzitional se transforma cu teo-rema de echivalenta ın automat finit determinist (practic se trece de la stari alesistemului tranzitional la submultimi de stari, ce devin starile automatului finit).


4

2 1

2 1

2 1

3 2 1

a- z

0- 9

/ / \ n

0- 9

0- 9 a - z

\ n\ t \ b

\ n\ t \ b

2 1

ID

NUM

WS

COM

ERR orice

a- z ,\b

Figura 2.9: Automatele finite corespunzatoare expresiilor regulate

In cazul particular al automatului nostru, diagrama de stari este data ın figura2.11.

Etapa IV. Programarea analizorului lexical.Automatul finit obtinut are starile finale asociate cu clasele de cuvinte recunos-

cute. Se asociaza actiuni starilor finale, corespunzator definitiilor unitatilor lexi-cale (de exemplu pentru constante numerice se genereaza reprezentarea interna, sememoreaza ın tabelul de constante si se returneaza codul unitatii lexicale NUM).Pentru programarea analizorului se folosesc trei variabile de tip pointer in textulsursa: FirstSymbol, CurrentSymbol, LastFinalSymbol, ce retin indicele carac-terului de ınceput al secventei, indicele caracterului ce urmeaza la citire, indiceleultimului caracter ce corespunde atingerii unei stari finale. Cei trei pointeri aufost reprezentati prin semnele grafice |, ⊥ respectiv >. De asemenea consideramo variabila State, ce retine starea curenta a automatului.

In tabelul 2.12 este indicata evolutia analizorului lexical (inclusiv actiunileasociate) pentru cazul analizei urmatorului text sursa.

if if8%// ha\n

Pentru simplificarea codificarii, starile automatului finit determinist au fostredenumite prin numere ıntregi ıncepand cu starea initiala 1, starea {3, 6, 16} = 2,{4, 6} = 3, {6, 16} = 4, s.a.m.d. de la stanga la dreapta si de sus ın jos. De obicei


14

3 2

10 9

8 7

6 5

13 12 11

4 i f

a - z

0- 9

/ / \ n

0- 9

0- 9 a - z

a - z

\ n\ t \b

\ n\ t \ b

,\b

16 15

IF

ID

NUM

WS

COM

ERR orice

1

Figura 2.10: Sistemul tranzitional ce recunoaste reuniunea limbajelor


3,6,16 4,6

12,16

6,16

10,16

8,16

13

1

6

14

16

ID IF f

i ID

ID NUM

WS

ERR / \ n

COM

ERR

a- e g - z

0-9 a- z 0-9 a- z

0-9 a- z

0-9

a-h j - z

0-9

/

a- z , \b

\ n\ t \b

orice altceva

0-9

\ n\ t \b

Figura 2.11: Automatul finit determinist ce recunoaste reuniunea limbajelor


int edges[][] = { /* ... 0 1 2 ... e f g h i j ... */

/* state 0 */ {0,0, ...,0,0,0, ...,0,0,0,0,0,0, ... },

/* state 1 */ {0,0, ...,6,6,6, ...,4,4,4,4,2,4, ... },

/* state 2 */ {0,0, ...,5,5,5, ...,5,3,5,5,5,5, ... },

etc

}

Figura 2.13: Reprezentarea functiei de evolutie a automatului finit

functia de evolutie asociata automatului finit determinist se memoreaza sub formaunui tablou bidimensional de ıntregi, ca ın figura 2.13. Starea 0 este asociata cublocarea automatului. Ajungerea ın aceasta stare echivaleaza cu gasirea ultimeiunitati lexicale, ıntre pointerii | si >. Se executa actiunea asociata starii finalesi se reia cautarea (resume) urmatoarei unitati lexicale ıncepand cu caracterulimediat urmator pointerului >.

Observatie: Cele mai costisitoare operatiuni (ca timp) din analiza lexicalasunt ignorarea comentariilor si tratarea erorilor lexicale. Primele generatoareautomate de analizoare lexicale si sintactice au aparut ın anii ′70 si au fost incluseın sistemul de operare Unix.


1. Construiti automate finite pentru recunoasterea limbajelor:

(a) L = {PSDR,PNL, PUNR};(b) L = {w| siruri de 0 si 1 terminate cu 1 };(c) L = {w|w identificator PASCAL };(d) L = {w|w constanta ıntreaga cu semn ın PASCAL };(e) L = {w ∈ {0, 1}∗|w multiplu de 3 };(f) L = {aibj|i, j > 0};(g) L = ∅.

2. Construiti automate finite echivalente cu gramaticile de tipul trei de laproblema 1 capitolul 1.


3. Construiti automate finite deterministe echivalente cu cele nedeterministeobtinute la problema precedenta.

4. Gasiti gramatici regulate echivalente cu automatele de la problema 1.

5. Folosind lema de pompare pentru limbaje regulate dovediti ca urmatoarelelimbaje nu sunt regulate:

(a) L = {0i2|i ≥ 1};(b) L = {02n |n ≥ 1};(c) L = {0n|n este numar prim };(d) L = {0m1n0m+n|m ≥ 1, n ≥ 1};

6. Specificati limbajele denotate de urmatoarele expresii regulate:

(a) (11|0)∗(00|1)∗;

(b) (1|01|001)∗(λ|0|00);

(c) 10|(0|11)0∗1;

(d) ((0|1)(0|1))∗;

(e) 01∗|1;

(f) ((11)∗|101)∗.

7. Construiti sisteme tranzitionale ce recunosc limbajele specificate la prob-lema precedenta. Pentru fiecare sistem tranzitional construiti un automatfinit determinist echivalent.

Capitolul 3

Limbaje Independente deContext

3.1 Arbori de derivare

Caracterizarea familiei L2 cu arbori de derivare. Una din caracteristicilede baza ale limbajelor independente de context este aceea ca o derivare ıntr-unastfel de limbaj poate fi reprezentata de un arbore, numit in acest context arborede derivare. Aceasta reprezentare este importanta ın mod special pentru faptulca permite o imagine intuitiva simpla a unei derivari si deci posibilitatea de alucra usor cu limbaje de tipul 2.

Vom prezenta ın primul rand cateva notiuni elementare de teoria grafurilor,cu scopul de a preciza notatiile si terminologia.

Un graf orientat G este o pereche G = (V, Γ) unde V este o multime finitaiar Γ o aplicatie Γ : V −→ P(V ). Multimea V se numeste multimea varfurilor(nodurilor) grafului iar daca v2 ∈ Γ(v1), perechea (v1, v2) este un arc ın graf; v1

este originea iar v2 este extremitatea arcului. Un drum de la vırful v′ la varfulv′′ ın graful G este o multime de arce (v1, v2)(v2, v3) . . . (vn−1, vn) cu v′ = v1 siv′′ = vn. Numarul n − 1 este lungimea drumului. Un drum pentru care v1 = vn

se numeste circuit. Un circuit de lungime 1 poarta numele de bucla.

Definitie 3.1 Un arbore este un graf fara circuite, cu card(V ) ≥ 2 si care sat-isface urmatoarele doua conditii :

1. ∃v0 ∈ V astfel ıncat v0 6∈ Γ(v),∀v ∈ V ; v0 se numeste radacina arbore-lui;

2. ∀v ∈ V \ {v0}, ∃!w cu v ∈ Γ(w); altfel spus orice varf diferit de v0 esteextremitatea unui singur arc.

Exemplu. V = {v0, v1, v2, v3, v4} iar functia Γ este data de:

x v0 v1 v2 v3 v4

Γ(x) {v1, v2} ∅ {v3, v2} ∅ ∅

51

52 CAPITOLUL 3. LIMBAJE INDEPENDENTE DE CONTEXT

v 0

v 2

v 4 v 3

v 1

Nivel 0

Nivel 1

Nivel 2

Figura 3.1: Reprezentarea grafica a arborelui G = (V, Γ).

Reprezentarea ın plan a acestui arbore este data in figura 3.1Nodurile v pentru care Γ(v) = ∅ se numesc noduri terminale (finale); celelalte

se numesc interne. Multimea nodurilor terminale constituie frontiera arborelui.In general vom nota un arbore cu litere mari, specificınd ca indici radacina si fron-tiera; de exemplu Av0, v1v2v3 . Un arbore comporta mai multe ramuri; ın exempluavem urmatoarele ramuri : v0v1, v0v2v3, v0v2v4.

Fie G = (VN , VT , S, P ) o gramatica de tipul 2.

Definitie 3.2 Un arbore de derivare ın gramatica G este un arbore cu urmatoareledoua proprietati .

(1) Nodurile sunt etichetate cu elementele din VG;(2) Daca un nod v are descendenti directi v1, . . . , vn atunci

v → v1v2 . . . vn ∈ P .

Exemplu. G = ({A, B}, {a, b}, A, P ) unde

P = {A → aBA|Aa|a,B → AbB|ba|abb}.

Arborele AA, aabbaa reprezentat ın figura 3.2 (Varianta 1) este un arbore dederivare (poate fi desenat coborand frontiera pe nivelul ultim , Varianta 2):

Teorema 3.1 Fie G o gramatica de tipul 2. Atunci X∗⇒p daca si numai daca

exista un arbore AX, p.

Demonstratie. X∗⇒p implica ∃AX, p.

Procedam prin inductie asupra lungimii derivarii l.Daca l = 1, X ⇒ p = i1 . . . in si X → i1 . . . in ∈ P . Arborele din figura 3.3corespunde cerintelor teoremei.

3.1. ARBORI DE DERIVARE 53

A

A B

a a

B

b b a a

Varianta 2

A

A

A B a

a B b

b a a

A

Varianta 1

Figura 3.2: Variante de reprezentare a arborelui AA, aabbaa.

X

i n i 2 i 1 . . .

Figura 3.3: Arbore corespunzator unei derivari directe.


X

X m X 2 X 1 . . .

p 1 p 2 p m . . .

Figura 3.4: Constructia arborelui AX,p1...pm .

Presupunem ca proprietatea este adevarata pentru derivari de lungime l siconsideram o derivare de lungime l+1, X

∗⇒p. Punem ın evidenta prima derivaredirecta

X⇒X1 . . . Xn∗⇒p

Conform lemei de localizare, p = p1 . . . pn si Xj∗⇒pj, j = 1,m. Putem face

urmatoarea constructie: conform ipotezei inductive, fiecarei derivari Xj∗⇒pj ıi

corespunde cate un arbore AXj ,pj; unim apoi toate nodurile Xj ın nodul X plasat

la nivelul zero. Obtinem astfel un arbore AX,p1...pm = AX,p (vezi figura 3.4) carecorespunde cerintelor teoremei.

Pentru implicatia , ∃AX,p ⇒ X∗⇒p, se parcurge o cale inversa, facand

o inductie asupra numarului de nivele. De exemplu, daca acest numar este 2,arborele de derivare trebuie sa arate ca ın 3.3 si deci avem X → i1i2 . . . in = p ∈ Psi X

∗⇒p, etc. 2

3.2 Ambiguitate ın familia L2.

Fie G o gramatica de tipul 2. O derivare S = u0 ⇒ u1 ⇒ . . . ⇒ un ın carela fiecare derivare directa se ınlocuieste simbolul neterminal cel mai din stanga(dreapta) se numeste derivare extrem stanga (dreapta). Sa observam ca ın par-ticular ıntr-o gramatica de tipul 3 orice derivare este extrem dreapta (scriereadrept liniara).

Definitie 3.3 O gramatica G de tipul 2 ın care exista un cuvant p ∈ L(G) carese poate obtine cu doua derivari extrem stangi (drepte) distincte, se numesteambigua. In caz contrar este neambigua.

3.2. AMBIGUITATE IN FAMILIA L2. 55

Exemplu. Gramatica A → aBA|Aa|a, B → AbB|ba|abb este ambigua. Intr-adevar, avem

A⇒aBA⇒aBa⇒aAbBa⇒aAbbaa⇒aabbaa;

A⇒Aa⇒aBAa⇒aBaa⇒aabbaa.

Definitie 3.4 Un limbaj este ambigu daca toate gramaticile care ıl genereazasunt ambigue. In caz contrar (adica daca exista o gramatica neambigua care saıl genereze) limbajul este neambigu.

Daca G este ambigua si p ∈ L(G) este un cuvant care se poate obtine cu douaderivari extrem stangi distincte, atunci exista arborii AS, p si A′

S, p, diferiti, darcare au aceiasi radacina si frontiera.

Teorema 3.2 Daca L1 si L2 sunt limbaje disjuncte neambigue, atunci L1 ∪ L2

este neambigu.

Demonstratie. Fie Gk = (VNk, VTk

, Sk, Pk), k = 1, 2 doua gramatici de tipul 2neambigue si fie G = (VN1 ∪ VN2 , VT1 ∪ VT2 , S, P1 ∪ P2 ∪ {S → S1|S2}) gramaticace genereaza limbajul L(G1) ∪ L(G2).

Sa presupunem ca L(G) este ambigua. Atunci exista p ∈ L(G) care se poateobtine cu doua derivari extreme stangi diferite. Sa presupunem ca p ∈ L(G1), p 6∈L(G2). Atunci obtinem doua derivari distincte ın gramatica G

(1) S ⇒G

S1∗⇒G

p, deci S1∗⇒

G1

p;

(2) S ⇒G

S1∗⇒G

p, deci S1∗⇒

G2

p,

deci si doua derivari extrem stangi ın gramatica G1. Aceasta ar ınsemna ca G1

este ambigua. Contradictie cu ipoteza!2

Teorema 3.3 Limbajele de tipul 3 sunt neambigue.

Demonstratie. Fie L un limbaj de tipul 3 si G gramatica care ıl genereaza; fie apoiAF automatul finit care recunoaste limbajul L si AFD automatul finit echivalentdeterminist. Construim gramatica G′ astfel ıncat L(G′) = L(AFD). Reamintimca regulile lui G′ se construiesc astfel f(A, a) = B ⇒ A → aB, f(A, a) ∈ Σf ⇒A → a.

Sa presupunem acum ca L este ambigu; atunci orice gramatica care ıl genereaza,inclusiv G′, este ambigua. Aceasta ınseamna ca exista un p ∈ L(G′) astfel ıncat

S⇒i1A1⇒i1i2A2⇒ . . .⇒i1 . . . in−1An−1

{⇒ i1 . . . inA′

n ⇒⇒ i1 . . . inA′′

n ⇒}

∗⇒p.

Deci exista regulile An−1 → inA′n si An−1 → inA

′′n, adica ın automatul AFD

avem

f(An−1, in) = A′n, f(An−1, in) = A′′

n,

ceea ce contrazice faptul ca AFd este determinist.2


3.3 Forme normale pentru gramatici de tipul 2

Forma normala Chomsky.

Definitie 3.5 O gramatica ın forma normala Chomsky este o gramatica cu regulide forma

A → BC,D → i,

unde A,B, C, D ∈ VN si i ∈ VT . Se accepta si regula de completare S → λ cuconditia ca S sa nu apara ın dreapta vreunei reguli.

Lema 3.1 (lema substitutiei). Fie G o gramatica de tipul 2 si X → uY v precumsi Y → p1 . . . pn toate regulile din G care au Y ın stanga . Atunci G este echiva-lenta cu o gramatica G′ ın care am facut ”substitutiile”; adica facem urmatoareaınlocuire

X → uY v se ınlocuieste cu X → up1v| . . . |upnv(Regulile Y → p1| . . . |pn le vom pastra neschimbate).

Demonstratie. Fie p ∈ L(G) si S∗⇒p. Punem ın evidenta doi pasi consecutivi

oarecare:

G : S∗⇒r⇒s⇒t

∗⇒p.

Daca ın r⇒s se utilizeaza regula X → uY v atunci ın mod necesar ın pasulurmator se utilizeaza una din regulile Y → p1| . . . |pn, sa presupunem Y → pj

(evident, este posibil ca aceasta regula sa nu se aplice ın pasul imediat urmator,dar ea poate fi ”adusa” ın aceasta pozitie). Prin urmare

(A) G : r = r′Xr′′⇒r′uY vr′′⇒r′upjvr′′ = t.

Acesti doi pasi se pot obtine si ın G′ (ıntr-un singur pas):

(B) G′ : r = r′Xr′′⇒r′upjr′′ = t.

Deci S∗⇒G′

p, p ∈ L(G′) si L(G) ⊆ L(G′).

Invers, daca p ∈ L(G′) si S∗⇒G′

p, atunci daca la un pas se utilizeaza o regula

nou introdusa (pasul (B)), transformarea respectiva se poate obtine si ın G cudoi pasi (pasii (A)); deci p ∈ L(G) si L(G′) ⊆ L(G).2

Corolar 3.4 Orice gramatica de tipul 2 este echivalenta cu o gramatica de acelasitip ın care multimea de reguli nu contine redenumiri. (O redenumire este o regulade forma A → B, A, B ∈ VN).

3.3. FORME NORMALE PENTRU GRAMATICI DE TIPUL 2 57

Intr-adevar, daca A → B ∈ P este o redenumire si B → p1| . . . |pn sunt toateregulile care au B ın stanga, efectuam substitutiile, deci ınlocuim regula A → Bcu A → p1| . . . |pn. In cazul ın care printre acestea apare o noua redenumire,repetam procedeul.2

Exemplu. Gramatica GE care genereaza expresii aritmetice E → E+T |T, T →T ∗ F |F, F → (E)|i se poate pune sub urmatoarea forma (fara redenumiri) :

E → E + T |T ∗ F |(E)|iT → T ∗ F |(E)|iF → (E)|i

Teorema 3.5 (teorema lui Chomsky de existenta a formei normale). Orice gra-matica independenta de context este echivalenta cu o gramatica ın forma normalaChomsky. ema2

Demonstratie. Putem porni de la o gramatica G care nu are redenumire si ale careireguli cu terminale au forma A → i, A ∈ VN , i ∈ VT . De asemenea presupunemca G nu are reguli de stergere.

Rezulta ca regulile lui G au una din formele:(1) A → BC,(2) D → i,(3) X → X1 . . . Xn, n > 2.Construim o gramatica G′ = (V ′

N , VT , S, P ′) unde VN ⊆ V ′N si P ′ contine toate

regulile din P de forma (1) si (2). Fiecare regula de forma (3) o ınlocuim cu:

X → X1Z1,Z1 → X2Z2,. . .Zn−2 → Xn−1Xn

si includem neterminalele Z1, . . . , Zn−2 (altele pentru fiecare regula de forma (3)ın V ′

N .Se poate relativ usor arata ca L(G) = L(G′). De exemplu, daca u⇒v (direct)

ın G si de aplica o regula de forma (1) sau (2), atunci evident derivarea respectivase poate obtine si ın G′; ın cazul ın care se aplica o regula de forma (3), avem

G : u = u′Xu′′⇒u′X1 . . . Xnu′′

= v.

Aceasta derivare se poate obtine si ın G′ ın mai multi pasi si anume

G′ : u = u′Xu′′⇒u′X1Z1u′′⇒u′X1X2Z2u

′′⇒ . . .⇒u′X1 . . . Xnu′′

= v.2

Observatie. O gramatica ce are reguli de forma A → BC, A → B, A → aunde A,B, C ∈ VN si a ∈ VT spunem ca este ın forma 2–canonica. Este evidentca orice gramatica de tip 2 este echivalenta cu o gramatica ın forma 2–canonica.

Gramatici recursive


Definitie 3.6 Un simbol neterminal X al unei gramatici de tipul 2 este recursivdaca exista o regula de forma X → uXv, u, v ∈ V ∗

G.

Daca u = λ (v = λ) simbolul X este stang (drept) recursiv. O gramatica ce arecel putin un simbol recursiv se numeste recursiva. De exemplu, gramatica GE

care genereaza expresiile aritmetice are doua simboluri stang recursive, E si T .Existenta simbolurilor stang recursive poate provoca dificultati ın aplicarea al-

goritmilor de analiza top-down. Intr-adevar, ıntr-o astfel de gramatica, ıncercareade a construi arborele de derivare corespunzator unui cuvant p prin aplicareaıntotdeauna a primei reguli pentru simbolul cel mai din stanga, poate sa conducala un ciclu infinit (de exemplu ın GE s-ar obtine E⇒E + T⇒E + T + T⇒ . . .).

Teorema 3.6 Orice limbaj de tipul 2 poate sa fie generat de o gramatica fararecursie stanga.

Demonstratie. Fie G = (VN , VT , S, P ) o gramatica de tipul 2; presupunem ca Gare un singur simbol recursiv X si fie

(A) X → u1|u2| . . . |un|Xv1| . . . |Xvm

toate regulile care au X ın stanga. Construim gramatica G′ = (V ′N , VT , S, P ′),

unde VN ⊂ V ′N , P ⊂ P ′ cu exceptia regulilor (A); acestea se ınlocuiesc cu

X → u1|u2| . . . |un|u1Y |u2Y | . . . |unY,Y → v1| . . . |vm|v1Y | . . . |vmY

G′ este de tipul 2 si nu are simboluri stang recursive; se vede ınsa ca Y este unsimbol drept recursiv.

Fie p ∈ L(G), S∗⇒G

p. Daca ın aceasta derivare nu intervine simbolul re-

cursiv, atunci evident ca S∗⇒G′

p. Sa presupunem ca X intervine la un anumit

pas: S⇒u⇒p, unde u = u′Xu′′. Putem aplica, ıncepand de la u spre dreapta, ın

primul rand regulile pentru X si sa urmarim numai subarborele respectiv, deci

G : X ⇒G

Xvj1 ⇒G

Xvj2vj1 ⇒G

. . . ⇒G

Xvjs . . . vj1 ⇒G

ujvjs . . . vj1 .

Aceeasi forma propozitionala o putem obtine si ın gramatica G′ astfel

G′ : X ⇒G′

ujY ⇒G′

ujvjsY ⇒G′

. . . ⇒G′

ujvjs . . . vj1 .

Prin urmare avem S ⇒G′

u ⇒G′

p, adica p ∈ L(G′) si L(G) ⊆ L(G′). Analog,

L(G′) ⊆ L(G).2Forma normala Greibach.


Definitie 3.7 O gramatica ın forma normala Greibach este o gramatica cu regulide forma

A → ip, unde A ∈ VN , i ∈ VT p ∈ V ∗N .

Se accepta si regula de completare S → λ cu conditia ca S sa nu apara ın dreaptavreunei reguli.

Teorema 3.7 (Teorema de existenta a formei normale Greibach). Orice gra-matica de tipul 2 este echivalenta cu o gramatica ın forma normala Greibach.

Demonstratie. Fie G o gramatica de tipul 2 ın forma normala Chomsky si fieVN = {S = X1, X2, . . . , Xn}. Vom construi o gramatica echivalenta care sasatisfaca cerintele din forma normala Greibach ın mai multe etape.Etapa I. Vom modifica regulile de generare astfel ıncat toate regulile care nu suntde forma X → i sa satisfaca conditia Xj → Xkp, j < k, p ∈ V ∗

N . Acest lucru ılfacem cu un algoritm pe care ıl prezentam ıntr-un limbaj nestandard de publicare(tip PASCAL):

j := 1;e1: begin

Se elimina recursiile stangi; neterminalelenoi le notam cu Y1, Y2, . . .endif j = n then STOP;j := j + 1;l := 1;

e2: beginFie Xj → Xlp, p ∈ V ∗

N si Xl → p1 . . . pm

toate regulile care au Xl ın stanga; se efectueaza toate substitutiile.endl := l + 1;if l < j − 1 then goto e2goto e1

Sa observam ca pentru j = 1 si dupa eliminarea recursiilor stangi conditiaceruta este evident ındeplinita; ın plus, daca au fost recursii, vom avea reguli cupartea stanga neterminale noi Y1, Y2, . . .. Mai departe, luam toate regulile care auın stanga X2 (j := j + 1 = 2) si efectuam substitutiile; acestea se vor transformaın X2 → Xkp cu k ≥ 2 si dupa o noua eliminare a recursiilor stangi vom aveak > 2 plus reguli cu partea stanga neterminale noi. In felul acesta toate regulilecare au ın stanga X1 si X2 satisfac conditia ceruta; ın continuare j := j + 1 = 3,etc.

Etapa II. Avem acum trei categorii de reguli:


(1) Xj → i;(2) Xj → Xkp, j < k, p ∈ V ∗

N ;(3) Y → iq, q ∈ V ∗

N , i = 1, . . . , m.Aranjam toate neterminalele ıntr-un sir unic, la ınceput Y1, . . . , Ym apoi X1, . . . , Xn

si le redenumim, de exemplu cu X1, . . . , Xm+n:Y1, Y2, . . ., Ym, X1, X2, . . ., Xn

X1, X2, . . ., Xm, Xm+1, Xm+2, . . ., Xm+n

Vom nota n + m = N . In felul acesta regulile gramaticii vor avea numaiformele (1) si (2).

Etapa III. Toate regulile care au XN ın stanga vor avea forma (1). Fie Xn−1 →XNp1| . . . |XNpn toate regulile care au XN−1 ın stanga si care nu sunt de forma(1). Efecuam substitutiile lui XN ; ın acest fel regulile care au XN si XN−1 ınstanga satisfac cerintele din forma normala Greibach. In continuare, consideramtoate regulile care au XN−2 ın stanga si efectuam substitutiile, etc.2

Forma normala operatorUna din formele importante pentru gramatici independente de context, uti-

lizata ın analiza sintactica prin metoda precedentei, este forma operator a acestorgramatici.

Definitie 3.8 O gramatica independenta de context G = (VN , VT , S, P ) se spuneca este ın forma normala operator daca oricare ar fi productia A → β ∈ P , ın βnu apar doua neterminale (variabile) consecutive, adica

P ⊆ VN × [(VN ∪ VT )∗ \ (VN ∪ VT )∗V 2(VN ∪ VT )∗].

Teorema 3.8 Orice gramatica independenta de context este echivalenta cu o gra-matica ın forma normala operator.

Demonstratie. Fie G = (VN , VT , S, P ) o gramatica de tipul 2 si L(G) limbajulgenerat. Fara a restrange generalitatea presupunem ca λ 6∈ L(G) si G esteın forma 2–canonica (regulile sunt de forma A → BC, A → B, A → a veziteorema ??). Definim o gramatica echivalenta G′ = (V ′

N , VT , S, P ′) astfel: V ′N =

{S} ∪ (VN × VT ), iar P ′ = P1 ∪ P2 ∪ P3 ∪ P4 unde

i) P1 = {S → (S, a)a| a ∈ VT};ii) P2 = {(A, a) → λ| A ∈ VN , a ∈ VT , A → a ∈ P};

iii) P3 = {(A, a) → (B, a)| A,B ∈ VN , a ∈ VT , A → B ∈ P};iv) P4 = {(A, a) → (B, b)b(C, a)| A, B, C ∈ VN , a, b ∈ VT , A → BC ∈ P}.

Sa observam ca G′ este ın forma normala operator. Pentru a demonstra caL(G) = L(G′) vom defini mai ıntai o functie φ : P2 ∪ P3 ∪ P4 −→ P astfel:

φ((A, a) → λ) = A → a pentru (A, a) → λ ∈ P2;φ((A, a) → (B, a)) = A → B pentru (A, a) → (B, a) ∈ P3;φ((A, a) → (B, b)b(C, a)) = A → BC pentru (A, a) → (B, b)b(C, a) ∈ P4.


Functia φ se extinde ın mod natural la φ′ : (P2 ∪P3 ∪P4)∗ −→ P ∗. Vom arata ca

ın gramatica G, ∀w ∈ V ∗T , ∀a ∈ VT are loc derivarea extrem dreapta A

∗⇒G

wa

folosind productiile π1, π2, . . . , πn daca si numai daca exista ın P ′ productiileπ′1, π

′2, . . . , π

′n astfel ca φ(π′i) = πi, 1 ≤ i ≤ n si ın G′ are loc derivarea extrem

dreapta (A, a)∗⇒G′

w folosind productiile π′1, π′2, . . . , π

′n.

Sa demonstram afirmatia prin inductie dupa n, lungimea derivarii.Daca n = 1 atunci w = λ,A → a ∈ P si ın P ′ exista productia (A, a) → λ,

deci (A, a)⇒λ si φ((A, a) → λ) = A → a.Invers, daca (A, a)⇒w ın G′ atunci w = λ (dupa forma productiilor din G′)

si are loc proprietatea enuntata.Sa presupunem afirmatia adevarata pentru derivari de lungime cel mult n−1

si sa o demonstram pentru derivari de lungime n > 1. Fie asadar A∗⇒G

wa

o derivare de lungime n ın gramatica G si punem ın evidenta prima derivaredirecta. Distingem doua cazuri:

I. Prima productie utilizata ın derivare este A → B. Atunci,

A ⇒G

B∗⇒G

wa

si conform ipotezei inductive avem ın G′ o derivare (B, a)∗⇒G′

w (de lungine n−1)

cu productii satisfacand conditiile aratate. Dar cum A → B ∈ P , ın P ′ avemproductia (A, a) → (B, a) deci (A, a)

∗⇒G′

w ın gramatica G′.

II. Prima productie este de forma A → BC. Atunci

A ⇒G

BC∗⇒G

wa.

In acest caz wa = ubva (conform lemei de localizare), astfel ca B∗⇒G

ub si

C∗⇒G

va. Dupa ipoteza inductiva, vom avea ın G′ derivarile:

(B, b)∗⇒G′

u, (C, a)∗⇒G′

v.

Cum A → BC ∈ P vom avea ın P ′ productia (A, a) → (B, b)b(C, a) si ın G′

putem scrie derivarea extrem dreapta

(A, a)⇒(B, b)b(C, a)∗⇒G′

(B, b)bv∗⇒G′

ubv = w

si productiile care s-au aplicat ındeplinesc conditiile din enunt.In mod analog se demonstreaza reciproca.


Din aceasta afirmatie, luand ın particular A = S, obtinem:

S∗⇒G

wa ⇔ (S, a)∗⇒G′

w, ∀w ∈ V ∗T , ∀a ∈ VT .

Cum ın G′ exista si productia S → (S, a)a, am gasit: wa ∈ L(G) daca si numaiwa ∈ L(G′), deci cele doua gramatici sunt echivalente.

Pentru a ıncheia demonstratia trebuie sa consideram si cazul λ ∈ L(G).Aplicam constructia de mai sus unei gramatici ce genereaza L(G)\{λ} si obtinemG′ = (V ′

N , VT , S, P ′) gramatica operator corespunzatoare. Consideram acum gra-matica G1 = (VN1 , VT , S1, P1) unde V1 = V ′ ∪ {S1}, P1 = P ′ ∪ {S1 → λ, S1 → S}care este ın forma normala operator si L(G1) = L(G).2

3.4 Lema Bar–Hillel

Ca si ın cazul limbajelor regulate, lema Bar–Hillel pune ın evidenta urmatoareaproprietate a unui limbaj independent de context: orice cuvant al unui astfel delimbaj, suficient de lung, contine un subcuvant (nevid) pe care multiplicandu–l de un numar arbitrar de ori, obtinem noi cuvinte care apartin de asemenealimbajului. Mai poarta denumirea de ”lema de pompare” sau ”lema uvwxy”.

Ne vom referi ın cele ce urmeaza la gramatici de tipul 2 ın forma normalaChomsky. Intr-o gramatica de aceasta forma arborii de derivare sunt ıntotdeaunaarbori binari.

Lema 3.2 Fie G o gramatica ın forma normala Chomsky si X∗⇒p, p ∈ V ∗

G. Dacacea mai lunga ramura din arborele AX,p contine m noduri, atunci |p| ≤ 2m−1.

Demonstratie. Procedam prin inductie asupra lui m.Pentru m = 2 arborele are doua nivele si ın mod evident |p| ≤ 2 = 2m−1.Presupunem ca proprietatea este adevarata pentru un m oarecare si con-

sideram un arbore care are pe cea mai lunga ramura m + 1 noduri. In derivareaX

∗⇒p punem ın evidenta prima derivare directa

X⇒Y Z∗⇒p.

Conform lemei de localizare, p = p1p2 si Y∗⇒p1, Z

∗⇒p2. Arborii de derivare AY,p1

si AZ,p2 contin, fiecare pe cea mai lunga ramura cel mult m noduri; conformipotezei de inductie, avem |p1| ≤ 2m−1, |p2| ≤ 2m−1. Prin urmare

|p| = |p1p2| = |p1|+ |p2| ≤ 2m−1 + 2m−1 = 2m.2

Observatie. Daca X∗⇒p si |p| > 2m−1 atunci exista ın arborele AX,p cel putin

o ramura cu m + 1 noduri.

3.4. LEMA BAR–HILLEL 63

S

v 1 =A

v 2 =A

u v w x y

p

Figura 3.5: Descompunerea cuvantului p.

Lema 3.3 Fie G o gramatica de tipul 2 si fie X⇒X1 . . . Xm∗⇒p. Atunci, conform

lemei de localizare, p = p1 . . . pm si Xj∗⇒pj, j = 1, . . . , m. Fie AY,q ⊆ AX,p.

atunci q este subcuvant ıntr–unul din cuvintele pj.

Demonstratie. Neterminalul Y apartine unuia din subarborii AXj ,pj, fie acesta

AXk,pk; atunci AY,q ⊆ AXk,pk

si q ∈ Sub(pk). 2

Lema 3.4 (Lema Bar–Hillel) Fie E un limbaj independent de context. Atunciexista un numar natural k astfel ıncat, daca p ∈ E si |p| > k atunci p se poatedescompune ın forma p = uvwxy cu urmatoarele proprietati:

1. vx 6= λ;

2. |vwx| ≥ k;

3. uvjwxjy ∈ E, ∀j ∈ N ,

Demonstratie. Fie n = card(VN). Luam k = 2n. Cum |p| > k = 2n, conformobservatiei de la prima lema, exista ın arborele AS,p cel putin o ramura cu n + 2noduri; pe aceasta ramura ultimul nod este terminal, deci exista n + 1 nodurietichetate cu acelasi simbol A. Descompunem cuvantul p ca ın figura 3.5, p =uvwxy.

(1) Consideram subarborele AA,vwx caruia ıi corespunde derivarea A∗⇒vwx.

Punem ın evidenta primul pas

A⇒BC∗⇒vwx,

si vwx se descompune ın vwx = pBpC , B∗⇒pB, C

∗⇒pC si pB, pC 6= λ. Cum AA,w ⊆AA,vwx, rezulta ca w este subcuvant ın pB sau ın pC . Sa presupunem ca w ∈Sub(pC); atunci pB ∈ Sub(v) si cum pB 6= λ rezulta v 6= λ.


(2)Putem alege nodurile v1 si v2 astfel ıncat pe ramura punctata ıncepand dela v1 ın jos pana la frontiera sa avem exact n + 1 noduri. Rezulta conform lemeiprecedente, |vwx| ≥ 2n = k.

(3) putem scrie derivarile A∗⇒w,A

∗⇒vAx. Deci

S∗⇒uAy

∗⇒uvAxy∗⇒uv2Ax2y

∗⇒ . . .∗⇒uvjwxjy.2

Problema ınchiderii familiei L2 la intersectie

Teorema 3.9 Familia L2 nu este ınchisa la intersectie.

Demonstratie. Consideram limbajul L3 = {anbncn|n ≥ 1}. Sa ratam ca L3 6∈ L2.Intr–adevar, sa presupunem ca L3 ∈ L2 si fie k constanta din lema Bar–Hillel.Luam n > k/3 si fie p = anbncn; avem |p| > k, deci conform acestei leme p sedescompune ın forma p = uvwxy cu vx 6= λ si uvjwxjy ∈ L3, j ∈ N .

Vom analiza posibilitatile de constituire a subcuvintelor v si x. Sa presupunemca ın v (sau x) intra doua din simbolurile a, b, c; de exemplu v = aabbb. atunciconsideram cuvantul p2 = uv2wx2y = uaabbaabbwx2y care nu are structura cu-vintelor lui L3 (”a” nu poate sa urmeze dupa ”b”) dar conform lemei Bar-Hillelapartine lui L3. Deci, ın v (sau x) nu pot intra doua (sau trei) din simbolurilea, b, c. Sa presupunem ca intra un singur simbol; de exemplu v ∈ {a}∗ si x ∈ {b}∗.Atunci multiplicand ın p subcuvintele v si x, puterile simbolurilor ”a” si ”b” semaresc iar ”c” ramane pe loc, contrazicandu–se din nou structura cuvintelor dinL3. In concluzie L3 nu este independent de context.

Fie acum limbajeleL′3 = {ambncn|m,n ≥ 1}L”

3 = {anbncm|m,n ≥ 1}.Se poate vedea usor ca aceste limbaje sunt de tipul 2; gramaticile care le genereazasunt S → aS|aA,A → bAc|bc si respectiv S → Sc|Ac,A → aAb|ab.

Avem L′3 ∩ L”3 = L3, deci intersectia a doua limbaje de tipul 2 este un limbaj

care nu apartine lui L2.2

Corolar 3.10 Familia L2 nu este ınchisa la complementariere.

Intr–adevar, sa presupunem ca L2 este ınchisa la complementariere si fie E1, E2 ∈L2. Cum familia L2 este ınchisa la reuniune, ar rezulta C(E1)∪C(E2) ∈ L2. Dar(de Morgan) C(E1) ∪ C(E2) = C(E1 ∩ C(E2) ∈ L2.

Complementul limbajului C(E1 ∩E2) este E1 ∩E2 si conform presupunerii artrebui ca E1 ∩ E2 ∈ L2, oricare ar fi E1, E2, ceea ce nu este adevarat.2

Generalizari ale lemei Bar–Hillel Lema lui Bar–Hillel reprezinta o conditienecesara ca un limbaj sa fie independent de context. cu ajutorul ei se poatedemonstra relativ usor ca anumite limbaje nu sunt independente de context.Ideea este aceea ca prin multiplicarea subcuvintelor v si x, de un numar suficientde ori, se contrazice structura limbajului.

3.5. AUTOMATE PUSH-DOWN (APD) 65

Totusi, nu orice limbaj care nu este de tipul 2 poate fi respins de lema luiBar–Hillel. De exemplu, aceasta lema nu poate respinge limbajul

L = {anb2m|n,m ≥ 1} ∪ {b}∗,

care nu este de tipul 2 (se demonstreaza pe alta cale). Intr–adevar, pentru oricep = anb2m

luam

u = λ, v = a, w = λ, x = λ, y = an−1b2m

.

Putem itera subcuvintele v si x fara sa contrazicem structura cuvintelor limba-jului.

O generalizare a lemei Bar–Hillel este

Lema 3.5 (Lema lui Ogden) pentru orice limbaj independent de context L existao constanta k astfel ıncat orice p ∈ L pentru care cel putin k simboluri sunt”marcate”, se poate descompune ın forma p = uvwxy astfel ıncat

1. sau u, v, w sau w, x, y contin fiecare cate un simbol marcat;

2. vwx contine cel mult k simboluri marcate;

3. uvjwxjy ∈ L, ∀j ∈ N

Cu ajutorul acestei leme se poate arata ca limbajul de mai sus nu este de tipul2, considerand marcate simbolurile b.

3.5 Automate push-down (APD)

Automatele push-down sunt mecanisme pentru recunoasterea limbajelor indepen-dente de context.

Un APD se compune din (vezi figura 3.6):

1. O banda de intrare care contine simboluri ale unui alfabet de intrare; acestesimboluri constituie pe o banda un anumit cuvant peste alfabetul de intrare.Banda se misca numai spre stanga;

2. O memorie push-down (memorie inversa, stiva, pila, etc) care contine sim-boluri ale unui alfabet propriu, numit alfabetul memoriei push-down. Aceastamemorie functioneaza ca o stiva - ultimul introdus, primul extras (Last In,First Out);

3. Un dispozitiv de comanda care se afla permanent ıntr-o anumita stare in-terna apartinand unei multimi finite de stari. Dispozitivul de comandaposeda un dispozitiv de citire de pe banda de intrare si un dispozitiv descriere-citire ın memoria push-down.


i 1 i 2 i 3 ... i k ... i n-1 i n ...

Dispozitiv de citire de pe banda

Dispoz itiv de comanda

s Î S

Banda de intrare

z 0

z 1

z m

Dispozitiv de citire / scriere

Memoria pushdown

Figura 3.6: Reprezentare schematica a unui automat push-down.

Ca si un automat finit, un automat push-down functioneaza ın pasi discreti;un pas de functionare comporta:

1. Dispozitivul de comada citeste simbolul de pe banda de intrare din dreptuldispozitivului de citire si muta banda cu o pozitie spre stanga.

2. In functie de starea interna, de simbolul citit si de simbolul din varfulmemoriei push-down dispozitivul de comanda efectueaza operatiile:(a) Trece ıntr-o noua stare;(b) Scrie ın memoria push-down un anumit cuvant peste alfabetul memorieipush-down; ın particular, acesta poate sa fie cuvantul vid, ceea ce are caefect stergerea simbolului din varful memoriei push-down.

Functionarea unui APD se termina ın general dupa ce s-a citit ultimul simbol alcuvantului scris pe banda de intrare dar este posibil ca el sa efectueze un anumitnumar de pasi, citind de fiecare data de pe banda cuvantul vid λ. De asemenea,este posibil ca ın timpul functionarii, deci ınainte de a ajunge la ultimul simbol,automatul sa se blocheze. De exemplu, automatul ajunge ıntr-o configuratie(stare, simbol pe banda, simbol ın varful memoriei push-down) inadmisibila sause goleste memoria push-down dar nu s-a epuizat cuvantul de pe banda, etc.

Matematic, un APD se defineste astfel:

Definitie 3.9 Un automat push-down este un sistemAPD = (Σ, I, Z, f, s0, z0)

unde:


Σ este multimea de stari (finita si nevida);I este alfabetul de intare;Z este alfabetul memoriei push-down;f : Σ× (I ∪ {λ})× Z −→ P(Σ× Z∗) este functia de evolutie;s0 ∈ Σ este starea initiala;z0 ∈ Z este simbolul initial al memoriei push-down.

Un APD are ın general o functioanre nedeterminista, card f(s, i, z) ≥ 1; multimeaautomatelor push-down deterministe formeaza o clasa speciala.

In termenii functiei de evolutie, un pas de evolutie comporta citirea simboluluii de pe banda, citirea simbolului z din varful memoriei push-down, apoi, ın functiede starea interna s si de aceste doua simboluri, automatul trece ıntr-o noua stares′ si scrie ın memoria push-down un cuvant q ∈ Z∗ astfel ıncat (s′, q) ∈ f(s, i, z).In cazul ın care f(s, i, z) = ∅ evolutia este oprita; este situatia ın care automatulse blocheza.

O stare a automatului (sau configuratie) este un sistem δ = (s, p, q) undes ∈ S este starea interna, p ∈ I∗ este subcuvantul de pe banda de intrare ramasde citit (inclusiv simbolul din dreptul dispozitivului de citire), iar q ∈ Z∗ estesubcuvantul din memoria push-down.

Vom spune ca un APD trece direct din starea δ1 = (s1, p1, q1) ın starea δ2 =(s2, p2, q2) si vom scrie δ1 7−→δ2 daca se executa un pas de evolutie; daca p1 =ip′1, q1 = zq′1 putem avea (s2, q) ∈ f(s1, i, z) si atunci p2 = p′1, q2 = qq′1 sau(s2, q) ∈ f(s1, λ, z) si atunci p2 = p1, q2 = qq′1.

Vom spune ca automatul evolueaza (fara specificatia direct) din starea δ′ ınstare δ′′ si vom scrie δ′ ∗7−→δ′′ daca:

(1) δ′ = δ′′;(2) ∃δ1, . . . , δn astfel ıncat δ′ = δ1 7−→δ2 7−→ . . . 7−→δn−1 7−→δn = δ′′.Limbajul recunoscut de un APD se poate defini ın doua moduri:(1) Limbajul recunoscut de un APD cu golirea memoriei push-down, este,

prin definitie

L(APD) = {p|p ∈ I∗ (s0, p, z0)∗7−→(s, λ, λ)}.

Aceata ınseamna ca, pornind din starea interna s0 si avand ın varful memo-riei push-down simbolul z0, cu ajutorul cuvantului p de pe banda de intrare,automatul poate sa evolueze astfel ıncat sa goleasca memoria push-down dupacitirea cuvantului. Mentionam ca golirea memoriei push-down nu trebuie nea-parat sa coincida cu citirea ultimului simbol al lui p; este posibil ca automatulsa mai efectueze cativa pasi citind de pe banda simbolul λ.

(2) Limbajul recunoscut de un APD cu stari finale; ın definitia automatului seadauga o submultime Σf a lui Σ numita multimea de stari finale. Prin definitie,limbajul recunoscut de un APD cu stari finale este:

L(APD) = {p|p ∈ I∗ (s0, p, z0)∗7−→(s, λ, q), s ∈ Σf , q ∈ Z∗}.


Prin urmare, este necesar ca dupa citirea lui p, eventual dupa ınca cativa pasi,APD sa ajunga ıntr-o stare finala. Vom vedea ca cele doua definitii sunt echiva-lente.Limbaje recunoscute de automate push-down cu golirea memoriei. Vomarata ca familia limbajelor recunoscute de APD cu stari finale coincide cu familialimbajelor independente de context. In felul acesta, APD constituie mecanismeanalitice de definire a limbajelor de tipul 2.

Teorema 3.11 Un limbaj este independent de context daca si numai daca esterecunoscut de un automat push–down cu golirea memoriei push–down.

Demonstratie. Partea I E ∈ L2⇒E = L(APD).Fie G = (VN , VT , S, P ) o gramatica de tipul 2 ın forma normala Greibach care

genereaza limbajul E. Construim un automat pushdown astfel:APD = ({s}, VT , VN , f, s, S), functia de evolutie fiind definita de:

A → ip ∈ P ⇒ (s, p) ∈ f(s, i, A),

altfel ∅.Fie p ∈ L(G), p = i1 . . . in, S

∗⇒G

p. Aceasta derivare trebuie sa aiba forma

(extrem stanga):

(A) S⇒i1X1u1⇒i1i2X2u2u1⇒i1i2i3X3u3u2u1⇒ . . .⇒i1 . . . in,

unde u1, u2, u3, . . . ∈ V ∗N = Z∗.

Observatie. Aparent, partea usus−1 . . . u1 se mareste cu fiecare derivare di-recta. In realitate, unele din cuvintele uj sunt vide, si anume atunci cand seaplica o regula de forma X → i; ın particular, ın ultimele derivari directe seaplica numai reguli de aceasta forma.

Avem

S → i1X1u1 ⇒ (s, X1u1) ∈ f(s, i1, S),X1 → i2X2u2 ⇒ (s, X2u2) ∈ f(s, i2, X1),X2 → i3X3u3 ⇒ (s, X3u3) ∈ f(s, i3, X2),. . . .

Prin urmare automatul poate sa aiba urmatoarea evolutie:

(s, i1i2i3i4 . . . in, S)7−→(s, i2i3i4 . . . in, X1u1)7−→

7−→(s, i3i4 . . . in, X2u2u1)7−→(s, i4 . . . in, X3u3u2u1)7−→ . . . .

Daca comparam aceasta evolutie cu derivarea (A) putem observa ca pe bandade intrare avem la fiecare pas partea complementara a cuvantului (fata de derivare)iar ın memoria push-down se reproduce partea de neterminale din formele propozitionale


ale derivarii. Cum ın derivare se ajunge la i1 . . . in, ın evolutie se va ajunge la(s, λ, λ).

Deci p ∈ L(APD) si L(G) ⊆ L(APD).Fie acum p ∈ L(APD); va trebui sa aratam ca p ∈ L(G), deci ca S

∗⇒G

p.

Vom arata o implicatie ceva mai generala, si anume, pentru orice u ∈ V ∗N , avem

(s, p, u)∗7−→(s, λ, λ) ⇒ u

∗⇒G

p.

In particular, daca u = S obtinem implicatia dorita.Procedam prin inductie asupra lungimii lui p.Daca |p| = 1, atunci p = i, u = X iar evolutia va avea un singur pas

(s, i, X)7−→(s, λ, λ), deci (s, λ) ∈ f(s, i, X) si X → i ∈ P . Putem scrie u =X ⇒

G

i = p.

Presupunem ca implicatia este adevarata pentru un cuvant |p| = l si con-sideram un p astfel ıncat |p| = l + 1. Fie i si X primele simboluri din p si u,deci p = ip′ si u = Xu′. In evolutia (s, p, u)

∗7−→(s, λ, λ) punem ın evidenta primaevolutie directa

(s, p, u) = (s, ip′, Xu′)7−→(s, p′, vu′) ∗7−→(s, λ, λ).

Din definitia evolutiei directe rezulta ca (s, v) ∈ f(s, i, X) deci X → iv ∈ P . Pede alta parte din ipoteza inductiva rezulta ca vu′ ∗⇒

G

p′. Avem

u = Xu′ ⇒G

ivu′ ∗⇒G

ip′ = p,

ceea ce demonstreaza implicatia.Prin urmare p ∈ L(G) si L(APD) ⊆ L(G), de unde L(G) = L(APD).2Partea II. E = L(APD) E ∈ L2

Fie APD = (Σ, I, Z, f, s0, z0). Construim G de forma G = (VN , VT , S, P )unde VN = {s0} ∪ {(s, z, s′)|s, s′ ∈ Σ, z ∈ Z}, VT = I, S = s0, iar regulile degenerare le definim astfel:

(1) s0 → (s0, z0, s), ∀s ∈ Σ;(2) Daca (s1, z1 . . . zm) ∈ f(s, i, z) vom introduce ın P reguli de forma

(s, z, s′) → i(s1, z1, s2)(s2, z2, s3) . . . (sm, zm, s′),

unde s′, s2, . . . , sm ∈ Σ;(3) Daca (s′, λ) ∈ f(s, i, z) vom introduce ın P reguli de forma

(s, z, s′) → i,


unde s′ ∈ Σ.Sa observam ca gramatica astfel construita este independenta de context, si

anume ın forma normala Greibach.Fie p ∈ L(APD), deci (s0, p, z0)

∗7−→(s′, λ, λ); trebuie sa aratam ca s0∗⇒G

p.

Vom arata implicatia ceva mai generala

(s, p, z)∗7−→(s′, λ, λ) ⇒ (s, z, s′) ∗⇒

G

p.

In particular pentru s = s0, z = z0 rezulta (s0, z0, s′) ∗⇒

G

p si putem scrie s0⇒(s0, z0, s′) ∗⇒

G

p,

adica p ∈ L(G).Procedam prin inductie asupra lungimii evolutiei l.Daca l = 1 atunci (s, p, z)7−→(s′, λ, λ), deci p = i si (s′, λ) ∈ f(s, i, z) si

(s, z, s′) → i este o regula, adica putem scrie (s, z, s′)⇒i = p.Presupunem ca implicatia este adevarata pentru evolutii de lungime oarecare

l si consideram o evolutie de lungime l + 1; punem ın evidenta prima evolutiedirecta

(s, p, z) = (s, i1p′, z)7−→(s1, p

′, z1 . . . zm)∗7−→(s′, λ, λ).

Descompunem cuvantul p′ ın forma p′ = p1 . . . pm astfel ıncat

(s1, p1, z1)∗7−→ (s2, λ, λ),

(s2, p2, z2)∗7−→ (s3, λ, λ),

. . .

(sm, pm, zm)∗7−→ (s′, λ, λ).

Observatie. Putem pune ın evidenta felul ın care se defineste cuvantul p1 urmarindevolutia lui APD;

(s1, i1i2 . . . in, z1z2 . . . zm) 7−→ (s′1, i2i3 . . . in, qz2 . . . zm) 7−→(a) (b). . . 7−→ (s2, ij1 . . . in, z2 . . . zm)

(c)

La primul pas (situatia a) automatul este ın starea s1, pe banda este i1 iar ınmemoria push-down este z1. Dupa efectuarea unui pas, automatul trece ın stareas′1, muta banda cu o pozitie spre stanga, extrage pe z1 si scrie ın memoria push-down un cuvant q (situatia b). Se poate observa ca z2 a ”coborat”; cum stim camemoria push-down se goleste (p ∈ L(APD)), trebuie ca la un moment dat z2 saajunga ın varful stivei (situatia c). In acest moment partea din p citita va fi p1

iar starea ın care a ajuns automatul o notam cu s2. Este clar ca daca pe bandaam avea scris numai p1 am avea evolutia (s1, p1, z1)7−→(s2, λ, λ).


Analog p2, . . . , pm.Din definitia derivarii directe (s, i1p

′, z)7−→(s1, p′, z1 . . . zm) avem

(s1, z1 . . . zm) ∈ f(s, i1, z) iar ın P va exista regula

(s, z, s′) → i1(s1, z1, s2)(s2, z2, s3) . . . (sm, zm, s′)

unde luam starile s2, . . . , sm cele rezultate la descompunerea lui p′. Pe de altaparte, din ipoteza inductiva, avem

(s1, z1, s2)∗⇒p1,

(s2, z2, s3)∗⇒p2,

. . .

(sm, zm, s′) ∗⇒pm.

Putem scrie derivarea

(s, z, s′)⇒i1(s1, z1, s2)(s2, z2, s3) . . . (sm, zm, s′) ∗⇒i1p1 . . . pm = i1p′ = p.

Dupa cum am vazut, rezulta mai departe p ∈ L(G) si L(APD) ⊆ L(G).Pentru a demonstra incluziunea inversa, vom arata mai ıntai implicatia(s, z, s′) ∗⇒p(s1, z1s2) . . . (sm, zm, s′) implica (s, p, z)

∗7−→(s1, λ, z1 . . . zm).Procedam prin inductie asupra lungimii derivarii l.Daca l = 1 atunci p = i si se aplica regula

(s, z, s′) → i(s1, z1, s2) . . . (sm, zm, s′)

deci (s1, z1 . . . zm) ∈ f(s, i, z) si (s, i, z)7−→(s1, λ, z1 . . . zm).Presupunem ca implicatia este adevarata pentru l oarecare si consideram o

derivare de lungime l + 1. Fie p = p′i si punem ın evidenta ultimul pas.(s, z, s′) ∗⇒p′(s′j−1, z

′j−1, s

′j)(sj, zj, sj+1) . . . (sm, zm, s′)

⇒p′i(s1, z1, s2) . . . (sj−1, zj−1, sj)(sj, zj, sj+1) . . . (sm, zm, s′),unde s′j = sj; la ultimul pas s-a aplicat regula

(s′j−1, z′j−1, sj) → i(s1, z1, s2) . . . (sj−1, zj−1, sj).

Rezulta (s1, z1 . . . zj−1) ∈ f(s′j−1, i, z′j−1) si putem scrie evolutia

(s′j−1, i, z′j−1)7−→(s1, λ, z1 . . . zj−1).

Pe de alta parte, conform ipotezei inductive, avem

(s, p′, z)∗7−→(s′j−1, λ, z′j−1zj . . . zm)

Prin urmare

(s, p, z) = (s, p′i, z)∗7−→(s′j−1, i, z

′j−1zj . . . zm)7−→(s1, λ, z1 . . . zm)


si implicatia este demonstrata.Fie acum p ∈ L(G), deci s0

∗⇒G

p. Tinand seama de forma regulilor din G,

ın aceasta derivare se va aplica prima data o regula de forma (1), apoi regula deforma (2) iar la sfarsit reguli de forma (3). La aplicarea regulilor (2) putem rescriela fiecare pas simbolul neterminal cel mai din stanga, deci sa obtinem o derivareextrem stanga. Sa observam ca ın acest caz structura formelor propozitionaleintermediare este cea mentionata, p(s1, z1, s2)(s2, z2, s3) . . . (sm, zm, s′).

Prin urmare, derivarea va avea forma

s0⇒(s0, z0, s′) ∗⇒p(s1, z1, s2) . . . (sm, zm, s′) ∗⇒p.

Trebuie sa avem regulile (sj, zj, sj+1) → λ, j = 1, . . . , m, sm+1 = s′ si putemscrie

(s0, p, z0)∗7−→(s1, λ, z1 . . . zm)7−→(s2, λ, z2 . . . zm)7−→ . . . 7−→(s′, λ, λ)

adica p ∈ L(APD) si L(G) ⊆ L(APD).2Automate push–down cu stari finale. Vom nota un automat push-down

cu stari finale cu APDf .

Teorema 3.12 Un limbaj este recunoscut de un automat push–down daca si nu-mai daca este recunoscut de un automat push–down cu stari finale.

Demonstratie. Partea I E = l(APD) ⇒ E ∈ L(APDf ).Daca APD = (Σ, I, Z, f, s0, z0) construim un automat push–down cu stari

finale astfelAPDf = (Σ ∪ {s′0, sf}, I, Z ∪ {z′0}, f ′, s′0, z′0)

unde multimea de stari finale este {s} iar functia de evolutie este definita de:f ′(s, i, z) = f(s, i, z), s ∈ Σ, i ∈ I ∪ {λ}, z ∈ Z;f ′(s′0, λ, z′0) = (s0, z0z

′0);

f(s, λ, z′0) = (sf , λ), s ∈ Σ;ın rest ∅.Fie p ∈ L(APD); atunci (s0, p, z0)

∗7−→(s, λ, λ). Evident ca aceiasi evolutie opoate avea si automatul push–down cu stari finale. Putem scrie ın APDf evolutia

(APDf ) : (s′0, p, z′0)

∗7−→(s0, λ, z′0)7−→(s, λ, λ),

deci p ∈ L(APDf ) si L(APD) ⊆ L(APDf ).Invers, fie p ∈ L(APDf ), atunci (ın APDf )

(s′0, p, z′0)7−→(s, p, z0z

′0)

∗7−→(sf , λ, q).

Ultimul pas trebuie sa fie de forma (s, λ, z′0) 7−→(sf , λ, λ) pentru ca nu exista altavaloare a lui f care sa ne duca ıntr-o stare finala. Deci (ın APDf )

(s′0, p, z0z′0)

∗7−→(s, λ, z′0)7−→(sf , λ, λ)

3.6. AUTOMATE PUSH–DOWN DETERMINISTE 73

si putem scrie ın APD evolutia (s0, p, z0)∗7−→(s, λ, λ), adica p ∈ L(APD) si

L(APDf ) ⊆ L(APD).2Partea II E = L(APDf ⇒ E ∈ L(APD).Fie APDf = (Σ, I, Z, f, s0, z0, Σf ) un automat push–down cu stari finale

(multimea starilor finale este Σf ) si construim un APD astfel

APD = (Σ ∪ {s′0, s′}, I, Z ∪ {z′0}, f ′, s′0, z′0)

undef ′(s, i, z) = f(s, i, z), s ∈ Σ, i ∈ I ∪ {λ}, z ∈ Z;f(s′0, λ, z′0) = (s, z0z

′0);

f(s, λ, z) = (s′, λ), s ∈ Σf ∪ {s′}, z ∈ Z ∪ {z′0};ın rest ∅.Fie p ∈ L(APDf ), atunci (s0, p, z0)

∗7−→(s, λ, q), s ∈ Σf . Este evident ca ınAPD avem evolutia (s0, p, z0)

∗7−→(s, λ, q). Putem scrie

APD : (s′0, p, z′0)7−→(s0, p, z0z

′0)

∗7−→(s, λ, qz′0)∗7−→(s′, λ, λ),

deci p ∈ L(APD) si L(APDf ) ⊆ L(APD).Invers, fie p ∈ L(APD). Avem

APD : (s′0, p, z′0)

∗7−→(s0, p, z0z′0)

∗7−→(s, λ, λ).

Simbolul z′0 nu poate fi sters decat cu o regula de forma f(s, λ, z) = (s′, λ),s ∈ Σf ∪{s′}, deci APD trebuie sa ajunga ıntr-o stare s ∈ Σf , apoi sa ramana ıns′.

APD : (s0, p, z0z′0)

∗7−→(s, λ, qz′0), s ∈ Σf .

Putem scrie

APDf : (s0, p, z0)∗7−→(s, λ, q), s ∈ Σf

si deci p ∈ L(APDf ), adica L(APD) ⊆ L(APDf ).2

3.6 Automate push–down deterministe

Functionarea unui APD este ın general nedeterminista, card f(s, i, z) ≥ 1. Pen-tru ca un APD sa aiba o functionare determinista nu ete suficient sa impunemconditia card f(s, i, z) = 1, deoarece daca pentru un anumit s ∈ Σ si z ∈ Z avemf(s, λ, z) 6= ∅ si f(s, i, z) 6= ∅, putem face un pas citind λ sau citind i.

Definitie 3.10 Un automat push–down este determinist daca(1) card f(s, i, z) ≥ 1, s ∈ Σ, i ∈ I ∪ {λ}, z ∈ Z;(2) daca f(s, λ, z) 6= ∅, atunci f(s, i, z) = ∅,∀i ∈ I.


Un limbaj recunoscut de un APD determinist ıl vom numi limbaj independentde context (sau de tipul doi) determinist. Familia limbajelor independente decontext deterministe este inclusa (strict) ın familia limbajelor de tipul 2 (dupacum vom vedea).

Un APD se poate bloca ın urmatoarel doua situatii

1. Automatul ajunge ın starea s, ın varful memoriei push–down se afla sim-bolul z, pe banda de intrare urmeaza i si f(s, i, z) = f(s, λ, z) = ∅;

2. Intra ıntr-un ciclu infinit citind de pe banda λ; de exemplu f(s, λ, z) = (s, z)si f(s, i, z) = ∅ pentru o anumita pereche (s, z).

Definitie 3.11 Un APD determinist este neblocabil daca pentru orice cuvantp ∈ I∗ exista o evolutie de forma (s0, p, z0)

∗7−→(s, λ, q).

Intr-un APD determinist neblocabil orice cuvant peste I poate fi citit. Evi-dent, de aici nu rezulta ca orice cuvant este recunoscut de APD.

Lema 3.6 Un APD determinist cu stari finale este echivalent cu un APD deter-minist cu stari finale neblocabil (relativ la prima situatie de blocare).

Demonstratie.Fie APDf = (Σ, I, Z, f, s0, z0, Σf ). Construim APD′f = (Σ ∪

{s′0, s′}, I, Z ∪ {z′0}, f ′, s′0, z′0, Σf ) unde:(1) f ′(s, i, z) = f(s, i, z) daca f(s, i, z) 6= ∅, s ∈ Σ, i ∈ I ∪ {λ}, z ∈ Z;(2) f ′(s, i, z) = (s′, z) daca f(s, i, z) = f(s, λ, z) = ∅, s ∈ Σ, i ∈ I, z ∈ Z;(3) f ′(s′, i, z) = (s′, z), i ∈ I, z ∈ Z;(4) f ′(s′, λ, z′0) = (s0, z0z

′0).

Avem

p ∈ L(APDf ) ⇔ (s0, p, z0)APDf

|= (s, λ, q), s ∈ Σf ⇔

(s′0, p, z′0)

APD′f|= (s0, p, z0z

′0)

APD′f|= (s, λ, qz′0), s ∈ Σf ⇔ p ∈ L(APD′

f ).

Deci L(APDf ) = L(APD′f .2

Observatie. Intr-o situatie de blocare (s, ip, zq) si f(s, i, z) = f(s, λ, z) = ∅putem scrie

(s, ip, zq)APD′f|= (s′, p, zq)

APD′f|= . . .

APD′f|= (s′, λ, zq).

Teorema 3.13 Orice limbaj independent de context determinist este recunoscutde un APD determinist neblocabil.

3.6. AUTOMATE PUSH–DOWN DETERMINISTE 75

Demonstratie. Fiind dat un APD determinist vom construi un APD deter-minist neblocabil echivalent. Conform lemei anterioare putem presupune ca nuare loc prima situatie de blocare.

Daca are loc a doua situatie de blocare, putem avea doua cazuri:

1. continutul memoriei push–down se mareste nelimitat;

2. lungimea cuvintelor scrise ın memoria push–down nu depaseste un anumitnumar.

Fie card(Σ) = n, card(Z) = k, l = max{|q|, q ∈ Z∗ | (s′, q) ∈ f(s, i, z)}.Cazul 1. Exista ın total un numar nk de perechi de forma (s, z). Daca ın

evolutia lui APD s-ar succede numai configuratii cu perechi de forma (s, z) dis-tincte atunci lungimea cuvantului din memoria push–down ar creste la maximumnkl simboluri. Prin urmare, daca (s′, λ, α′) ∗7−→(s”, λ, α”) si |α”| − |α′| > nkl,atunci ın aceasta evolutie trebuie sa existe doua configuratii cu aceiasi stare s sicu acelasi simbol z ın varful memoriei push–down. Deci

(s′, λ, α′) ∗7−→(s, λ, zr)∗7−→(s, λ, zqr)

∗7−→(s”, λ, α”),

de unde urmeaza ca

(s′, λ, α′) ∗7−→(s, λ, zr)∗7−→(s, λ, qmr),∀m ∈ N.

Cazul II Lungimea cuvantului scris ın memoria push–down nu depaseste nkl,caci daca |α”| − |α′| > nkl, ar rezulta ca ın memoria push–down am aveazqm,∀m ∈ N si lungimea cuvantului nu ar fi finita.2

Teorema 3.14 Daca E este un limbaj independent de context determinist atuncilimbajul complementar I∗ \E este de asemenea independent de context determin-ist.

Demonstratie. Fie APDf = (Σ, I, Z, f, s0, z0, Σf ) automatul push–down de-terminist care recunoaste limbajul E. Construim un automat push–down deter-minist care va recunoaste limbajul I∗ \ E ın modul urmator

APD′f = (Σ× {σ1, σ2, σ3}, I, Z, f ′, s′0, z0, Σ

′f )

unde

s′0 =

{(s0, σ1) pentru s0 ∈ Σf ,(s0, σ2) pentru s0 6∈ Σf ,

multimea de stari finale este Σ′f = {(s, σ3)|s ∈ Σ} iar functia de evolutie este

definita de


(1) daca f(s, i, z) = (s′, q) atuncif ′((s, σ1), i, z) = ((s′, k′), q),f ′((s, σ2), i, z) = ((s, σ3), q),f ′((s, σ3), i, z) = ((s′, k′), q);

(2) daca f(s, λ, z) = (s′, q) atuncif ′((s, σ1), λ, z) = ((s′, k′), q),f ′((s, σ3), λ, z) = ((s′, k′), q);

unde k′ = 1 daca s′ ∈ Σf si k′ = 2 daca s′ 6∈ Σf .

Fie p ∈ L(APD′f ), atunci ((s0, σk), p, z0)

∗7−→((s, σ3), λ, q), k = 1, 2. In modnecesar, ultima configuratie trebuie sa fie precedata de o configuratie de forma((s′, σ2), λ, q), deci

(A) ((s0, σk), p, z0)∗7−→((s′, σ2), λ, q)7−→((s, σ3), λ, q)

de unde rezulta ca (s0, p, z0)∗7−→(s′, λ, q) si s′ 6∈ Σf . Deci p ∈ I∗\E si L(APD′

f ) ⊆I∗ \ E.

Invers, fie p ∈ I∗ \E, atunci ın APD′f avem evolutia (s0, p, z0)

∗7−→(s, λ, q), s 6∈Σf si putem scrie evolutia (A). Prin urmare p ∈ L(APD′

f ), adica I∗ \ E ⊆L(APD′

f ).2Consecinta. Putem enunta proprietatea de mai sus astfel: Familia limbajelor

independente de context deterministe este ınchisa la complementariere. Cumfamilia limbajelor independente de context nu este ınchisa la complementarieresi cum ea coincide cu familia limbajelor recunoscute de automatele push–downnedeterministe putem mai departe obtine urmatorul rezultat:

APD nedeterministe nu sunt echivalente cu APD deterministe.


1. Sa se arate ca L(G) = {(ab)na|n ≥ 0} unde G are productiile S →SbS, S → a. Sa se construiasca o gramatica echivalenta cu G care safie neambigua.

2. Eliminati redenumirile din gramatica GE ce genereaza expresiile aritmeticesimple.

3. Aduceti la forma normala Chomsky gramaticile ce au regulile:

(a) S → TbT, T → TaT |ca;

(b) S → aAC, A → aB|bAB, B → b, C → c;

(c) S → A.A,A → 0A|1A| . . . 9A|λ.

4. Gasiti forma normala Greibach pentru gramaticile:


(a) A1 → A2A3, A2 → A1A2|1, A3 → A1A3|0.

(b) GE care genereaza expresiile aritmetice simple.

5. Construiti un automat push–down pentru recunoasterea limbajului:

(a) L = {w|w ∈ {a, b}∗, numarul literelor a ın w este egal cu numarulliterelor b ın w };

(b) L = {w|w ∈ {a, b}∗, w = w};(c) L = {w|w ∈ {(, )}∗, w este un cuvant ın care fiecare paranteza deschisa

are o pereche, paranteza ınchisa }.6. Folosind lema de pompare sa se arate ca urmatoarele limbaje nu sunt inde-

pendente de context:

(a) L = {aibjck|i < j < k};(b) L = {aibj|j = i2};(c) L = {anbncn|n ≥ 1};(d) L = {ai|i prim };(e) L = {aibicj|j ≥ i};

Capitolul 4

Analiza Sintactica

Analiza sintactica este o faza a procesului de compilare care are urmatoarele douaobiective principale:

• Stabileste daca un cuvant dat apartine sau nu limbajului, deci daca cuvantuleste corect din punct de vedere sintactic. In particular limbajul poatefi definit de o gramatica generativa de tip Chomsky si deci termenul deanaliza sintactica trebuie ınteles ın sensul teoriei limbajelor formale. Maimentionam ca prin cuvant ıntelegem orice structura constituita cu sim-bolurile acceptate de limbaj, ın particular un ıntreg program, dar de obiceine vom margini la anumite entitati, de exemplu, o linie sau un rand.

• Determina derivarea (arborele de derivare) corespunzator cuvantului. Odatacu aceasta operatie sunt degajate anumite structuri pentru care se poategenera cod intermediar, structuri pe care le vom numi unitati sintactice.

Pe langa aceste obiective principale se mai efectuaza si alte operatii, de ex-emplu, analiza si tratarea erorilor, prelucrarea tabelelor, etc. Rezultatul anal-izei sintactice va fi un fisier care contine derivarile (arborii de derivare) core-spunzatoare unitatilor sintactice ın care este descompus programul: expresii ar-itmetice, declaratii, etc. Acest fisier este utilizat ın faza de generare a formatuluiintermediar. In mod curent ınsa, generatoarele de format intermediar sunt nisterutine, apelate de analizorul sintactic, astfel ıncat formatul intermediar se obtinesuccesiv.

Teoretic, problema analizei sintactice este rezolvata de automatele corespunzatoarediverselor tipuri de limbaje; aceasta cale conduce ınsa la algoritmi cu complex-itate mare (numar mare de stari, functie de tranzitie conmplexa, etc.). Existaalgoritmi speciali de analiza sintactica cu eficienta supe- rioara. In continuare nevom ocupa cu doua clase de astfel de algoritmi:

• Algoritmi top-down (de sus ın jos);

• Algoritmi bottom-up (de jos ın sus).

79

80 CAPITOLUL 4. ANALIZA SINTACTICA

4.1 Algoritmi TOP-DOWN

4.1.1 Algoritmul general de analiza top-down

Algoritmul general de analiza top-down are un principiu foarte simplu: se aplicaın mod sistematic regulile de generare, ıncepand cu simbolul de start; ın cazul unuiesec 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 preferentialade scriere, ıntrucat natura algoritmului nu permite nici un fel de ierarhizare aregulilor din punctul de vedere al frecventei de utilizare.

Pentru descrierea riguroasa a acestui algoritm am urmat modelul din cartealui 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 aceastaalegere este corecta trebuie sa avem x0 ⇒ x11 . . . x1n1

∗⇒p si ın conformitate culema de localizare a gramaticilor de tipul 2, cuvantul p se poate descompune ınforma p = p1p2 . . . pn1 , unde x1j

∗⇒pj, j = 1, . . . n1.Simbolul x0 ıl activeaza pe x11 si ıi cere sa gaseasca derivarea x11

∗⇒p1; daca x11

reuseste, transmite lui x0 succes. Simbolul x0 ıl dezactiveaza pe x11, ıl activeaza pex12 si ıi cere sa gaseasca derivarea x12

∗⇒p2, etc. Daca toate simbolurile activate dex0 transmit succes, constructia este terminata. Sa presupunem ca x1j transmiteesec; 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 reactiveaza pe x1j−2 caruia ıi cere o alta derivare. Procesul se continua ınacest mod fie spre dreapta, fie spre stanga. Daca se ajunge la x11 si acesta nureuseste sa gasasca o alta derivare, x0 decide ca prima regula aleasa nu este bunasi ıncearca cu urmatoarea regula, adica x0 → x21 . . . x2n2 , s. a. m. d.

Observatii

• Fiecare simbol devenit activ, procedeaza exact ca si parintele sau, alegeprima regula, activeaza primul simbol, etc.

• Nu se cunoaste anticipat descompunerea p = p1p2 . . . pn1 . Deci x1j trans-mite 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 punctulunde s-a terminat p1j−1. De exemplu, daca p = i1i2 . . . i8 . . . si p1 = i1i2i3i4,

4.1. ALGORITMI TOP-DOWN 81

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 exemplul demai sus, daca x13 coincide sau nu cu i7).

• Cand se reactiveaza un simbol si i se cere o noua derivare, acesta reactiveazaultimul simbol fiu si ıi cere acelasi lucru.

Exemplu Consideram urmatoarea gramatica GE care genereaza expresii ar-itmetice simple. Operanzii sunt notati simbolic cu a, operatorii sunt + si * iarordinea naturala a operatiilor este completata de paranteze.

E → T + E|TT → F ∗ T |FF → (E)|a

Procesul de analiza sintactica top-down pentru cuvantul p = a∗a este prezen-tat ın figura 4.1.

In aceasta figura, revenirile ın sus au fost marcate prin ıncadrarea ıntr-undreptunghi a subarborelui care a condus la un esec. Dreptunghiurile interioareau semnificatia unor esecuri realizate mai devreme (este vorba de timpul dedesfasurare al procesului). Arborele corespunzator cuvantului este cel neıncadratın vreun dreptunghi (ın figura acesta este situat ın partea dreapta).

4.1.2 Analiza top-down fara reveniri

In cazul unor gramatici cu o forma speciala se poate face o analiza de tip top-downfara reveniri. Principala conditie este ca ın cazul mai multor alternative (reguli cuacelasi simbol ın stanga), sa se poata decide cu precizie ramura corecta. In generalo astfel de decizie se poate realiza prin analiza unor simboluri care urmeaza ıncuvantul de analizat.

Exemplu Consideram urmatoarea gramatica G care genereaza secvente dedeclaratii si instructiuni cuprinse intre cuvintele cheie Program si EndPro-gram. Declaratiile sunt notate simbolic cu d,iar instructiunile cu i. Fiecareinstructie sau declaratie se ıncheie cu ;, exceptand cazul celei ce precede End-Program.

G

< program >→ Program D I EndProgramD → d; XX → d; X|λI → iYY →; iY |λ

Sa consideram urmatorul cuvant de analizat


E

T + E

F * T

( E ) F * T

( E ) i

i

F

( E )

i

F

( E )

i

7

5

3

2

4

6

1 F T

( E ) F * T

( E ) i

i

F

( E )

i

E

T

*

8

9

10

11

Figura 4.1: Arborele sintactic pentru p = i ∗ i


Program

d;

d;

i;

i;

i;

EndProgram

O derivare extrem stanga pentru acest cuvant este

< program >⇒ Program D I EndProgram ⇒ Program d; X I EndProgram⇒ Program d; d; X I EndProgram ⇒ Program d; d; I EndProgram⇒ Program d; d; iY EndProgram ⇒ Program d; d; i; iY EndProgram⇒ Program d; d; i; i; iY EndProgram ⇒ Program d; d; i; i; i EndProgram

Pentru constructia derivarii extrem stangi se procedeaza astfel: initial se con-sidera simbolul de start < program > pentru care se alege singura regula disponi-bila (daca primul simbol din sirul de analizat nu coincide cu primul terminal alregulii se poate decide imediat eroare sintactica).Urmatorul simbol neterminalpentru care trebuie aleasa o regula este D iar sirul ramas de analizat (de generat)ıncepe cu d, astfel ca regula aleasa va fi D → d; X. Din cuvantul initial trebuiegenerata ın continuare secventa d; i; i; i; EndProgram ce ıncepe cu d iar neter-minalul cel mai din stanga este X, astfel ca se alege regula ce ıncepe cu d. Incontinuare, din cuvantul initial ramane de generat secventa i; i; i; EndProgramce ıncepe cu i iar neterminalul cel mai din stanga este X, astfel ca se alege regulace X → λ, s.a.m.d.

Daca se considera gramatica ce genereaza expresii aritmetice simple, ın formaconsiderata la algoritmul general top-down (4.2.9), atunci la primul pas al uneiderivari extrem stangi pentru cuvantul (a + a ∗ a) + a nu se poate decide regulade ales prin citirea primului terminal ( deoarece ar fi necesar sa consultam sirulrezultat pana la ıntalnirea operatorului + aflat dupa paranteza ınchisa.

O gramatica pentru care alegerea regulii de aplicat este unic determinatade urmatorul simbol terminal din sirul de analizat se numeste gramatica LL(1)(Left to right parsing, Leftmost derivation, 1 symbol lookahead). In multe cazuriexista posibilitatea de a transforma gramatica ıntr-una echivalenta de tip LL(1).Pentru cazul particular al gramaticii pentru generarea expresiilor aritmetice, ogramatica echivalenta este urmatoarea:

E → TE ′

E ′ → +TE ′| − TE ′|λT → FT ′

T ′ → ∗FT ′|/FT ′|λF → (E)|id|num


< bloc >→ {< lista >}< lista >→< instr > LL →; < instr > L | λ< instr >→ id = E|if(E)then < instr > |while(E)do < instr > |{< lista >}E → TE ′

E ′ → +TE ′| − TE ′|λT → FT ′

T ′ → ∗FT ′|/FT ′|λF → (E)|id|num

Figura 4.2: Gramatica pentru generarea blocurilor de instructiuni.

{

a = 2;

b = b + 1;

if ( b-a ) then { x = x-1;

a = 3 };

c = b*72

}

Figura 4.3: Program sursa de analizat sintactic

4.1.3 Programarea unui analizor sintactic. Studiu de caz

Programarea unui analizor sintactic top-down fara reveniri se poate face relativusor asociind cate o functie la fiecare neterminal. Analiza unui cuvant revinela un sir de apeluri corespunzatoare tratarii simbolurilor ce apar pe parcursulconstructiei derivarii extrem stangi. Fiecare functie asociata contine o singurainstructiune switch cu clauze ce corepund regulilor gramaticii. Alegerea reguliise face dupa urmatoarea unitate lexicala din textul de analizat.

Sa consideram urmatoarea gramatica (vezi figura 4.2) ce genereaza un blocde instructiuni de atribuire, conditionale de tip if (expresie aritmetica) theninstructiune sau repetitive de tip while. Instructiune poate fi o instructie simplasau bloc de instructiuni separate prin delimitatorul ;(SEMICOLON).

Un text sursa ce poate fi analizat de aceasta gramatica este cel din figura 4.3.

Lista de unitati lexicale furnizate de analizorul lexical este pentru acest caz

LBRACE id LET num SEMI id LET id PLUS num SEMI if LPAR id MINUS idRPAR then LBRACE id LET id LET id minus num SEMI id LET num RBRACESEMI id LET id ORI num RBRACE.


Un program pentru analiza sintactica top-down fara reveniri corespunzatorgramaticii din figura 4.2 este reprezentat partial ın figura 4.4. Lista codurilorde unitati lexicale (terminalele gramaticii) contine SEMI LPAR RPAR s.a.m.d.Presupunem ca analizorul lexical functioneaza ca functie ce returneaza codulurmatoarei unitati lexicale din textul sursa. Variabila de tip ıntreg token continecodul returnat de analizorul lexical ALEX(). S-au mai definit doua functii: err()pentru tratarea erorilor de sintaxa depistate si eat(int tok) ce consuma din textulsursa unitatea lexicala tok pe care ne asteptam sa o gasim ın text.

Rularea programului pentru exemplul din figura 4.3 va produce o secventa deapeluri recursive ca ın figura 4.5.

Un pic de algebraVom da ın cele ce urmeaza o definitie riguroasa a gramaticilor LL(k) (k sim-

boluri citite ın avans) vom da ın cele ce urmeaza , ımpreuna cu conditiile necesaresi suficiente ca o gramatica sa intre ın aceasta categorie.

Definitie Fie G = (VN , VT , S,P) o gramatica independenta de context. G sezice de tip LL(k) daca si numai daca oricare ar fi doua 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 limba-jelor ce por fi analizate cu astfel de gramatici. Un inconvenient major pentruk > 1 este cresterea exponentiala a dimensiunii tabelei de predictie (cate o in-trare ın tabel pentru fiecare combinatie de k simboluri. O varianta mai eficientade analiza se obtine cu gramatici LR(1) (Left to right parsing, Rightmost deriva-tion, 1 symbol lookahead).

Pentru orice α ∈ V +G , X ∈ VN , X → α ∈ P vom considera urmatoarele

multimi:

Prim(α) = {a ∈ VT |α ∗⇒aβ, β ∈ V ∗G}

Urm(α) = {a ∈ VT |S ∗⇒uXv, a ∈ Prim(v)}SD(X, α) = {a ∈ VT | a ∈ Prim(α) sau (α

∗⇒λ si a ∈ Urm(X) )}NULL(G) = {X ∈ VN |X ∗⇒λ}

Daca un terminal a ∈ Prim(α) atunci a poate aparea pe prima pozitie ıntr-unsir derivat din α. Multimea SD(X, α) poarta denumirea de multimea simbolurilordirectoare asociate regulii X → α, iar NULL(G) contine neterminalele ce se potsterge (ın unul sau mai multi pasi) cu reguli din G.

Teorema.

G ∈ LL(k) ⇔ SD(X, α) ∩ SD(X, β) = Φ, ∀X → α, X → β ∈ P , β 6= α


final int if=1, then=2, LPAR=3, RPAR=4, LBRACE=5, RBRACE=6,

PLUS=7, MINUS=8, ORI=9, DIV=10, SEMI=11, id=12,

while=13, do=14, LET=15;

void err();

int ALEX();

int token = ALEX();

void eat(int tok){

if (tok==token) token=ALEX else err()

};

void bloc(){

eat(LBRACE); lista(); eat(RBRACE)

};

void lista(){

instr();L()

};

void L(){

switch(token){

case SEMI: eat(SEMI); instr(); L(); break;

default: break }

};

void instr(){

switch(token){

case if: eat(if); eat(LPAR); E(); eat(RPAR); eat (then); instr(); break;

case id: eat(id); eat(LET); E(); break;

case while: eat(while); eat(LPAR); E(); eat(RPAR); eat(do); instr(); break;

case LBRACE: eat(LBRACE); instr(); eat(RBRACE); break;

default: printf("syntax error: if, identif, while or left brace expected");

err()}

};

...

void E(){

T(); Eprime();

};

void Eprime(){

switch(token) {

case PLUS: eat(PLUS);T();Eprime();break;

case MINUS: eat(MINUS);T();Eprime();break;

default: break;

}

};

...

Figura 4.4: Cod C corespunzator analizorului sintactic


bloc()

eat(LBRACE);

lista()

instr()

eat(id);

eat(LET);

E()

T()

F()

eat(num);

return_F;

Tprime()

return_Tprime;

return_T;

Eprime()

return_Eprime;

return_E;

return_instr;

L()

eat(SEMI)

instr()

.... aici se recunoaste ; b = b + 1

return_instr;

L()

eat(SEMI);

instr()

.... aici se recunoaste ; if ( ... }

return_instr;

L()

.... aici se recunoaste ; c = b * 72

return_L();

return_L;

return_L;

return_lista;

eat(RBRACE);

return_bloc;

Figura 4.5: Executia analizei lexicale pentru textul sursa


Determinarea multimilor definite anterior se poate face usor. Pentru NULL(G),se poate aplica algoritmul definit la eliminarea regulilor de stergere pentru o gra-matica independenta de context.

NULL = {X ∈ VN |X → λ ∈ P}repeat(1) AUX = NULL;(2) NULL = NULL ∪ {X ∈ VN |X → p, p ∈ AUX+};until NULL = AUX2

Calculul multimilor Prim(X) si Urm(X) se poate face cu algoritmul urmator:

Pas 1: { Initializare }Prim(a) = {a};∀a ∈ VT

Prim(X) = Urm(X) = Φ; ∀X ∈ VN

Pas 2: RepeatPentru fiecare regula X → Y1Y2 . . . Yk Do

For(i = 1; i ≤ k; i + +)(2.1)if (i = 1 sau Y1Y2 . . . Yi ∈ NULL+)

Prim(X) = Prim(X) ∪ Prim(Yi);(2.2)if (i = k sau Yi+1 . . . Yk ∈ NULL+)

Urm(Yi) = Urm(Yi) ∪ Urm(X);(2.3)For (j = i + 1 j ≤ k; j + +)

if (j = i + 1 sau Yi+1 . . . Yj−1 ∈ NULL+)Urm(Yi) = Urm(Yi) ∪ Prim(Yj);

end forend for

end doUntil Prim(X), Urm(X) nu se schimba la o iteratie.2

Calculul multimilor Prim(α) revine la definitia recursiva

Prim(Xα) =

{Prim(X) dac′a X /∈ NULL(G)Prim(X) ∪ Prim(α) dac′aX ∈ NULL(G)

Daca se considera gramatica ce genereaza expresii aritmetice 4.1.2, atuncirezultatul aplicarii algoritmilor este prezentat ın tabelul urmator:

NULL Prim UrmE ( , i )E ′ DA + , − )T ( , i + , − , )T ′ DA ∗ , / + , − , )F ( , i ∗ , / , )

,


iar multimile simbolurilor directoare suntSD(E, TE ′) = {( , i}SD(E ′, +TE ′) = {+}SD(E ′, λ) = {)}SD(T, FT ′) = {( , i}SD(T ′, ∗FT ′) = {∗}SD(T ′, λ) = {+ )}SD(F, (E)) = {(}SD(F, id) = {id}SD(F, num) = {num}

Functiile C sau Java corespunzatoare neterminalelor se modifica putin, ın sen-sul ca vom avea clauze corespunzatoare simbolurilor terminalelor ce se regasescın multimile simbolurilor directoare asociate regulilor. Daca la reconstructia de-rivarii trebuie aplicata o regula pentru X si urmatorul terminal din textul deanalizat nu face parte din multimea simbolurilor directoare asociate vreunei reg-uli cu X ın stanga, atunci se apeleaza modulul de tratare a erorilor sintactice.

Pentru cazul gramaticii anterioare, cateva din secventele de cod asociate neter-minalelor sunt prezentate ın continuare.

...

void E(){

switch(token) {

case LPAR:

case id:

case num: T(); Eprime(); break;

default: printf("syntax error: (,identifier or number expected");

err()

}

}

void Tprime(){

switch(token) {

case ORI: eat(ORI);F();Tprime();break;

case DIV: eat(DIV);F();Tprime();break;

case PLUS:

case RPAR: break;

default: printf("syntax error: *,/,+,) expected");

err()

}

}

Tratarea erorilor este dependenta de proiectantul compilatorului si limbaj.Principial, exista trei modalitati de tratare.


• Se opreste analiza sintactica ın punctul unde s-a depistat o eroare, cu trans-miterea unui mesaj prietenos catre utilizator, de exemplu: Eroare sintac-tica: asteptam sa urmeze delimitator de instructiune. Mai ınvata sintaxalimbajului! BYE!.

• Se ıncearca repararea greselii de sintaxa inserand ın textul sursa un simboldin multimea de simboluri directoare asociate regulii ce s-a aplicat. Desigurca este suficient sa presupunem ca am inserat ın text, astfel ıncat analizapoate continua (desigur nu vom uita sa anuntam utilizatorul ca nu cunoasteregulile de sintaxa si l-am corectat noi!). Inserarea poate conduce la cicluriinfinite, astfel ca nu este recomandabila totdeauna.

• Se ıncearca gasirea unui simbol ce se potriveste ignorand toate terminaleletextului sursa pana se ıntalneste un simbol din multimea simbolurilor di-rectoare. Se transmite acelasi mesaj prietenos catre autorul textului sursa,apoi se continua analiza.

4.2 Algoritmi BOTTOM-UP

4.2.1 Gramatici cu precedenta 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 frontiera 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.

Exemplu. Consideram gramatica GE 4.2.9 si forma propozitionala p = T ∗F +a ∗ (E + T ). Arborele de derivare este prezentat ın figura 4.6. Se poate observaca frazele simple sunt T ∗ F, a, E + T .

Observatie. Subcuvantul F respecta prima conditie dar nu este fraza simpla,ıntrucat nu este satisfacuta conditia a doua din definitie.

Definitia 2. Fraza simpla cea mai din stanga poarta denumirea de frazasimpla 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. In principiu, acestialgoritmi prevad urmatorii pasi (descrisi de figura 4.7):

Regulile determinate la pasul (3), aplicate ın ordine inversa, ne vor da derivareacorespunzatoare lui p. Sa mai observam ca ın acest mod arborele de derivare se

4.2. ALGORITMI BOTTOM-UP 91

E

E + T

T

T * F F

T * F

( E )

a E + T

Figura 4.6: Arborele de derivare corespunzator derivarii lui p = T ∗F +a∗(E+T )

(1) Initializare p;(2) Se determina fp, fraza simpla stanga a lui p;(3) Se determina regula x → fp;(4) Se reduce fraza simpla stanga, adica daca p = rfps, se pune p = rxs;GOTO(2).

Figura 4.7: Algoritmul bottom-up


construieste de jos ın sus (bottom-up). Problema cea mai dificila este desigurdeterminarea frazei simple stangi de la pasul (2). In principiu ar trebui cunoscutanticipat arborele de derivare corespunzator lui p, dar tocmai acesta este scopulanalizei sintactice. Dupa cum vom vedea, aceasta dificultate se poate elimina,deci putem determina fraza simpla stanga fara a cunoaste acest arbore. De fapt,fraza simpla stanga este legata de anumite proprietati ale gramaticii pe care letratam ın continuare.

4.2.2 Relatii de precedenta

Definitia 3. Fie x, y ∈ VG doua simboluri oarecare ale gramaticii.Vom spune ca:(1) x ≺ y (x precede pe y) daca ∃p astfel ıncat p = rxys, x /∈ fp, y ∈ fp;(2) x± y (x este egal cu y) daca ∃p astfel ıncat p = rxys, x ∈ fp, y ∈ fp;(2) x Â y (y succede lui x) daca ∃p astfel ıncat p = rxys, x ∈ fp, y /∈ fp;

Relatiile ≺ ± Â se numesc relatii de precedenta simple (atunci cand nu existaposibilitatea de confuzie se folosesc denumirile mai mic, egal, mai mare pentrurelatiile de precedenta). Sa observam ca aceste relatii nu se exclud reciproc, decica putem avea, de exemplu, x ≺ y si ın acelasi timp x Â y, ıntrucat pot existacazuri de gramatici ın care putem gasi doua forme propozitionale p1, p2 astfelıncat sa avem simultan cele doua relatii. Sa mai facem de asemenea observatiaca exista mai multe tipuri de astfel de relatii, cu definitii asemanatoare, ıntrucatrelatiile trebuie sa satisfaca conditii suplimentare care depind si de gramatica;pentru toate aceste tipuri de relatii vom utiliza aceleasi notatii.

Definitia 4. O gramatica de tipul 2 spunem ca este cu precedenta simpladaca ıntre oricare doua simboluri ale gramaticii exista cel mult o relatie deprecedenta.

Pentru algoritmul de analiza sintactica ascendenta este important ca sa nuexiste reguli cu partile drepte identice; altminteri, ın cadrul pasului (4) din algo-ritmul de analiza sintactica nu se poate decide la cine sa se faca reducerea frazeisimple stangi. De asemenea regulile de stergere nu sunt admise, pentru acestcaz notiunea de fraza simpla neavand sens. Aceste conditii presupunem ın modsistematic ca sunt satisfacute.

Fie acum VG = {x1, x2, . . . , xn} alfabetul general, unde am adoptat o anumitaordine a simbolurilor. Definim matricea de precedenta a gramaticii,

M = (aij), unde aij =

≺ daca xi ≺ xj

± daca xi ± xj

Â daca xi Â xj

Exemplu. Consideram urmatoarea gramatica

G = ({A,B}, {0, 1}, A, {A → A0|1B, B → 1}).


Matricea de precedenta va fi

A B 0 1A ≺B Â0 Â1 ± Â ≺

4.2.3 Proprietati ale gramaticilor cu precedenta simpla

Proprietatea 1. Fie p = a1 . . . an o forma propozitionala ıntr-o gramatica cuprecedenta simpla (ai sunt simboluri neterminale sau terminale ale gramaticii).Atunci fp = ai . . . aj daca si numai daca

a1

±≺a2 . . .±≺ai−1 ≺ ai ± ai+1 . . .± aj Â aj+1 (∗)

Demonstratia acestei proprietati se efectueaza considerand toate structurilede arbori de derivare posibile ıntr-o situatie data. Vom exemplifica aceasta ideepentru cuvanul p = a1 . . . a7. Daca presupunem ca fp = a3a4a5, atunci, conformdefinitiei frazei simple stangi, avem

a2 ≺ a4, a4 ± a5, a5 Â a6

Mai trebuie aratat ca a1

±≺a2. In acest scop vom considera toate posibilitatilede structuri arborescente; o parte din ele sunt prezentate ın figura 4.8.

Se poate observa ca ın ipoteza ca fp = a3a4a5, singurele situatii posibile sunt(a) si (b). Celelalte situatii contrazic aceasta ipoteza, de exemplu, ın cazurile (c)si (d) fraza simpla stanga ar fi , respectiv, a1a2 sau a2. Acum, ın cazul (a), prinreducerea succesiva a frazei simple stangi, vom obtine un arbore ın care frazasimpla stanga va fi a1a2, adica a1 ± a2 iar ın cazul (b), fraza simpla stanga va fia2 si atunci a1 ≺ a2.

Implicatia inversa se bazeaza pe cea directa; se presupune ca fp = al . . . akcul 6= i si k 6= j si se considera ın continuare toate posibilitatile de pozitionare aindicilor l, k fata de i, j. De exemplu, daca fp = a2a3 atunci, conform implicatieidirecte, avem

a1 ≺ a2 ± a3 Â a4

ceea ce contrazice relatia (*), conform careia a3±a4 iar gramatica are precedentasimpla.

Observatie La delimitarea frazei simple stangi se procedeaza astfel: parcurgemsirul de simboluri de la stanga la dreapta pana se gaseste relatia Â (sau margineadreapta a formei propozitionale) pentru determinarea ultimului simbol din fp,apoi se parcurge sirul spre stanga, trecand peste relatii ±, pana la gasirea unei


a 3 a 4 a 5 a 6 a 7 a 1 a 2 a 3 a 4 a 5 a 6 a 1 a 2

a 3 a 4 a 5 a 6 a 1 a 2 a 3 a 4 a 5 a 6 a 1 a 2 a 7 a 7

a 7

(a) (b)

( c) (d)

Figura 4.8: Arbori de derivare posibili

x 0

a 1 a 2 . . . a n

Figura 4.9: Arborele de derivare pentru ni = 1

relatii ≺ (sau marginea dreapta a formei propozitionale) pentru determinareaprimului simbol din fp.

Proprietatea 2. O gramatica cu precedenta simpla este neambigua.

Schita de demonstratie. Fie p o forma propozitionala si Ax0,p arborele dederivare corespunzator. Vom arata ca acest arbore este unicul arbore de derivarecare are radacina x0 si frontiera p. Procedam prin inductie asupra numarului denoduri interne ni. Daca ni = 1 atunci arborele de derivare va avea forma dinfigura 4.9 si unicitatea acestuia este evidenta. Presupunem acum ca proprietateaeste adevarata pentru un ni oarecare si consideram cazul ni + 1. Sa presupunemca ar exista doi arbori diferiti cu radacina x0 si frontiera p; fie acestia A′

x0,p siAx0,p.

Deoarece gramatica este cu precedenta simpla, rezulta ca fraza simpla stanga,care este aceiasi ın cei doi arbori, este situata ın aceiasi pozitie, p = rfps.Efectuam reducerea frazei simple fp (conform regulii aplicate x → fp) si vom


obtine arborii A′x0,q si Ax0,q unde q = rXs iar cei doi arbori trebuie sa fie diferiti.

Dar numarul de noduri interne este ni, ın contrazicere cu ipoteza.

4.2.4 Determinarea relatiilor de precedenta pentru gra-matici cu precedenta simpla

Asa cum s-a precizat deja, relatiile de precedenta sunt proprietati intrinseci alegramaticii, nu depind de contextul ın care se afla cele doua simboluri. Prin ur-mare, cunoasterea anticipata a acestor relatii ımpreuna cu proprietatea 1, rezolvacomplet problema pasului 2 de la algoritmul de analiza bottom-up, adica deter-minarea frazei simple stangi. In acest subparagraf vom prezenta o teorema decaracterizare pe baza careia se pot determina relatiile de precedenta simple siimplicit faptul daca gramatica este sau nu cu precedenta simpla.

Vom defini doua relatii specifice gramaticilor si care vor fi utilizate ın con-tinuare, numite, respectiv, F (First) si L (Last). Fie x ∈ VN si y ∈ VG douasimboluri ale gramaticii. Vom spune ca

xFy daca ∃x → yu ∈ P , u ∈ V ∗G

xLy daca ∃x → uy ∈ P , u ∈ V ∗G

Inchiderile tranzitive, respectiv, tranzitive si reflexive ale acestor relatii le vomnota cu F+, L+ si respectiv, F ∗, L∗. Exista numerosi algoritmi directi carepermit calcularea acestei ınchideri,cu complexitate redusa.

Teorema 2. Avem

(1) x ≺ y ⇔ ∃u → . . . xv . . . ∈ P , vF+y;(2) x± y ⇔ ∃u → . . . xy . . . ∈ P ;(3) x Â y ⇔ ∃u → . . . vw . . . ∈ P , vL+x,wF ∗y;

Schita de demonstratie. Se analizeaza posibilitatile de arbori de derivare careraspund cerintelor teoremei. De exemplu, pentru cazul (1), trebuie sa existestructura de arbore ca ın figura 4.10.

Este clar ca daca x ≺ y, atunci conform definitei frazei simple stangi, tre-buie sa existe p astfel ıncat p = rxys, x /∈ fp, y ∈ fp, adica sa existe struc-tura din 4.10. Invers, daca exista o astfel de structura, atunci fie o formapropozitionala care contine u. Efectuam reduceri succesive pana cand vom obtineo forma propozitionala pentru care u apartine frazei simple stangi; la arboreleastfel obtinut, adaugam subarborele de mai sus. Vom avea ın mod evidentx /∈ fp, y ∈ fp.

4.2.5 Studiu de caz

Sa consideram cazul gramaticii pentru generarea expresiilor aritmetice simpleGE, cu regulile obisnuite


u

v

... x y ...

Ramificatii spre dreapta

Figura 4.10: Arborele de derivare corespunzator cazului x ≺ y

E T F + ∗ ( ) aE ± ±T Â ±F Â Â+ ≺ ± ≺ ≺ ≺∗ ± ≺ ≺( ≺ ± ≺ ≺ ≺ ≺) Â Â Âa Â Â Â

Figura 4.11: Matricea de precedenta pentru GE

E → E + T |TT → T ∗ F |FF → (E)|a

Relatiile First, Last si ınchiderile acestora sunt:

E F {E, T} E F+ {E, T, F, (, a} E F ∗ {E, T, F, (, a}T F {T, F} T F+ {T, F, (, a} T F ∗ {T, F, (, a}F F {(, a} F F+ {(, a} F F ∗ {F, (, a}

E L {T} E L+ {T, F, a, )} E F ∗ {E, T, F, a, )}T L {F} T L+ {F, a, )} T F ∗ {T, F, a, )}F L {a, )} F L+ {a, )} F F ∗ {F, a, )}

Conform teoremei de calcul a relatiilor de precedenta vom obtine matricea deprecedenta (vezi figura 4.11) asociata simbolurilor gramaticii GE.


G :

{A → A0 | B1B → 1

S a bS ± ≺ ±a ± ≺ ±b Â Â Â

Figura 4.12: Exemplu de gramatica cu precedenta simpla

Regula Forma propozitionalaa ≺ a ≺ a± b Â aababbbabb

S → ab a ≺ a± S ≺ a ≺ a± b Â abbbabbS → ab a ≺ a± S ≺ a± S ≺ a± b Â bbabbS → ab a ≺ a± S ≺ a± S ± S ± b Â babbS → aSSb a ≺ a± S ± S ± b Â abbS → aSSb a± S ≺ a± b Â bS → ab a± S ± S ± bS → aSSb S

Figura 4.13: Reconstructia derivarii cuvantului p = aaabaababbbabb

Deci gramatica GE nu are proprietatea de precedenta simpla, astfel ca nupoate fi aplicat direct algoritmul de analiza sintactica bottom up.

Vom exemplifica algoritmul de analiza pentru gramatica din figura 4.12, ma-tricea de precedenta asociata este cea alaturata.

Reconstituirea derivarii cuvantului p = aaabaababbbabb este prezentata ıntabelul 4.13, unde fiecare linie corespunde formei propozitionale, ın care frazasimpla stanga este subliniata, precedata de regula identificata.

4.2.6 Gramatici operatoriale

Gramaticile operatoriale sunt gramatici cu o structura speciala a regulilor derescriere, ın care anumite simboluri sunt considerate operatori iar celelalte oper-anzi, operatorii trebuind sa separe operanzii. Aceasta structura este preluata dela gramaticile care genereaza expresiile aritmetice iar principiul de analiza estede asemenea preluat de la algoritmul de evaluare a expresiilor aritmetice. In con-tinuare vom prezenta acest principiu pentru evaluarea expresiilor aritmetice faraparanteze, cazul expresiilor cu paranteze putandu-se reduce la cel fara paranteze,de exemplu utilizand tehnica de modificare a ponderilor operatorilor la ıntalnireaparantezelor.

In primul rand se atribuie operatorilor anumite ponderi care vor defini ordineade efectuare a operatiilor. De obicei, se considera p(+) = p(−) = 1 < 2 = p(∗) =


p(/), ceea ce ınseamna ca mai ıntai se fac adunarile si scaderile, apoi ınmultirilesi ımpartirile, etc. Efectuarea unei operatii depinde de contextul ın care se aflaoperatorul respectiv, si anume, daca ponderea operatorului precedent este maimare sau egala cu ponderea operatorului curent, atunci se poate efectua operatiadefinita de operatorul precedent. Din acest motiv, acest tip de gramatici senumesc cu operator de precedenta (operator precedence grammars).

Putem realiza un algoritm simplu de evaluare utilizand doua stive

• P- stiva operatorilor;

• S- stiva operanzilor.

Vom utiliza indicii i si k pentru a indica nivelele celor doua stive. Prin urmare,notatia pi, respectiv sk au sensul de operatorul, respectiv operandul din stiva aflatpe nivelul i, respectiv k. Pentru simplificare, vom utiliza aceiasi notatie pi atatpentru operator cat si pentru ponderea operatorului respectiv.

Algoritmul de evaluare:PAS 1: Initializari: Se introduce primul operator si primul operand ın stivele Psi S si se initializeaza nivelele celor doua stive, i = k = 2;PAS 2: Se introduce urmatorul operator ın stiva P si se actualizeaza nivelul,i = i + 1;PAS 3: Daca pi−1 < pi atunci se introduce urmatorul operand ın lista S, seactualizeaza nivelul stivei, k = k + 1, si se revine la pasul 2;PAS 4: Daca pi−1 ≥ pi atunci:

ın stiva P : pi−1 se ınlocuieste cu pi;ın stiva S: sk−1 se ınlocuieste cu sk−1pi−1sk;se actualizeaza nivelele celor doua stive, i = i − 1; k = k − 1 si se revine la

pasul 3.Observatie. Pentru uniformitatea algoritmului se introduce operatorul mar-

caj, notat cu # , cu ponderea cea mai mica; orice expresie se ıncadreaza ıntre douamarcaje iar oprirea algoritmului are loc la pasul 4 ın cazul ın care p1 = p2 = #.Schematic, acest algoritm este prezentat ın figura 4.14.

Exemplu. Tabelul 4.15 contine starea dinamica a celor doua stive pentruexpresia #a + b ∗ c/d− f#. Mentionam ca ın cadrul pasilor 2 si 4 s-a completatcate un rand nou ın tabel.

Observatie. Ponderile operatorilor sunt legate de ierarhia lor ın gramatica, cucat un operator este mai jos cu atat ponderea lui este mai mare. Acest fapt esteilustat ın figura 4.16.

Pentru cazul expresiilor aritmetice cu paranteze algoritmul se pastreaza, dareste aplicat dupa preprocesarea expresiei prin modificarea dinamica a ponder-ilor operatorilor si renuntarea la paranteze. Se parcurge expresia de la stanga ladreapta alocand ponderi operatorilor; la ıntalnirea unei paranteze deschise pon-derile se incrementeaza cu 10, iar la ıntalnirea unei paranteze ınchise se decre-menteaza ponderile operatorilor cu 10. In continuare parantezele sunt ignorate.


p 1 s 1 i=2, k =2 1.

2.

3.

4.

p i

i=i+1

p i-1 < p i

s k

k = k +1

p i-1 ³ p i

dupa prelucrare

i=i+1, k = k +1

s k p i-1

p i-1

p i

p i s k - 1 p i - 1 s k

s k -1

s k -1

inainte de prelucrare

Figura 4.14: Prelucrarile efectuate asupra celor doua stive

1 2 3 4 1 2 3 41 #0 a2 #0 +1 a b3 #0 +1 −1 a b4 #0 −1 a + b c5 #0 −1 ∗2 a + b c d6 #0 −1 ∗2 /2 a + b c d7 #0 −1 /2 a + b c ∗ d f8 #0 −1 /2 #0 a + b c ∗ d f9 #0 −1 #0 a + b c ∗ d/f10 #0 #0 a + b− c ∗ d/f

Figura 4.15: Evaluarea expresiei #a + b− c ∗ d/f#


E

E + T

*

E

+

T

T E

*

T

F T

F

p(+)<p(*) p(*)>p(+)

Figura 4.16: Ierarhia operatorilor

De exemplu, expresia

a ∗ (b− c ∗ d)− (x + y/(z − t)) ∗ h

devine prin preprocesare

a ∗2 b−11 c ∗12 d−1 x +11 y/12z −21 t∗2

ceea ce va asigura ordinea corecta de evaluare.

4.2.7 Gramatici operatoriale

Fie G = (VN , VT , x0,P) o gramatica de tipul 2. Vom considera ca simbolurileneterminale VN sunt operanzii limbajului iar simbolurile terminale VT sunt oper-atorii. Sa observam ca ın cazul gramaticii GE care genereaza expresii aritmeticesimple o asemenea conventie este justificata, deoarece oricare din neterminaleleE, T, F deriveaza ın terminalul a (generic, acest terminal reprezinta operanzii),sau ıntr-o expresie (eventual ıntre paranteze) care are rolul de operand.

Definitia 1. Vom spune ca o gramatica este operatoriala daca regulile derescriere au forma

X → NiTiNi+1Ti+1 . . . TjNj+1,

unde Nk sunt neterminale (operanzi), inclusiv cuvantul vid, iar Tk sunt terminale(operatori).

Observatie. Intr-o gramatica operatoriala orice forma propozitionala are struc-tura:

p = N1T1N2T2 . . . TnNn+1


N i N i +1 N j +1

T i T i +1 T j N' i N' i +1 N' j +1

x

Figura 4.17: Structura subarborelui

Aceasta ınseamna ca ıntr-o forma propozitionala a unei gramatici operatorialeıntre oricare doi operanzi exista cel putin un operator; pot ınsa exista mai multioperatori alaturati, de exemplu, . . . ((a . . ..

Definitia 2. Fie p = N1T1N2T2 . . . TnNn+1 o forma propozitionala ıntr-ogramatica operatoriala. Vom spune ca f este o fraza simpla a lui p daca f =NiTiNi+1Ti+1 . . . TjNj+1 este un subcuvant al lui p care contine cel putin un simbolterminal si ın plus:

(1) ∃x → N ′iTiN

′i+1Ti+1 . . . TjN

′j+1 ∈ P , si N ′

k∗⇒Nk ∀k = i, . . . , j.

(2) Ax,f ⊂ Ax0,p.Structura de arbore corespunzatoare unei fraze simple este prezentata ın figura4.17.

Ca si ın cazul gramaticilor cu precedenta simpla, fraza simpla cea mai dinstanga poarta denumirea de fraza simpla stanga. Principiul de analiza sintacticaeste identic cu cel de la gramatici cu precedenta simpla. Problema principalaeste si aici determinarea frazei simple stangi. Aceasta operatie poate fi facutautilizand relatiile de precedenta dintre simbolurile gramaticii care pentru gra-matici operatoriale au o definitie putin modificata.

Definitia 3. Fie x, y ∈ VT . Vom spune ca:

(1) x◦<y (x precede pe y) daca ∃p astfel ıncat p = rxNys, N ∈ VN , x /∈ fp, y ∈ fp;

(2) x◦=y (x este egal cu y) daca ∃p astfel ıncat p = rxNys, N ∈ VN , x /∈ fp, y ∈

fp;

(2) x◦>y (y succede lui x) daca ∃p astfel ıncat p = rxys, N ∈ VN , x ∈ fp, y /∈ fp;

Matricea de precedenta se defineste numai pe multimea simbolurilor termi-nale, ceea ce conduce la o simplificare a algoritmului de analiza.

Definitia 4. O gramatica operatoriala se spune ca are precedenta simpla dacaıntre doua simboluri ale gramaticii exista cel mult o relatie de precedenta.

Ca si la celelalte tipuri de gramatici, ın vederea efectuarii pasului 3 din algo-ritmul de analiza, vom presupune ca nu exista reguli cu partile drepte identice.


N 1 N 2 T 1 T 2

N 3

T 3 T 5 T 4

N 4 N 5

N' 3 N' 4 N' 5 N 1 N 2 T 1 T 2

N 3

T 3 T 5 T 4

N 4 N 5

N' 3 N' 4 N' 5

(a) (b)



Figura 4.18: Structurile posibile de arbori

De asemenea, sunt valabile proprietatile de caracterizare si de neambiguitate.Proprietatea 1. Fie p = N1T1N2T2 . . . TnNn+1 o forma propozitionala ıntr-o

gramatica cu precedenta simpla. Atunci fp = NiTiNi+1Ti+1 . . . TjNj+1 daca sinumai daca

T1

◦<=T2 . . .

◦<=Ti−1

◦<Ti

◦=Ti+1 . . .

◦=Tj

◦>Tj+1 (∗)

Schita de demonstratie. Presupunem ca p = N1T1N2T2 . . . TnNn+1 si ca frazasimpla stanga este fp = N3T3N4T4N5T5. Atunci din definitia frazei simple stangi,

rezulta T2

◦<T3

◦=T4

◦=T5

◦>T6. Mai trebuie sa aratam ca T1

◦<T2 sau T1

◦=T2. In acest

scop analizam structurile posibile de arbori (figura 4.18).

Efectuam reduceri succesive pana cand T2 ∈ fp. In acest moment avem T1

◦<T2

pentru cazul (a) si T1◦=T2 pentru cazul (b). Pentru implicatia inversa presupunem

ca fp = NkTkNk+1Tk+1 . . . TlNl+1, l 6= j, k 6= i si consideram toate cazurile depozitionare a indicilor k, l ın raport cu i, j. De exemplu, daca l < j atunci, ın

conformitate cu implicatia directa, rezulta Tl

◦>Tl+1 iar conform relatiei (∗) din

ipoteza, avem Tl

◦<Tl+1 sau Tl

◦=Tl+1 ceea ce contrazice ipoteza initiala conform

careia gramatica este cu precedenta simpla.Proprietatea 2. O gramatica operatoriala cu precedenta simpla este neam-

bigua.Schita de demonstratie. Fie p o forma propozitionala si Ax0,p arborele de

derivare corespunzator. Vom arata ca acest arbore este unicul arbore de derivarecare are radacina x0 si frontiera p. Procedam prin inductie asupra numarului denoduri interne ni. Daca ni = 1 atunci arborele de derivare va avea forma dinfigura 4.19 si unicitatea acestuia este evidenta. Presupunem acum ca proprietatea


N 1 T 1 T n N n

x 0

...

Figura 4.19: Arborele de derivare pentru ni = 1

este adevarata pentru un ni oarecare si consideram cazul ni + 1. Sa presupunemca ar exista doi arbori diferiti cu radacina x0 si frontiera p; fie acestia A′

x0,p siAx0,p.

Deoarece gramatica este cu precedenta simpla, rezulta ca fraza simpla stanga,care este aceiasi ın cei doi arbori, este situata ın aceiasi pozitie, p = rfps.Efectuam reducerea frazei simple fp (conform regulii aplicate x → fp) si vomobtine arborii A′

x0,q si Ax0,q unde q = rXs iar cei doi arbori trebuie sa fie diferiti.Dar numarul de noduri interne este cel mult ni, ceea ce contrazice ipoteza induc-tiva.

4.2.8 Determinarea relatiilor de precedenta pentru gra-matici operatoriale

Vom defini mai ıntai relatiile F1,2 si L1,2,analoage cu F si L de la gramaticile cuprecedenta simpla.

Definitie Fie x ∈ VN si y ∈ VG. Vom spune ca

xF1,2y daca ∃x → yu ∈ P , sau x → Nyu ∈ P , u ∈ V ∗G, N ∈ VN

xL1,2y daca ∃x → uy ∈ P , sau x → uyN ∈ P , u ∈ V ∗G, N ∈ VN

Inchiderile tranzitive, respectiv, tranzitive si reflexive ale acestor relatii levom nota cu F+

1,2, L+1,2 si respectiv, F ∗

1,2, L∗1,2. Acum, determinarea relatiilor deprecedenta operatoriale se poate face cu ajutorul urmatoarei teoreme.

Teorema (determinarea relatiilor de precedenta). Avem

(1) x◦<y ⇔ ∃u → . . . xv . . . ∈ P , vF+

1,2y;

(2) x◦=y ⇔ ∃u → . . . xNy . . . ∈ P ;

(3) x◦>y ⇔ ∃u → . . . vy . . . ∈ P , vL+

1,2x;

Schita de demonstratie. Demonstratia se poate face prin analiza structurilorposibile ale arborilor de derivare Pentru cazul (1), trebuie sa existe structura dearbore ca ın figura 4.20.


u

v

x N' i y T j N' j +1

N i N j +1

Figura 4.20: Structura posibila de arbore

Aceasta teorema ne permite sa determinam matricea de precedenta a gra-maticii pe baza careia putem apoi aplica algoritmul de analiza bottom-up. Prob-lema neterminalelor de la capetele frazei simple stangi se poate rezolva analizandpartile drepte ale regulilor de rescriere. Intr-adevar, teorema ne da numai ter-minalele care intra ın fraza simpla stanga si neterminalele interioare; cele douaeventuale neterminale de la capete vor apartine sau nu frazei simple stangi de-pinzand de forma partii drepte ale regulii respective. Evident, se pot face siipoteze de neambiguitate suplimentare pentru gramatica, similare cu conditia dea nu exista reguli cu partile drepte identice.

4.2.9 Studiu de caz

Sa consideram cazul gramaticii pentru generarea expresiilor aritmetice simpleGE, cu regulile obisnuite

E → E + T |TT → T ∗ F |FF → (E)|a

Relatiile F1,2, L1,2 si ınchiderile acestora sunt:

E F1,2 {E, T, +} E F+1,2 {E, T, F, +, ∗, (, a} E F ∗

1,2 {E, T, F, +, ∗, (, a}T F1,2 {T, F, ∗} T F+

1,2 {T, F, ∗, (, a} T F ∗1,2 {T, F, ∗, (, a}

F F1,2 {(, a} F F+1,2 {(, a} F F ∗

1,2 {F, (, a}

E L1,2 {T, +} E L+1,2 {T, +, F, ∗, a, )} E F ∗

1,2 {E, T, +, F, ∗, a, )}T L1,2 {F, ∗} T L+

1,2 {F, ∗, a, )} T F ∗1,2 {T, F, ∗, a, )}

F L1,2 {a, )} F L+1,2 {a, )} F F ∗

1,2 {F, a, )}


+ ∗ ( ) a

+◦>

◦<

◦<

◦>

◦<

∗ ◦>

◦>

◦<

◦>

◦<

(◦<

◦<

◦<

◦=

◦<

)◦>

◦>

◦>

a◦>

◦>

◦>

Figura 4.21: Matricea de precedenta operatoriala pentru GE

Regula Forma propozitionala

a◦> +

◦<(a + a) ∗ a ∗ a

F → a F +◦<(

◦<a

◦> + a) ∗ a ∗ a

F → a F +◦<(

◦<F +

◦<a

◦>) ∗ a ∗ a

F → a F +◦<(

◦<F + F

◦>) ∗ a ∗ a

T → T ∗ F , T → F F +◦<(T

◦=)

◦> ∗ a ∗ a

F → (E) , E → T F +◦<F ∗ ◦

<a◦> ∗ a

F → a F +◦<F ∗ F

◦> ∗ a

T → T ∗ F , T → F F +◦<T

◦< ∗ ◦

<a

F → a F +◦<T ∗ F

T → T ∗ F F + TE → E ∗ T , E → T , T → F E

Figura 4.22: Reconstructia derivarii cuvantului p = a + (a + a) ∗ a ∗ a

Conform teoremei de calcul a relatiilor de precedenta vom obtine matricea deprecedenta (vezi figura 4.21) asociata simbolurilor gramaticii GE.

Deci gramatica GE are proprietatea de precedenta operatoriala simpla, astfelca se poate aplica direct algoritmul de analiza sintactica bottom up.

Reconstituirea derivarii cuvantului p = a + (a + a) ∗ a ∗ a este prezentataın tabelul 4.22, unde fiecare linie corespunde formei propozitionale, ın care frazasimpla stanga este subliniata, precedata de regula identificata.

Capitolul 5

Sinteza Programelor

5.1 Forme interne ale programelor

5.1.1 Tabelele compilatorului

Compilatoarele prelucreaza un numar important de informatii, variabile de di-verse tipuri, date organizate ın anumite structuri standard sau definite de utiliza-tor, etc. De cele mai multe ori aceste informatii sunt stocate ın tabele si memoratepe suporturile de informatii ale sistemului. Organizarea si prelucrarea tabelelorconstituie o problema distincta, cu infuenta importanta asupra performantelorunui compilator, mai ales daca acestea sunt memorate pe un suport extern. Incele ce urmeaza vom prezenta pe scurt principalele tabele utilizate ın mod obisnuitın cadrul unui compilator si modul de organizare a informatiilor stocate ın acestetabele. Mentionam ca structura acestor tabele este definita de proiectantul decompilator si ca prin urmare exista un anumit grad de subiectivitate ın modul deorganizare al acestora.

• Tabelul de variabile. Contine variabilele utilizate ıntr-un program si infor-matii asupra lor. Mentionam ca variabilele contin datele prelucrate deprogram, ın conformitate cu tipul acestora, continut care se modifica ınmod dinamic pe parcursul evolutiei programului. Informatiile din fiecarelinie a tabelului pot fi:

– numele variabilei; asa cum s-a precizat la analiza lexicala, numele uneivariabile este de obicei un sir de caractere, litere sau cifre, primulcaracter trebuind sa fi o litera.

– tipul variabilei; relativ la tipurile de variabile utilizate ın programaretrebuie sa facem mentiunea ca acestea depind ın mod esential de dome-niul de aplicabilitate al limbajului. De exemplu, pentru un limbaj detip matematic (Pascal), tipul unei variabile este caracterizat ın generalde trei atribute: structura (scalar, tablou), calitatea (intreg, flotant,

107

108 CAPITOLUL 5. SINTEZA PROGRAMELOR

logic), dimensiunea ( simpla precizie, dubla precizie, etc). In prin-cipiu, fiecare variabila poseda toate aceste trei caracteristici, putandexista si anumite restrictii, de exemplu, variabilele ıntregi pot aveadimensiunea numai simpla precizie sau dubla precizie.

– adresa; adresa de ınceput a zonei de memorie rezervata variabilei;

– Alte informatii: sunt informatii de tip semantic, utilizate la depanareaprogramului; de exemplu, daca variabila a fost sau nu initializata(adica daca ınainte de prima utilizare i s-a atribuit valoare), daca afost utilizata sau nu, etc.

Pentru uniformitatea prelucrarii tabelului se poate prevedea o anumitalungime fixa pentru elementele tabelului, chiar daca spatiul nu este folositın ıntregime. De exemplu, ın cazul variabilelor de tip tablou, se pot uti-liza doua sau mai multe linii pentru a stoca valorile maxime ale indicilor(aceste dimensiuni vor fi utilizate atat la rezervarea zonei de memorie catsi la calculul deplasamentului unui element.

Observatie asupra functiilor. Denumirile functiilor sunt deseori utilizate cavariabile care contin valoarea pe care functia respectiva o returneaza. Estenatural ca ın acest caz numele functiei sa fie considerat variabila si sa fiestocat ın acest tabel ımpreuna cu atributele respective; de exemplu, unuldin aceste atribute trebuie sa fie contorul de amplasare, (CA), adica adresaprimei instructii executabile a rutinei corespunzatoare functiei.

• Tabelul de etichete. Contine etichetele utilizate ıntr-un program si adreseleprimelor instructii ale secventelor de program corespunzatoare. In esenta,etichetele nu difera de variabilele obisnuite, dar exista anumite particu-laritati; de exemplu, numele unei etichete trebuie sa fie constituit dintr-unidentificator urmat de un delimitator special (doua puncte, etc.) sau numaidin caractere numerice (cazul limbajului BASIC) iar valoarea unei eticheteeste ıntodeauna o valoare de adresa. De asemenea, ın cazul etichetelor tre-buie facuta analiza compatibilitatii dintre etichetele definite si etichetelereferite.

• Tabelul de variabile temporare. Contine variabile ale compilatorului nece-sare pastrarii unor rezultate intermediare. Avand ın vedere ca rezultateleintermediare, la fel ca si variabilele definite de utilizator, pot avea tipuridiferite, se pot constitui zone separate ın care se vor memora rezultate deun anumit tip bine precizat. In acest caz, variabilele temporare pot avea ostructura liniara iar adresa unei astfel de variabile se determina cu o formulade tipul

adr = adr0 + c× i

5.1. FORME INTERNE ALE PROGRAMELOR 109

unde adr0 este adresa de ınceput a zonei, c este lungimea elementelor iar inumarul de ordine al variabilei temporare. Se poate adopta un sistem dealocare dinamica a variabilelor temporare ın scopul economisirii memoriei.

• Tabelul de constante. Contine constantele de diverse tipuri utilizate ıntr-unprogram. In general este un tabel de mai mici dimensiuni, de aceea nucomporta probleme deosebite de organizare si prelucrare.

5.1.2 Cvadruple si triplete

Cvadruplele si tripletele sunt forme intermediare ale programelor ın care fiecareoperatie elementara ımpreuna cu operanzii ei se stocheaza ıntr-o secventa depatru sau trei elemente.

Cvadruple

Ne vom referi ın continuare numai la operatii binare, pentru celelalte operatiiputandu-se proiecta structuri similare. Consideram deci o secventa de text deforma A op B, unde A si B sunt operanzi (variabile, constante, variabile tem-porare, etc.) iar op este un operator binar. Cvadrupul corespunzator acesteisecvente va fi

op, A, B, ti

unde op, A, B sunt codurile unitatilor lexicale respective iar ti este o variabilatemporara. Semnificatia acestui cvadruplu este urmatoarea: se executa operatiadefinita de operatorul op ıntre operanzii A si B, ın aceasta ordine, iar rezultatuleste memorat la ti. In continuare vom folosi aceiasi notatie pentru un operandsi pentru codul operandului, posibilitatea de confuzie fiind redusa, deci nu vommai utiliza notatii de forma A, etc.

Exemplu. Cvadruplele corespunzatoare expresiei aritmetice a− b + (c + d)/esunt

(1) −, a, b, t1(2) +, c, d, t2(3) /, t2, e, t3(4) +, t1, t3, t4

In cazul altor operatii, chiar de n-aritate diferita de doi, se stabilesc structurilespecifice ale cvadruplelor; pentru operatii cu mai mult de doi operanzi, se potutiliza doua sau chiar mai multe cvadruple. Un exemplu de cvadruple pentrustructurile uzuale ale limbajelor de programare este prezentat ın tabelul 5.1.

Observatie asupra instructiei if. Presupunem ca structura instructiei esteif (expresie logica) then instructiune bloc;


Text Sursa Cvadruplea+b +,a,b,t, idem -,*,/a=b =,a,b,goto i BR, i, ,if (a==b) then BE, a,b, n

Figura 5.1: Exemplu de codificare prin cvadruple

Instructie Bloc

Expresie logica rezultatul in t

Expresie

r ,a,b, n

Instructie Bloc

t fals

adevarat

if,_,_,_

Schema logica (b) Cvadruple (a)

Figura 5.2: Instructiunea If logic


Semantica acestei instructii este prezentata ın figura 5.2. Mentionam ca ex-presie logica va avea forma particulara E1rE2, unde r este un operator relational.

In figura (a) prezinta schema logica a instructiei iar (b) cvadruplele core-spunzatoare. Partea de cod corespunzatoare expresiei logice va stoca valoarea(logica ) a expresiei ıntr-o variabila temporara t; aceasta valoare va fi utilizata ıninstructia de salt, ın conformitate cu tipul de salt prevazut ın programul sursa (<,=, etc.). In consecinta, cvadrupul de salt r va trebui sa prevada aceasta variabilatemporara, plus numarul de ordine n al primului cvadruplu care urmeaza dupacvadruplele corespunzatoare instructiei sau blocului. De exemplu, acest cvadru-plu poate avea urmatoarea forma r, a, b, n unde n este numarul cvadruplului lacare trebuie sa se faca saltul.

Triplete

Este o alta posibilitate de format intermediar, asemanator cu cvadruplele, sin-gura deosebire fiind accea ca nu se prevede explicit o variabila temporara pentrustocarea rezultatului. Prin urmare, tripletul corespunzator unei operatii binarede forma A op B va fi op, A, B. In cazul ın care ca operand al unui triplettrebuie specificat rezultatul unui triplet anterior, se va scrie numarul de ordineal tripletului respectiv.

Exemplu. Pentru secventa de program xx = a− b + (c + d)/e sirul de tripletegenerat va fi

(1) −, a, b(2) +, c, d(3) /, (2), e(4) +, (1), (3)(5) =, xx, (4)

Notatia poloneza

Notatia poloneza a fost introdusa initial pentru a se putea evalua expresii aritmet-ice printr-o singura parcurgere secventiala. Din punctul de vedere al proiectariicompilatoarelor, aceasta notatie poate fi utilizata ca un format intermediar alprogramelor, ın mod special pentru limbajele de programare algoritmice, For-tran, Pascal. In continuare vom ilustra ideea de evaluare secventiala a expresiiloraritmetice printr-un exemplu.

Consideram expresia aritmetica a∗b+(c−d∗e)∗f . Ideea sirului polonez constaın scrierea operanzilor si a operatorilor acestei expresii (fara a utiliza paranteze)ıntr-un sir cu urmatoarea proprietate: se parcurge sirul secvential de la stanga ladreapta si fiecare operator ıntalnit provoaca efectuarea operatiei respective ıntrecei doi operanzi din fata, ın ordinea aparitiei lor. Pentru exemplul considerat, un


sir care satisface aceasta conditie este

ab ∗ cde ∗ −f ∗+

Vom numi acest sir notatia poloneza corespunzatoare expresiei, sau notatiapoloneza inversa. Evaluarea se poate face utilizand o stiva cu urmatoarea pre-lucrare: se parcurge secvential sirul, operanzii se introduc ın stiva fara nici uncontrol, iar fiecare operator citit provoaca efectuarea operatiei ıntre operanziiaflati ın penultimul si ultimul element al stivei, ın aceasta ordine si memorarearezultatului ın penultimul element. Starea dinamica a stivei pentru exemplulconsiderat este urmatoarea:

(1) a a*b a*b a*b a*b a*b+(c-d*e)*f(2) b c c c-d*e (c-d*e)*f(3) d d*e f(4) e

Continutul stivei a fost rescris atunci cand un operator provoaca efectuareaunei operatii. Se poate observa ca sirul considerat de noi (notatia poloneza aexpresiei) satisface conditia de evaluare secventiala. De fapt, aceasta conditieeste esentiala si ea poate fi luata chiar ca o definitie a sirului polonez.

Fie V un alfabet si B o multime de operatori binari.Definitia 1. Vom numi sir polonez orice cuvant peste alfabetul V ∪B obtinut

recursiv cu ajutorul regulilor:(1) daca a ∈ V atunci a este sir polonez;(2) daca p si q sunt siruri poloneze si b ∈ B, atunci pqb este sir polonez.Sa observam ca utilizand aceste doua reguli, putem sa obtinem succesiv toate

sirurile poloneze avand operanzii V si operatorii binari B. De exemplu, daca V ={a, b, c} si B = {+, ∗}, atunci sirurile poloneze vor fi a, b, c, ab+, ac+, bc+, ab∗,. . . , aab + +, aac + +, . . ..

In cele ce urmeaza vom da o alta definitie, tot constructiva, folosind gramati-cile generative Chomsky. Este necesar sa precizam expresiile aritmetice pentrucare introducem aceste siruri.

Definitia 2. Fie gramatica Gexp = ({E, T, F}, {a, +, ∗}, E,P) unde regulilede rescriere sunt

E → E + T |TT → T ∗ F |FF → a

Observatie. Terminalul a desemneaza operanzii, deci a este de fapt o notatiesimbolica pentru variabile de forma a, b, c, etc. Este usor de vazut ca aceasta gra-matica genereaza expresii aritmetice fara paranteze, ın care singurele operatiisunt + si ∗. Utilizarea a trei neterminale E, T, F se face numai pentru a precizaponderea operatiilor, cresterea facandu-se odata cu adancimea, deci p(+) < p(∗).


Acelasi limbaj al expresiilor aritmetice fara paranteze poate fi generat cu o gra-matica cu un singur neterminal, fie acesta A, si avand regulile

A → A + A|A ∗ A|a

Dar ın acest caz trebuie introduse alte conventii pentru a preciza ordinea operatiilor;de exemplu, pentru expresia a+b∗c, ın acest ultim caz, nimic nu arata ca operatia∗ trebuie facuta ınainte de +. Trebuie sa precizam ca prin considerarea a numaidoi operanzi nu se impune o constrangere asupra notiunii de expresie aritmetica,foarte usor putem generaliza aceasta gramatica la un numar oarecare de operatoribinari, de exemplu

A1 → A1op1A2|A2

A2 → A2op2A3|A3

etc.

De asemenea, putem considera operatori de n-aritate oarecare precum si regulide rescriere ın concordanta cu sintaxa pe care dorim sa o satisfaca acestia. Uti-lizarea unor paranteze pentru a indica o anumita ordine de efectuare a operatiilor,iarasi nu difera esential de cazul expresiilor fara paranteze. Putem folosi algorit-mul de modificare dinamica a ponderilor descris la gramatici operatoriale: par-curgem expresia de la stanga la dreapta si atasam fiecarui operator ponderea sa;ın momentul ın care ıntalnim o paranteza deschisa, marim toate ponderile cu oconstanta mai mare decat cea mai mare pondere iar la ıntalnirea unei parantezeınchise, scadem aceasta constanta. Apoi eliminam toate parantezele. Este evi-dent ca ın acest fel operatiile din interiorul parantezelor vor avea prioritatae maimare, mergandu-se spre parantezele din interior.

Definitia 3. Fie Gp = (VN , VT , x0,P), unde VN = {A}, VT = {a, +, ∗},x0 = A iar regulile sunt

A → AA + |AA ∗ |aOrice cuvant p ∈ L(Gp) va fi numit sir polonez. Este natural ca aceste

siruri poloneze sa fie puse ın legatura cu expresiile aritmetice fara parantezeprezentate mai sus. Gramatica Gp nu stabileste o ordine intrinseca de efectuarea operatiilor, ıntocmai ca si gramatica cu un singur neterminal de generare aexpresiilor. Convenim ınsa ca aceasta ordine sa fie cea secventiala.

Daca p ∈ L(Gp) atunci convenim sa notam cu aes(p) cuvantul obtinut din pcu ajutorul algoritmului de evaluare secventiala.

Urmatoarea teorema stabileste legatura ıntre cele doua entitati.Teorema. Pentru orice cuvant e ∈ L(Gexp) exista un pe ∈ L(Gp) astfel ıncat

aes(pe) = e.Demonstratie. Procedam prin inductie asupra numarului n de operatori din

e. Daca n = 1 atunci e = a+b sau e = a∗b si sirul polonez care satisface conditiadin teorema va fi pe = ab+ sau pe = ab∗. Sa presupunem ca proprietatea este


E

E + T

e 1 e 2 e 1

E

T

T * F

a

(a) (b)

Figura 5.3: Structurile posibile ale arborelui de derivare

adevarata pentru o expresie care contine un numar de operatori mai mic sau egalcu n si consideram o expresie e cu n operatori. Arborele de derivare al acesteiava avea una din formele prezentate ın figura 5.3.

In cazul (b) putem considera e2 = a. In ambele cazuri expresiile e1 si e2 auun numar de operanzi inferior lui n si ın conformitate cu ipoteza inductiva avemaes(pe1) = e1 si aes(pe2) = e2. Luam pe = pe1pe2+ pentru cazul (a) si pe = pe1pe2∗pentru cazul (b). Este evident ca aes(pe) = e.

5.2 Generarea formatului intermediar

In aceasta sectiune vom analiza problema generarii formatului intermediar pentrulimbaje algoritmice de tip Fortran, Pascal, Basic. Formele intermediare avute ınvedere sunt cvadruplele si notatia poloneza, ıntr-un singur caz ne vom referi sila triplete, avand ın vedere ca principial generarea acestora nu difera esential decea a cvadruplelor.

Schema generala a algoritmilor este urmatoarea.Fie G gramatica (de tipul 2) care genereaza limbajul de programare. Prima

faza consta ın stabilirea unor elemente semantice ın concordanta cu structuralimbajului; astfel, fiecarui simbol x ∈ VG i se atribuie un anumit sens seman-tic, notat S(x), sens care contine o anumita informatie depinzand de simbolulrespectiv, de contextul ın care acesta apare, etc. De asemenea, fiecarei regulide generare i se ataseaza o anumita rutina semantica. Operatiile obisnuitecare se efectueaza ın aceste rutine sunt: analize specifice, atribuirea unui senssemantic simbolului din stanga, generarea unui cvadruplu sau a unei secventede sir polonez, etc. Faza a doua este faza de generare propriuzisa si ea com-porta ın principiu urmatoarele operatii: Se efectueaza analiza sintactica a tex-

5.2. GENERAREA FORMATULUI INTERMEDIAR 115

tului sursa cu un algoritm de analiza pe care proiectantul de compilator a decissa ıl utilizeze. Indiferent de algoritmul ales, analiza poate fi conceputa ın douaetape, mai ıntai constructia arborelui de derivare si apoi reducerea lui succesivaprin eliminarea unor subarbori. In mod natural acesti subarbori sunt cei core-spunzatori frazelor simple stangi asa ıncat actiunile care se realizeaza cu acestprilej sunt cele corespunzatoare rutinelor semantice din prima faza. Mentionamca frontierele subarborilor care se reduc vor constitui, prin definitie, unitatile sin-tactice ale limbajului. In momentul ın care se ajunge la simbolul de start (s-aefectuat ıntreaga reducere) ıntr-un fisier de iesire se obtine programul ın formatintermediar, cvadruple, sir polonez, etc. Se poate observa ca analiza sintacticajoaca ın acest proces un rol central. In cele ce urmeaza vom presupune ca analizasintactica se efectueaza cu un algoritm de tip bottom-up si deci subarborele carese reduce are drept frontiera fraza simpla stanga.

5.2.1 Generarea cvadruplelor

Gramatica care genereaza expresiile aritmetice GE este cunoscuta; pentru a nesitua ıntr-un context cat mai apropiat de cazul real, vom completa aceasta gra-matica cu operatiile - si / (diferenta si ımpartire). Prin urmare regulile acesteigramatici vor fi

E → E + T |E − T |TT → T ∗ F |T/F |FF → (E)|a

Sensul semantic este prestabilit numai pentru simbolul terminal a, si anume,S(a) este adresa zonei de memorie atasata identificatorului desemnat de a. Pentrucelelalte simboluri neterminale, E, T, F sensul semantic se atribuie pe parcursulefectuarii analizei. Rutinele semantice corespunzatoare regulilor sunt prezentateın tabelul 5.4. Mentionam ca actiunile prevazute ın aceste rutine sunt stabiliteın conformitate cu ıntelesul pe care proiectantul doreste sa ıl atribuie diverselorstructuri si nu au o ratiune intrinseca. Ca o regula generala ınsa, putem safacem precizarea ca ın cazul cvadruplelor, variabila temporara ın care se retinerezultatul intermediar, va fi transmisa ca sens semantic simbolului din stanga.

Exemplu. Consideram urmatoarea expresie aritmetica (a+ b) ∗ c− d ∗ (e− f).Arborele de derivare corespunzator este prezentat ın figura 5.5.

In dreapta fiecarui nod al arborelui (nodurile sunt etichetate cu simboluri alegramaticii), se afla ınscris sensul semantic corespunzator variabilei si contextuluiın care aceasta se afla. Procesul de generare al cvadruplelor se desfasoara astfel:la ınceputul procesului, dupa cum se poate vedea pe arborele de generare, frazasimpla stanga este a. Se efectueaza reducerea F → a si se aplica rutina semanticacorespunzatoare acestei reguli (ın tabelul rutinelor pozitia (8) ); singura operatiecare se face este transmiterea sensului semantic lui F . In continuare, acest sens


Regula Cvadruplu Sens(1) E1 → E2 + T +, S(E2), S(T ), ti S(E1) = ti(2) E1 → E2 − T −, S(E2), S(T ), ti S(E1) = ti(3) E → T S(E) = S(T )(4) T1 → T2 ∗ F ∗, S(T2), S(F ), ti S(T1) = ti(5) T1 → T2/F /, S(T2), S(F ), ti S(T1) = ti(6) T → F S(T ) = S(F )(7) F → (E) S(F ) = S(E)(8) F → a S(F ) = Adr(a)

Figura 5.4: Rutine semantice asociate regulilor

E

E , t 2 T , t 4

T , t 2

T , t 1 F , c

F , t 1 c

E , t 1 ( )

( ) E , t 3

* T ,d

F ,d

d

T ,b E ,a +

T ,a

F ,a

a

F ,b

b

e

F , e

T , e

E , e T , f

F , f

f

F , t 3

*

_

_

Figura 5.5: Arborele de derivare


Regula Cvadruplu Sens(1) E1 → E2 + T +, S(E2), S(T ) S(E1) = (n)(2) E1 → E2 − T −, S(E2), S(T ) S(E1) = (n)(3) E → T S(E) = S(T )(4) T1 → T2 ∗ F ∗, S(T2), S(F ) S(T1) = (n)(5) T1 → T2/F /, S(T2), S(F ) S(T1) = (n)(6) T → F S(T ) = S(F )(7) F → (E) S(F ) = S(E)(8) F → a S(F ) = Adr(a)

Figura 5.6: Rutine semantice pentru generarea tripletelor

se transmite pana la E, apoi fraza simpla stanga este b si se transmite sensulsemantic pana la T . In acest moment fraza stanga este E + T iar cele douasimboluri au sensurile S(E) = a, S(T ) = b; se efectueaza reducerea E → E + Tsi se genereaza cvadruplul +, a, b, t1 iar sensul semantic care se transmite lui Eeste t1. Procesul continua ın acelasi mod si se obtine ın final sirul de cvadruple:

+, a, b, t1∗, t1, c, t2−, e, f, t3∗, d, t3, t4−, t2, t4, t5

5.2.2 Generarea tripletelor

Modificarea ceva mai importanta intervine la rutinele semantice precum si lafaptul ca dupa generarea unui triplet, sensul semantic care se transmite va finumarul de ordine al tripletului generat. Aceste rutine sunt prezentate ın tabelul5.6.

Generarea tripletelor se desfasoara la fel cu cea a cvadruplelor. Pentru expre-sia considerata la generarea cvadruplelor se obtine urmatorul sir de triplete

(1) +, a, b(2) *, (1), c(3) -, e, f(4) *, d, (3)(5) -, (2), (4)


Regula Notatia poloneza(1) E → E + T pi = +(2) E → E − T pi =(3) E → T(4) T → T ∗ F pi = ∗(5) T → T/F pi = /(6) T → F(7) F → (E)(8) F → a pi = Adr(a)

Figura 5.7: Metoda rutinelor semantice

5.2.3 Generarea sirului polonez

Tehnica rutinelor semantice

Dupa cum s-a precizat, notatia poloneza constituie o interesanta si utila formaintermediara a programelor. In paragraful precedent aceasta notatie s-a introdusnumai pentru expresii aritmetice fara paranteze, dar aceasta constructie se poateface pentru majoritatea structurilor sintactice ale limbajelor de programare. De-sigur ca cea mai naturala tehnica de generare a notatiei poloneze pentru o expresieeste procedura generala prezentata la ınceputul capitolului, bazata pe rutinele se-mantice atasate regulilor de generare. Spre deosebire de procedura de generare acvadruplelor si a tripletelor, pentru sirurile poloneze nu mai avem nevoie de sensulsemantic al neterminalelor; acestea sunt utilizate ın momentul aparitiei lor si decinu mai este necesara stocarea unor informatii suplimentare. In continuare suntprezentate rutinele semantice pentru generarea notatiei poloneze corespunzatoareexpresiilor aritmetice cu paranteze (vezi figura 5.7), generate de gramatica GE.Notatia pi o utilizam pentru a desemna elementul i din sirul polonez; indicele ise actualizeaza dupa fiecare prelucrare a sirului.

Exemplu. Vom aplica rutinele semantice de mai sus pentru generarea siruluipolonez corespunzator expresiei aritmetice a∗b+(c−d∗e)∗f . Analiza sintacticase efectueaza cu un algoritm de tip bottom-up, asa ıncat trasarea explicita aarborelui de derivare nu mai este necesara. Prelucrarea efectiva se poate organizaıntr-un tabel ca ın figura 5.8; mentionam ca fraza simpla stanga este indicata prinsublinierea secventei corespunzatoare de text.

Tehnica parantezelor

Ideea de baza consta ın aceea ca se plaseaza ıntre doua paranteze fiecare operatorımpreuna cu cei doi operanzi ai sai; apoi generarea notatiei poloneze se poate facesimplu, folosind o stiva de operatori.


Textul sursa Regula aplicata Notatia polonezaa * b + (c - d * e) * f F → a aF * b + (c - d * e) * f F → b abF * F + (c - d * e) * f T → T ∗ F, T → F ab*T + (c - d * e) * f F → c ab*cT + (F - d * e) * f F → d ab*cdT + (F - F * e) * f F → e ab*cdeT + (F - F * F) * f T → T ∗ F, T → F ab*cde*T + (F - T) * f E → E − T, E → T, T → F ab*cde*-T + (E) * f F → (E) ab*cde*-

T + F * f F → f ab*cde*-fT + F * F T → T ∗ F, T → F ab*cde*-f*T + T E → E + T, E → T ab*cde*-f*+E ab*cde*-f*+

Figura 5.8: Generarea sirului polonez: tehnica analizei sintactice

Plasarea parantezelor. Se atribuie fiecarui operator cate o pondere ın con-formitate cu conventia de prioritati sau cu gramatica care genereaza expresiileconsiderate. In cazul unei expresii aritmetice fara paranteze se poate proceda ınurmatorii pasi:

• (1) Se ataseaza fiecarui operator ponderea sa.

• (2) Se parcurge expresia de la stanga la dreapta pana cand ıntre doi op-eratori se gaseste relatia ≥; de exemplu . . . a ∗ b + c . . . si, cu conventiauzuala, ∗ ≥ +. Se plaseaza ıntre paranteze operatorul ∗ ımpreuna cu ceidoi operanzi ai sai, adica . . . (a ∗ b) + c . . ..

• (3) Se sterge ponderea operatorului curent (cel care a fost inclus ıntre paran-teze) si se reia procesul de la punctul (2) ıncepand cu operatorul urmator(ın exemplul nostru de la +).

De exemplu, expresia a/b ∗ c + d− e va avea forma ((((a/b)*c)+d)-e).In cazul unor expresii aritmetice cu paranteze se foloseste un algoritm asemanator

ın care se modifica pasul (1) si anume: se parcurge expresia de la stanga la dreaptaatasand fiecarui operator ponderea sa. La ıntalnirea unei paranteze deschise semodifica provizoriu ponderile prin adaugarea unei constante ıntregi (aceasta con-stanta trebuie sa fie mare decat cea mai mica pondere) si se atribuie ın con-tinuare noile ponderi. La ıntalnirea unei paranteze ınchise, aceasta constantaeste scazuta, astfel ıncat operatorii din interiorul parantezelor vor avea ponderisuperioare. Apoi toate parantezele se sterg. De exemplu, ın expresia

(a + b) ∗ (c/(d− e)− f),


dupa efectuarea acestei operatii, presupunand ca initial ponderile operatorilor+,−, ∗, / sunt, respectiv, 1, 2, 3, 4 si constanta de majorare are valoarea 10, op-eratorilor li se vor atribui ponderile:

a + b * c / d - e - f11 3 14 22 12

Generarea sirului polonez. Pornind de la expresiile aritmetice ın care au fostplasate parantezele ın conformitate cu prima parte, sirul polonez poate fi construitcu ajutorul algoritmului:

• Se parcurge expresia de la stanga la dreapta, parantezele deschise suntignorate si se executa operatiile

– operanzii se scriu succesiv ın sirul polonez;

– operatorii se scriu ıntr-o stiva.

• La citirea unei paranteze ınchise, operatorul din varful stivei se scrie ın sirulpolonez.

Tehnica stivei de operatori

Este probabil cea mai raspandita metoda de generare a sirului polonez pentruexpresii aritmetice. Se utilizeaza doua liste liniare si o stiva. Prima lista contineexpresia aritmetica data iar ın cealalta se obtine succesiv sirul polonez core-spunzator. Operatorii sunt plasati ın stiva tinandu-se cont de ponderile lor,apoi sunt extrasi si scrisi ın sir conform cu un algoritm care ın esenta repro-duce actiunea rutinelor semantice. Mecanismul care realizeaza acest proces esteprezentat ın figura 5.9.

Algoritmul este urmatorul:

(1) Operanzii se scriu direct ın sirul polonez.

(2) Operatorii si parantezele deschise se scriu ın stiva respectandu-se urmatoarelereguli

• Parantezele deschise au pondere 0 si se scriu fara conditii;

• Pentru ceilalti operatori, se compara ponderea operatorului de introduscu ponderea operatorului din varful stivei; daca aceasta este mai mare,introducerea are loc; daca este mai mica sau egala, se extrage varful stivei(acesta trece ın sirul polonez), se reia comparatia cu operatorul din varfulstivei pana la prima paranteza deschisa sau pana la baza stivei, si apoi seintroduce noul operator;

5.3. GENERAREA FORMATULUI INTERMEDIAR PENTRU INSTRUCTII CLASICE121

Stiva

Varful stivei

Intrare ( Expresie aritmetica )

Iesire (Sir polonez )

Figura 5.9: Structura dispozitivului

(3) Citirea unei paranteze ınchise provoaca extragerea operatorilor din stivapana la prima paranteza deschisa; aceasta este extrasa si ea din stiva (dar paran-teza extrasa nu trece ın sirul polonez) iar ın continuare cele doua paranteze suntignorate.

(4) In finalul procesului, deci dupa ce ultimul operand a fost trecut ın sirulpolonez, se extrag toti operatorii din stiva si se scriu ın sirul polonez.

Exemplu. Pentru expresia a * b + (c - d * e) * f, stare dinamica a stivei deoperatori este prezentata ın figura 5.10.

5.3 Generarea formatului intermediar pentru instructii

clasice

5.3.1 Instructiunea de atribuire

to fill

5.3.2 Instructiunea If

to fill

5.3.3 Variabile indexate

to fill


a*b+( c -d* e )* f ab * cde *- f *+

2 *

4

2

1

1

*

(

+

*

3 -

Figura 5.10: Starea dinamica a stivei

Capitolul 6

Masina Turing

6.1 Limbaje de tipul zero

Limbajele de tipul 0 sunt generate de gramatici Chomsky fara restrictii asupraregulilor de derivare. Se poate arata ca orice gramatica de tipul zero acceptaurmatoarea forma normala

S → SA,B → C|i|λ,DE → FH,

unde A,C, F,H 6= S. Se observa ca singura deosebire fata de gramaticile depen-dente de context este aceea ca putem avea si λ–reguli.

Demonstratia existentei formei normale se face prin transformari succesive aleregulilor. In prealabil gramatica se completeaza cu neterminale noi astfel ıncatorice regula u → v care nu este de stergere sa respecte conditia de monotonie,adica |u| ≤ |v|. Acest lucru se poate realiza dupa cum urmeaza. Fie

X1 . . . Xn → Y1 . . . Ym, n > m,

o regula care nu respecta conditia de monotonie. Vom pune

X1 . . . Xn → Y1 . . . YmZm+1 . . . Zn, Zm+1 → λ, . . . , Zn → λ.

Este clar ca orice derivare directa u⇒v ın gramatica initiala se poate obtinesi ın gramatica modificata si reciproc (neterminalele Z nu pot aparea ın stangaaltor relatii). In acest fel, gramatica se va transforma astfel ıncat sa contina douacategorii de reguli: reguli care respecta conditia de monotonie si λ–reguli.

In continuare reducem lungimea partii drepte a regulilor folosind urmatoareatransformare. Fie u → v ∈ P, |v| > 2; atunci v = Y1Y2Y3v

′.

1. daca u = X1 atunci regula se ınlocuieste cu

X1 → Z1Z2,Z1 → Y1,Z2 → Y2Y3v

′.

123

124 CAPITOLUL 6. MASINA TURING

2. daca u = X1X2u′ atunci regula se ınlocuieste cu

X1X2 → Z1Z2,Z1 → Y1,Z2u

′ → Y2Y3v′.

In ambele cazuri Z1, Z2 sunt neterminale noi.Este clar ca noile lungimea partii drepte a regulilor se reduce cu o unitate

pentru cazul ın care exista minim 3 simboluriın dreapta. repetand procedura sepoate obtine o gramatica echivalenta ın care regulile au una din formele:

1. B → C|i|λ,

2. DE → FH,

3. X → Y Z.

Regulile (1) si (2) satisfac conditiile de la forma normala, iar cele de forma (3)presupunem ca nu satisfac aceste conditii, deci ca X 6= S sau Y 6= S. In general,putem avea mai multe astfel de reguli; pentru simplificare presupunem ca existadoua reguli de forma (3):

(3′); X1 → Y1Z1, X2 → Y2Z2.

Construim o gramatica echivalenta G′ = (VN ∪ {S ′, X1, X2}, VT , S ′, P ′), unde P ′

contine toate regulile care convin (de formele (1) si (2)) precum si

S ′ → S,S ′ → S ′X1|S ′X2,X1X1 → Y1Z1, X2X2 → Y2Z2.

De asemenea vom include ın P ′ urmatoarel reguli de comutare (relativ la sim-bolurile nou introduse X1, X2):

AX1 → X1A,AX2 → X2A,

,∀A ∈ VN .

Se vede ca G′ este o gramatica ın forma normala. Este trivial sa aratam caL(G) = L(G′).

Fie p ∈ L(G), deci S∗⇒G

p. Presupunem ca ın aceasta derivare exista o

singura secventa u∗⇒v ın care se aplica reguli de forma (3′), adica

G : S∗⇒u

∗⇒v∗⇒p.

6.1. LIMBAJE DE TIPUL ZERO 125

Presupunem ca secventa u∗⇒v are forma

u = u1X1u2X2u3X2u4∗⇒u1Y1Z1u2Y2Z2u2Y2Z3u4 = v,

unde u1, u2, u3, u4 ∈ V ∗N . In G′ putem scrie

S ′⇒S ′X2⇒S ′X2X2⇒S ′X1X2X2⇒SX1X2X2∗⇒uX1X2X2 = u1X1u2X2u3X2u4X1X2X2

∗⇒u1X1X1u2X2X2u3X2X2u4∗⇒u1Y1Z1u2Y2Z2u3Y2Z2u4 = v

∗⇒p

Prin urmare, S ′ ∗⇒G′

p si p ∈ L(G′).

Invers, fie p ∈ L(G′), deci S ′ ∗⇒G′

p. Daca ın derivarea S ′ ∗⇒G′

p apar sim-

bolurile X1, X2 ele nu pot aparea dacat ın urma aplicarii regulilor S ′ → S ′X1

si S ′ → S ′X2, deci la ınceputul derivarii, apoi singura posibilitate de continuareeste S ′ → S; de asemenea, aceste simboluri nu pot fi eliminate decat cu regulileX1X1 → Y1Z1 si X2X2 → Y2Z2, etc. Astfel derivarea noastra trebuie sa aibaforma descrisa mai sus, de unde rezulta S

∗⇒G

p, p ∈ L(G).2

Relativ la puterea generativa a gramaticilor de tipul zero se poate arata caL1 ⊂ L0 (strict). Demonstratia se face pe o cale indirecta.

Mentionam si urmatoarea ”teorema a spatiului de lucru”. Fie G o gramaticade tipul zero. Pentru o derivare

D : S = u0⇒u1⇒ . . .⇒un = p ∈ V ∗T

definim

WSD(p) = max|ui|i = 1, . . . , n

si

WS(p) = min{WSD(p)}.D

Observatie. WS este prescurtare de la working space.

Spunem ca o gramatica de tipul zero G are spatiul de lucru marginit dacaexista k ∈ N astfel ıncat pentru ∀p ∈ L(G) sa avem WS(p) ≤ k|p|. Sa observamca orice gramatica care nu are reguli de stergere (exceptie S → λ si atunci S nuapare ın dreapta) satisface aceasta conditie cu k = 1.

Teorema 6.1 (teorema spatiului de lucru) daca o gramatica G are spatiul delucru marginit, atunci L(G) ∈ L1.


i 1 i 2 i 3 i 5

Dispozitiv de citire / scriere

Dispozitiv de comanda s Î S

Banda de intrare / iesire i 4

p= i 1 i 2 i 3 i 4 i 5 , n =4

Figura 6.1: Reprezentarea schematica a masinii Turing

6.2 Masina Turing

Conceptul de masina Turing. Masina Turing este un mecanism de recunoastere

a limbajelor de tipul zero. In felul acesta, familiilor de limbaje din clasificareaChomsky le corespund automate specifice de recunoastere.

Familia L3 - automate finite,Familia L2 - automate push–down,Familia L1 - automate liniar marginite,Familia L0 - masina Turing.

O masina Turing (prescurtat MT) se compune dintr–un dispozitiv de comandacare poseda un dispozitiv de scriere–citire si o banda de intrare. Banda de intrarese considera marginita la stanga si nemarginita la dreapta; ea contine simboluriale unui alfabet de intrare, ıncepand din prima pozitie. Alfabetul are un sim-bol special numit blanc si notat [ (sau spatiu), care se considera ınregistrat ıntoata partea neocupata a benzii. Indicele simbolului din dreptul dispozitivului descriere–citire ıl notam cu n si el va constitui un element al starii masinii Turing.Dispozitivul de comanda se afla ıntr-o anumita stare interna, element al uneimultimi finite de stari.

Schema unei masini Turing este data ın figura 6.1. O masina Turing functioneazaın pasi discreti. Un pas de functionare consta din:

Dispozitivul de comanda citeste simbolul aflat ın dreptul dispozitivului descriere–citire; ın functie de simbolul citit, masina Turing trece ıntr-o noua stareinterna, scrie pe banda un nou simbol (ıntotdeauna diferit de blanc) ın loculsimbolului citit si muta banda cu o pozitie (spre stanga sau dreapta) sau o lasa

6.2. MASINA TURING 127

pe loc. Conventional, vom nota cu +1 o miscare spre stanga, cu −1 spre dreaptasi cu 0 pe loc.

Din punct de vedere matematic, o masina Turing este un sistem

MT = (Σ, I, f, s0, Σf )

unde:Σ este multimea de stari;I este alfabetul de intrare;f : (Σ× I)′ −→ Σ× (I − {[})× {1, 0,−1}, (Σ× I)′ ⊆ Σ× I,

este functia de evolutie;s0 ∈ Σ este simbolul de start;Σf ⊆ Σ este multimea de stari finale.Observatie. Functia f nu este definita pe ıntregul produs Σ× I; daca masina

ajunge ıntr-o stare s iar ın dreptul dispozitivului de scriere–citire se afla simbolul isi (s, i) 6∈ (Σ×I)′ spunem ca masina se blocheaza. Exista si alte cazuri de blocare,de exemplu situatia ın care dispozitivul de scriere–citire se afla ın dreptul primuluisimbol, iar pasul de functionare prevede o miscare a benzii spre dreapta.

O stare (sau configuratie) a unei masini Turing este un triplet de forma σ =(s, p, n) unde s este starea interna, p este cuvantul scris pe banda iar n esteindicele simbolului din dreptul dispozitivului de scriere–citire.

Vom spune ca starea σ1 = (s1, p1, n1) evolueaza direct ın starea σ2 = (s2, p1, n2)si vom scrie σ1 7−→σ2 daca se efectueaza un pas de evolutie. In termenii functieide evolutie, avem

(1)f(s1, in1) = (s2, i, +1), p2 = i1 . . . in1−1iin1+1 . . . im, n2 = n1 + 1;(2)f(s1, in1) = (s2, i,−1), p2 = i1 . . . in1−1iin1+1 . . . im, n2 = n1 − 1;(3)f(s1, in1) = (s2, i, 0), p2 = i1 . . . in1−1iin1+1 . . . im, n2 = n1;(4)f(s1, [) = (s2, i, +1), p2 = p1i, n2 = n1 + 1;(5)f(s1, [) = (s2, i,−1), p2 = p1i, n2 = n1 − 1;(6)f(s1, [) = (s2, i, 0), p2 = p1i, n2 = n1;Vom spune ca σ′ evolueaza (fara specificatia direct) ın σ′′ si vom nota σ′ ∗7−→σ′′

daca σ′ = σ′′ sau daca exista σ1, . . . , σn astfel ıncat

σ′ = σ1 7−→σ2 7−→ . . . 7−→σn = σ′′.

Limbajul recunoscut de o masina Turing este prin definitie

L(MT ) = {p|p ∈ I∗, (s0, p, 1)∗7−→(s, q, ε), s ∈ Σf}.

Observatie. Este posibil ca masina sa ajunga ıntr-o stare finala ınainte decitirea integrala a lui p; analiza starii finale trebuie facuta numai dupa parcurgereacuvantului.

Exemplu. Consideram masina turing MT = (Σ, I, f, s0, Σf ) unde Σ = {s0, s1, s2},I = {0, 1}, Σf = {s1} iar functia de evolutie este data de


f s0 s1 s2

[ (s2, 1, 1) (s0, 0,−1)0 (s1, 0, 1)1 (s0, 1, 1) (s0, 0, 1)

Evolutia masinii pentru p = 001 este

(s0, 011, 1) 7−→(s1, 011, 2)7−→(s0, 001, 3)7−→(s0, 001, 4)7−→

(s2, 0011, 5)7−→(s0, 0011, 4) 7−→(s0, 00110, 5)7−→(s1, 00110, 6)

Se poate observa ca dupa citirea ıntregului cuvant masina poate sa efectuezeun numar de pasi suplimentari pana la ajungerea ıntr-o stare finala, deci esteposibil ca |p| < |q|.

Situatii ın care o masina Turing se blocheaza (ın aceste situatii cuvantul scrispe banda nu este recunoscut):

1. MT ajunge ıntr-o stare s, ın dreptul dispozitivului de citire–scriere se aflasimbolul i si (s, i) 6∈ (Σ× I)′;

2. MT este ın starea s, a citit simbolul din prima pozitie i si f(s, i) = (s′, i′,−1);

3. MT efectueaza un ciclu infinit ın interiorul cuvantului.

Definitie 6.1 Vom spune ca o masina Turing este nestationara daca

f : (Σ× I)′ → Σ× (I \ {[})× {−1, +1}.

Prin urmare, o masina Turing nestationara nu lasa ın nici o situatie banda peloc.

Lema 6.1 Orice masina Turing este echivalenta cu o masina Turing nestatio-nara.

Demonstratie. Pornind de la o MT data construim o MT ′ nestationara astfel:Daca f(s, i) = (s′, i′,±1) vom pune f ′(s, i) = f(s, i);Daca f(s, i) = (s′, i′, 0) vom pune f ′(s, i) = (s′′, i′,−1) si f ′(s′′, j) = (s′, j, +1),∀j ∈

I, unde s′′ este o stare nou introdusa.Astfel, ın cazul unei ramaneri pe loc a lui MT, noua masina va face un pas

spre stanga si unul spre dreapta, fara sa modifice nici starea si nici continutulbenzii. Evident, cele doua masini sunt echivalente.

Limbajele recunoscute de masini Turing.

Teorema 6.2 Un limbaj este recunoscut de o masina Turing daca si numai dacaeste de tipul zero.


Demonstratie. Partea I. E = L(MT ) ⇒ E ∈ L0.Fie MT = (Σ, I, f, s0, Σf ) o masina Turing astfel ıncat E = L(MT ). Putem

presupune ca MT este nestationara. Fie Iλ = (I \ {[}) ∪ {λ}.Construim o gramatica de tipul zero astfel: G = (VN , VT , S, P ) unde

VN = Σ ∪ {(i, j)|i ∈ Iλ, j ∈ I} ∪ {S, X1, X2}; VT = I \ {[}.

Definitia lui P :S → s0X1, X1 → (i, i)X1, i ∈ I \ {[},X1 → X2, X2 → (λ, [)X2, X2 → λ,daca f(s, i) = (s′, i′, 1) atunci s(i1, i) → (i1, i

′)s′, ∀i1 ∈ Iλ,daca f(s, i) = (s′, i′,−1) atunci (i1, i2)s(i3, i) → s′(i1, i2)(i3, i′), i1, i3 ∈ Iλ, i2 ∈

I,daca s ∈ Σf , atunci s(i1, i2) → si1s si (i1, i2)s → si1s.Fie p ∈ L(MT ), p = i1 . . . in. Presupunem ca MT utilizeaza ın recunoastere

m pozitii de pe banda situate la dreapta cuvantului p. In G avem

S⇒s0X1∗⇒s0(i1, i1) . . . (in, in)X2

∗⇒s0(i1, i1) . . . (in, in)(λ, [)m.

Cuvantul p fiind recunoscut de MT avem

(1) (s0, i1 . . . in, 1)∗7−→(sf , i

′1 . . . i′h, k), h ≥ n.

Vom arata ca (1) implica existenta unei derivari de forma

2)s0(i1, i1) . . . (in, in)(λ, [)m ∗⇒(i1, i′1) . . . (ik−1, i

′k−1)sf (ik, i

′k) . . . (in+m, i′n+m),

undei1, . . . , in ∈ I \ {[}, in+1, . . . , in+m = λ,i′1, . . . , i

′h ∈ I \ {[}, i′h+1, . . . , i

′n+m = λ.

Demonstratie prin inductie asupra lungimii l a evolutiei.Pentru l = 0 avem

(s0, i1 . . . in, 1)∗7−→(s0, i1 . . . in, 1), k = 1, h = n, i′j = ij.

Partea dreapta a lui 2) va avea forma s0(i1, i1) . . . (in, in)(λ, [)m si deci 2) esteadevarata.

Presupunem ca implicatia este adevarata pentru l oarecare si consideram oevolutie de lungime l + 1. Punem ın evidenta ultima evolutie directa

(s0, i1 . . . in, 1)∗7−→(s, i′′1 . . . i′′g , j)7−→(sf , i

′1 . . . i′h, k).

In general h = g sau h = g + 1 ın conformitate cu urmatoarele doua cazuri(figura 6.2).


i" 1 i" 2 i" 3 i" g . . .

s

i" 1 i" 2 i" 3 i" g . . .

s

h = g g + 1 h =

Figura 6.2: Configuratii posibile ale masinii Turing

Intotdeauna k = j ± 1. apoi i′′t = i′t, t = 1, . . . , g, t 6= j, adica

i′′1, i′′2, . . . , i

′′j−1, i

′′j , i

′′j+1, . . . , i

′′g ;

i′1, i′2, . . . , i

′j−1, i

′j, i

′j+1, . . . , i

′g.

In urma ultimei evolutii directe vor diferi numai simbolurile i′′j , i′j.

Din ipoteza inductiva rezulta

s0(i1, i1) . . . (in, in)(λ, [)m ∗⇒(i1, i′′1) . . . (ij−1, i

′′j−1)s(ij, i

′′j ) . . . (in+m, i′′n+m).

In conformitate cu definitia evolutiei directe avem

f(s, i′′j ) = (sf , i′j, 1), k = j + 1, s(ij, i

′′j ) → (ij, i

′′j )sf ;

f(s, i′′j ) = (sf , i′j,−1), k = j − 1, (ij−1, i

′′j−1)s(ij, i

′′j ) → sf (ij, i

′′j−1)(ij, i

′j).

In ambele cazuri

s0(i1, i1) . . . (in, in)(λ, [)m ∗⇒(i1, i′1) . . . (ik−1, i

′k−1)sf (ik, i

′k) . . . (in+m, i′n+m).

Acum, deoarece sf ∈ Σf , putem scrie

S∗⇒s0(i1, i1) . . . (in, in)(λ, [)m

∗⇒(i1, i′1) . . . (ik−1, i

′k−1)sf (ik, i

′k) . . . (im+n, i′m+n)

⇒(i1, i′1) . . . (ik−1, i

′k−1)sf iksf (ik+1, i

′k+1) . . . (im+n, i

′m+n)

⇒(i1, i′1) . . . (ik−2, i

′k−2)sf ik−1sf iksf ik+1sf (ik+2, i

′k+2) . . . (im+n, i′m+n)

∗⇒sf i1sf i2sf . . . sf insf∗⇒i1 . . . in = p.

Prin urmare p ∈ L(G) si L(MT ) ⊆ L(G). Analog se arata si incluziunea inversasi deci L(MT ) = L(G).2

Bibliografie

1. Octavian C. Dogaru, Bazele informaticii. Limbaje formale, Tipografia Uni-versitatii din Timisoara, 1989.


2. Gheorghe Grigoras, Limbaje formale si tehnici de compilare, TipografiaUniversitatii ”Alexandru Ioan Cuza”, Iasi, 1984.

3. J. E. Hopcroft si J. D. Ullman, Introduction to Automata Theory, Languagesand Computation, Reading Mass., 1979.

4. Solomon Marcus, Gramatici si automate finite, Editura Academiei, Bu-curesti, 1964.

5. Stefan Maruster, Curs de Limbaje formale si tehnici de compilare, Ti-pografia Universitatii din Timisoara, 1980.

6. Gheorghe Orman, Limbaje formale, Editura tehnica, Bucuresti, 1982.

7. Gheorghe Paun, Probleme actuale ın teoria Limbajelor formale, EdituraStiintifica si Enciclopedica, Bucuresti, 1984.

8. Teodor Rus, Mecanisme formale pentru specificarea limbajelor, Editura Academiei,Bucuresti, 1983.

9. Arto Salomma, Formal languages, Academic Press, New York, 1973.

10. Dan Simovici, Limbaje formale si tehnici de compilare, Editura didactica sipedagogica, Bucuresti, 1978.

11. Luca Dan Serbanati, Limbaje de programare si compilatoare, Editura Academiei,Bucuresti, 1987.

Limbaje Formale si Tehnici de Compilare

Documents

Transcript of Limbaje Formale si Tehnici de Compilare