- 1 -

Proiectarea compilatoarelor

Capitolul 1 Analiza lexicala

1.1. GENERALITATI

Obiectivele analizei lexicale Ca prima faza a procesului de translatare, analiza lexicala transform programul sursa vazut ca un

sir de caractere intr-un sir de simboluri numite atomi lexicali sau particule lexicale (in elng.: tokens). Un atom lexical poate fi privit ca un reprezentant al unei clase de siruri de caractere cu reguli de formare precise. In majoritatea limbajelor de programare, printre alte clase, vom gasi:

- clasa identificatorilor; - clasa constantelor intregi; - clasa constantelor fractionare (reale); - clasa operatorilor, etc.

Clasele sunt, pentru o anumita implementare, multimi finite. Totusi, daca in clasa operatorilor intra de obicei putin operatori (10-20), in clasa identificatorilor sau a constantleor vom gasi un numar relativ mare de elemente, de cele mai multe ori limitarea aparand in urma implementarii si nu datorita definitiei limbajului. Deci sarcina analizorului lexical (in engl.: scanner) este sa detecteze in sirul de caractere ale programului sursa subsiruri ce resprecta regulile de formare ale atomilor lexicali, sa clasifice aceste subsiruri si sa le traduca in atomi lexicali, adica in informatii codificate ce vor pastra esentialul: clasa fiecarui subsir si eventual, modul de regasire al subsirului. De exemplu, in cazul unui sir clasificat ca identificator, atomul lexical va contine un cod numeric, sa zicem 1, respectand clasa si un indicator spre zona in care se gaseste memorat sirul de caractere (fig. III.1.a). In mod obisnuit insa, indicatia este mai prelucrata pentru a servi si altor scopuri. Astfel, pentru fiecare identificator depistat ne intereseaza daca el apare pentru prima data in program sau ce reprezinta el in general, atributele sale. De aceea, compilatorul mentine o zona rezervata pentru tabela de simboluri, in esenta, un dictionar al tuturor identificatorilor si constantelor din program. In aceasta tabela trebuie cautat identificatorul depistat in sirul de la intrare, iar in loc de indicator spre sir, in atomul lexical se plaseaza un indicator spre intarea din tabela de simboluri corespunzatoare identificatorului (fig. III.1.1.b). De ce analiza lexicala? Rolul analizei lexicale este foarte asemnator cu cel al analizei sintactice: detectare, clasificare, traducere. Este normal sa ne intrebam din ce ratiuni structura clasica a compilatorului separa net cele doau faze? Argumentele pun mai bine in evidenta obiectivele specifice analizei lexicale[Gr 71].

a) Separarea conduce la o proiectare mai simpla a fiecarei parti(principiul proiectarii modulare). b) Prelucrarea sirului de caractere ale programului sursa necesita: preluarea inregistrare cu

inregistrare a textului de pe suportul extern accesul la fiecare caracter, comparatii numeroase cu seturi cunoscute de caractere in vederea clasificarii, cautarii in tabele etc. De aceea, aceasta prelucrare consuma, de regula, mult timp in raport cu prelucrarile altor faze, operatiile in sine fiind de nivel coborat: citire, acces la bit, comparatii de caractere etc. Pentru a avea o analiza lexicala mai eficienta, se va prefera deci scrierea in limbaj de asamblare a analizorului lexical spre deosebire de fazele urmatoare pentru care programarea se face deobicei in limbaj de nivel inalt.

c) Sintaxa atomilor lexicali este mai simpla, ea poate fi exprimata printr-o gramatica regulata ceea ce simplifica mult procesu de analiza. In cadrul acestui proces se va simula in esenta un automat finit

- 2 -

si un un atomat push-down cum se intampla in cazul analizei sintactice. Vor fi deci necesare tehnici mai simple de proiectare si programare.

