UNIVERSITATEA ALEXANDRU IOAN CUZA FACULTATEA DE INFORMATIC

DEPARTAMENTUL DE NVMNT LA DISTAN

Gheorghe Grigora

PROIECTAREA COMPILATOARELOR

2006 2007

EDITURA UNIVERSITII ALEXANDRU IOAN CUZA IAI

Adresa autorului: Universitatea Alexandru Ioan Cuza Iai Facultatea de Informatic str. Berthelot 16 700483, Iai grigoras@infoiasi.ro, http://www.infoiasi.ro/~grigoras

Prefa i

Cuprins

1. LIMBAJE..................................................................................................................2

1.1 Limbaje de programare................................................................................................................ 3 1.1.1 Descrierea sintaxei i semanticii unui limbaj ....................................................................................................3 1.1.2 Implementarea limbajelor....................................................................................................................................7 1.1.3 Analiza lexical i analiza sintactic....................................................................................................................9

1.2 Limbaje formale .......................................................................................................................... 11 1.2.1 Expresii regulate..................................................................................................................................................11 1.2.2 Automate finite....................................................................................................................................................13 1.2.3 Gramatici independente de context.................................................................................................................17 1.2.4 Arbori sintactici. Ambiguitate...........................................................................................................................18

2 ANALIZA LEXICAL...........................................................................................23

2.1 Un algoritm de trecere de la o expresie regulat la automatul echivalent.................................. 24

2.2 De la un automat cu -tranziii la automatul determinist echivalent ......................................... 27

2.3 Proiectarea unui analizor lexical ................................................................................................ 28

2.4 Generatorul Lex.......................................................................................................................... 32

3 ANALIZA SINTACTIC DESCENDENT .......................................................35

3.1 Rolul analizorului sintactic ........................................................................................................ 36

3.2 Problema recunoaterii. Problema parsrii ................................................................................ 36

3.3 Analiza sintactic descendent .................................................................................................. 37 3.3.1 Parser descendent general..................................................................................................................................38 3.3.2 Gramatici LL(k)...................................................................................................................................................40 3.3.3 O caracterizare a gramaticilor LL(1)................................................................................................................41 3.3.4 Determinarea mulimilor FIRST i FOLLOW..............................................................................................42 3.3.5 Tabela de analiz sintactic LL(1) ...................................................................................................................45 3.3.6 Analizorul sintactic LL(1) ..................................................................................................................................45 3.3.7 Eliminarea recursiei stngi.................................................................................................................................47

4 ANALIZA SINTACTIC N GRAMATICI LR ................................................... 51

4.1 Gramatici LR(k) ..........................................................................................................................51

4.2 O caracterizare a gramaticilor LR(0).......................................................................................... 52

4.3 Algoritm de analiz sintactic LR(0).......................................................................................... 60

4.4 Gramatici i analizoare SLR(1)................................................................................................... 65

4.5 O caracterizare a gramaticilor LR(1)...........................................................................................71

4.6 Analiz sintactic LR(1) i LALR(1) .......................................................................................... 73

5 GENERATOARE DE ANALIZOARE SINTACTICE........................................79

Prefa ii 5.1 Utilizarea generatorului de parsere YACC ................................................................................. 82

5.2 Aplicaii cu LEX i YACC .......................................................................................................... 86

6 ANALIZA SEMANTIC .......................................................................................91

6.1 Gramatici cu atribute.................................................................................................................. 91 6.1.1 Numere raionale n baza 2 (Knuth) ............................................................................................................... 91 6.1.2 Declararea variabilelor ntr-un program ......................................................................................................... 93 6.1.3 Definiia gramaticilor cu atribute ..................................................................................................................... 96

6.2 Grafuri ataate unei gramatici cu atribute .................................................................................. 98 6.2.1 Graful DGp.......................................................................................................................................................... 98 6.2.2 Graful BGp........................................................................................................................................................... 99 6.2.3 Graful DGt .......................................................................................................................................................... 99

6.3 Metode de evaluare a atributelor ............................................................................................... 101 6.3.1 Evaluatorul rezultat din definiia gramaticii ................................................................................................. 101

6.4 Traducere bazat pe sintax ......................................................................................................102 6.4.1 Reprezentri intermediare ............................................................................................................................... 103 6.4.2 Traducerea codului n notaie postfix ........................................................................................................... 105 6.4.3 Traducerea codului n arbore sintactic.......................................................................................................... 106 6.4.4 Traducerea codului n secvene de quadruple.............................................................................................. 107

6.5 Proiectarea unui interpreter cu flex i yacc................................................................................113

BIBLIOGRAFIE .......................................................................................................... 121

1. Limbaje Acest capitol trece n revist chestiuni legate de limbajele de programare de nivel nalt, precum i elemente de limbaje formale necesare abordrii problemelor de analiz structural n cadrul compilatoarelor . Este tiut faptul c exist i sunt folosite un numr impresionant de limbaje de programare. Vom examina caracteristicile ctorva din aceste limbaje, lucru util pentru compararea lor i, prin urmare, pentru alegerea limbajului potrivit pentru o aplicaie anume. De asemenea, caracteristicile limbajelor de programare sunt importante pentru proiectarea i implementarea compilatoarelor. Limbajul este instrumentul principal al comunicrii. Gradul de succes sau de eec al comunicrii este influenat de caracteristicile limbajului folosit. Comunicarea ntre subieci de o anume specialitate se poate face prin intermediul unui limbaj ce incorporeaz o terminologie special care face ca multe pri ale comunicrii s fie neinteligibile pentru un neiniiat. Tot aa, comunicarea cu computerul presupune utilizarea unui vocabular i a unei gramatici specializate n care regulile chiar dac sunt mai uor de specificat dect pentru limbajele naturale trebuiesc cunoscute de ambele pri. Oamenii comunic cu computerul prin limbaje specializate; exist numeroase astfel de limbaje i se proiecteaz mereu altele noi. Aceste limbaje sunt numite, unele, limbaje de programare, altele limbaje de comand sau limbaje de interogare a bazelor de date etc.

Limbaje formale 3

1.1 Limbaje de programare Limbajele de programare sunt instrumente folosite pentru a construi descrieri formale ale algoritmilor. Un limbaj de programare trebuie s conin, pe lng operaiile de baz ce transform o stare iniial dat ntr-o stare final, i modul n care paii ce conin aceste operaii sunt nlnuii pentru a rezolva o anume problem. Pentru a rspunde la aceste cerine, un limbaj de programare trebuie s conin trei componente:

tipuri de date, obiecte i valori mpreun cu operaiile ce se pot aplica acestora; reguli pentru stabilirea relaiilor cronologice ntre operaiile specificate; reguli ce stabilesc structura (static) a unui program.

Aceste componente constituie nivelul de abstracie la care putem reprezenta algoritmi n limbajul respectiv. n raport cu acest nivel de abstracie, limbajele de programare se pot clasifica simplificnd destul de mult lucrurile - n dou grupe mari: limbaje de nivel sczut i limbaje de nivel nalt. Limbajele de nivel sczut sunt mai apropiate de limbajele main: exist o coresponden destul de puternic ntre operaiile implementate de limbaj i operaiile implementate de hardware-ul corespunztor. Limbajele de nivel nalt, pe de alt parte, sunt mai apropiate de limbajele folosite de oameni pentru a exprima probleme i algoritmi. Fiecare propoziie ntr-un limbaj de nivel nalt poate s fie echivalent cu o succesiune de operaii (mai multe propoziii) dintr-un limbaj de nivel sczut. n realitate, exist o mulime de limbaje ntre cele dou clase, de nivel sczut i de nivel nalt, i nu se poate face o mprire strict a limbajelor doar n dou clase. Abstractizrile ntr-un limbaj de programare permit programatorului s extrag proprietile eseniale necesare pentru soluia problemei de rezolvat, ascunznd detaliile de implementare a soluiei. Cu ct nivelul de abstractizare este mai nalt, programatorul se gndete mai puin la maina (hardware-ul) pe care va fi implementat soluia problemei. Cu alte cuvinte, ideile de programare pot fi separate n ntregime de arhitectura sistemului pe care va fi executat programul. De pild, n limbajele de programare de nivel nalt, programatorul lucreaz cu nume de variabile simbolice i nu cu adrese numerice de memorie. Abstraciile de date permit ca locaiile de memorie s fie privite drept celule de memorare pentru tipuri de date de nivel nalt; programatorul nu trebuie s-i pun problema reprezentrii acestora. Abstraciile de control permit programatorului s exprime algoritmii cu ajutorul structurilor de tipul if, while sau al procedurilor. Cum sunt implementate acestea n maina respectiv, este un lucru care nu-l intereseaz, n general, pe programator. Un program scris ntr-un limbaj de nivel nalt este tradus n cod main echivalent, cu ajutorul unui program special numit compilator. n aceast carte vom prezenta unele din tehnicile cunoscute pentru proiectarea unui compilator.

1.1.1 Descrierea sintaxei i semanticii unui limbaj Limbajele, formal vorbind, sunt mulimi de iruri de caractere dintr-un alfabet fixat. Acest lucru este valabil att pentru limbajele naturale, ct i pentru cele artificiale. irurile de caractere ale limbajului se numesc propoziii (sentences) sau instruciuni, afirmaii (statements). Orice limbaj are un numr de reguli sintactice care stabilesc care din irurile de caractere ce se pot forma cu simboluri din alfabet fac parte din limbaj. Dac pentru limbajele naturale regulile sintactice sunt n general complicate, limbajele de programare sunt relativ simple din punct de vedere sintactic. Exist n fiecare limbaj de programare unitile sintactice de nivelul cel mai mic numite lexeme care nu sunt cuprinse n descrierea formal a sintaxei limbajului. Aceste uniti sunt cuprinse ntr-o specificare lexical a limbajului care precede descrierea sintaxei. Lexemele unui limbaj de programare cuprind identificatorii, literalii, operatorii, cuvintele rezervate, semnele de punctuaie. Un program poate fi privit ca un ir de lexeme i nu un ir de caractere;

Prefa 4obinerea irului de lexeme din irul de caractere (programul obiect) este sarcina analizorului lexical. Un token al unui limbaj este o categorie de lexeme. De exemplu, un identificator este un token care are ca instane lexeme ca: suma, total, i, par5, etc. Tokenul PLUS pentru operatorul aritmetic + are o singur instan. Instruciunea:

delta = b2 - ac este compus din lexemii i tokenurile specificate n tabela urmtoare:

Lexem Token delta IDENTIFICATOR = ASIGNARE b2 IDENTIFICATOR - MINUS ac IDENTIFICATOR

Un limbaj de programare poate fi descris, formal, prin aazisele mecanisme de generare a irurilor din limbaj. Aceste mecanisme se numesc gramatici i au fost descrise de Chomsky n anii 1956 1959. Nu mult dup ce Chomsky a descoperit cele patru clase de limbaje formale, grupul ACM GAMM a proiectat limbajul Algol 58 iar la o conferin internaional John Backus a prezentat din partea grupului acest limbaj folosind o metod formal nou de descriere a sintaxei. Aceast nou notaie a fost modificat de Peter Naur la descrierea limbajului Algol 60. Metoda de descriere a sintaxei limbajelor de programare aa cum a fost folosit de Naur poart numele de forma Backus - Naur sau simplu BNF. De remarcat faptul c BNF este aproape identic cu mecanismul generativ al lui Chomsky gramatica independent de context. BNF este un metalimbaj. Acesta folosete abstraciile pentru a descrie structurile sintactice. O abstracie este scris ntre paranteze unghiulare, ca de exemplu: , , , , etc. Definiia unei abstracii este dat printr-o regul sau producie care este format din:

