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 intruna
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.
Documentul este oferit gratuit,
trebuie doar să te autentifici in contul tău.