d) In urma prelucrarii efectuate de analizorul lexical, textul este curatat din mai multe puncte de vedere. Intai, numarul atomilor lexicali este, de regula, mult mai mic decat numarul caracterelor textului programului. Apoi, se elimina portiunile inutile: comentarii, blancuri etc. In fine, analizorul lexical preia analiza anumitor constructii dificil de exprimat in sintaxa limbajului, deci dificil de analizat prin metodele sistematice cunoscute fara a face anumite derogari de la aceste metode. Vom prefera intotdeauna sa rezolvam aceste probleme la analiza lexicala decat sa perturbam procesul mai complex al analizei sintactice.

De exemplu, in instructiunea FORTRAN: DO1I=5,M

de abea la intalnirea caracterului , putem decide ca suntem intr-o instructiune de ciclare si nu intr-una de atribuire. O asemenea decizie poate si luata si la analiza sintactica, dar cu pretul unor complicatii: se revine asupra identificatorului DO1I pentru a-l inlocui cu trei atomi lexicali corespunzatori lui DO,1 si I. In schimb, pentru analizorul lexical rezolvarea este mai usoara: la depistarea sirului DO se cauta caracterul , in anumite conditii (dupa intalnirea caracterului =, sa nu fie intre paranteze etc). Daca il gaseste, decide ca DO este cuvant cheie. Daca nu gaseste , , decide ca DO1I este identificator. Decizia asupra tipului de instructiune este luata insa de analizorul sintactic. (Din fericire, asemenea sittuatii se intalnesc tot mai rar in limbajele de programare mai noi decat FORTRAN).

e) Separarea creste portabilitatea compilatorului, de fapt a algoritmului de compilare. De multe ori, doua versiuni ale aceluiasi limbaj de programare difera prin reprezentarile elementelor de baza, ale atomilor lexicali. De exemplu: $BEGIN in loc de BEGIN sau LOGAND in loc de & etc. Cele doua implementari vor diferi prin analizoarele lor lexicale in timp ce analizorul sintactic va ramane acelasi. Decizii in proiectarea analizoarelor lexicale Proiectarea unui analizor lexical este strans legata de structura intregului compilator, de restrictiile impuse proiectarii acestuia. In functie de aceste considerente, vom intalni diferite decizii in proiectarea analizorului lexical. Referitor l arelatia cu analizorul sintactic deosebim:

a) Analizor lexical independent de anlizorul sintactic. In acest caz analizorul lexical reprezinta un pas al compilatorului, legatura cu fazele urmatoare fiind realizata pintr-un fisier sau zona de memorie ce contin datele prelucrate.

b) Analizorul lexical comandat de analizorul sintactic. El apare ca o rutina a analizorului sintactic pe care acesta o apeleleaza ori de cate ori are nevoi de un nou simbol. Este solutia cel mai frecvent utilizata. Referitor la structura anizorului lexical deosebim:

a) Analizor lexical monobloc. Analiza lexicala este abordata si rezolvata global. b) Analizor lexical structurat. Prin proiectare se disting sarcini oarecum independente in cadrul

analizei lexicale, fiecareia corespunzandu-i o parte distincta a analizorului. La aceasta solutie se ajunge prin stratificarea gramaticii atomilor lexicali. Fiecarui strat ii va corespunde o subfaza a nalizei lexicale.

In figura II. 1.2. se prezinta o astfel de solutie. Transliterarea clasifica caracterele din textul sursa, explorarea depisteaza si clasifica subsirurile atomilor lexicali, iar selectarea definitiveaza clasificarea, elimina caracterele inutile si codifica atomii lexicali (fig. III . 1.2.a). In (fig. III . 1.2.b) sunt prezentate rezultatele prelucarilor celor trei subfaze pentru un text sursa din PASCAL. S-au notat, conventional, cu %XYZ codurile stabilite de prelucrare, unde XYZ este un mnemonic ce precizeaza clasa din care face parte simbolul. Desigur, in cazurile reale aceste coduri sunt numerice.

- 3 -