partea stng a regulii ce conine abstracia care se definete. o sgeat (sau caracterele ::= ) care desparte partea stng a regulii de partea

dreapt. partea dreapt a regulii care este un ir format din abstracii, tokenuri, lexeme.

De exemplu, regula: = definete sintaxa unei asignri: abstracia este o instan a abstraciei urmat de lexemul = urmat de o instan a abstraciei . O propoziie care are structura sintactic descris de aceast regul este: total = suma1 + suma2 ntr-o regul BNF abstraciile se numesc simboluri neterminale sau simplu neterminali, lexemii i token-urile se numesc simboluri terminale sau simplu terminali. O descriere BNF sau o gramatic (independent de context) este o colecie de reguli. Dac se ntmpl ca un neterminal s aib mai multe definiii acestea se pot insera ntr-o singur regul n care partea dreapt conine prile drepte ale definiiilor sale desprite prin simbolul |. De exemplu, definiiile: if then if then else se scriu: if then | if then else Iat un exemplu de gramatic (BNF) ce descrie un minilimbaj de programare: begin end

Limbaje formale 5 | ; = LITERA + | - | | NUMAR Aici apar dou tokenuri: LITERA i NUMAR. Acestea pot la rndul lor s fie descrise prin acelai mecanism: LITERA a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z NUMAR | NUMAR 0|1|2|3|4|5|6|7|8|9 Se observ c de data aceasta gramatica este de tip 3 (sau gramatic regulat) ceea ce nseamn c tokenurile se pot descrie folosind expresiile regulate iar recunoaterea lor (analiza lexical) se poate face cu automate finite deterministe. BNF a fost extins n diverse moduri mai ales din raiuni de implementare a unui generator de analizor sintactic. Orice extensie a BNF este numit EBNF (Extended BNF). Extensiile BNF nu mresc puterea descriptiv a mecanismului ci reprezint faciliti privind citirea sau scrierea unitilor sintactice. Extensiile ce apar frecvent sunt:

includerea, n partea dreapt a unei reguli, a unei pri opionale ce se scrie ntre paranteze drepte. De exemplu, instruciunea if ar putea fi descris astfel:

if then [else ] includerea n partea dreapt a unei reguli a unei pri ce se repet de zero sau

mai multe ori. Aceast parte se scrie ntre acolade i poate fi folosit pentru a descrie recursia: {; }

includerea n partea dreapt a unei reguli a opiunii de a alege o variant dintr-un grup. Acest lucru se face punnd variante n paranteze rotunde, desprite prin |. De exemplu, o instruciune for se poate defini astfel:

