- 1991-

Introducere - organizarea unui compilator . . . . . . . . . . 1

1. Elemente de teoria limbajelor formale . . . . . . . . . . 5

1.1. Gramatici . . . . . . . . . . . . . . . . . . . . . . 6 l7h4ht
1.1.1. Verificarea limbajului generat de catre o . . . 8 gramatica
1.1.2. Transformari asupra gramaticilor . . . . . . . 9
1.1.3. Constructii dependente de context . . . . . . . 22
1.1.4. Propietati ale limbajelor independente de . . . 23 context

1.2. Multimi regulate, expresii regulate. . . . . . . . . . 25

1.3. Acceptoare . . . . . . . . . . . . . . . . . . . . . . 28
1.3.1. Automate finite . . . . . . . . . . . . . . . . 30
1.3.1.1. Constructia unui automat finit 31 nedeterminist care accepta limbajul descris de o expresie regulata data
1.3.1.2. Conversia unui automat finit 34 nedeterminist (AFN) intr-un automat finit determinist(AFD)
1.3.1.3. Constructia unui automat finit 38 determinist care accepta limbajul descris de o expresie regulata data
1.3.1.4. Simularea unui automat finit 43 determinist
1.3.1.5. Simularea unui automat finit 44 nedeterminist
1.3.1.6. Probleme de implementare pentru 46 automatele finite deterministe si nedeterministe
1.3.1.7. Minimizarea numarului de stari pentru 48
AFD

1.4. Automate cu stiva(pushdown) . . . . . . . . . . . . . 50

1.5. Masina Turing . . . . . . . . . . . . . . . . . . . 60
1.5.1. Compunerea masinilor Turing. . . . . . . . . . 65
1.5.2. Extensii pentru masini Turing . . . . . . . . 70
1.5.3. Relatia intre masina Turing si gramatici . . . 77
1.5.4. Elemente de calculabilitate . . . . . . . . . 80

2. Analiza lexicala . . . . . . . . . . . . . . . . . . . . . 86

2.1. Interfata analizorului lexical . . . . . . . . . . . 89

2.2. Aspecte privind implementarea unui analizor lexical 92

2.3. Un exemplu elementar de analizor lexical . . . . . . 94
3. Analiza sintactica . . . . . . . . . . . . . . . . . . . 102
3.1. Analiza sintactica top - down . . . . . . . . . . 105
3.1.1. Analiza sintactica predictiva . . . . . . . 106
(descendent recursiva)
3.1.2. Gramatici LL(1) . . . . . . . . . . . . . . 112
3.1.3. Tratarea erorilor in analiza predictiva . . 117
3.2. Analiza sintactica bottom-up . . . . . . . . . . . 119
3.2.1. Analiza sintactica de tip . . . . . . . . . 119 deplaseaza reduce
3.2.2. Implementarea analizei sintactice . . . . . 119 bottom-up deplaseaza reduce
3.2.3. Gramatici de precedenta cu operatori . . . . 122
3.2.4. Relatii de precedenta stabilite pe baza . . 125 proprietatilor de asociativitate si prioritatile operatorilor
3.2.5. Analiza sintactica de tip LR(k) . . . . . . 129
3.2.5.1. Analiza SLR . . . . . . . . . . . . 137
3.2.5.2. Analiza canonica LR . . . . . . . . 143
3.2.5.3. Analiza sintactica LALR . . . . . . 148
3.2.5.4. Compactarea tabelelor LR . . . . . 156
3.2.5.5. Utilizarea gramaticilor ambigue . . 158
3.2.5.6. Revenirea din eroare pentru . . . . 164 analiza LR

Bibliografie . . . . . . . . . . . . . . . . . . . . . . . 167
Introducere - organizarea unui compilator

Un compilator este un program complex care realizeaza traducerea unui program sursa intr-un program obiect. De obicei programul sursa este scris intr-un limbaj de nivel superior celui in care este scris programul obiect.
Structura generala pentru un compilator este:

program sursa

|
+-----------------+
| preprocesor | pas 1
+-----------------+
| pas 2
+ - - - - - - - | - - - - - - - - - - - - - - - - - - - - - - +
| | |
| | |
| +------------------+ +--------------------+ |
| | analiza lexicala |--------->| analiza sintactica | |
| | |<---------| | |
| +------------------+ +--------------------+ |
| | | | |
| +------------------+ +--------------------+ |
| | gestiunea tabelei| | analiza semantica | |
| | de simboli |<---------| | |
| +------------------+ +--------------------+ |
| | | |
| | +--------------------+ |
| +--------------------| generarea de cod | |
| | intermediar | |
| +--------------------+ |
+ - - - - - - - - - - - - - - - - - - - - - - | - - - - - - -+
| cod intermediar
|
+--------------------+ pas 3 | optimizare |
+--------------------+
|
| cod intermediar
+--------------------+ pas 4 | generarea de cod |
+--------------------+
| limbaj de asamblare sau cod masina

Preprocesorul realizeaza activitati de tip macro substitutie, eliminarea comentarilor, etc.
Al doilea pas reprezinta de fapt componenta principala a unui compilator (celelalte componente ar putea sa lipseasca).
Efectul executiei acestui pas consta din verificarea corectitudinii formale a textului programului si traducerea acestui text intr-o forma intermediara.
Ultimii doi pasi realizeaza prelucrari asupra programului in cod intermediar in scopul imbunatatirii performantelor acestuia
(optimizarea) si generarii programului obiect.
Pasul cel mai complex dintr-un compilator ramine pasul 2 in care se realizeaza cele mai importante operatii fara de care nu poate avea loc procesul de compilare. Intr-un compilator real cele cinci componente care il formeaza : analiza lexicala, analiza sintactica, analiza semantica, gestiunea tabelei de simboli si generarea de cod nu sint neaparat identificabile sub forma unor proceduri ori functii distincte. In cele ce urmeaza aceste componente vor fi descrise separat pentru simplificarea expunerii.

Analiza lexicala

Aceasta faza a compilatorului realizeaza traducerea textului programului intr-o forma mai usor de prelucrat de catre celelalte componente. Si anume, analizorul lexical considera textul primit la intrare ca fiind format din unitati lexicale pe care le recunoaste producind atomi lexicali. Un atom lexical poate sa fie de exemplu, un cuvint cheie al limbajului (for, while, etc) dar si un numar sau un nume. Sirul de intrare initial pe care analizorul lexical il recunoaste ca atom lexical este numit in literatura de specialitate "lexema". Se observa ca nu exista o corespondenta biunivoca intre sirurile de intrare si atomii lexicali. Adica, daca pentru atomul lexical corespunzator cuvintului cheie while exista un singur sir de intrare, pentru atomul lexical corespunzator unui numar intreg pot sa existe foarte multe siruri de intrare. Una dintre decizile ce trebuie luate la inceputul proiectarii unui compilator consta din stabilirea atomilor lexicali. De exemplu, se pune problema daca sa existe cite un atom lexical pentru fiecare operator de comparatie (<, <=, >, >=) sau sa existe un unic atom lexical - corespunzator operatiei de comparatie. In primul caz generarea de cod poate sa fie mai simpla. Pe de alta parte existenta unui numar mare de atomi lexicali poate complica in mod exagerat analiza sintactica. In general, operatorii care au aceasi prioritate si asociativitate pot sa fie grupati impreuna.
Rolul unui analizor lexical este de a traduce sirurile de intrare in atomi lexicali. Un atom lexical este reprezentat printr-un cod numeric care specifica clasa acestuia si o serie de atribute care pot sa fie specifice fiecarei clase. Astfel, poate sa existe clasa operatorilor relationali pentru care trebuie sa se specifice si tipul concret al operatorului. Prima informatie este necesara pentru analiza sintactica in timp ce a doua informatie este semnificativa pentru generarea de cod. Pentru un numar este semnificativa atit clasa, cit si informatii privind tipul numarului sau valoarea acestuia.
Un analizor lexical apare in general ca o procedura care interfera cu restul compilatorului printr-o interfata simpla : ori de cite ori analizorul sintactic are nevoie de un nou atom lexical va apela analizorul lexical care ii va intoarce atomul lexical urmator.
Analiza sintactica