Se observa ca in sirul explorat apar indicatori catre sirul sursa, in timp ce in sirul selectat acestia sunt inlocuiti cu indecsi in tabela de simboluri. Programarea celor trei subfaze se face folosind pentru transliterare si selectare folosind proceduri. Astfel, transliterarea, inclusiv citirea de pe suport extern este asigurata de o procedura, s-o numim CITCAR, iar selectarea de un set de proceduri, numite si proceduri semantice, care cauta in tablela de simboluri si tabela cuvintelor cheie formand atomi lexicali in forma definitiva. Aceasta va fi solutia adoptata in paragrafele urmatoare. 1.2. MODELUL ANALIZORULUI LEXICAL Dupa cum s-a aratat, sintaxa atomilor lexicali se prezinta sub forma unei gramatici regulate sau a unei gramatici independente de context care genereaza un limbaj regulat. In acest din urma caz exista metode simple de a transforma gramatica intr-o gramatica regulata echivalenta. In general, restrictia impusa gramaticii independente de context pentru a putea fi transformata este ca nici un neterminal sa nu fie autocontinut, adica:

)]()[())()(( ===> sauAANAA O solutie simpla pentru a obtine aceasta conditie este ca in productiile gramaticii sa se foloseasca daca este posibil numai un tip de recursivitate: la stanga sau la dreapta. Odata stabilit tipul limbajului atomilor lexicali si avand o gramatica pentru acest limbaj, problema analizei lexicale apare in primul rand ca o problema de decizie: sa stabileasca despre un sir de caractere daca este sau nu un atom lexical. Pentru a avea o imagine completa, problema de decizie trebuie in continuare completata cu problema codificarii atomilor lexicali si cu problema semanlarii si tratarii erorilor. In legatura cu acesta ultima sarcina, sa reamintim ca in diferitele faze ale compilarii exista sarcini comune ale tratarii erorilor. De acee se obisnuieste ca toate aspectele legate de tratarea erorilor sa se rezolve printr-o colectie de proceduri comune tuturor fazelor. Ele vor fi abordate intr-un capitol separat. Aici vom pune in evidenta doar modul in care se face detectarea erorilor in analiza lexicala. Revenind la problema centrala, cea a deciziei, sa reamintim ca in cazul unui limbaj regulat, instrumentul matematic, modelul formal folosit in acceptarea cuvintelor din limbaj este automatul finit. De asemenea, stim ca problema apartenentei la un limbaj regulat este decidabila. De aceea atuomatul finit poate fi considerat modelul de baza al analizorului lexical. Modelului ii vom adauga la momentul proiectarii si alte facilitati pentru a raspunde mai bine nevoilor analizei lexicale, in primul rand necesitatii de generare a atomilor lexicali. 1.3. PROIECTAREA UNUI ANALIZOR LEXICAL Tratarea gramaticii atomilor lexicali Ne vom ocupa de proiectarea analizorului lexical folosind o gramatica in BNF a atomilor lexicali, redusa ca dimensiuni, dar reprezentativa pentru majoritatea limbajelor de programare. (G0) 10. ::=| 20. ::=|||| 30. ::=|| 40. ::=|const> 50. ::=+|*|= | = |

- 4 -

Gramatica G0 nu este regulata, dar poate fi transformata intr-o gramatica regulata echivalenta marind numarul productiilor si a neterminarelor. De exemplu productiile 4 se pot scrie: ::= 0|1|2|...|9|0|1|...|9. Corespunzator, vom avea un automat finit, mai complex si o programare mai greoaie a analizorului. De aceea se prefera o simplificare a proiectarii prin startificarea gramatici G0, intr-o ierarhie de gramatici mai simple, regulate, deci mai usor de tratat, si care ulterior trebuie cupalte astfel incat, pe ansamblu, limbajul sa ramana acelasi. Stratificarea porneste de la partitionarea multimii de neterminale si stabilirea unei ierarhii intre elementele partitiei. In cazul nostru o asemenea partitionare este: N1={,}

N2= {,,,,} N3={,}

Formam in jurul neterminalelor din cele trei multimi gramatici plecand de la productiile lui G0. Pentru fiecare gramatica vom considera ca terminale, pe langa temrinalele lui G0 si neterminalele din grupul imediat inferior in ierarhie. Noile gramatici sunt urmatoarele: (G1) : ::=| ::=id|const|op|del|com

(G21) :::=lit|lit|cif (G22) :::=cif|cif (G23) :::=+|*|

- 5 -

nivelul inferior, notata cu simbolul terminal resprectiv, a fost parcursa din starea initiala intr-o stare finala. Atingerea starii finale echivaleaza cu efectuarea tranzitiei din diagrama nivelului superior. Deci, un automat aflat pe un nivel inferior trebuie sa transmita nivelului superior informatia de acceptarea a sirului inspectat. Vom avea deci o asamblare a automatelor din fig. III.1.3. cum este cea din fig. III.1.4. Automatele A2 si A3 rezulta dintr-o cuplare speciala a automatelor componente si anume prin suprapunerea starilor initiale alea acestora (se poate concepe si o unica stare initiala din care pleaca -tranzitii spre autoamatele componente). Cuplarea autoamatelor A1, A2,A3 se face in serie : iesirea unuia este intrarea celuilalt. Sa observam insa ca automatul Ai+1 emite un simbol de iesire doar atunci cand a ajuns intr-o stare finala. Simbolul va identifica tocmai aceasta stare. Deoarece obiectivul nostru consta in descrierea functionarii automatului A0, intr-un limbaj de programare trebuie sa completam cele aratate cu inca doua conditii:

a) automatele rezultate din diferitele cuplari trebuie sa fie deterministe; b) orice simbol primit la intrarea unui automat si care nu activeaza nici o tranzitie trebuie sa