for = (to | downto) do Trebuie precizat c parantezele de orice fel din descrierea EBNF fac parte din metalimbaj, ele nu sunt terminali ci doar instrumente de a nota o anume convenie. n cazul n care unele din aceste simboluri sunt simboluri terminale n limbajul descris, acestea vor fi puse ntre apostrof : [ sau { etc. EBNF nu face altceva dect s simplifice ntr-un anume fel definiiile sintactice. Spre exemplificare iat cum se descrie expresia aritmetic folosind cele dou mecanisme: BNF: + | - | * | / | ( ) | EBNF: {(+| -) } {(* | /) } ( )|

Prefa 6Un exemplu de program n minilimbajul de programare descris mai sus este urmtorul:

begin a = b + c ; d = 5 - a end

O derivare a acestui program n gramatica dat este: begin end begin ; end begin ; end begin =; end begin LITERA=; end

begin LITERA=+; end begin LITERA=LITERA+; end

begin LITERA=LITERA+LITERA; end begin LITERA=LITERA+LITERA; =end begin LITERA=LITERA+LITERA;LITERA=end begin LITERA=LITERA+LITERA;LITERA=- end begin LITERA=LITERA+LITERA;LITERA=NUMAR- end begin LITERA=LITERA+LITERA;LITERA=NUMAR-LITERA end Arborele de derivare pentru acest program este dat n figura 1.1. Se observ o strns legtur ntre derivrile dintr-o gramatic i arborii de parsare.

Figura 1.1

Exist reguli ale limbajelor de programare care nu pot fi descrise utiliznd BNF. De pild faptul c o variabil nu poate fi utilizat nainte de a fi declarat este o caracteristic ce nu poate fi descris prin BNF. Reguli de acest fel fac parte din semantica static a limbajului: reguli ce in indirect de nelesul unui program relativ la execuie. Semantica static este denumit aa pentru c poate fi verificat nainte de execuie, la momentul compilrii. Un mecanism care descrie semantica static a fost introdus de Knuth n 1968 i este denumit gramatic cu atribute. O gramatic cu atribute este o gramatic independent de context, care descrie sintaxa, la care s-au adugat urmtoarele:

begin end

;

=

= LITERA -

LITERA +

LITERA LITERA

NUMAR LITERA

Limbaje formale 7 fiecrui simbol al gramaticii i se ataeaz o mulime de atribute, unele dintre ele

sunt sintetizate (valorile lor depind de valorile atributelor descendenilor), altele motenite (valorile lor depind de valorile atributelor prinilor i frailor);

fiecrei reguli din gramatic i se asociaz o mulime de funcii semantice care determin valorile atributelor sintetizate ale prii stngi i valorile atributelor motenite ale simbolurilor din partea dreapt.

Un arbore de derivare ntr-o gramatic cu atribute este arborele de derivare din gramatica ce descrie sintaxa mpreun cu mulimea valorilor atributelor ataate fiecrui nod al arborelui. Pentru a evita circularitatea n obinerea valorilor atributelor, deseori se pune restricia ca un atribut motenit s depind doar de valorile atributelor prii stngi a regulii i de atributele simbolurilor din stnga sa n irul din partea dreapt a regulii. Aceast restricie permite proiectarea unui evaluator care parcurge arborele de derivare n preordine. Nodurile frunze din arborele de derivare au atribute sintetizate ale cror valori se determin n afara arborelui de derivare; acestea se numesc atribute intrinseci. Spre exemplu, tipul unei instane a unei variabile ntr-un program se obine din tabela simbolurilor care este construit la analiza lexical i conine numele variabilelor, tipul lor etc.. n capitolul Analiza semantic vor fi date exemple de gramatici cu atribute i modul de evaluare a atributelor. Descrierea nelesului unui program nseamn semantica dinamic. Este vorba despre nelesul expresiilor, a instruciunilor, a unitilor de program. Dac pentru descrierea sintaxei formalismul BNF este universal acceptat, nu exist nc o notaie universal acceptat pentru semantic (n continuare semantica dinamic o s fie numit semantic). i aceasta n condiiile n care fiecare programator trebuie s cunoasc atunci cnd folosete un limbaj, ce transformri face fiecare din instruciunile sale i cum sunt obinute aceste transformri. De obicei ei nva semantica citind text n limbaj natural care descrie fiecare instruciune. Or se tie c, din multe motive, aceste explicaii sunt imprecise i / sau incomplete. Pe de alt parte, cei care implementeaz limbajele deseori folosesc explicaiile n limbaj natural atunci cnd proiecteaz compilatoarele. Utilizarea semanticii n limbaj natural att de ctre programatori, ct i de ctre implementatori se poate explica prin aceea c mecanismele formale de descriere a semanticii sunt n general complexe i greu de utilizat practic. De aceea domeniul acesta este nc n atenia multor cercettori.

1.1.2 Implementarea limbajelor Dou din componentele primare ale unui computer sunt memoria intern i procesorul. Memoria intern este folosit pentru pstrarea programelor i a datelor. Procesorul este o colecie de circuite care implementeaz operaii sau instruciuni main. n absena altor componente software un computer nelege doar propriul limbaj main. Pentru a fi folosit, computerul are nevoie de un sistem de operare - care reprezint interfaa pentru alte sisteme software - i de un numr de limbaje de programare care s faciliteze rezolvarea de probleme diverse. Limbajele de programare pot fi implementate prin trei metode generale: compilare, interpretare i sisteme de implementare hibride. Un compilator este un sistem software care traduce programele scrise ntr-un limbaj de programare (programe surs) n programe scrise n limbaj main (programe obiect) ce pot fi executate direct de ctre computer. Avantajul acestei metode de implementare este acela c execuia programelor este foarte rapid. Procesul de compilare, n cele mai multe cazuri, se desfoar dup schema din figura 1.2. Analizorul lexical identific n textul surs unitile lexicale (tokenurile) i transform acest text ntr-un ir de uniti lexicale,

Prefa 8ignornd spaiile albe i comentariile. Uniti lexicale ntr-un limbaj de programare sunt identificatorii, operatorii, cuvintele rezervate, semnele speciale. Analizorul sintactic preia irul de uniti lexicale de la analizorul lexical i construiete arborele de derivare (de parsare) al acestui ir n gramatica ce descrie sintaxa limbajului de programare. De fapt, de cele mai multe ori, se obine o reprezentare a acestui arbore de derivare, un set de informaii din care poate fi construit acest arbore. Tabela de simboluri, construit de cele dou analizoare amintite mai sus, cuprinde informaii privind numele, tipul, atributele tuturor identificatorilor definii de utilizator n program. Aceste informaii sunt necesare analizorului semantic i generatorului de cod. Analizorul semantic este de regul un generator de cod intermediar care are rolul de a verifica erorile ce nu pot fi detectate de analizorul sintactic (de exemplu cele referitoare la tipul variabilelor) i de a obine din arborele de derivare un program echivalent cu cel iniial, dar ntr-un limbaj intermediar ntre limbajul surs i limbajul main. O parte opional a procesului de compilare este optimizarea. Aceasta are rolul de a mbunti programul obinut, n ceea ce privete mrimea sa, prin eliminarea unor instruciuni sau n ceea ce privete viteza de calcul. Optimizarea, atunci cnd se face, este mai uor de aplicat codului intermediar dect codului main.

Figura 1.2

Cod main Date de intrare

Cod intermediar

Arbore de derivare

Uniti lexicale

Program surs

Analizor lexical

Analizor sintactic

Analizor semantic

Tabela de simboluri

Generator de cod

Computer

Rezultate

Limbaje formale 9Generatorul de cod traduce codul intermediar (optimizat) ntr-un program echivalent scris n cod main. Acest program cod main are nevoie, de cele mai multe ori, pentru a fi executat, de module program oferite de sistemul de operare (cum ar fi programe de introducere sau extragere a datelor n/din memorie). Procesul de colectare a programelor sistem necesare execuiei programului utilizator compilat i de legare a lor la acesta se face de ctre un program special numit linker. O tehnic destul de folosit n implementarea limbajelor de programare este interpretarea sau interpretarea pur cum mai este cunoscut n literatura de specialitate. Programele scrise n limbajul surs sunt interpretate de ctre un alt program, numit interpreter, care acioneaz ca un simulator software al unei maini ce execut instruciune cu instruciune programul scris n limbajul surs fr ca acesta s fie tradus n limbaj main. Simulatorul software ofer o main virtual pentru limbajul surs n cauz. Avantajul interpretrii este acela c permite implementarea uoar a operaiilor de depanare a programelor, pentru c erorile de execuie se refer la uniti ale limbajului surs i nu in de limbajul main. Din pcate, dezavantajele sunt mai numeroase: timpul de execuie este serios diminuat n cazul interpretrii fa de compilare (un program interpretat se execut de 10 pan la 100 ori mai lent dect unul compilat); spaiul folosit de un program interpretat este mai mare; n cazul interpretrii, semantica unei construcii trebuie determinat din programul surs la momentul execuiei. Aceste dezavantaje fac ca doar limbajele cu structuri simple s fie implementate prin interpretare (comenzi sistem n UNIX, APL, LISP). Exist i excepii: cu toate c nu este un limbaj simplu, JavaScript este interpretat. Sistemele de implementare hibrid folosesc att compilarea, ct i interpretarea pentru implementarea limbajelor. Aceast tehnic se rezum la obinerea unui cod intermediar pentru programul scris n limbaj de nivel nalt (compilare) i apoi interpretarea acestui cod intermediar. Desigur, se alege limbajul intermediar aa fel ca el s poat fi uor interpretat. Avantajul implementrilor hibride rezult din aceea c obinerea codului intermediar se poate face automat iar execuia este mai rapid dect n cazul interpretrii pure. Ca exemple de implementri hibride consemnm limbajul Perl i implementrile de nceput ale limbajului Java care este tradus n cod intermediar numit byte code i poate fi portat pe orice main care dispune de un interpreter de byte code asociat cu un sistem de execuie, n fapt ceea ce se numete main virtuala Java.

1.1.3 Analiza lexical i analiza sintactic Sintaxa unui limbaj de programare se descrie folosind formalismul gramaticilor independente de context sau aa zisa BNF Backus Naur Form. Utilizarea BNF n descrierea sintaxei este avantajoas pentru c este un formalism clar i concis i poate fi uor transcris n sistemele software care implementeaz limbajul respectiv. n aproape toate compilatoarele, verificarea corectitudinii sintactice se face n dou etape distincte: analiza lexical i analiza sintactic. Analiza lexical se ocup de construciile simple ale limbajului precum: identificatori, literali numerici, operatori, cuvinte rezervate, semne speciale. Analiza sintactic se ocup de construciile evoluate din limbaj precum expresiile, instruciunile, unitile de program. Tehnicile pentru analiza lexical sunt mult mai puin complexe fa de cele ale analizei sintactice. Asta face ca implementarea separat a analizei lexicale s duc la obinerea unor module relativ mici i uor de ntreinut pentru fiecare din cele dou faze. n esen un analizor lexical este un program pentru recunoaterea subirurilor de caractere dint-un ir dat, subiruri ce se potrivesc cu un anume ablon (problema este cunoscut sub numele de pattern matching i se ntlnete frecvent n editoarele de text). Analizorul lexical citete textul surs i colecteaz caracterele n grupri logice care se numesc lexeme. Acestor grupri logice li se asociaz coduri interne care se numesc tokenuri. De pild, textul urmtor:

Prefa 10alpha = beta + 734;

n urma analizei lexicale se prezint astfel: Lexem Token

alpha IDENT = ASIGN

beta IDENT + PLUS 734 INT_LIT ; PV

IDENT, ASIGN etc. sunt nite nume pentru nite coduri numerice care vor fi returnate de ctre analizor atunci cnd grupul de caractere citit ndeplinete condiia de a fi identificator, operator de asignare etc. Pentru c spaiile albe i comentariile nu sunt relevante pentru execuia unui program, acestea sunt ignorate de ctre analizorul lexical. Rolul analizorului lexical, n contextul compilrii unui program, este de a citi textul surs i de a oferi analizorului sintactic tokenurile. Partea de analiz a textului surs care se refer la unitile sintactice precum expresii, instruciuni, blocuri etc. poart numele de analiz sintactic sau parsare. Rolul unui analizor sintactic este dublu. n primul rnd, este acela de a verifica dac programul este corect sintactic. Dac se ntlnete o eroare atunci analizorul produce un diagnostic i analizeaz mai departe textul astfel nct s fie semnalate ct mai multe din erorile de sintax existente n text. Al doilea rol este acela de a construi arborele de derivare al programului respectiv n gramatica ce descrie limbajul. De fapt, sunt obinute informaiile din care se poate construi arborele de derivare: derivarea extrem stng sau derivarea extrem dreapt corespunztoare, care nsemna moduri de traversare a arborilor de derivare. Sunt cunoscute dou tipuri de parsere, n funcie de direcia n care este construit arborele de derivare: parsere top down (descendente) care construiesc arborele de la rdcin ctre frunze i parsere bottom up (ascendente) care construiesc arborele de la frunze ctre rdcin. Un parser top down traseaz derivarea extrem stng a cuvntului de analizat. Arborele de derivare este construit n preordine: se ncepe cu rdcina i apoi fiecare nod este vizitat nainte ca descendenii si s fie generai. Acetia sunt vizitai n ordinea de la stnga la dreapta. n termenii derivrii, acest lucru se poate sintetiza astfel: dat o form propoziional (un cuvnt dintr-o derivare extrem stnga), sarcina parserului este de a determina urmtoarea form propoziional n derivare. Dac forma propoziional curent este uA unde u este un cuvnt format din terminali (tokenuri), A este neterminal iar este un cuvnt format din terminali i neterminali, atunci sarcina parserului este de a nlocui pe A cu partea dreapt a unei reguli ce are pe A n partea stng. Dac regulile corespunztoare lui A au n partea dreapt respectiv 1, 2,..., n i se alege k, atunci noua form propoziional este uk. n general, alegerea corect a variantei de rescriere a lui A se face prin analiza simbolului urmtor lui u n cuvntul de analizat uv. Dac acest lucru este posibil, atunci gramatica se numete gramatic LL(1) i metoda de parsare se numete parsare LL(1). Implementarea se face fie prin transformarea fiecrei reguli din gramatic (forma BNF) ntr-un numr de linii de cod (parsare recursiv descendent) fie prin utilizarea unei tabele de parsare pentru implementarea regulilor BNF. n capitolul al treilea vom trata pe larg parsarea LL(1). Un parser bottom-up construiete arborele de derivare pornind de la frunze i naintnd spre rdcin. Acesta produce reversul unei derivri extrem drepte a cuvntului de analizat. Parsarea bottom-up se poate descrie succint astfel: dat forma propoziional dreapta (un cuvnt din derivarea extrem dreapt) parserul trebuie s gseasc n partea dreapt a unei reguli, iar aceasta se reduce la partea stng i se obine forma propoziional precedent. Dac se gsete = u i este partea dreapt a regulii ce

Limbaje formale 11are n stnga A, atunci precedenta form propoziional este Au. Algoritmii de analiz bottom-up sunt cei bazai pe relaii de preceden sau, cei mai utilizai, cei din familia LR.

1.2 Limbaje formale n acest paragraf trecem n revist, succint, noiuni de limbaje formale necesare n abordarea analizei lexicale, sintactice i semantice n cadrul procesului de compilare. Un limbaj (formal) este o mulime de cuvinte peste un alfabet . Notm prin * limbajul total: mulimea tuturor cuvintelor peste . Dac L1 i L2 sunt limbaje, atunci la fel sunt i reuniunea lor, intersecia, complementara lui L1 fa de *. De asemenea, dac vom considera produsul uv a dou cuvinte u i v ca fiind un nou cuvnt ce se obine prin concatenarea celor dou, notm prin L1L2 produsul celor dou limbaje care nseamn mulimea cuvintelor uv unde u este din L1 iar v este din L2. Vom nota prin cuvntul nul, cel fr de litere. Atunci putem vorbi de puterea Ln a unui limbaj L folosind produsul i stabilind c L0 este limbajul ce conine doar . Considerm i iteraia unui limbaj L, notat L* ca fiind reuniunea limbajelor Ln pentru n = 0, 1, 2, .... Este cunoscut ierarhia lui Chomsky n care limbajele se clasific n limbaje regulate, limbaje independente de context, limbaje dependente de context i limbaje de tip 0. Limbajele regulate joac un rol important n analiza lexical. Unitile lexicale pot fi descrise cu ajutorul expresiilor regulate (algebric) sau al gramaticilor regulate (generativ) i pot fi recunoscute cu ajutorul automatelor finite. n esen, un analizor lexical este implementarea unui automat finit. Vom trece n revist pentru nceput chestiunile legate de expresii regulate automate finite, fr a intra n detalii. Apoi, vom aminti cte ceva despre gramatici independente de context, instrumentul generativ pentru descrierea sintaxei limbajelor de programare. Cititorul este ndemnat a parcurge lucrri precum [Juc99], [Gri86] pentru a afla amnunte, mai ales de ordin teoretic. Noi suntem interesai aici de utilizarea acestor modele de calcul pentru dezvoltarea de algoritmi de analiz structural a textelor surs nct, vom prezenta att ct este necesar pentru acest lucru.

1.2.1 Expresii regulate

Definiia 1.2.1 Fie un alfabet, simbolurile , , |, , *, (, ) care nu aparin lui i E un cuvnt peste alfabetul { , , |, , *, ),( }. O expresie regulat peste se definete inductiv astfel: 1. E este un atom regulat peste dac E este un simbol din { , } sau este de

forma (E1) unde E1 este o expresie regulat peste ; 2. E este un factor regulat peste dac E este un atom regulat peste sau este de forma

E1* unde E1 este un factor regulat peste ; 3. E este un termen regulat peste dac E este un factor regulat peste sau este de

forma E1E2 unde E1 este un termen regulat, iar E2 este un factor regulat peste ; 4. E este o expresie regulat peste dac E este un termen regulat peste sau este de

forma E1 | E2, unde E1 este o expresie regulat, iar E2 este un termen regulat peste .

Aici , sunt privite ca simple simboluri fr vreo semnificaie. Mai jos, interpretarea acestor expresii va fi desigur limbajul {} respectiv limbajul vid. n definiia de mai sus, pe lng noiunea de expresie regulat se dau cele de termen regulat, factor regulat, atom regulat care reflect precedena i asociativitatea operatorilor |, , *. n cele ce urmeaz vom omite scrierea operatorului aa cum se obinuiete la scrierea operatorului de nmulire.

Prefa 12Definiia 1.2.2 Limbajul L(E) descris (sau notat, sau denotat) de expresia regulat E peste alfabetul este definit inductiv astfel:

1. L( ) = , L() = {}, L(a) = {a}, pentru orice a din ; 2. L((E)) = L(E), pentru orice expresie regulat E peste ; 3. L(E*) = (L(E))*, pentru orice factor regulat E peste ; 4. L(E1E2) = L(E1)L(E2), pentru orice E1, termen regulat, i pentru orice E2 factor

regulat peste ; 5. L(E1 | E2) = L(E1) 4 L(E2), pentru orice E1 expresie regulat, i pentru orice E2

termen regulat peste . Proprietile 1 i 2 de mai sus asigur faptul c L(E1E2) i L(E1 | E2) sunt bine definite. Exemplul 1.2.1 Fie E1 = | (a | b)*(ab | baa) o expresie regulat. Atunci limbajul descris de E1 este: L(E1) = L( | (a | b)*(ab | baa) ) = L() 4 L( (a | b)*(ab | baa) ) = = {} 4 L( (a | b)*) L((ab | baa) ) = = {} 4 (L (a | b))* L(ab | baa ) = = {} 4 (L(a | b))* (L(ab) 4 L( baa) ) = = {} 4 (L(a) 4 L( b))* (L(a)L(b) 4 L(b)L(a)L(a) ) = = {} 4 ({a} 4 {b})*({a}{b} 4 {b}{a}{a}) = = {} 4 {a,b}*{ab, baa}. Analog pentru E2 = (a | b)(a | b) obinem L(E2) = {aa, ab, ba, bb} Este binecunoscut faptul c mulimea limbajelor descrise de expresiile regulate coincide cu mulimea limbajelor regulate [Juc99]. Asta nseamn c pentru fiecare expresie regulat E poate fi construit (efectiv) un automat finit care s recunoasc exact limbajul descris de expresia E. De asemenea, pentru orice automat finit, exist o expresie regulat (care poate fi obinut efectiv) ce descrie limbajul recunoscut de el. Cum suntem interesai n proiectarea unui analizor lexical, parte a unui compilator, vom descrie algoritmic n paragrafele urmtoare trecerea de la o expresie regulat la un automat finit; algoritmii difer substanial de cei utilizai n demonstraiile teoretice. Definiia 1.2.3 Dou expresii regulate E1, E2 peste alfabetul , sunt echivalente dac L(E1) = L(E2). Notm acest lucru prin E1 = E2. Exemplul 1.2.2 Se verific uor c au loc urmtoarele : a | b = b | a i | (a | b)* = (a | b)*. Lema 1.2.1 (Proprieti algebrice ale expresiilor regulate). Fie E, E1, E2, E3 expresii regulate peste alfabetul . Sunt adevrate urmtoarele:

1. E1 | E2 = E2 | E1 2. (E1 | E2) | E3 = E1 | (E2 | E3) 3. (E1E2)E3 = E1(E2E3) 4. E1(E2 | E3) = E1E2 | E1E3 5. (E1 | E2)E3 = E1E3 | E2E3 6. E = E, E = E, E = , E = 7. E* = (E | )*, * = 8. (E*)* = E* 9. (E1*E2*)* = (E1 | E2)*

Demonstraie Rezult din definiia anterioar i proprietile operaiilor cu mulimi.

Limbaje formale 13n procesul de descriere a limbajelor, un rol important l joac noiunea de ambiguitate. Dac D este o descriere a unui limbaj iar L(D) este limbajul descris de D, spunem c D este ambigu dac exist mcar un cuvnt din L(D) care este descris n dou moduri diferite. De exemplu expresia regulat E = ab | (a | b)* este ambigu deoarece cuvntul ab n L(E) are dou descrieri: una n expresia ab i alta n (a | b) *. Formal, neambiguitatea unei expresii regulate este definit inductiv astfel: Definiia 1.2.4 (Expresii regulate neambigue) 1. Expresiile regulate , , a i (E) sunt neambigue, pentru orice a din i oricare ar fi

expresia neambigu E peste ; 2. Pentru orice factor E peste , E* este neambigu dac E este neambigu i pentru

orice u L(E*) exist exact un numr n 0 i o secven unic (u1, u2,, un) de cuvinte din L(E) astfel nct u1u2un = u (pentru cazul n = 0, u1u2un = ) ;

3. Pentru orice termen E1 i pentru orice factor E2 peste , E1E2 este neambigu dac: a. L(E1E2) = , sau b. E1 i E2 sunt neambigue i pentru orice u L(E1E2) exist o pereche unic

(u1,u2) n L(E1) L(E2) astfel nct u1u2 = u. 4. Pentru orice expresie E1 i orice termen E2, expresia E1 | E2 este neambigu dac E1

i E2 sunt neambigue i n plus L(E1) 3 L(E2) = . 1.2.2 Automate finite

Definiia 1.2.5 Un automat finit este sistemul A = (Q, , , q0, F) unde Q i sunt mulimi finite, nevide, numite mulimea strilor respectiv alfabetul de intrare, q0 Q este starea iniial, F Q este mulimea strilor finale iar este o funcie : Q ({}) 2Q, numit funcia de tranziie (unde prin 2Q am notat mulimea prilor lui Q ). Observaia 1.2.1 Modelul definit mai sus este cel cunoscut n literatur i sub denumirea de sistem tranziional (sau automat nedeterminist cu - tranziii). Prin particularizri ale lui vom obine modelul de automat nedeterminist (fr - tranziii) i cel de automat determinist. Un automat finit poate fi reprezentat prin tabela de tranziie (funcia ) sau prin graful de tranziie. n reprezentarea grafului de tranziie facem convenia ca strile care nu sunt finale s le reprezentm prin cercuri iar cele finale prin ptrate. De asemenea - tranziiile sunt reprezentate prin arce neetichetate. Exemplul 1.2.3 Fie Q = {0, 1, 2}, = {a, b, c}, F = {2}, q0 = 0, iar este dat astfel:

Tabela de tranziie: Graful de tranziie:

a b c 0 {0} {1} 1 {1} {2} 2 {2}

Figura 1.3

Exemplul 1.2.4 Q = {0, 1, 2}, = {a, b}, F = {2}, q0 = 0, iar este:

a c b

0 1 2

Prefa 14Tabela de tranziie: Graful de tranziie:

a b 0 {0, 1} 1 {1} {2} 2 {2} {0, 1}

Figura 1.4

Exemplul 1.2.5 Q = {0, 1, 2, 3}, = {a, b}, F = {0}, q0 = 0, iar este dat n figura 1.5.

Tabela de tranziie: Graful de tranziie:

a b 0 1 3 1 0 2 2 3 1 3 2 0

Figura 1.5

Exemplul 1.2.6 Q = {0, 1, 2,}, = {a, b}, F = {2}, q0 = 0, iar este:

Tabela de tranziie: Graful de tranziie:

a b c 0 {0,1, 2} {1, 2} {2} 1 {1, 2} {2} 2 {2}

Figura 1.6

Definiia 1.2.6 Un automat A = (Q, , , q0, F) se numete:

aa

b

a

a

0 1

2

a, b

c

b,ca a, b, c

b

0 1

2

b

a

b b b

a

a

a

3

1

2

0

Limbaje formale 151. nedeterminist (fr -tranziii), dac (q, ) = , q Q 2. determinist, dac (q, ) = , q Q i |(q, a)| 1, q Q, a

n literatura de specialitate, de obicei, un automat finit determinist are proprietatea c |(q, a)| = 1, q Q, a . Condiia |(q, a)| 1, dat n definiia precedent, permite ca un automat determinist s fie parial definit (eventual) dar nu este restrictiv relativ la puterea de calcul: putem obine automatul total definit dac adugm la automat o stare special (numit stare moart sau stare de blocare) i definim astfel: (q, a) = , dac |(q,a)| < 1 i (, b) = , b . Aadar, putem subnelege, atunci cnd este nevoie, c este ndeplinit condiia |(q,a)| = 1 (de exemplu cnd un automat trebuie s ,,citeasc n ntregime orice cuvnt, chiar dac nu-l accept). Pentru definirea limbajului acceptat (recunoscut) de un automat finit, s extindem funcia de tranziie la cuvinte. Vom nota mai nti, pentru q Q : Cl(q) = {q |q Q, n graful automatului A exist un drum de la q la q

de lungime k 0 ale crui arce sunt etichetate cu }. Facem precizarea c q Cl(q) pentru c q este legat de q printr-un drum de lungime 0. Dac S Q, atunci notm: Cl(S) = 4qSCl(q) iar (S, a) = 4qS (q, a). Definiia 1.2.7 Dac A = (Q, , , q0, F) este un automat, atunci extensia lui la cuvinte este funcia : Q * 2Q care se definete astfel:

1. (q, ) = Cl(q), q Q ; 2. (q, ua) = Cl(( (q, u), a)), q Q, u *, a .

Lema 1.2.2 Fie A = (Q, , , q0, F) un automat finit, o stare q Q i un cuvnt w *, unde w = a1a2 an. Atunci q (q, w) dac i numai dac n graful automatului, exist un drum de la q la q de lungime m n cu arcele etichetate respectiv y1, y2, ,ym (n aceast ordine) astfel nct y1y2 ym = w. Demonstraie. 1. Se demonstreaz prin inducie dup lungimea lui w. 2. Se demonstreaz prin inducie dup lungimea drumului de la q la q.

Observaia 1.2.2 Pentru automatele fr -tranziie (n care (q, ) = , q Q), deoarece Cl(q) = {q} are loc (q, a) = (q, a), q Q, a . Din acest motiv, pentru astfel de automate va fi notat de asemenea cu . n cazul automatelor cu - tranziii vom pstra notaia pentru extensie pentru c, n general, (q, ) (q, ) i, de asemenea, (q, a) (q,a), a . De pild, n Exemplul 1.2.4 avem: (0, a) ={0, 1, 2} iar (0, a) = {0} i (0, ) = {0, 1, 2} iar (0, ) ={1}. Lema 1.2.3 Fie A = (Q, , , q0, F) un automat finit i cuvintele u, v *. Atunci are loc: (q, uv) = ( (q, u), v). Demonstraie. Inducie dup |v|.

Definiia 1.2.8 Limbajul acceptat (recunoscut) de automatul A = (Q, , , q0, F) este mulimea notat L(A) dat de expresia: L(A) = {w | w *, (q0, w) 3 F }.

Prefa 16Aadar, un cuvnt w este recunoscut de un automat A dac, dup citirea n ntregime a cuvntului w, automatul (pornind din starea iniial q0 ) poate s ajung ntr-o stare final. n cazul automatelor finite deterministe, putem scrie: L(A) = {w | w *, (q0, w) F}. deoarece (q0, w) este o mulime format dintr-un singur element i identificm aceast mulime cu elementul respectiv. Teorema 1.2.1 Pentru orice expresie regulat E peste exist un automat finit (cu - tranziii) A, astfel nct L(E) = L(A). Demonstraie Procedm prin inducie asupra complexitii expresiei E. Dac E {, , a} ( a ) atunci automatul corespunztor este respectiv:

Figura 1.7 Dac E = E1 | E2, E = E1E2 sau E = E1* atunci presupunem c exist automatele finite A1 = (Q1, , q01, 1, {f1}), A2 = (Q2, , q02, 2, {f2}), cu Q1, Q2 disjuncte i 1(f1, a) = 2(f2, a) = , a (ipoteza inductiv care are loc pentru E = , sau a ), care recunosc limbajele L(E1) respectiv L(E2). S considerm dou stri noi q0, f (ce nu sunt din Q1 4 Q2). Atunci, automatul A = (Q, , , q0, F) se construiete astfel:

1. E = E1 | E2 : Q = Q1 4 Q2 {q0, f }, F = {f }, (q0, ) = {q01, q02}, (f1, ) = (f2, ) = {f }, (q, a) = i(q, a) q Qi, a , i = 1, 2.

2. E = E1E2 : Q = Q1 4 Q2, q0 = q01, F = {f2 }, (f1, ) = q02, (q, a) = i(q, a) q Qi, a , i = 1,2.

3. E = E1* : Q = Q1 4 {q0, f }, (q0, ) = { q01, f }, (f1, ) = {q01, f }, (q, a) = 1(q, a) q Q1, a .

Schematic, acest lucru se exprim ca n figura 1.8. Se dovedete uor c automatele construite mai sus recunosc respectiv limbajele L(E1 4 E2 ), L(E1E2), L(E1*).

Clasa limbajelor recunoscute de automatele finite coincide cu clasa limbajelor descrise de expresii regulate i aceast clas este cunoscut sub numele de clasa limbajelor regulate (sau de tip 3). Aceast clas conine numai limbaje neambigue: un automat finit determinist este un mecanism neambiguu. De aici rezult c pentru orice expresie regulat E exist o expresie regulat E neambigu, echivalent cu E. Teoretic vorbind, trecerea de la o expresie ambigu E la echivalenta sa neambigu E se face astfel: se construiete A, automatul finit determinist echivalent cu E (trecnd prin automatul cu - tranziii i apoi prin cel nedeterminist fr - tranziii) pentru ca apoi s se determine expresia regulat E care descrie limbajul L(A); aceasta este neambigu. Practic ns, descrierile ambigue pot s fie mai concise i mai uor de neles dect echivalentele lor neambigue (care cost i timp substanial pentru a fi obinute).

a0 0 1 1 0 1

Limbaje formale 17

Figura 1.8 Exemplul 1.2.7 Limbajul L = {w {0,1}*|w conine 000 sau 111} este descris de expresia ambigu E = (0 | 1)*(000 | 111)(0 | 1)*. Expresia E neambigu, echivalent cu E, n afar de faptul c se obine greoi, nu mai exprim n mod evident forma cuvintelor din L(E). Cititorul se poate convinge de acest lucru printr-un exerciiu.

1.2.3 Gramatici independente de context Definiia 1.2.9 O gramatic independent de context este sistemul G = (V, T, S, P) unde V i T sunt mulimi nevide, finite, disjuncte de neterminali (variabile), respectiv terminali, = V T se numete vocabularul gramaticii, S V este o variabil special numit simbol de start sau axioma gramaticii, iar P V (V 4 T)* este mulimea regulilor de producie (derivare) sau simplu mulimea produciilor. Convenii de notaie. n scopul simplificrii expunerii, vom face cteva convenii care vor fi pstrate de-a lungul acestei lucrri, cu excepia situaiilor n care se fac precizri suplimentare.

1. Urmtoarele simboluri noteaz neterminali: S, folosit pentru a nota axioma gramaticii; A, B, C , (literele majuscule de la nceputul alfabetului); numele italice scrise cu minuscule: expresie, instruciune,...

2. Urmtoarele simboluri noteaz terminali: literele mici de la nceputul alfabetului: a, b, c,... operatori: +, -, *, /, etc. simboluri de punctuaie, paranteze. cifrele: 0, 1, , 9 numele scrise cu fontul courier (unitile lexicale): id, if, while,

begin, etc.. 3. Literele mari de la sfritul alfabetului, X, Y, Z,... noteaz simboluri gramaticale

(neterminali sau terminali, adic elementele din ); 4. Literele mici de la sfritul alfabetului, u, v, x, y, z, w noteaz cuvinte din T*

(formate din terminali);

q01 qfq0 f

q01 f1 q02 f2

q0

q01 f1

q02 f2

f

Prefa 185. Literele greceti , , , reprezint cuvinte peste . Aadar, o producie a

gramaticii se va nota prin A (n loc de (A, ) P, convenim s scriem A ).

6. Dac A 1, A 2,, A n sunt toate produciile care au A n partea stng (numite A-producii), le vom nota prin:

A 1 | 2 |,, |n 7. O gramatic va fi dat prin produciile sale. De aici se subneleg mulimile V i

T, iar simbolul de start este partea stng a primei producii. Exemplul 1.2.8 Gramatica:

E EOE |(E) |-E | id O + | - | * | /

este constituit din elementele V = {E, O }, T = { id, +, -, *, /, (,) }, E este simbolul de start, iar produciile sunt cele indicate mai sus. Definiia 1.2.10 Fie G = (V, T, S, P) o gramatic independent de context. Relaia de derivare n gramatica G este o relaie din *V**, notat G, i este definit astfel:

1 G 2 dac i numai dac 1 = A, 2= i A . Vom nota prin *G (+G) nchiderea reflexiv i tranzitiv (nchiderea tranzitiv) a relaiei G. Atunci cnd nu exist confuzii, vom renuna la a indica G n aceste relaii (scriem simplu , *, + ). Dac spunem c deriveaz ntr-un pas ; dac *G ( +G ) spunem c deriveaz ( deriveaz propriu ):

*G dac i numai dac exist 0, 1,, n, n 0 astfel ca: = 0 1 n =

+G dac i numai dac exist 0, 1,, n, n 1 astfel ca: = 0 1 n =

Dac S *G spunem c este form propoziional n gramatica G, iar dac este format din terminali, = w, spunem c w este o fraz n gramatica G. Definiia 1.2.11 Limbajul generat de gramatica G (notat L(G)) este mulimea frazelor gramaticii G, L(G)= {w| w T*, S + w }. Pentru c n aceast lucrare ne vom ocupa numai de gramatici independente de context, le vom numi pe acestea simplu gramatici. Pentru studiul ierarhiei lui Chomsky, cititorul este invitat a consulta lucrrile [Gri86], [Juc99]. De asemenea, vom considera c gramaticile cu care lucrm n continuare sunt gramatici reduse, adic orice simbol X este simbol util:

este accesibil: S + X, pentru anumii , *; este productiv: X * w, pentru un anume w T*.

Este cunoscut faptul c pentru orice gramatic G exist o gramatic G', cu L(G) = L(G') (G i G' se zic echivalente n acest caz), astfel nct orice simbol al vocabularului gramaticii G' este util (vezi [Gri86], [Juc99], [JuA02]). O gramatic fr simboluri inutile (simboluri care nu sunt utile) se numete gramatic redus. n continuare vom considera numai gramatici reduse.

1.2.4 Arbori sintactici. Ambiguitate Un arbore sintactic ilustreaz ntr-o gramatic modul n care axioma genereaz o (se rescrie ntr-o) fraz a gramaticii. Ideea care st la baza atarii unui arbore unei derivri este aceea c, dac ntr-o derivare se folosete o producie de forma A X1X2 Xn, atunci n arbore exist un nod interior etichetat A care are n descendeni etichetai respectiv cu X1, X2, , Xn de la stnga la dreapta.

Limbaje formale 19Definiia 1.2.12 Fie G = (V, T, S, P) o gramatic. Un arbore sintactic (arbore de derivare, arbore de parsare) n gramatica G este un arbore ordonat, etichetat, cu urmtoarele proprieti:

1. rdcina arborelui este etichetat cu S ; 2. fiecare frunz este etichetat cu un simbol din T sau cu ; 3. fiecare nod interior este etichetat cu un neterminal; 4. dac A eticheteaz un nod interior care are n succesori etichetai de la stnga la

dreapta respectiv cu X1, X2, , Xn, atunci A X1X2 Xn este o producie. Cazul n care producia este A este un caz special: nodul etichetat A are un singur descendent etichetat .

Frontiera unui arbore de derivare este cuvntul w = a1a2an unde ai, 1 i n sunt etichetele nodurilor frunz n ordinea de la stnga la dreapta. Exemplul 1.2.10 S considerm gramatica care descrie expresiile aritmetice ce se construiesc cu +, *, id i paranteze:

E E+E | E*E | (E) | id. Un arbore de derivare n aceast gramatic este prezentat n figura 1.9. S observm c acestui arbore de derivare i putem ataa derivrile: E E+E id+E id+E*E id+id*E id+id*id E E+E E+E*E E+E*id E+id*id id+id*id E E+E E+E*E E+id*E id+id*E id+id*id Este clar c cele trei derivri (mai pot fi scrise i altele) sunt distincte. Ele difer prin ordinea de aplicare a regulilor. n prima derivare, la fiecare pas s-a rescris cea mai din stnga variabil a formei propoziionale (curente); astfel de derivri se numesc derivri

extrem stngi. Vom nota o derivare extrem stnga prin st

: uA

st u dac u T*, A P, *

Aadar, prima din derivrile de mai sus se scrie: E +st

id+id*id.

Figura 1.9

E

E + E

id E * E

id id

Prefa 20Cea de-a doua derivare are proprietatea c, la fiecare pas, s-a rescris cea mai din dreapta variabil din forma propoziional. Vom numi astfel de derivri derivri extrem drepte i le

vom nota prindr :

Au dr u dac u T*, A P, *

Prin urmare cea de-a doua derivare se scrie: E +dr

id+id*id. Aadar, arborele sintactic este o reprezentare grafic a unei derivri n care a disprut alegerea ordinii n care se aplic regulile de producie. Unui arbore sintactic i corespunde o singur derivare extrem stng (respectiv o singur derivare extrem dreapt). Se demonstreaz relativ uor urmtoarea lem (vezi [Gri86] i[Juc99]): Lema 1.2.4. Fie G o gramatic i w T*. Atunci, exist o derivare S + w (sau echivalent w L(G)) dac i numai dac exist un arbore de derivare cu frontiera w. Mai mult, dac A V, * are loc: A + dac i numai dac exist un arbore (construit dup aceleai reguli ca arborele de derivare) n care rdcina este etichetat cu A, iar frontiera este .

S observm acum c, pentru cuvntul w= id+id*id (gramatica din exemplul precedent), se mai poate construi un arbore de derivare distinct de cel de mai sus, anume cel din figura 1.10. Acestui arbore i corespunde derivarea extrem stng:

S E*E E+E*E id+E*E id+id*E id+id*id care difer de derivarea extrem stng precedent. Cele dou derivri extrem stngi (respectiv cei doi arbori de derivare) corespund aceluiai cuvnt din L(G). Fenomenul este cunoscut sub numele de ambiguitate. Definiia 1.2.13 O gramatic G=(V, T, S, P) se zice c este ambigu dac exist w L(G) pentru care se pot construi mcar dou derivri extrem stngi distincte (respectiv doi arbori de derivare distinci).

Figura 1.10

Exemplul 1.2.10 Gramatica urmtoare ce descrie construciile if-then i if-then-else este ambigu:

E

E * E

+ E E id

id id

Limbaje formale 21I if e then I | if e then I else I | a

n adevr, pentru fraza: w = if e then if e then a else a

putem construi dou derivri extrem stngi distincte: I if e then I if e then if e then I else I if e then if e then a else I if e then if e then a else a I if e then I else I if e then if e then I else I if e then if e then a else I if e then if e then a else a care corespund, evident, la arbori de derivare distinci. Este de dorit ca, atunci cnd abordm analiza sintactic, s o facem pentru o specificare neambigu. Uneori, o gramatic ambigu se poate transforma ntr-o gramatic echivalent neambigu. Aceast transformare este legat de anumite reguli care se impun. De pild, n gramatica ambigu:

E E+E | E*E | (E) | id nu este specificat nici o ordine de prioritate ntre operatorii + i *. Dac impunem ca * s aib prioritate asupra lui +, atunci o nou gramatic se poate scrie pentru descrierea expresiilor aritmetice:

E E+T | T T T*F | F F (E) | id

n aceast nou gramatic, noii neterminali au semnificaia natural: T noteaz ceea ce se cheam termen, F este notaia pentru factor, nct putem spune c de data aceasta gramatica exprim mai fidel ceea ce se numete expresie. Dac ncercm s impunem reguli similare pentru cazul if-then-else, putem ajunge la o exprimare de forma:

I I1 | I2 I1 if e then I1 else I1 | a I2 if e then I | if e then I1 else I2

Prin aceasta s-a exprimat regula: se asociaz else acelui then precedent, cel mai apropiat care nu are corespondent. n capitolele urmtoare vom construi o serie de algoritmi. Pentru descrierea acestora vom folosi un limbaj(algoritmic) bazat pe limbajul C: vom utiliza operatori specifici limbajului C ca ++(incrementare), ==(egalitate logic), !=(neegalitate logic), !(negaie) blocurile vor fi specificate prin acolade, instruciunile while, for, if care vor fi folosite funcioneaza ca n C.

Analiza lexical 23

2 Analiza lexical Rolul pe care l are un analizor lexical este de a citi textul surs, caracter cu caracter, i a-l transforma ntr-o secven de uniti primitive (elementare) numite uniti lexicale (tokens n limba englez). Fiecare unitate lexical descrie o secven de caractere cu o anumit semnificaie i este tratat ca o entitate logic. Pentru fiecare limbaj de programare se stabilesc (atunci cnd se proiecteaz limbajul) unitile lexicale. n majoritatea limbajelor se disting urmtoarele uniti lexicale:

Nr. Crt.

Unitatea Lexical

Exemple

1 Constanta 573 -5.89 2e+3 2 Identificator alpha un_ident 3 Operator + * / < > 4 Cuvnt rezervat begin while 5 Semn special ; . :

n acest capitol vom discuta tehnicile de analiz lexical, proiectarea i implementarea unui analizor lexical. Problema analizei lexicale prezint cel puin dou aspecte. Mai nti, trebuie gsit o modalitate de descriere a unitilor lexicale. Se constat c expresiile regulate modelul algebric de descriere a limbajelor regulate - sunt mecanismele care pot descrie orice unitate lexical. Un al doilea aspect este cel al recunoaterii acestor uniti lexicale (analiza lexical propriu-zis). Dac descrierea se face cu expresii regulate atunci mecanismul de recunoatere este automatul finit determinist. Se tie din teoria limbajelor formale c mulimea limbajelor descrise de expresii regulate coincide cu cea a limbajelor recunoscute de automate finite (clasa limbajelor regulate). Vom descrie n acest capitol algoritmii (eficieni) de construcie a unui automat finit (determinist) echivalent cu o expresie regulat i, apoi, implementarea unui automat finit (analizorul lexical). Unitile lexicale sunt de dou categorii:

uniti care descriu un ir de caractere anume (de exemplu if, while, ++, :=, ; );

uniti care descriu o clas de iruri: (identificatori, constante etc.). n cel din urm caz, vom trata o unitate lexical ca fiind o pereche format din tipul i valoarea unitii lexicale. Pentru unitile lexicale care descriu un ir anume, convenim c tipul este acel ir, iar valoarea coincide cu tipul. De exemplu caracterul ( este de tip parantez stng iar alpha este unitatea lexical de tip identificator care are valoarea alpha. n literatura de specialitate alpha se mai numete instan a tokenului identificator sau lexem. Vom descrie unitile lexicale prin expresii regulate. De pild, o constant ntreag fr semn este descris de expresia: (1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9)(0 | 1 | 2 |3 | 4 | 5 | 6 | 7 | 8 | 9)* Pentru comoditatea notaiilor, se pot da nume unor expresii regulate iar cu ajutorul acestora pot fi definite alte expresii regulate. Fie un alfabet, d1, d2, , dn nume distincte date unor expresii regulate iar E1, E2,, En expresii regulate astfel nct E1 este expresie regulat peste iar Ei (1 < i n) este expresie regulat peste alfabetul {d1, d2,, di-1},. Atunci o definiie regulat este un ir de definiii de forma:

Analiza lexical 24 d1 E1 d2 E2 dn En

De exemplu, mulimea identificatorilor PASCAL poate fi dat prin definiia regulat urmtoare (din comoditate s-a scris dar trebuiesc nelese caracterele corespunztoare):

A | B | | Z | a | b | | z 0 | 1 | | 9 ( | )*

Constantele fr semn n PASCAL se definesc astfel:

0 | 1 | | 9 * .( | ) (E | e)(+ | - | ) |

Operatorul unar * semnific repetarea de zero sau mai multe ori a unei instane. Dac folosim operatorul unar + pentru a desemna operaia ,,cel puin o instan din, adic E+ = EE*, atunci definiia numelui se poate scrie:

+

2.1 Un algoritm de trecere de la o expresie regulat la automatul echivalent

S transpunem construciile din teorema 1.2.1 ntr-un algoritm pentru transformarea unei expresii regulate n automat finit. Mai nti s observm c fiecare din apariiile operatorilor | i * dintr-o expresie regulat E introduce dou noi stri n automatul construit, pe cnd operatorul * nu introduce alte stri (figura 1.8). De asemenea, pentru orice apariie a unui simbol din , ct i pentru , dac acesta apare explicit n E, este nevoie de 2 stri n automatul construit. Aadar, dac n este numrul de simboluri din E iar m este numrul de paranteze mpreun cu apariiile simbolului *, atunci numrul strilor automatului echivalent cu E este 2(n m). S mai observm c, din orice stare a automatului, se fac cel mult dou tranziii: fie o tranziie cu un simbol din , fie una sau dou - tranziii, fie zero tranziii. Atunci, reprezentarea automatului echivalent cu o expresie regulat se poate face cu un tablou de dimensiune p3 unde p este numrul strilor (acestea sunt numerotate de la 1 la p), prima coloan conine simbolurile cu care se fac tranziiile iar urmtoarele dou coloane conin strile rezultate n urma tranziiilor. Pentru descrierea algoritmului o s identificm cele trei coloane prin vectorii simbol, next1, next2. Algoritmul pe care-l descriem mai jos este datorat lui Rytter (Ryt91). Algoritmul 2.1.1 Intrare: Expresia regulat E cu n simboluri dintre care m sunt paranteze i apariii ale operatorului produs; Ieire: Vectorii simbol, next1, next2 de dimensiune p = 2(n-m) ce descriu automatul cu - tranziii echivalent cu E; Metoda: 1. Se construiete arborele ataat expresie E (o metod se d mai jos);

Un algoritm de trecere de la o expresie regulat la automatul echivalent 252. Se parcurge arborele n preordine i se ataeaz nodurilor vizitate, exceptnd pe cele

etichetate cu *, respectiv numerele 1, 2, , n-m; 3. Se parcurge arborele n postordine i se ataeaz fiecrui nod N o pereche de

numere (i, f) care reprezint starea iniial respectiv final a automatului corespunztor subarborelui cu rdcina N, astfel: 3.1. Dac nodul are numrul k (de la pasul 2) atunci N.i = 2k-1, N.f = 2k; 3.2. Dac nodul este etichetat * atunci N.i = S.i iar N.f = D.f (S i D sunt fii lui N,

stng respectiv drept); 4. for(1

Analiza lexical 26Exemplul 2.1.1 S considerm expresia E = a*b | bb(a | c)*. 1. Arborele expresiei este prezentat n figura 2.1. 2. Nodurilor arborelui le sunt ataate respectiv numerele 1, 2, , 10 prin parcurgerea

n preordine i exceptnd nodurile produs. 3. Numrul strilor automatului va fi p = 20. Dup parcurgera n postordine a

arborelui, fiecare nod are ataat o pereche (i, j) (figura 2.2). 4. Se iniializeaz vectorii simbol, next1 i next2. 5. Tabela de tranziie a automatului, n urma aplicrii procedurilor descrise la 5 n

fiecare nod al arborelui, este dat n continuare.

Figura 2.1

Figura 2.2

Tabela de tranziie a automatului:

p simbol[p] next1[p] next2[p] 1 3 9 2 0 0 3 5 4 4 7 0 5 a 6 0 6 5 4 7 b 8 0 8 2 0 9 b 10 0

(1,2) (9,14)

(13,14)(9,12)

(3,8)

(15,16)8

(19,20) (17,18)

(7,8)(3,4)

(11,12) (9,10) (5,6) 9 10

7

63

2

1+

* *b * **

a b b +

a c

4

5

8

9 10

7

63

2

1

|

* *

b * **

a b b |

a c

4

5

Un algoritm de trecere de la o expresie regulat la automatul echivalent 2710 11 0 11 b 12 0 12 13 0 13 15 14 14 2 0 15 17 19 16 15 14 17 a 18 0 18 16 0 19 c 20 0 20 16 0

Teorema 2.1.1 Algoritmul 2.1.1 este corect: automatul cu - tranziii obinut este echivalent cu expresia regulat E. Demonstraie S observm c modul n care au fost alese perechile (i, f) de stri pentru fiecare nod al arborelui construit corespunde construciilor din teorema 1.2.1. De asemenea tranziiile care se definesc n pasul 5 al algoritmului urmresc construcia din teorema amintit. Aadar, automatul obinut este echivalent cu expresia dat la intrare.

2.2 De la un automat cu -tranziii la automatul determinist echivalent

n paragraful precedent am descris procedeul de trecere de la o expresie regulat la automatul finit echivalent. Programul care descrie activitatea acestui automat finit pentru un cuvnt de intrare este de fapt analizorul lexical. Pentru ca acest analizor s fie eficient este de dorit ca automatul obinut s fie determinist. Cum prin procedeul descris n teorema precedent se obine un automat cu - tranziii (nedeterminist deci), s indicm o modalitate de trecere de la un automat cu - tranziii la automatul determinist echivalent. Mai nti s descriem un algoritm pentru calculul mulimii Cl(S) = (S, ). Algoritmul 2.2.1 Intrare: Automatul (cu - tranziii) A = (Q, , , q0, F), S Q. Ieire: Cl(S) = (S, ). Metoda: Stiva STIVA se iniializeaz cu S i pentru fiecare q din top, strile din (q, ) ce nu au fost puse n Cl(S) se adaug n Cl(S) i n stiv. 1. R = S; STIVA = S; 2. while (STIVA ) { 3. q = STIVA.pop(); // Se extrage q din stiv 4. T = (q, ) ; 5. if(T ) { 6. for ( p T ) { 7. if ( p R) { 8. R = R {p} ; 9. STIVA.push(p);//Se adaug p in stiva

}//endif }//endfor }//endif }//endwhile 10. Cl(S) = R;

Analiza lexical 28Algoritmul 2.2.2 Transformarea unui automat cu - tranziii n automat finit determinist. Intrare: Automatul (cu - tranziii) A = (Q, , , q0, F). Procedura de calcul pentru Cl(S) (Algoritmul 2.2.1). Ieire: Automatul determinist A = (Q, , , q0, F), echivalent cu A. Metoda: Se construiesc strile lui A ncepnd cu q0 i continund cu cele accesibile prin tranziii cu simboluri din alfabet. 1. q0 = Cl(q0); Q = {q0} ; 2. marcat(q0) = false; F = ; 3. if ( q0 3 F ) then F = F 4 {q0} ; 4. while (q Q && !marcat(q)){//q este nemarcat 5. for(a ){ 6. p = Cl(( q, a)); // = (q, a) 7. if ( p ) { 8. if ( p Q) { 9. Q = Q 4 {p}; 10. marcat(p) = false; 11. (q,a) = p ; 12. if(p 3 F != )then F = F 4 {p}; }//endif }//endif }//endfor 13. marcat(q) = true;

}//endwhile

2.3 Proiectarea unui analizor lexical Definiia 2.4.1 Fie un alfabet (al unui limbaj de programare). O descriere lexical peste este o expresie regulat E = (E1 | E2 || En)+, unde n este numrul unitilor lexicale, iar Ei descrie o unitate lexical, 1 i n. Exemplul 2.4.1 S considerm = {a, b, , y, z, 0, 1,,9, :, =} i urmtoarele expresii regulate:

Litera a | b | c | | z Cifra 0 | 1 | | 9 Id Litera ( Litera | Cifra)* Intreg Cifr+

Asignare := Egal = Douapuncte :

O descriere lexical care cuprinde aceste uniti lexicale este: E = ( Id | Intreg | Asignare | Egal | Douapuncte)+

Definiia 2.4.2 Fie E o descriere lexical peste ce conine n uniti lexicale i w +. Cuvntul w este corect relativ la descrierea E dac w L(E). O interpretare a cuvntului w L(E) este o secven de perechi (u1, k1), (u2, k2), , (um, km), unde w = u1u2um, ui L(Eki) 1 i m, 1 ki n. Uneori, n loc de ki n (ui, ki), punem chiar Eki, asta nsemnnd faptul c ui este o unitate de tipul Eki.

Generatorul Lex 29Exemplul 2.4.2 Fie E din Exemplul 2.4.1 i w = alpha:=beta=542. O interpretare a cuvntului w este:

(alpha, Id), (:=, Asignare), (beta, Id), (=, Egal), (542, Intreg) Sigur c aceasta nu este singura interpretare. Urmtoarea secven este de asemenea o interpretare a aceluiai cuvnt: (alpha, Id), (:, Douapuncte), (=, Egal), (b, Id}), (eta, Id), (=, Egal), (5, Intreg), (42, Intreg). Faptul c am obinut interpretri diferite pentru acelai cuvnt este consecin a ambiguitii expresiei regulate E: unitatea lexical Asignare are dou descrieri distincte n E : Asignare i produsul DouapuncteEgal. La fel se ntmpl cu Id i cu Intreg. Din teorie se tie c, pentru orice expresie regulat E, exist o expresie regulat E neambigu, echivalent cu E. Soluia de a construi E pentru a obine interpretri unice pentru fiecare cuvnt nu este convenabil pentru c, pe de o parte, transformarea E n E consum timp iar, pe de alt parte, E nu descrie n mod natural limbajul n cauz. n toate cazurile, se prefer s se dea nite reguli n plus pentru a putea alege o singur interpretare a unui cuvnt atunci cnd descrierea lexical este ambigu. Definiia 2.4.3 Fie E o descriere lexical peste i w L(E). O interpretare a cuvntului w, (u1, k1)(u2, k2), (um, km), este interpretare drept - orientat dac (i) 1 i m, are loc:

|ui| = max{|v| /v L(E1 | E2 || En) Pref(uiui+1um)}. (unde prin Pref(w) am notat mulimea prefixelor cuvntului w ). Observaia 2.4.1 Exist descrieri lexicale E n care nu orice cuvnt din L(E) admite o interpretare drept-orientat. Fie descrierea E = (a | ab | bc)+ peste alfabetul = {a, b} i w = abc. Singura interpretare a cuvntului w este (a, 1), (bc, 3) dar aceasta nu este drept orientat pentru c a nu este cel mai lung cuvnt din L(a | ab | bc) 3 Pref(abc), acesta din urm fiind ab. Definiia 2.4.4 O descriere lexical E este bine - format dac orice cuvnt w din limbajul L(E) are exact o interpretare drept-orientat. Definiia 2.4.5 Fie E = (E1 | E2 | | En)+ o descriere lexical bine format peste . Un analizor lexical (scanner) pentru E este un program ce recunoate limbajul L(E) i produce, pentru fiecare w L(E), interpretarea sa drept-orientat. Dat o descriere lexical E peste alfabetul , proiectarea unui analizor lexical cuprinde urmtoarele proceduri:

1. Se construiete automatul finit (cu - tranziii) A, astfel ca L(E) = L(A) (utiliznd Algoritmul 2.1.1).

2. Se aplic Algoritmul 2.2.1 i se obine automatul determinist echivalent cu E, fie acesta A.

3. (Opional) Se aplic Algoritmul 2.3.1 pentru a obine automatul minimal echivalent cu A.

4. Se scrie un program care implementeaz evoluia automatului obinut. Ne vom ocupa n continuare de modificrile ce trebuiesc aduse construciilor 1-3 pentru a putea obine o interpretare orientat dreapta pentru un cuvnt w din L(E). Distingerea ntre clasele de uniti lexicale E1, E2,, En, poate fi fcut adugnd fiecrei expresii Ei o marc de sfrit #i, 1 i n. Noua descriere lexical, notat E# este: E# = (E1#1 | E2#2 || En#n)+, peste alfabetul {#1,,#n }. Automatul determinist ce recunoate L(E#) va avea, desigur, tranziii pentru simbolurile #i. Pentru c aceste simboluri nu apar n irul de intrare (se analizeaz cuvintele w + ), vom trata aceste tranziii ntr-un mod special (n programul scris la etapa 4): cnd apare o tranziie de tipul #i, programul raporteaz o unitate lexical din clasa Ei. Exemplul 2.4.3 S considerm descrierea lexical:

Analiza lexical 30litera a | b ||z cifra 0 | 1 || 9 identificator litera (litera | cifra)* semn + | - numar (semn | ) cifra+ operator + | - | * | / | < | > | = | < > asignare := doua_puncte : cuvinte_rezervate if | then |else paranteze ) | (

Figura 2.5 Dup cele discutate n paragraful precedent, exist automatele (cu - tranziii) Ai, An, Ao, Aa, Ad, Ac, Ap care recunosc respectiv limbajele descrise de expresiile regulate din E. Atunci, un automat cu - tranziii ce recunoate E se construiete dup schema din figura 2.5. Pentru acest automat cu - tranziii, exist un automat determinist echivalent care recunoate L(E). Acest automat determinist poate fi nc simplificat prin gsirea automatului cu cele mai puine stri care recunoate acelai limbaj. n sfrit, se scrie un program - analizorul lexical - care simuleaz acest automat. Automatul determinist (minimal) echivalent cu cel descris n fig. 2.5 i cu tranziiile corespunztoare simbolurilor #i, #n, #o, #a, #d, #c, #p, care desemneaz sfritul unei uniti lexicale de tip identificator, numr, operator, asignare, doua_puncte, cuvinte_rezervate, paranteze, este dat n figura 2.6.

q0

Ai

Aa

Ao

An

Ad

Ac

Ap

Generatorul Lex 31

Figura 2.6

Aadar, 0 este stare iniial i final, tranziiile notate cu liter, cifr nseamn c sunt tranziii pentru orice simbol din clasa liter respectiv cifr. Tranziia cu un delimitator # semnific faptul c s-a identificat o unitate lexical; aceasta se raporteaz i se reia activitatea automatului din starea iniial. Programul (analizorul lexical) const din cte un segment de program pentru fiecare stare a automatului. Dac vom nota prin buffer zona de memorie unde se ncarc o unitate lexical, getnext(ch), store(ch) funciile ce citesc respectiv memoreaz ch n buffer, atunci pentru starea q care are tranziii respectiv n strile qi pentru simbolurile ai, 1 i m i tranziia cu #h n q0, segmentul de program este dat mai jos.

q : switch(ch){ case: a1

store(ch); getnext(ch); goto q1;

case: a2 store(ch); getnext(ch); goto q2;

.

.

case: am store(ch); getnext(ch); goto qm; default: write(buffer, i); empty(buffer); goto q0; }

Aadar, n cazul n care caracterul citit este ai, se memoreaz acesta, se citete alt caracter i se continu programul pentru starea qi, 1 i m, iar dac nu este nici unul dintre simbolurile a1, a2, , am, s-a depistat unitatea lexical de tip i, se raporteaz aceasta (

litera

cifra

#p

#d

#a

#o

#o

#n

#i sau #c

litera, cifra

), (

=:

operator-{+,-}

+, -

cifra

cifra

0

1

7

65

4

3

2

Analiza lexical 32write(buffer,i) ), se golete zona buffer pentru a primi o nou unitate lexical dup care se trece la programul strii iniiale. Dac din starea q nu exist # - tranziie, grupul default se nlocuiete prin:

default: write(buffer,"eroare"); empty(buffer); goto q0;

Pentru starea iniial q0 (care este n acelai timp i stare final, grupul default se nlocuiete prin:

default: if(EOF){

write(Sfarsitul analizei); exit(0);

}else{ write(buffer,"eroare"); empty(buffer);

getnext(ch); goto qo; }

2.4 Generatorul Lex LEX este un instrument software deosebit de util celor care doresc s implementeze limbaje de programare, dar poate fi folosit i n multe alte aplicaii. Acesta a fost dezvoltat la Bell Laboratories n anul 1975 de ctre M.E. Lesk i E. Schmidt. LEX citete un fiier de intrare (n general cu extensia .l) care conine expresii regulate ce definesc unitile lexicale i genereaz un program C care realizeaz analiza lexical a unui text, n conformitate cu specificaiile date. LEX a devenit instrument standard UNIX ncepnd cu versiunea a 7-a a acestui sistem de operare. Proiectul GNU al Fundaiei Free Software distribuie FLEX (Fast LEXical Analyzer Generator) care este o mbuntire a generatorului LEX. De asemenea exist versiuni pentru sistemele de operare DOS i WINDOWS; una dintre acestea este PCLEX lansat de Abraxax Software Inc.. Pentru a utiliza LEX, se parcurg trei pai: 1. Scrierea specificaiilor LEX ntr-un fiier cu extensia .l care reprezint descrierea lexical pentru care dorim s construim un analizor lexical. 2. Executarea programului LEX (sau PCLEX) cu intrarea fiierul construit: lex [optiuni] flex [optiuni] pclex [optiuni] Pentru a afla descrierea opiunilor ce se pot folosi, executai programul lex h. Ca rezultat al execuiei cu argumentul se obine un fiier cu acelai nume dar cu extensia .c, care este de fapt un program n limbaj C. 3. Se compileaz acest program mpreun, eventual, cu alte fiiere surs. Programul C obinut n urma executrii LEX - ului este de fapt o funcie cu numele yylex() care, pentru a fi executat, trebuie inclus ntr-o funcie main() (furnizat de utilizator) care conine apelul yylex() sau, se integreaz aceast rutin cu altele (de exemplu ntr-o aplicaie yacc). O specificare LEX (fiierul de intrare) are structura:

Declaraii %% Reguli %% Rutine auxiliare

Generatorul Lex 33Seciunea Declaraii precum i Rutine auxiliare pot lipsi nct o specificare minim trebuie s conin cele dou linii %% ntre care sunt scrise liniile ce conin reguli de specificare a unitilor lexicale. Seciunea Declaraii conine dou pri. Prima parte const din declaraii C pentru variabilele sau constantele care se vor folosi ulterior iar a doua parte conine definiii ce se folosesc n specificaiile LEX n seciunea Reguli. O definiie (macro pentru expresii regulate) are forma:

unde este o expresie (regulat) ce poate folosi orice caracter mpreun cu urmtorii operatori: " \ [ ] ^ - ? . * + | () $ / {} % Aceti operatori au o anume semnificaie iar dac se dorete a-i folosi drept caractere trebuiesc precedai de \ (backslash). Semnificaia operatorilor este: " Caracterele text sunt incluse ntre ghilimele "". Construcia "c" este echivalent cu \c. [ ] Definete o clas de caractere sub forma unei liste alternative. n interior se poate folosi caracterul pentru a indica un domeniu. De exemplu, o cifr ntreag se poate defini prin [0123456789] sau prin [0-9]. Expresiile urmtoare: [-a+], [+a-], [a\-+] sunt echivalente i desemneaz unul din caracterele a, + sau . Dac se folosete n [] atunci el trebuie pus primul, ultimul sau sub forma \. ^ Acest simbol este considerat operator dac este primul ntr-o anume descriere, altfel este caracter text. Se folosete pentru a exclude din definiie anumite caractere. De exemplu expresia [^ \t\n] desemneaz un caracter diferit de spaiu, tab sau linie nou. ? Elementul precedent acestui operator este opional. Expresia ab?c desemneaz abc sau ac iar a[b-c]?d noteaz abd, acd sau ad. * Operatorul iteraie de la expresii regulate. + Operatorul iteraie proprie (repetare de 1 sau mai multe ori) de la expresii regulate. | Operatorul alternativ (reuniune) de la expresii regulate. () Operatorul () (grupare) de la expresii regulate. {} n macro-definiii acest operator se poate folosi pentru a specifica numrul de repetiii ale unei expresii. De pild AAA i A{3} sunt echivalente, iar dac scriem [a-z]{1,5} aceasta desemneaz una pn la 5 litere mici ale alfabetului. . Acest caracter (punct) desemneaz orice caracter n afar de \n. De exemplu, descrierea a.b reprezint a0b,a1b,a\b,axb etc. ntr-o descriere lexical ce urmeaz a fi inclus ntr-un fiier intrare pentru lex, alternativa default se descrie printr-o linie ce are punctul n prima coloan, asta nsemnnd orice alt caracter ce nu a fost inclus pn la aceast linie n vreo definiie sau descriere. Urmtoarele dou linii n seciunea declaraii:

cifra [0-9] litera [a-zA-Z]

sunt definiii ale expresiilor regulate cifra, litera care pot fi folosite pentru definirea altor expresii n seciunea Reguli. Numele definite aici trebuiesc folosite ntre acolade: {litera}, {cifra}. Tot n aceast seciune pot fi scrise segmente de cod C care urmeaz a fi incluse n procedura yylex (de pild linii pentru preprocesor de tipul #include sau #define). Aceste elemente trebuiesc incorporate ntr-un bloc de forma %{%}. De exemplu:

%{ #include %}

Seciunea Reguli definete funcionalitatea analizatorului lexical. Fiecare regul este compus dintr-o expresie regulat i o aciune. Aadar, aceast seciune are forma:

Analiza lexical 34 m1 {Aciune1} m2 {Aciune2} . . . mn {Aciunen}

unde mi sunt expresii regulate iar Aciunei este un segment de program C care se va executa atunci cnd analizorul ntlnete un exemplar din unitatea lexical descris de mi (1 i n). Pentru scrierea expresiilor regulate se folosesc operatorii pe care i-am descris mai sus, numele unor expresii deja definite, cuprinse ntre acolade precum i orice alte caractere text. Spre exemplu, expresia {litera}({litera}|{cifra})* desemneaz un identificator. Seciunea a treia, Rutine auxiliare, conine toate procedurile auxiliare care ar putea fi utile n procesul de analiz lexical. Dac analizorul lexical creat este independent, aceast seciune trebuie s conin o funcie main() care face apel la funcia yylex(). Exemplul 2.5.1 Iat coninutul fiierului de intrare pentru descrierea lexical din paragraful precedent: %{ /* scaner1.l // Exemplu de fisier de intrare pentru flex */ # include %} litera [a-zA-Z] cifra [0-9] cifre ({cifra})+ semn [+-] operator [+*/=-] spatiu [' \t\n] %% "if" | "then" | "else" { printf("%s cuvant rezervat\n", yytext);} ({litera})({litera}|{cifra})* { printf("%s identificator\n", yytext);} {cifre}|({semn})({cifre}) { printf("%s numar intreg\n", yytext);} {operator} {printf("%c operator\n", yytext[0]);} \:\= {printf("%s asignare\n", yytext);} \: {printf("%c doua puncte\n", yytext[0]);} (\()|(\)) {printf("%c paranteza\n", yytext[0]);} {spatiu} {} . {printf("%c caracter ilegal\n", yytext[0]);} %% int main( ){ yylex( ); return 0; } Exemplul 2.5.2 Urmtorul fiier constituie o descriere lexical pentru un limbaj ce conine cuvintele rezervate set, sqrt, quit, identificatori, numere i operatori. %{ /* scaner2.l // Scaner expresii */ #include #include #include %} %%

Problema recunoaterii. Problema parsrii 35quit {printf(" Cuvant cheie: %s\n", yytext);} set {printf(" Cuvant cheie: %s\n", yytext);} sqrt {printf(" Cuvant cheie: %s\n", yytext);} \+ {printf(" Operator: %c\n", yytext[0]);} \- {printf(" Operator: %c\n", yytext[0]);} \* {printf(" Operator: %c\n", yytext[0]);} \/ {printf(" Operator: %c\n", yytext[0]);} \( {printf(" Paranteza stanga: %c\n", yytext[0]);} \) {printf(" Paranteza dreapta: %c\n", yytext[0]);} \:\= {printf(" Asignare: %s\n", yytext);} (([0-9]+(\.[0-9]*)?)|(\.[0-9]+))((e|E)(\-|\+)?[0-9]+)? { printf(" Numar: %f\n", atof(yytext));} [_A-Za-z]+ {printf(" Identificator: %s\n", yytext);} [ \t]+ ; /* Eliminare spatii */ \n {return 0;} . {printf(" Caracter ilegal: %c\n", yytext[0]);} %% int main(){ printf("******************************************\n"); printf("** Exemplu de scaner **\n"); printf("** Cuvinte cheie: set sqrt quit **\n"); printf("** Operator: + - * / ( ) **\n"); printf("** Operanzi: numere, identificatori **\n"); printf("******************************************\n"); yylex(); return 0; }

3 Analiza sintactic descendent La proiectarea limbajelor de programare se stabilesc reguli precise care descriu structura sintactic a programelor. n limbajul Pascal spre exemplu, un program este format din blocuri, un bloc conine instruciuni, o instruciune are n componena sa expresii, iar o expresie este o niruire de o anumit form de uniti lexicale. Sintaxa unui limbaj de programare poate fi descris cu ajutorul gramaticilor independente de context sau a notaiei BNF (Backus - Naur Form). Descrierea sintaxei prin gramatici independente de context are avantaje att din punct de vedere al proiectrii, ct i din cel al implementrii limbajelor. Aceste avantaje pot fi sintetizate astfel: o gramatic independent de context ofer o specificare sintactic precis i n

acelai timp uor de neles; pentru anumite clase de gramatici este posibil construirea automat a unui analizor

sintactic eficace. Analizorul sintactic are rolul de a determina dac un program surs este corect din punct de vedere sintactic. Mai mult, n procesul de construcie a analizorului sintactic pot fi depistate ambiguiti sintactice sau alte construcii dificile, care pot rmne nedetectate n timpul proiectrii unui limbaj;

descrierea sintaxei printr-o gramatic independent de context impune limbajului o structur care se dovedete a fi util pentru traducerea programului pus n cod obiect corect, precum i pentru detectarea erorilor.

Analiza lexical 363.1 Rolul analizorului sintactic Un analizor sintactic primete la intrare un ir de uniti lexicale i produce arborele de derivare al acestui ir n gramatica ce descrie structura sintactic (mai degrab o anume reprezentare a acestui arbore). n practic, odat cu verificarea corectitudinii sintactice, se produc i alte aciuni n timpul analizei sintactice: trecerea n tabela de simboluri a unor informaii legate de unitile sintactice, controlul tipurilor sau producerea codului intermediar i alte chestiuni legate de analiza semantic (unele din acestea le vom discuta n capitolul ce trateaz semantica). S ne referim n cteva cuvinte la natura erorilor sintactice i la strategiile generale de tratare a acestora. Dac un compilator ar trebui s trateze doar programele corecte, atunci proiectarea i implementarea sa s-ar simplifica considerabil. Cum ns programatorii scriu adesea programe incorecte, un compilator bun trebuie s asiste programatorul n identificarea i localizarea erorilor. Cea mai mare parte a specificrilor limbajelor de programare nu descriu modul n care implementarea (compilatorul) trebuie s reacioneze la erori; acest lucru este lsat pe seama celor care concep compilatoarele. Erorile ntr-un program pot fi:

lexicale: scrierea eronat a unui identificator, a unui cuvnt cheie, a unui operator etc. ;

sintactice: omiterea unor paranteze ntr-o expresie aritmetic, scrierea incorect a unei instruciuni, etc. ;

semantice: aplicarea unui operator aritmetic unor operanzi logici, nepotrivirea tipului la atribuiri etc. ;

logice: un apel recursiv infinit.

3.2 Problema recunoaterii. Problema parsrii Problema recunoaterii n gramatici independente de context este urmtoarea: Dat o gramatic G = (V, T, S, P) i un cuvnt w T*, care este rspunsul la ntrebarea w L(G)? Se tie c problema este decidabil; mai mult, exist algoritmi care n timp O(|w|3) dau rspunsul la ntrebare (Cooke-Younger-Kasami, Earley, vezi [Gri86]). Problema parsrii (analizei sintactice) este problema recunoaterii la care se adaug: dac rspunsul la ntrebarea w L(G) este afirmativ, se cere arborele sintactic (o reprezentare a sa) pentru w.

Fie G = (V, T, S, P) o gramatic i w L(G). S notm prin pst

(q

dr ) relaia de derivare

extrem stng (dreapt) n care, pentru rescriere s-a aplicat producia p P (q P). Atunci, pentru w L(G) exist o derivare extrem stng:

S = 0 1p

st 1

2p

st 2

3p

st pn

st n = w

i o derivare extrem dreapt:

S = 0 1q

dr 1

2q

dr 2

3q

dr qm

dr m = w

Atunci, arborele sintactic corespunztor se poate reprezenta prin secvena de producii p1p2pn P+ (respectiv q1q2qm P+ ) care s-au aplicat, n aceast ordine, n derivarea extrem stng (dreapt) pentru obinerea lui w.

Definiia 3.2.1 Secvena de producii = p1p2pn P+ pentru care S st

w se numete analizare stng (parsare stng) pentru cuvntul w L(G).

Problema recunoaterii. Problema parsrii 37

Secvena de producii = q1q2qm P+ pentru care S ~

dr w se numete analizare dreapt

(parsare dreapt) pentru cuvntul w (unde ~ = qmqm-1q1). Exemplul 3.2.4 Fie gramatica

1. E E+T 2. E T 3. T T*F, 4. T F 5. F (E) 6. F id

unde 1, 2, , 6 identific cele 6 producii ale acesteia.

Figura 3.1

Pentru cuvntul w = id+id*id, arborele sintactic este dat n figura 3.1. Analizarea stng pentru acest cuvnt este: 1 = 12463466 iar analizarea dreapt este 2 = 64264631. Aici am identificat fiecare producie prin numrul su.

3.3 Analiza sintactic descendent Analiza sintactic descendent (parsarea descendent) poate fi considerat ca o tentativ de determinare a unei derivri extrem stngi pentru un cuvnt de intrare. n termenii arborilor sintactici, acest lucru nseamn tentativa de construire a unui arbore sintactic pentru cuvntul de intrare, pornind de la rdcin i construind nodurile n manier descendent, n preordine (construirea rdacinii, a subarborelui stng apoi a celui drept). Pentru realizarea acestui fapt avem nevoie de urmtoarea structur (figura 3.2):

o band de intrare n care se introduce cuvntul de analizat, care se parcurge de la stnga la dreapta, simbol cu simbol;

o memorie de tip stiv (pushdown) n care se obin formele propoziionale stngi (ncepnd cu S). Prefixul formei propoziionale format din terminali se compar cu simbolurile curente din banda de intrare obi