Analiza sintactica descompune textul programului sursa in componentele sale "gramaticale", construind un arbore care reflecta aceasta structura. Sa consideram de exemplu expresia :

A * B + C * D

Aceasta expresie poate sa fie descrisa de urmatorul arbore (numit arbore sintactic) :

+
/ \
/ \
/ \
* *
/ \ / \
/ \ / \
A B C D

In acest arbore au fost evidentiate relatiile (din puctul de vedere al modului de evaluare) intre componentele expresiei. Daca se doreste insa sa se evidentieze structura expresiei din punctul de vedere al unitatiilor sintactice din care este formata, structura arborelui devine :

expresie
| factor + factor

/ \
/ \
/ \ factor * factor factor * factor
| | | | nume nume nume nume
| | | |
A B C D

Arborele astfel obtinut se numeste arborele de derivare (parse tree). Orice analizor sintactic realizeaza de fapt traducerea unui sir de atomi lexicali intr-un astfel de arbore de derivare care descrie de fapt relatia ierarhica intre o descriere generala a propozitiei analizate (radacina arborelui) si sirul de atomi lexicali din care este format (frunzele). Un analizor sintactic poate sa construiasca efectiv o structura de date de tip arbore
(cu pointeri si inregistrari) sau poate sa sintetizeze informatiile din care se poate face constructia acestuia.

Analiza semantica

Aceasta faza poate sa fie practic incorporata in faza de analiza sintactica. Rolul acestei faze consta din verificarea din punct de vedere semantic a structurilor recunoscute drept corecte din punct de vedere sintactic. Majoritatea verificarilor realizate de catre aceasta faza se refera la tipurile elementelor. De asemenea aceasta faza completeaza arborele de derivare cu o serie de informatii necesare generarii de cod.

Generarea de cod

Aceasta faza nu este intodeauna separata de analiza sintactica, exista compilatoare care genereaza cod chiar in timpul analizei sintactice. In general generarea de cod se face prin parcurgerea arborelui de derivare. Ceea ce se genereaza de obicei este o forma intermediara din care eventual se poate reconstitui arborele de derivare de catre pasul de optimizare, deoarece este mai simplu de realizat optimizarea pe un arbore decit pe o structura liniara.
Utilizarea formelor intermediare se justifica prin citeva argumente. In primul rind anumite optimizari nu se pot face in timpul analizei sintactice si sint dificil de realizat pe un text de program intr-un limbaj de programare de nivel foarte scazut.
Alt motiv ar putea sa fie utilizarea aceleeasi faze de optimizare si generare de cod masina pentru diferite limbaje de programare.
De asemenea o astfel de faza poate sa fie utilizata pentru realizarea de compilatoare incrementale sau interpretoare. Acest tip de translatoare executa direct codul intermediar fara a mai trece prin fazele urmatoare - editare de legaturi, incarcare, etc.
Dezavantajul utilizarii unei forme intermediare consta in mod evident din marirea timpului necesar pentru executia unei compilari.

Gestiunea tabelei de simboli

In tabela de simboli se inregistreaza identificatorii utilizati in program si informatii asupra acestora. Aceste informatii pot sa se refere la tip, domeniu de valabilitate; daca este vorba de identificatori de tip nume de procedura la aceste informatii se adauga si numarul si tipul argumentelor eventual modul de transfer al parametrilor. In general o tabela de simboli este o structura de date care contine cite o inregistrare pentru fiecare identificator avind cimpuri pentru atributele posibile.
Introducerea simbolilor in tabela se face in general de catre analizorul lexical. Atributele acestora sint completate in tabela de catre analizoarele sintactic si semantic.

Detectarea erorilor

Fiecare faza a unui compilator poate sa identifice prezenta unei erori specifice. De exemplu, in analiza lexicala intilnirea unui sir care nu corespunde unui atom lexical; in analiza sintactica se identifica erori legate de structura instructiunilor. Ca de exemplu:

int real alfa;

Fiecare atom in parte este corect dar nu formeaza impreuna o propozitie corecta din punct de vedere sintactic. In faza de analiza semantica se verifica daca constructiile corecte din punct de vedere sintactic sint corecte si din punct de vedere semantic. De exemplu daca la nivelul sintaxei poate sa apara ca fiind corecta o expresie de forma: nume + nume, fara nici o restrictie asupra tipului identificatorilor corespunzatori, atunci este rolul analizei semantice sa identifice ca eronata o expresie in care primul nume este al unui vector iar al doilea nume este al unei proceduri.
Problema cea mai dificila legata de tratarea erorilor consta din modul in care se continua analiza dupa identificarea unei erori, pentru ca un compilator care se opreste la prima eroare intilnita nu este prea comod de utilizat. Exceptie face modul de abordare in primele versiuni ale compilatorului pentru TURBO
Pascal pentru care la intilnirea unei erori se revine in regim de editare pentru corectarea acesteia.

1. Elemente de teoria limbajelor formale

Fie T o multime de simboli denumita alfabet. Orice submultime a multimii T* reprezinta un limbaj asupra alfabetului
T. Elementele limbajului se numesc propozitii. Daca limbajul este finit atunci el poate sa fie definit prin enumerare, cazul interesant este insa cel in care limbajul este infinit. Sa consideram de exemplu limbajul "sirurilor formate din 0 si 1 a caror lungime este divizibila cu 3". Evident este vorba de un limbaj infinit. Textul pe care l-am dat pentru a specifica limbajul constituie o reprezentare finita a limbajului. Nu este singura solutie posibila. De exemplu daca notam cu L limbajul respectiv atunci

L = A w E A0,1S* | |w| mod 3 = 0S

Se pune problema daca dindu-se un limbaj oarecare este posibila construirea unei reprezentari finite. Sa consideram ca o astfel de reprezentare finita se realizeaza utilizind simboli dintr-un alfabet finit A. Se poate demonstra ca multimea A* este infinit numarabila (se poate construi o bijectie f : N --> A*). Deci exista o multime infinit numarabila de reprezentari finite.
Numarul de limbaje ce se pot construi utilizind simboli dintr-un
* alfabet dat T, este 2T deci este infinit nenumarabila. Rezulta deci ca ar trebui sa reprezentam un numar infinit nenumarabil de obiecte utilizind un numar infinit numarabil de reprezentari. Din acest motiv nu orice limbaj va putea sa fie reprezentabil intr-un mod finit. Spre norocul nostru, nu sintem interesati chiar de orice limbaj.
In general exista doua mecanisme distincte de definire finita a limbajelor : prin generare sau prin recunoastere. In primul caz este vorba de un "dispozitiv" care stie sa genereze toate propozitiile din limbaj (si numai pe acestea) astfel incit alegind o propozitie din limbaj intr-un interval finit de timp dispozitivul va ajunge sa genereze propozitia respectiva. In al doilea caz este vorba de un "dispozitiv" care stie sa recunoasca
(sa accepte ca fiind corecte) propozitiile limbajului dat.

1.1. Gramatici

O gramatica reprezinta cel mai important exemplu de generator de limbaje. Prin definitie o gramatica este G = (N, T,
P, S) unde :

- N este o multime finita de simboli numita multimea simbolilor neterminali;
- T este o multime finita de simboli numita multimea simbolilor terminali (T n N = O);
- P este o submultime finita din

(N U T)* N (N U T)* x (N U T)*;

- S E N este un simbol special numit simbol de start al gramaticii G.

Un element p E P, p = (a, B) este notat cu a -> B si se numeste productie.

In cele ce urmeaza vom utiliza o serie de notatii devenite de fapt "clasice". Si anume :

- literele mici de la inceputul alfabetului latin
(a,b,c,...) reprezinta elemente din T (simboli terminali);
- literele mici de la sfirsitul alfabetului latin (u, v, x,...) reprezinta elemente din T* (siruri de simboli terminali);
- literele mari de la inceputul alfabetului latin (A, B,
C,...) reprezinta elemente din N (simboli neterminali);
- literele mari de la sfirsitul alfabetului latin (U, V,
X,...) reprezinta elemente din N U T (simboli terminali sau neterminali);
- literele alfabetului grecesc (a, B, ...) reprezinta siruri din (N U T)* (siruri de simboli terminali si neterminali).