conduca la o situatie de neacceptare sau eroare. In exemplul nostru, eliminarea nedeterminismului apare doar in cazul automatului A2. El se

manifesta prin existenata a doua tranzitii din starea initiala pentru simbolul *. Automatul determinist echivalent este cu cel din fig. III.1.5.

In figura poate apare un element nou: marcajul cu * al unor stari finale. Pentru a explica rolul lui sa ne fixam atentia asupra starii 212. Automatul A2 ramane in starea 212 cat timp primeste la intrare lit sau cif deci cat timp se gaseste in interiorul unui identificator. La intalnirea primului simbol diferit de lit sau cif, A2 trebuie sa-si opreasca functionarea, emitand o iesire pentru A1 care sa-l anunte pe acesta ca s-a gasit un identificator. Sa observam insa ca in acest moment automatul A2 a consumat deja un simbol care apartine atomului urmatorl. In figura exista stari finale, de exemplu starile 232, 234, 239, etc., in care avansul in sirul de intrare nu s-a produs. Pentru a-l distinge de acesta, starile care necesita un avans in sirul de intrare sunt marcate cu * Este natural sa dorim uniformizarea situatiei pentru toate starile finale. Solutiile in implementare constau fie in revenirea in sirul de intrare cu un simbol, fie in generalizarea avansului pentru toate starile finale, adica adaugarea unei tranzitii suplimentare pentru starile nemarcata cu *. In continuare vom adopta aceasta ultima solutie. Completarea diagramei de prozitii cu proceduri semantice In proiectarea analizorului lexical, automatul de recunoastere are un simbol orientativ. El arata ca sunt sarcinile analizorului in identificare constructiilor sintactice corespunzatoare atomilor lexicali. Pentru rezolvarea celorlalte doua probleme: semnalarea erorilor si emiterea unor iesiri, in practica proiectarii analizoarelor lexicale se folosesc proceduri semantice asociate tranzitiilor autoamtului de recunoastere. Procedurile lucreaza asupra unor structuri de date pe care le utilizeaza in luarea deciziilor si pe care, eventual, le modifica. Aceste structuri de date alcatuiesc baza de date a analizorului lexical , contextul activitatii lui. Controlul contextului realizat de procedurile semnatice are ca scop restabilirea la sfarasitul analizei a unui atom lexical, a unui context adecvat cautarii urmatorului atom, emiterea unei iesiri corecte care sa reprezinte atomul analizat si semnalarea eroroilor. I) In figura III.1.6. se prezinta diagrama de tranzitii a automatului A3 completata cu procedurile CITCAR si IESCAR. 10 Procedura CITCAR este activata inainte de inceputul functionarii atuotmatului. Rolul ei este sa simuleze canalul de intrare al atutomatului. Pentru aceasta preia din fisierul de intrare caracterul urmator, plasandu-l in variabila globala car. Procedura foloseste un tablou de caractere, linie, ca zona

- 6 -

tamplon intre fisier si variabila car. In aceasta zona, CITCAR depune cate o inregistrare din fisier de indata ce a terminat prelucrarea precedentei. Vom considera inregistrari de lungime variabila avand cel mult 80 caractere si terminand intotdeauna cu un caracter special (carriage return) Descrierea procedurii CITCAR in PASCAL impreuna cu structura datelor necesare este urmatoare: { Fisierul textului de intrare este INPUT } var Linie: packed array [1..81] of char; { Zona tampon} I1: 1..81; { Indicatorul sfirsitului liniei} Ic: 1..81; { Indicatorul caracterului curent din linie} Car: char; { variabila ce contine caracterul curent} Procedure CITCAR; { Citeste urmatorul caracter din INPUT} begin if I1=Ic then begin if eof(INPUT) then begin EROARE(1); Goto 1111 {iesire} end; I1 : =0; Ic : =0; while not eoln do begin I1:=I1+1; read(Car); write(Car); Linie[I1] :=Car end; writeln; I1:=I1+1; Read(Linie[I1]) end; Ic:=Ic+1; Car:=Linie[Ic] end; P.III.1.1. 20 Procedura IESCAR formeaza iesirea automatului A3. Aceata iesire reprezinta o dubla informatie: clasa caracterului si caracterul propriu-zis. Iesirile corespunzatoare tranzitiilor atutomatului A3 sunt obtinute prin apelurile procedurii IESCAR asociate tranzitiilor (fig. III.1.6.). Notatiile %... reprezinta coduri numerice ce se pot concretiza la implementare. Cele doua coduri de iesire se gasesc in variabilele clcar si car. Plasarea unei valori in clcar este strans legata de functionarea automatului si anume de atingerea unei anumite stari si consta intr-o simpla atribuire. De aceea, procedura IESCAR o vom ingloba in procedura de simulare a atutomatului A3 (vezi 1.5.4.). II) In fig III.1.7. se afla diagrama de tranzitii a autoamatului A2 completata cu procedurile semnatice AD, CARNOU si IES. Diagrama prezinta o diferenta fata de cea din figura III.1.5. : tranzitia datorata lui %BL in starea 16. Aceasta modificare, fara sa fie absolut necesara introduce o

- 7 -

sporire a eficientei implementarii analizorului lexical. Se bazeaza pe faptul ca in marea majoritate a limbajelor de programare, pentru delimitarea diferitilor atomi lexicali este suficient un blanc. Daca sunt mai multi, ceilalti nu aduc nimic nou, deci nu pot fi ignorati de analiza lexicala.

1) Pentru identificatori si constante procedura AD adauga in tabloul de caractere sir caracterul primit la intrare. Tabloul va acumula toate caracterele identificatorului sau constantei analizate. Rezulta deci o limitare a lungimii acestora la lungimea tabloului (lm). Structurile de date utilizate precum si textul procedurii AD sunt in P.III.1.2.: var Sir: packed array [1..Lm] of char; {Lm este o constanta} K: 0..Lm; Car: char; ...................... Procedure AD; {Adauga un caracter} begin if K