O forma propozitionala pentru o gramatica G se defineste recursiv in modul urmator :

(1) S este o forma propozitionala
(2) daca aBt este o forma propozitionala si exista o productie B -> r atunci art este o forma propozitionala.

O forma propozitionala care contine numai simboli terminali se numeste propozitie generata de G. Notam cu L(G) multimea tuturor propozitiilor generate de G. L(G) este limbajul generat de gramatica G.
Se observa ca o gramatica este o reprezentare finita (toate elementele sale sint finite) a unui limbaj care poate sa fie infinit. Conform observatiei facute la inceputul acestui capitol nu orice limbaj are o reprezentare finita, cu alte cuvinte nu pentru orice limbaj exista o gramatica care sa il reprezinte.

Doua gramatici G si G' sint echivalente daca si numai daca L(G) = L(G').
Asupra formelor propozitionale se defineste o relatie numita relatie de derivare =G> in modul urmator. Fie a si B doua forme propozitionale, a =G> B daca si numai daca exista w1, w2 si z -> s E P astfel incit a = w1 z w2 si B = w1 s w2.
Relatia =G> poate sa fie extinsa obtinindu-se derivarea in k pasi. Si anume a =k> B daca exista a0, a1, ...,ak forme propozitionale astfel incit a = a0, ai-1 =G> ai 1 <= i <= k si ak
= B.
Inchiderea tranzitiva a relatiei =G> se noteaza cu =+>.
Inchiderea tranzitiva si reflexiva a relatiei =G> se noteaza cu
=*>.
Sa consideram de exemplu gramatica G = (AA,SS, A0,1S, P, S) unde P = AS-> 0A1, 0A -> 00A1, A -> ?S (cu ? s-a notat sirul vid de simboli).

S =G> 0A1 =G> 00A11 =G> 000A111, S =+> 0A1 =*> 0A1.

000111 este o propozitie in L(G).

Se observa ca L(G) = A w | w E T+, S =+> wS.

Ierarhia Chomsky.
Gramaticile pot sa fie clasificate conform complexitatii productilor in urmatoarea ierarhie :

gramatici de tip 0 - au productiile de forma

a -> B cu a E (N U T)* N (N U T)* , B E (N U T)*

gramatici de tip 1 (dependente de context) - au productiile de forma :

a A B -> a r B, a, B E (N U T)*, A E N, r E (N U T)+

(se observa ca |aAB| < |arB|).
In cazul garamaticilor de tip 1, exista eventual si o productie

S -> ?

in acest caz S nu apare in membrul drept al niciunei productii.

gramatici de tip 2 (independente de context) - au productiile de forma :

A -> a, A E N, a E (N U T)*.

gramatici de tip 3 (regulate la dreapta) au productii de forma:

A -> aB cu A E N , B E (N U A?S) si a E T*.

Se poate arata simplu ca intre gramaticile care formeaza ierarhia exista o relatie de incluziune. Adica orice gramatica regulata este o gramatica independenta de context, orice gramatica independenta de context este o gramatica dependenta de context, etc.
Sa consideram citeva exemple:

a) G1 = (ASS,A0,1S,AS -> 0S, S -> 1S, S -> ?S, S). Se observa ca
G1 este o gramatica regulata care genereaza limbajul A0,1S*. b) G2 = (AS, AS,A0,1S,AS -> AS, S -> ?, A -> ?, A -> 0, A -> 1S,
S). Se observa ca G2 este o gramatica independenta de context iar limbajul generat este tot A0,1S*. Rezulta deci ca un acelasi limbaj poate sa fie definit de mai multe gramatici diferite eventual chiar de tipuri diferite (evident orice gramatica regulata este si o gramatica independenta de context, si o gramatica dependenta de context, etc). c) G3 = (AE, T, FS,Aa, +, *, (, )S, P, E) cu P = A E -> E + T, E
-> T, T -> T * F, T -> F, F -> (E), F -> aS. Sa considerm un exemplu de derivare in aceasta gramatica :

E => E + T => T + T => F + T => a + T => a + T * F => a + F * F => a + a * F => a + a * a.
Se observa ca gramatica G3 este o gramatica independenta de context si este o gramatica care descrie limbajul expresiilor aritmetice cu paranteze care se pot forma cu operandul a si cu operatorii + si *.

In cele ce urmeaza pentru simplificarea notatiilor daca pentru un neterminal exista mai multe productii :

A -> w1, A -> w2, ... A -> wk

vom reprezenta aceste notatii sub o forma mai compacta :

A -> w1 | w2 | ... | wk.

De asemenea pentru specificarea unei gramatici nu vom mai preciza in general decit multimea productiilor sale, celelalte elemente rezultind in mod banal din aceasta.

1.1.1. Verificarea limbajului generat de catre o gramatica

In toate exemplele considerate pina acum s-a facut
"ghicirea" gramaticii care genereaza un limbaj dat sau a limbajului generat de catre o gramatica data. Se pune insa problema cum se poate demonstra corectitudinea rezultatului unei astfel de ghiciri.
Sa consideram de exemplu gramatica:

G = (ASS, A(,)S, AS --> (S)S | ?S, S)

Aceasta gramatica genereaza toate sirurile de paranteze bine inchise (echilibrate). Dorim insa sa demonstram aceasta afirmatie. In acest scop trebuie sa demonstram ca orice sir derivat din S satisface conditia enuntata si apoi trebuie sa demonstram incluziunea in sens invers. Adica, dindu-se un sir de paranteze bine inchise trebuie sa aratam ca acest sir poate sa fie derivat din S. Pentru prima parte a demonstratiei vom utiliza inductia asupra numarului de pasi in derivare. Sirul vid care se obtine intr-un pas din S este un sir de paranteze bine inchise.
Sa presupunem ca pentru toate derivarile realizate in mai putin de n pasi se obtin siruri de paranteze bine inchise si sa consideram o derivare de exact n pasi. O astfel de derivare poate sa arate ca :

S ==> (S)S =*=> (x)S =*=> (x)y

unde x si y sint siruri de terminale derivate din S in mai putin de n pasi. Rezulta deci ca sirul (x)y este un sir de paranteze bine inchise. Cu alte cuvinte orice sir derivat din S este
"corect". Sa consideram acum si demonstratia in sens invers. De data asta demonstratia se face prin inductie asupra lungimii sirului. Pentru primul pas observam ca sirul vid este un sir derivabil din S. Sa presupunem acum ca orice sir cu mai putin de
2n simboli este derivabil din S. Sa consideram un sir w de paranteze bine inchise avind lungimea de 2n, cu n mai mare sau egal cu 1. Sigur sirul incepe cu o paranteza deschisa. Fie (x) cel mai scurt prefix format din paranteze bine inchise. Se observa ca w = (x)y, unde x si y sint siruri de paranteze bine inchise de lungime mai mica decit 2n. In acest caz x si y pot sa fie derivate din S. Rezulta ca exista o derivare:

S ==> (S)S =*=> (x)y

in care pentru obtinerea sirurilor x si respectiv y s-au utilizat mai putin de 2n pasi si deci w este un sir derivabil din S.
Desigur o astfel de demonstratie este practic imposibil de realizat pentru un limbaj "adevarat". Insa in general se pot face pe portiuni demonstratii ca cea de mai sus.

1.1.2. Transformari asupra gramaticilor