- 8 -

simboluri. Procedura intoarce adresa la care se gaseste identificatorul, completand cu ea atomul lexical si anume a doua informatie din atom. Procedura CAUTAID mai poate avea o functie: sa verifice daca identificatorul nu este cuvant cheie, in care caz ea va schimba atomul lexical, inlocuind clasa %ID cu %DO, %END, %THEN etc. in functie de cuvantul depistat. Noi vom presupune o procedura speciala pentu aceasta functie: CUVCHEIE, apelata de CAUTAID si care actualizeaza variabila clatom cu codul cuvnatului cheie gasit. Detalii privind proiectarea procedurii CAUTAID vor fi prezentate in capitolul referitor la tabela de simboluri. 2) Procedura CAUTAC determina valoarea constantei numerice din tabela sir si cauta in tabela de constante (sau in tabela de simboluri daca aceasta contine si constantele) daca se gaseste o constanta cu aceiasi valaore. Daca nu se gaseste, constanta din sir este plasata in tabel. Procedura determina adresa intrarii corespunzatoare constantei si memoreaza adresa in atomul lexical. Procedura CAUTAC este in multe privinte similara procedurii CAUTAID. 3) Procedura SEL discerne blancul de ; determinand tranzitii diferite spre starea 1 pentru blanc si spre starea 5 pentru :. In implementarea acesta procedura poate fi evitata dupa cum se va vedea in paragraful urmator. 1.4 IMPLEMENTAREA UNUI ANALIZOR LEXICAL Aceasta ultima etapa a elaborarii unui analizor lexical are ca obiectiv principal descrierea in limbaj de programare a functionarii diagramelor de tranzitii imbogatite cu procedurile semantice. In principiu, fiecarui nivel din stratificarea initiala a gramaticii i se poate asocia o procedura de descriere a functionarii automatului nivelului respectiv. In cazul prezentat anterior, automatele nivelurilor 3 si 1 sunt extrem de simple si de aceea ele s-ar putea reuni intr-o singura procedura, analizorul lexical. Vom prefera sa implementam pe A1 si pe A2 intr-o procedura, de fapt chiar analizorul lexical ANLEX, iar pe A3 intr-o alta procedura care, asa cum am vazut, este CARNOU. Inscrierea algoritmului de simulare a comportarii unui automat finit, putem opta pentru una din urmatoarele doua metode:

a) folosim o tabela de tranzitii a autoamatului (completata pentru fiecare intrare cu numele sau adresele procedurilor semantice) si o procedura ce selecteaza pe baza simbolului de la intrare si starii curente starea urmatoare si procedurile semantice de executat.

b) descriem explicit prin transferuri, in cadrul algoritmului tranzitiile de la o stare la alta mijlocite de simbolul de intrare.

Pentru implementarea procedurilor CARNOU si ANLEX vom folosi metoda b). Prezentam in continuare, in limbajul PASCAL, cele doua proceduri (P.III.1.3. si P.III.1.4.)

type Tcar=(Lit, Cif, Pl, Ml, Sl, Lt, Gt, El, Le, Ne, Ge, Pv, Bl}; var Clcar: Tcar; {Clcar si Car formeaza interfata lui CARNOU cu ANLEX } Car: char; procedure CARNOU; {Simuleaza automatul A3} Label 222; procedure CITCAR; begin .................. end; {Citcar}

- 9 -

begin 222: CITCAR; {CITCAR actualizeaza Car} if Car in [A..Z] then Clcar :=Lit else Clcar :=Cif else case Car of +: Clcar:=Pl; *: Clcar :=Ml; / : Clacar :=Sl; : Clcar :=Gt; = : Clcar :=El; ; : Clcar :=Pv; : Clcar :=B1; oherwise begin EROARE(2); Goto 222 end end end; P. III.1.3.