Utilizarea unei gramatici este interesanta pentru faza de analiza sintactica, pentru care se utilizeaza gramatici independente de context. Exista o serie de metode de analiza sintactica, bine puse la punct atit din punct de vedere teoretic cit si practic. Fiecare dintre aceste metode impune insa o serie de restrictii asupra gramaticilor utilizate. In general atunci cind se construieste o gramatica se pleaca de la forma generala a structurilor pe care aceasta trebuie sa le descrie si nu de la metoda de analiza sintactica ce va fi utilizata. In acest mod se obtine o gramatica ce poate sa fie "citita" si deci verificata.
Pentru a satisface insa conditiile impuse de catre metodele de analiza sintactica sau de catre generarea de cod, se realizeaza transformari asupra gramaticilor, transformari care pastreaza neschimbat limbajul generat. In cele ce urmeaza vom prezenta citeva transformari tipice asupra gramaticilor independente de context. Deoarece analiza sintactica se realizeaza pe baza arborelui de derivare vom prezenta in continuare citeva informatii legate de acesta.
Un arbore de derivare este o reprezentare grafica pentru o secventa de derivari. Intr-un arbore de derivare nu se mai poate identifica ordinea in care s-a facut substitutia simbolilor neterminali. Fiecare nod interior arborelui, reprezinta un neterminal. Descendentii unui nod etichetat cu un neterminal A sint etichetati de la stinga la dreapta prin simbolii care formeaza partea dreapta a unei productii care are in partea stinga neterminalul A. Parcurgind de la stinga la dreapta frunzele unui astfel de arbore se obtine o forma propozitionala.
Sa consideram de exemplu din nou gramatica sirurilor de paranteze bine formate:

G = (ASS, A(,)S, AS --> (S)S | ?S, S)

Sa consideram de exemplu urmatoarea secventa de derivari:

S ==> ( S ) S ==> ( ( S ) S ) S ==> ( () S ) S ==>
( () ( S ) S ) S ==> ( () () S ) S ==>
( () () ) S ==> ( () () ) ( S ) S =+=> ( ()() ) ()

Se obtine arborele de derivare:

S

/ / \ \
/ / \ \
/ / \ \
( S ) S

/ / \ \ / / \ \
/ / \ \ ( S ) S
/ / \ \ | |
( S ) S ? ?
|
? / / \ \
/ / \ \
( S ) S
| |
? ?
Arborele de derivare este construit de catre analizorul sintactic. Aceasta constructie se poate face pornind de la radacina aplicind succesiv productii - in acest caz se spune ca analiza sintactica este top-down. Dar, se poate porni si invers de la sirul de atomi lexicali (frunze) identificindu-se simbolii neterminali din care se poate obtine un sir de atomi lexicali. In acest caz se spune ca analiza sintactica este de tip bottom-up.
Deoarece arborele de derivare descrie relatia ierarhica intre entitatile sintactice (neterminale) si atomii lexicali
(terminale) se poate asocia o interpretare in termeni de evaluare a entitatilor sintactice. Astfel, considerind de exemplu gramatica expresilor aritmetice pentru sirul a + a * a se obtine arborele derivare :
E
/ | \
/ | \
E + T
| / | \
T / | \
| T * F
F | |
| F a a | a

in care se poate observa ca a fost evidentiat faptul ca operatia de inmultire este prioritara fata de operatia de adunare (aspect semantic).

a. Eliminarea ambiguitatii

O gramatica care produce mai multi arbori de derivare pentru aceeasi propozitie este o gramatica ambigua. Deoarece exista tehnici de analiza sintactica care lucreaza numai cu gramatici neambigue vom incerca sa construim gramatici care genereaza acelasi limbaj si care sint neambigue.
Sa consideram de exemplu urmatoarea gramatica :

instr -> if expresie then instr | if expresie then instr else instr | alte_instr

Sa construim arborele de derivare pentru propozitia :

if E1 then if E2 then S1 else S2

instr
/ /\ \
/ / \ \
/ / \ \
/ expr \ \
/ / \ then \ if / E1 \ \
------- instr
/ /\ \ \ \
/ / \ \ \ \
/ / \ \ \ \
/ expr \ \ \ \
/ / \ then \ \ \ if / E2 \ \ \ \
------- instr \ \
/ \ else \
/ S1 \ instr
------ / \
/ S2 \
------

Pentru aceasta propozitie mai exista insa un arbore de derivare :

instr
/ / \ \ \ \
/ / \ \ \ \
/ / \ \ \ \
/ expr \ \ \ \
/ / \ then \else \ if / E1 \ \ \
------- instr instr
/ \ / \
/ /\ \ / S2 \
/ / \ \ ----- if / then\ expr instr
/ \ / \
/ E2 \ / S1 \
------ ------

In toate limbajele de programare care accepta constructii de tip if then else se considera cu sens prima derivare in care fiecare clauza else este atribuita instructiunii if cea mai interioara. Rezulta deci conditia pe care trebuie sa o satisfaca o instructiune if. Instructiunea cuprinsa intre then si else trebuie sa nu fie o instructiune if sau sa fie o intructiune if cu clauza else. Rezulta urmatoarea gramatica obtinuta prin transformarea gramaticii anterioare:

instr -> if_cu_else| if_fara_else if_cu_else -> if expresie then if_cu_else else if_cu_else | alte_instr if_fara_else -> if expresie then instr | if expresie then if_cu_else else if_fara_else

Se observa ca aceasta gramatica genereaza acelasi limbaj cu gramatica anterioara dar accepta o derivare unica pentru propozitia :

if E1 then if E2 then S1 else S2 instr
| if_fara_else
/ /\ \
/ / \ \
/ / \ \
/ expr \ \
/ / \ then \ if / E1 \ \
------- instr
| if_cu_else
/ /\ \ \ \
/ / \ \ \ \
/ / \ \ \ \
/ expr \ \ \ \
/ / \ then \ \ \ if / E1 \ \ \ \
------- instr \ \
/ \ else \
/ S1 \ instr
------ / \
/ S2 \
------

Se numeste productie ambigua o productie care are in partea dreapta mai multe aparitii ale aceluiasi simbol neterminal.
Existenta unei productii ambigue nu implica faptul ca gramatica este ambigua. Sa consideram gramatica G = (AS, AS, Aa, b, c S, AS
-> aAbAc, A -> a | bS). Se observa ca aceasta gramatica nu este ambigua.
Sa consideram de exemplu si gramatica pentru expresii aritmetice:

G = (AES, Aa, +, *S, AE -> E + E | E * E | aS, E)

Gramatica G este o gramatica ambigua (se poate verifica usor utilizind sirul a + a * a). Aceasta gramatica poate sa fie transformata intr-o gramatica neambigua in doua forme:

1. E --> E + T | T
T --> T * F | F
F --> a

2. E --> T + E | T
T --> F * T | F
F --> a

Sa consideram sirul a * a * a. Pentru cele doua gramatici se obtin arborii de derivare respectivi:

E E

| |

T T

/ | \ / | \
/ | \ / | \

T * F F * T

/ | \ | | / | \
/ | \ / | \ a a
T * F F * T

| | | |

F a a F

| |

a a

Se observa ca primul arbore evidentiaza asociativitatea stinga a operatorului * in timp ce al doilea arbore evidentiaza asociativitatea dreapta. In functie de definitia limbajului si de modul in care arborele de derivare va fi explorat pentru generarea de cod este de preferat prima sau a doua solutie.
In cazul general daca pentru un neterminal A exista productiile:

A --> A B A | a1 | a2 | ... | an , B, a1, ... an E T*

acestea pot sa fie inlocuite cu:

A --> A' B A | A'
A' --> A | a1 | a2 | ... | an

Productia A' --> A poate sa fie eliminata (exista si A --> A') si se obtine:

A --> A' B A | A'
A' --> a1 | a2 | ... | an

Daca se construieste arborele de derivare se observa ca in acest caz se utilizeaza asociativitatea dreapta. Pentru a se obtine asociativitate stinga se utilizeaza transformarea:

A --> A B A' | A'
A' --> a1 | a2 | ... | an.

Trebuie sa remarcam insa faptul ca exista limbaje pentru care nu se pot construi gramatici neambigue. Un astfel de limbaj se numeste inerent ambiguu. De exemplu limbajul :

L = A aibjckdl | i = k sau j = l, i, j, k, l >= 0S

este inerent ambiguu.

b. Eliminarea ? - productiilor
Se spune ca o gramatica este ?- free daca satisface una dintre urmatoarele conditii :

a. Nu exista nici o productie care sa aiba in partea dreapta sirul vid sau b. Exista o singura productie care are in partea dreapta sirul vid si anume productia S --> ?. Simbolul S nu apare in acest caz in partea dreapta a nici unei productii.

Algoritmul de transformare este :

Intrare O gramatica G = (N, T, P, S)
Iesire O gramatica G' = (N', T, P', S') care satisface conditiile :

(i) L(G) = L(G')
(ii) G' este ? - free.

Descrierea algoritmului este :

i = 0
Ni = AA | A --> ? E PS repeta i = i + 1
Ni = A A | A --> a E P, a E N*i-1S U Ni-1 pina Ni = Ni-1
Ne = Ni daca S E Ne atunci
N' = N U AS'S
P' = AS' --> ?, S' --> SS altfel
N' = N
S' = S
P' = O/
= pentru fiecare p E P executa daca p este de forma : A --> a0 B1 a1 ... Bk ak, k >= 0,

Bi E Ne, 1 <= i <= k, aj E ((N \ Ne) U T)*, 0 <= j <= k atunci
P' = P' U (AA -> a0 X1 a1 ... Xk ak | Xi E ABi, ?SS \
AA --> ?S) altfel
P' = P' U ApS
=
=

Fie de exemplu gramatica S --> aSbS | bSaS | ?. Aplicind algoritmul anterior se obtine :

S' --> S, S --> aSbS | aSb | abS | ab | bSaS | bSa | baS | ba

c. Eliminarea recursivitatii stinga

O gramatica este recursiva stinga daca exista un neterminal
A astfel incit exista o derivare A =+=> AB pentru B E (T U N)*. O analiza sintactica de tip top-down nu poate sa opereze cu o astfel de gramatica, deci este necesara o transformare. Sa consideram intii ca in gramatica exista productiile A --> AB | r.
In acest caz se poate face transformarea : A --> r A', A' -->
BA'| ?.
Sa consideram de exemplu gramatica expresiilor aritmetice :

E --> E + T | T, T --> T * F | F, F --> (E) | a

Se observa ca pentru un sir de forma a + a * a, examinind numai primul simbol terminal(a) nu este clar cu care dintre productiile pentru E trebuie sa se inceapa derivarea. Aplicind ideea anterioara se obtine :

E --> T E', E' --> +TE' | ?, T -->FT', T' --> *FT' | ?
F --> (E) | a

In acest caz derivarea va incepe sigur cu productia E -> TE' si se obtine derivarea E ==> TE' ==> FT'E'. In acest moment se vede ca pentru F trebuie sa se aplice productia F --> a. Deci se obtine E =+=> aT'E'. Urmeaza simbolul terminal + datorita caruia pentru T' se va aplica productia T' --> ?, etc.
In general daca pentru un neterminal A exista productiile :

A --> AB1 |AB2 | ... |ABm | r1 | r2 | ... | rn

unde ri nu incepe cu A, 1 <= i <= n, se pot inlocui aceste productii cu :

A --> r1A' | r2A' | ... | rnA'
A' --> B1A' | B2A' | ... | BmA'| ?

Aceasta constructie elimina recursivitatea stinga imediata. Sa consideram insa gramatica :

S --> Aa | b
A --> Ac | Sd | e

Se observa ca este posibila urmatoarea derivare S ==> Aa => Sda, deci gramatica este recursiva stinga.
Daca gramatica nu permite derivari de tipul A =+=> A (fara cicluri) si nu contine ? - productii poate sa fie transformata in vederea eliminarii recursivitatii stinga utilizind urmatorul algoritm.

Intrare O gramatica fara cicluri si ?- productii
Iesire O gramatica echivalenta fara recursivitate stinga.

Descrierea algoritmului este :

Se aranjeaza neterminalele in ordinea A1, ..., An pentru i = 1 pina la n executa pentru j = 1 pina la i - 1 executa inlocuieste fiecare productie de forma Ai --> Aj r cu productiile Ai --> u1 r | u2 r | ... | uk r unde Aj --> u1|u2| ... |uk sint toate productiile pentru Aj
= elimina recursivitatea stinga intre productiile Ai
=

Sa consideram pasul i. Productiile Ak --> Alr care au mai ramas pentru care k < i, au l > k. In aceasta iteratie prin variatia lui j se ajunge ca pentru orice productie de forma Ai --> Am r, m
>= i. Daca se elimina recursivitatea directa ramine m > i.
Sa consideram de exemplu din nou gramatica :

S --> Aa | b, A --> Ac | Sd | e

Consideram pentru neterminale ordinea : S, A. Pentru S (i = 1) nu exista recursivitate stinga directa deci nu se face nici o modificare. Pentru i = 2, productia A --> Sd se inlocuieste cu A
--> Aad | bd. Rezulta deci ca A --> Ac | Aad | bd | e. Eliminind recursivitatea stinga se obtine :

S --> Aa | b, A --> bdA' | eA', A' --> cA' | adA' | ?

d. Factorizare stinga

Acest tip de transformare este util pentru producerea unei gramatici potrivite pentru analiza sintactica top down de tip determinist. Ideea este ca daca nu este clar care dintre productiile alternative poate sa fie aplicata pentru un neterminal se va amina luarea unei decizii pina cind s-a parcurs suficient din sirul de intrare pentru a se putea lua o decizie.
Sa consideram de exemplu productiile :

E --> T + E | T
T --> F * T | F
F --> a | (E)

Sa presupunem ca incercam sa construim sirul derivarilor pornind de la simbolul de start al gramaticii. Din recunoasterea simbolului a la inceputul sirului nu se poate inca trage concluzia care dintre cele doua productii corespunzatoare neterminalului E trebuie sa fie luata in considerare (abia la intilnirea caracterului + pe sirul de intrare se poate face o alegere corecta). In general pentru productia A --> r u1 | r u2 daca se recunoaste la intrare un sir nevid derivat din r nu se poate stii daca trebuie aleasa prima sau a doua productie.
Corespunzator este utila transformarea: A --> r A', A' --> u1 | u2.
Algoritmul de factorizare functioneaza in modul urmator.
Pentru fiecare neterminal A se cauta cel mai lung prefix r comun pentru doua sau mai multe dintre productiile corespunzatoare neterminalului A. Daca r =/ ? atunci se inlocuiesc productiile de forma A --> ru1 | ru2 | ... | run | t (unde t reprezinta alternativele care nu incep cu r) cu :

A --> r A' | t
A' --> u1 | u2 | ... | un

A' este un nou neterminal. Se aplica in mod repetat aceasta transformare pina cind nu mai exista doua alternative pentru un neterminal avind un prefix comun.
Reluind exemplul considerat se obtine :

E --> TX
X --> +E | ?
T --> FY
Y --> *T | ?
F --> a | (E)

Deci in analiza sirului a + a la intilnirea operatorului + pentru neterminalul Y se va utiliza productia Y --> ?, in acest mod rezulta sirul de derivari :

E ==> TX ==> FYX ==> aYX ==> ...

e. Eliminarea simbolilor neterminali neutilizati

Un simbol neterminal neutilizat este un simbol care nu poate sa apara intr-o forma propozitionala (inaccesibil) sau din care nu poate deriva un sir format numai din simboli terminali sau care apare intr-o forma propozitionala datorita sau impreuna cu simboli neterminali nefinalizati.
Eliminarea simbolilor nefinalizati se face utilizind urmatorul algoritm :

Intrare O gramatica G = (N, T, P, S)
Iesire O gramatica G' = (N', T, P', S) care satisface urmatoarele conditii :

(i) L(G) = L(G')
(ii) V- A E N, A =+=> w, w E T*.

Descrierea algoritmului este :
N0 = O/ i = 0 repeta i = i + 1
Ni = A A | A --> a E P si a E (Ni-1 U T)* S U Ni-1 pina Ni = Ni-1
N' = Ni
P' C_ P contine numai productiile din P care au in partea stinga simboli din N'

Prin inductie asupra numarului de pasi se poate demonstra corectitudinea algoritmului.

Sa consideram o gramatica avind productiile : P = AS --> A, A - > b, B --> aS, se observa ca B este un simbol neterminal inaccesibil. Aparent conditia de inaccesibilitate consta din ne aparitia in partea dreapta a unei productii. Daca insa consideram o gramatica avind productiile: AS -->A, A --> a, B --> cC, C --> bBS se observa ca este necesara o conditie mai puternica.
Eliminarea simbolilor inaccesibili se poate face utilizind urmatorul algoritm.

Intrare O gramatica G = (N, T, P, S)
Iesire O gramatica G' = (N', T, P', S) care satisface urmatoarele conditii :

(i) L(G) = L(G')
(ii) V- A E N', exista w E (N U T)*, S => w si A apare in w

Descrierea algoritmului este:

initializare stiva lista = ASS push(stiva, S) cit timop stiva nu este vida executa
A = pop(stiva) pentru fiecare neterminal B din partea dreapta a unei productii pentru A executa daca B nu este in lista atunci push(stiva, B) lista = lista U ABS
=
=
=
N' = lista elimina din gramatica toate productiile care corespund unor simboli din N \ lista.

Prin inductie asupra numarului de pasi se poate determina corectitudinea algoritmului.
Utilizind algoritmii pentru eliminarea simbolilor nefinalizati si cel pentru eliminarea simbolilor inaccesibili se obtine o gramatica care nu contine simboli neutilizati. Ordinea in care se aplica acesti algoritmi nu este indiferenta. Sa consideram de exemplu gramatica cu productile :
S --> a | A, A --> AB, B --> b.
Daca se aplica intii algoritmul pentru eliminarea simbolilor nefinalizati, ramin productiile S --> a si B --> b. Prin eliminarea simbolilor inaccesibili ramine numai productia S --> a. Daca insa se aplica intii algoritmul pentru eliminarea simbolilor inaccesibili si apoi cel pentru eliminarea simbolilor nefinalizati vor ramine pina la sfirsit ambele productii S --> a si B --> b. g. Substitutia de inceputuri(corner substitution)

Anumite metode de analiza sintactica presupun ca partea dreapta a fiecarei productii care nu este sirul vid sa inceapa cu un terminal. Sa consideram de exemplu gramatica avind productiile:

lista --> elem lista | a elem --> a(numar) | *elem

Sa inlocuim aparitia neterminalului elem in prima productie. se obtine:

lista --> a(numar) lista | *elem lista | a elem --> a(numar) | *elem

Sa realizam si factorizarea productiilor neterminalului lista:

lista --> aX | *elem lista
X --> (numar) lista | ? elem --> a(numar) | *elem

Se observa ca in acest caz in functie de simbolul terminal curent se poate selecta productia urmatoare pentru derivare.
O gramatica independenta de context pentru care este indeplinita conditia ca partea dreapta a oricarei productii incepe cu un terminal sau este sirul vid se numeste gramatica de tip Q. O forma particulara de gramatica de tip Q este forma normala Greibach. In acest caz nu exista ?-productii cu exceptia cel mult a unei ?-productii corespunzatoare simbolului de start al gramaticii. In cazul in care aceasta productie exista simbolul de start al gramaticii nu apare in partea dreapta a nici unei productii. In forma normala Greibach productiile sint de forma A
--> a a cu a E T si a E N*. Sa presupunem ca o gramatica are productile:
P --> a1 a1 | a2 a2 | ... | an an | ?

unde ai E T, i =/ j ==> ai =/ aj, 1 <=i, j <= n. O procedura care recunoaste sirurile derivate din P este de forma:

p()
A switch (caracter_urmator)
A case a1 : avans(); a1 /* tratare a1 */ case a2 : avans(); a2
... case an : avans(); an default: /* ? - productie */
S
S

Se poate elabora un algoritm pentru construirea unei gramatici in forma normala Greibach pentru o gramatica independenta de context care nu este recursiva stinga.
Se defineste intii o relatie de ordine asupra neterminalelor unei gramatici. Si anume A < B daca exista o productie A --> B a.
Considerind aceasta relatie se observa ca se obtine o relatie partiala de ordine care poate sa fie extinsa la o relatie liniara de ordine. Daca gramatica pentru care se construieste aceasta relatie nu este recursiva dreapta atunci productiile celui "mai mare" neterminal incep cu simboli terminali. In acest caz algoritmul este:

Intrare O gramatica G independenta de context care nu este recursiva stinga, nu are cicluri, nu are simboli neutilizati si nu are ?-productii cu exceptia cel mult a unei ?-productii corespunzatoare simbolului de start al gramaticii. In acest ultim caz simbolul de start al gramaticii nu apare in partea dreapta a nici unei productii.
Iesire O gramatica G' in forma normala Greibach

Descrierea algoritmului este:

Se construieste relatia de ordine asupra N astfel incit N
= AA1, A2, ..., AnS si A1 < A2 < ... < An. pentru i = n - 1 pina la 1 pas = -1 executa fiecare productie de forma Ai --> Aj a cu i < j se inlocuieste cu Ai --> B1 a | ... | Bm a unde Aj --> B1
| ...| B m (se observa ca B1, ..., Bm incep cu terminale)
= pentru fiecare productie de forma p = A --> a X1 ... Xk executa pentru i = 1 pina la k executa daca Xi E T atunci
N = N U AXi'S
P = P U A Xi' --> XiS, inlocuieste productia p cu p' = A --> aX1 ... Xi'
... Xk
=
=
=

Prin inductie asupra numarului de pasi se poate demonstra ca algoritmul realizeaza transformarea dorita. De exemplu pentru gramatica expresiilor aritmetice in forma fara ?-productii:

E --> T E' | T ,
E'--> +TE' | +T,
T --> FT' | F,
T'--> *FT' | *F
F --> (E) | a

Relatia de ordine liniara poate sa fie E' < E < T' < T < F. Se porneste de la F, pentru care toate productiile incep cu un terminal. Rezulta modificarea productiilor pentru T:

T --> (E) T' | a T' | (E) | a.

Urmeaza T' care nu necesita transformari. pentru E se obtine:

E --> (E)T'E' | a T' E' | (E)E' | aE' | (E)T' | aT' | (E) | a

De asemenea E' nu se modifica. Rezulta urmatoarea gramatica in forma normala Greibach:

E --> (EAT'E' | a T' E' | (EAE' | aE' | (EAT' | aT' | (EA | a
E' --> +TE' | +T
T --> (EA T' | a T' | (EA | a.
T' --> *FT' | *F
F --> (EA | a
A --> )

1.1.3. Constructii dependente de context

Anumite constructii specifice limbajelor de programare de nivel inalt nu pot sa fie descrise prin limbaje independente de context. Sa consideram citeva exemple :

1. Fie limbajul L1 = Awcw| w E A0,1S*S. Acest limbaj realizeaza abstractizarea conditiei ca un identificator sa fie declarat inainte de a fi utilizat. L1 nu poate sa fie generat de o gramatica independenta de context. Din acest motiv conditia ca un identificator sa fie definit inainte de a fi utilizat nu pot fi verificate prin analiza sintactica, deci va fi verificat de catre analiza semantica.
2. Fie limbajul L2 = Aanbmcndm | n > 1, m > 1S. Acest limbaj realizeaza abstractizarea corespondentei ca numar intre numarul de parametrii cu care au fost declarate procedurile si numarul de parametrii cu care se utilizeaza acestea. Nici acest limbaj nu pot fi descris de o gramatica independenta de context. Pe de alta parte limbajul L2' = Aanbn | n > 1S, poate sa fie descris de gramatica : S --> a S b | a b. Deci o gramatica independenta de context poate sa "numere" doi termeni dar nu trei sau mai multi.
De asemenea o gramatica regulata nu poate sa "numere" decit pina la o limita finita.

1.1.4. Propietati ale limbajelor independente de context

Dupa cum s-a vazut acelasi limbaj poate sa fie descris de mai multe gramatici, eventual de tipuri diferite. Este utila gasirea unui criteriu prin care sa se indice tipul restrictiv al gramaticilor care pot sa descrie un limbaj dat. De exemplu sa consideram limbajul:

A anxn | n > 1 S

Se pune problema daca exista o gramatica independenta de context care sa-l genereze. Urmatoarea teorema ofera un criteriu de stabilire a tipului probabil pentru gramaticile care genereaza un limbaj dat.

Teorema Ogden

Pentru orice gramatica independenta de context G = (N, T, P,
S) exista un numar intreg k > 1 astfel incit daca z E L(G), |z| > k si k sau mai multe pozitii din sirul z sint marcate atunci sirul z poate sa fie scris sub forma z = uvwxy astfel incit sint indeplinite urmatoarele conditii:

(1) in w apare cel putin o pozitie marcata;
(2) fie u si v contin fiecare cite cel putin o pozitie marcata fie acest lucru este valabil pentru x si y;

(3) in vwx apar cel mult k pozitii maracte;
(4) exista un neterminal A astfel incit:

S =+=> uAy =+=> uvAxy =+=> u vi A xi y =+=> u vi w xi y

pentru orice i > 0 , numar intreg.

Demonstatie Fie m = Card(N) si fie l lungimea celei mai lungi parti dreapta a unei productii din P. Fie k = l2m + 3. Sa consideram arborele de derivare T pentru un sir z E L(G) astfel incit |z| > k. Sa marcam cel putin k pozitii din z. Deoarece |z|
> k inseamna ca arborele va contine cel putin o cale mai lunga sau egala cu 2m + 3. Se numeste nod de ramificare in T un nod care are cel putin doi descendenti directi astfel incit din fiecare din ei se pot deriva siruri ce contin pozitii marcate.
Se construieste o cale n1, n2, ... in T in modul urmator:

(1) n1 este nodul radacina pentru T
(2) daca ni are un singur descendent direct din care deriveaza un sir care contine pozitii marcate atunci ni+1 va fi acest nod;
(3) daca ni este un nod de ramificare se alege ca ni+1 nodul descendent direct al nodului ni care are numarul maxim de pozitii marcate in sirul derivat. Daca exista egalitate se alege dintre nodurile cu acelasi numar nodul care apare cel mai in dreapta;
(4) daca ni este o frunza s-a ajuns la sfirsitul caii.

Sa presupunem ca n1, n2, ..., np este calea construita. Sa demonstram prin inductie asupra valorii numarului i ca daca calea n1, .., ni contine r noduri de ramificare atunci ni+1 are cel putin l2m+3-r descendenti marcati. Pentru i = 0 se obtine r =
0. Evident, n1 are cel putin l2m + 3 descendenti marcati (k = l2m + 3). Daca ni este un nod de ramificatie atunci ni+1 are cel putin 1/l descendenti marcati fata de nodul ni. Daca ni nu este nod de ramificatie atunci ni+1 are toti atitia descendenti marcati ca si ni. Pentru ca n1 are l2m + 3 descendenti marcati exista in calea n1, ..., np cel putin 2m + 3 noduri de ramificatie. In plus np este o frunza (deci nu este nod de ramificatie) si deci p > 2m + 3.
Fie b1, b2, .., b2m+3 noduri de ramificatie dintre n1, ..., np. Vom spune ca bi este un nod de ramificatie stinga daca un descendent direct al nodului b care nu face parte din cale are un descendent marcat aflat la stinga nodului np. In caz contrar bi este un nod de ramificare dreapta. Sa presupunem ca cel putin m +
2 noduri intre b1, ..., b2m + 3 sint noduri de ramificatie stinga.
Cazul in care conditia nu este indeplinita este cazul in care cel putin m + 2 noduri dintre b1, ..., b2m + 3 sint noduri de ramificatie dreapta si se trateaza similar. Fie l1, ...,lm+2 cele mai din stinga noduri de ramificatie stinga dintre b1, ..., b2m + 3. Deoarece Card(N) = m, exista doua noduri intre l2, ..., lm+2 pe care sa le notam lf si lg astfel incit f < g, si etichetele pentru lf si lg sint aceleasi. Fie A neterminalul respectiv.

S
/ \
/\ \
/ \l \
/ \1 \
/ l _\ \
/ f /\ \
/ / \ \
/ / __\ l \
/ / /\ \ g \
/ / / \ \ \
/ / / \ \ \
/ u / v/ w \x \ y \

Daca se sterg toti descendentii pentru lf se ajunge la frontiera uAy, cu u terminalele obtinute la stinga sirului derivat din A iar y terminalele obtinute la dreapta sirului derivat din A. Deci
S =+=> uAy. Se observa ca A =*=> w. Rezulta deci:

S =+=> uAy =+=> uvAxy =+=> uv2Ax2y =+=> ... =+=> uviwxiy.

Rezulta ca este indeplinita conditia (4). Se observa ca u are cel putin un terminal marcat (lf a fost ales pornind de la l2). De asemenea v va contine cel putin un terminal marcat
(conditie 2). De asemenea conditia (1) este satisfacuta cel putin prin np. Pentru conditia (3) se observa ca b1 este cel de al 2m +
3 nod de ramificatie pornind de la sfirsit poate avea maximum k pozitii marcate. Se observa ca lf este un descendent pentru b1.

Corolar (lema de pompare) Fie L un limbaj independent de context.
Atunci exista o constanta k caracteristica limbajului astfel incit daca z E L si |z| >= k, atunci z poate sa fie scris sub forma z = uvwxy cu vx =/ ?, |vwx| <= k si pentru orice i, uviwxiy
E L.
Sa utilizam rezultatul obtinut pentru a studia limbajul:

L = Aan x n | n > 1S

sa presupunem ca L este independent de context. Inseamna ca exista un numar k astfel incit daca n * n >= k atunci anxn = uvwxy astfel incit v si x nu sint amindoua siruri vide si |vwx| < k. Sa presupunem ca n = k ( k * k > k). Rezulta ca uv2wx2y E L.
Deoarece |vwx| <= k rezulta 1 < |vx| < k deci k x k < |uv2wx2y| < k x k + k. Dupa k x k urmatorul patrat perfect este (k + 1) x (k
+ 1) care este mai mare deci k x k + k, adica |uv2wx2y| nu poate sa fie un patrat perfect, deci L nu poate sa fie generat de o gramatica independenta de context.

1.2. Multimi regulate, expresii regulate.

Fie T un alfabet finit. Se numeste multime regulata asupra alfabetului T multimea construita recursiv in modul urmator :

1. o este o multime regulata asupra alfabetului T;
2. Daca a E T atunci AaS este o multime regulata asupra alfabetului T;
3. Daca P si Q sint multimi regulate atunci PUQ, PQ, P* sint multimi regulate asupra alfabetului T.
4. Nimic altceva nu este o multime regulata

Se observa deci ca o submultime a multimii T* este o multime regulata asupra alfabetului T daca si numai daca este multimea vida, este o multime care contine un singur simbol din T sau poate sa fie obtinuta din aceste doua tipuri de multimi utilizind operatiile de reuniune (P U Q), concatenare (PQ) sau inchidere P*.

Descrierea multimiilor regulate se poate face cu ajutorul expresiilor regulate. O expresie regulata este la rindul ei definita recursiv in modul urmator (prin analogie cu definitia multimiilor regulate) :

1. ? este o expresie regulata care descrie multimea A?S;
2. a E T este o expresie regulata care descrie multimea AaS;
3. daca p,q sint expresii regulate care descriu multimile P si Q atunci : a. (p + q) sau (p | q) este o expresie regulata care descrie multimea P U Q; b. (pq) este o expresie regulata care descrie multimea
PQ; c. (p)* este o expresie regulata care descrie multimea
P*.
4. nimic altceva nu este o expresie regulata.

De exemplu expresia (0 | 1)* reprezinta multimea A0,1S*, expresia regulata : (00 | 11)*((01 | 10)(00 | 11)*(01 | 10)(00 |
11)*)* reprezinta multimea care contine toate sirurile formate din 0 si 1 si care contin un numar par din fiecare simbol.
In particular pp* este notat cu p+. Intre operatorii utilizati in descrierea multimilor regulate exista o serie de relatii de precedenta si anume cea mai prioritara operatie este operatia de inchidere (notata cu *), urmeaza operatia de concatenare cel mai putin prioritara fiind operatia + (|). De exemplu expresia regulata (0 | (1(0)*)) poate sa fie scrisa si sub forma 0 | 10*.
Expresiile regulate au o serie de proprietati. Fie a, B, t expresii regulate. Spunem ca a = B daca si numai daca a si B descriu aceleasi multimi regulate. Sint adevarate urmatoarele proprietati :

1. a | B = B | a 2. a | (B | t) = (a | B) | t
3. a(Bt) = (aB)t 4. a(B | t) = aB | at
5. (a | B)t = at | Bt 6. a? = ?a = a
7. a* = a | a* 8. (a*)* = a*
9. a | a = a

Utilizind expresii regulate se pot construi si rezolva ecuatii cu solutii expresii regulate. Sa consideram de exemplu ecuatia:

X = aX + b

unde a,b si X sint expresii regulate. Se poate verifica usor ca X
= a*b este o solutie a acestei ecuatii.
Daca a este o expresie regulata care poate sa genereze sirul vid atunci solutia prezentata anterior nu este unica. Sa inlocuim in ecuatie pe X cu expresia regulata:

a*(b + t)

Se obtine:

a*(b + t) = aaa*(b + t)i + b =
= a+b + a+t + b =
= (a+ + ?)b + a+t = a*b + a*t
= a*(b + t)

Se numeste punct fix al unei ecuatii cea mai mica solutie a ecuatiei respective.

Propozitie Daca G este o gramatica regulata atunci L(G) este o multime regulata.
Demonstratia acestei teoreme se face prin constructie. Sa consideram de exemplu gramatica:

G = (AA, B, CS, A0,1S, P,A)

cu P = AA ->1A | 0B, B -> 0B | 1C, C->0B| 1A| ?S. Se cere sa se construiasca expresia regulata care genereaza acelasi limbaj ca si G. Se pot scrie urmatoarele ecuatii:

A = 1A + 0B
B = 0B + 1C
C = 0B + 1A + ?

Din prima ecuatie se obtine:

A = 1*0B

Din a doua ecuatie se obtine:

B = 0*1C

Inlocuind in A se obtine:

A = 1*00*1C = 1*0+1C

Inlocuind in a treia ecuatie se obtine :

C = 0+1C + 1+0+1C + ?
C = (? + 1+)0+1C + ? = 1*0+1C
C = (1*0+1)*

Rezulta:

A = 1*0+1 (1*0+1)*
A = (1*0+1)+

Multimea regulata descrie sirurile de 0 si 1 care se termina cu subsirul 01. Evident o expresie mai simpla pentru descrierea aceluiasi limbaj este:

(0 | 1)*01

Se observa ca se poate considera ca limbajul se obtine prin concatenarea a doua limbaje unul descris de expresia (0 | 1)* si celalalt descris de expresia 01. Rezulta urmatoarea gramatica:

S --> AB
A --> 0A | 1A | ?
B --> 01

Se observa ca gramatica obtinuta nu este regulata. Sa transformam aceasta gramatica prin substitutie de inceputuri:

S --> 0AB | 1AB | B
A --> 0A | 1A | ?
B --> 01

Se obtine:

S --> 0S | 1S |01

Utilizind factorizarea:

S --> 0X | 1S
X --> S | 1

Din nou prin inlocuire de capete se obtine:

X --> 0X | 1S |1

Aplicind factorizarea:

X --> 0X | 1Y
Y --> S | ?

Rezulta gramatica descrisa de productiile:

S --> 0X | 1S
X --> 0X | 1Y
Y --> 0X | 1S | ?.

Se observa ca s-a ajuns la aceasi gramatica cu cea initiala (prin redenumirea neterminalelor).
Rezulta deci ca expresiile regulate reprezinta o metoda alternativa de tip generare pentru definirea limbajelor regulate.
Limbajele definite de gramatici regulate sint utilizate la nivelul analizei lexicale, in majoritatea limbajelor de programare modul de scriere al numelor si al identificatorilor pot sa fie descrise de gramatici respectiv de expresii regulate.
Construirea expresiilor regulate corespunzatoare atomilor lexicali reprezinta prima etapa in proiectarea unui analizor lexical.

1.3. Acceptoare

Un acceptor este un dispozitiv format dintr-o banda de intrare, o unitate de control si o memorie auxiliara.
+-------------- |a0|a1|...|an|
+-------------- \ cap de citire
\
+---------+
| unitate |
| de |
| control |
+---------+
|
+-----------+
| memorie |
| auxiliara |
+-----------+

Banda de intrare este formata din elemente in care se inscriu simbolii din sirul de intrare. La un moment dat capul de citire este fixat pe un simbol. Functionarea dispozitivului este data de miscarile acestuia. Capul de citire se poate deplasa la stinga sau la dreapta in cadrul unei astfel de miscari sau poate sa ramina nemiscat. De asemenea in cadrul executiei unei miscari unitatea de control are acces la informatia din memoria auxiliara pe care o poate modifica. Se observa ca acest model este foarte general. Exprimind diferite restrictii asupra benzii de intrare, organizarii si accesului la memoria auxiliara se obtin diferite cazuri particulare de acceptoare.
O miscare a acceptorului este formata din :

- deplasarea capului de citire la stinga sau la dreapta sau mentinerea capului de citire pe aceeasi pozitie si / sau;
- memorarea unei informatii in memoria auxiliara si / sau;
- modificarea starii unitatii de control.

Comportarea unui acceptor poate sa fie descrisa in functie de configuratiile acestuia. O configuratie este formata din urmatoarele informatii :

- starea unitatii de control;
- continutul benzii de intrare si pozitia capului de citire;
- continutul memoriei.

Rezulta ca o miscare a acceptorului poate sa fie precizata prin configuratia initiala (inainte de miscare) si cea finala (dupa executia miscarii).
Daca pentru o configuratie data sint posibile mai multe miscari atunci spunem ca acceptorul este nedeterminist altfel este determinist.
In general un astfel de acceptor are o configuratie initiala in care unitatea de control este intr-o stare initiala, capul de citire este fixat pe simbolul cel mai din stinga iar memoria are un continut initial specific. De asemenea acceptorul are o configuratie finala pentru care capul de citire este situat pe simbolul cel mai din dreapta de pe banda de intrare. Se spune ca dispozitivul a acceptat un sir de intrare w daca pornind din configuratia initiala ajunge in configuratia finala. Eventual, notiunea de acceptare poate sa fie conditionata si de ajungerea intr-o anumita stare sau de un anumit continut al memoriei auxiliare. Evident daca acceptorul este nedeterminist dintr-o configuratie initiala pot avea loc mai multe evolutii. Daca exista intre acestea una pentru care se ajunge la o configuratie finala atunci se spune ca dispozitivul a acceptat sirul.
Limbajul definit de catre un acceptor este format din multimea sirurilor acceptate de catre acesta.
Pentru fiecare tip de gramatica din ierarhia Chomsky exista o clasa de acceptoare care definesc aceasi clasa restrictiva de limbaje. Dintre acestea cele mai cunoscute sint automatele finite care sint acceptoare pentru limbaje regulate si automatele cu stiva (push-down), care sint acceptoare pentru limbajele independente de context. Automatele finite sint acceptoare fara memorie auxiliara iar automatele cu stiva sint acceptoare pentru care accesul la memoria auxiliara se face conform unui mecanism de tip stiva.

1.3.1. Automate finite

Un automat finit este un obiect matematic AF = (S, T, m, s0,
F) unde :

- S este multimea finita a starilor;
- T este o multime finita numita alfabet de intrare;
- m : S x (T U A?S) -> P(S) este functia partiala a starii urmatoare;
- s0 E S este o stare numita stare de start;
- F C_ S este o multime de stari numita multimea starilor finale (de acceptare).

Daca pentru s E S, a E T m(s,a) este definita, atunci (s,a) se numeste tranzitie, daca a = ? atunci (s,a) se numeste ? tranzitie. Se observa ca pentru o combinatie stare(s E S), intrare(i E I) pot sa corespunda mai multe stari urmatoare, deci asa cum a fost definit, automatul este nedeterminist.
In definirea unui automat finit se pot utiliza doua moduri de reprezentare, printr-o tabela de tranzitie sau printr-un graf.
Sa consideram de exemplu automatul care accepta limbajul definit de expresia (a | b)* abb. Poate sa fie descris sub forma urmatoarei tabele :

+---------------------+
| simbol de intrare | stare | a b |
------------+---------------------|
0 | A0,1S | A0S |
------------+----------+----------| F = A3S
1 | - | A2S |
------------+----------+----------|
2 | - | A3S |
----------------------------------+

Se observa ca in fiecare intrare este specificata multimea staril