Exemple de aplicare a tehnicilor de compilare dirijate de sintaxa

Exemple de aplicare a tehnicilor de compilare dirijate de sintaxa

In acest capitol se va proiecta si realiza un program complet care sa traduca expresiile infix in forma postfix. Din punct de vedre al activitatii desfasurate, programul reprezinta partea de front-end a unui compilator deoarece primeste la intrare un sir de aractere reprezentand expresia initiala si genereaza kla iesire expresia transformata in postfix sau chiar va genera cod intermediar pentru evaluarea expresieie postfix.

Tehnica de compilare de baza care va fi utilizata este traducerea dirijata de sintaxa din capitolul 6.

Observatii:

a.       => 9 5 - 2 +

b.       Notatia postfix przinta avantajul ca poate fi transformata direct in cod virtual pentru un calculator abstract care efectueaza operatii aritmetice pe principiul stivei

Pentru inceput se va construi un program simplu care accepta doar expresii formate doar dintr-o singura cifra si operatorii + , _. In final programul va fi extins pentru expresii mai generale. Structura programului compilator ce va fi realizat este urmatorul:

Analizor lexical

Translator dirijat de sintaxa

sir de intrare sir de atomi reprezentare intermediara

Translatorul dirijat de sintaxa va fi un analizor sintactic combinat cu un generator de cod virtual. In ceea ce priveste analizorul lexical, pentru prima varianta a programului ( operanzii sunt doar cifre) el este foarte simplu, deoarece fiecare caracter este un atom. In varianta a doua el trebuie complicat in sensul ca va accepta ca si atomi urmatoarele combinatii de caractere: numere, identificatori, cuvinte cheie (div, mod, not).

Observatie: In notatia postfix nu sunt necesare paranteze deoarece pozitia si aritatea operatorilor conduc la un inteles unic si bine determinat pentru expresia respectiva.

Ex : (9-5) *2 => 95-2*

Exemplu de translator pentru expresii simple

Specificatia initiala a tramnslatorului ca schema de traducere este urmatoarea:

<expr> -> <expr>+<term>

<expr> -> <expr>-<term>

<expr> -> <term>

<term> -> 0

<term> -> 1

<term> -> 2

s.a.m.d.

<term> -> 9

Gramatica inclusa in schema de traducere este recursiva la stanga. Aceasta recursivitate trebuie eliminata pentru a aplica translatarea descendent recursiva. Tehnica de eliminare a recursivitatii este cea cunoscuta de la analiza sintactica (cap 4), implicand insa si includerea in productii a atrivutelor semantice (cap 6).

A -> A alfa | A beta | gamma => A -> gamma R

R -> alfa R | beta R | lambda

In exemplul nostru <expr > este A, alfa este +<term> iar beta este -<term> , gamma=<term>. Rezulta urmatoarea schema de traducere transformata:

<expr> -> <term><rest>

<rest> -> +<term> <rest>

<rest> -> -<term> <rest>

<rest> -> lambda

<term> -> 0

<term> -> 1

<term> -> 2

s.a.m.d.

<term> -> 9

Traducerea efectiva a unui sir de intrare concret (9-5+2) poate fi pusa in evidenta prin traversarea in adancime a urmatorului arbore sintactic:

<expr>

<term> <rest>

- <term> <rest>

5 + <term> <rest>

lambda

Translatorul descendent recursiv se elaboreaza in felul urmator: se construieste cate o functie pentru ficare neterminal : expr, rest, term. Se mai construiesc functii ajutatoare rezultate pe parcurs dupa care se elaboreaza programul principal in care trebuie sa apara doua operatii esentiale : citirea primului caracter si apelul functiei expr().

Expr()

term()

else eroare(0);

rest()

else if (simb=='-')

else ;

Functia corespunde este cea prexzentata in exemplele capitolelor anterioare si are rolul de a pune in corespondenta un atom anume cu simbolul de anticipare si de a avansa in sirul de intrare. In cazul simplu in care fiecare atom este un singur caracter, functia compara si citeste caractere. Codul functiei pentru un anumit neterminal urmareste cu fidelitate partile drepte ale productiilor acelui neterminal, existand cate o ramura pentru fiecare parte dreapta Acest cod poate fi optimizat in continuare prin inlocuirea apelurilor recursive ale functiilor cu iteratii.

In situatia in care o functie se incheie cu apelul recursiv catre ea insasi (ex. apelul functiei rest), acest apel se numeste recursiv final si poate fi imnlocuit simplu si direct printr-un salt la inceputul functiei ca mai jos:

rest()

else if (simb=='-')

else ;

Prin aceasta modificare, singurul apel al fucntiei rest a ramas cel din expr(), motiv pentru care se poate combina corpul functiei expr()si rest(), rezultand o functie unica. In plus, tinand cont de faptul ca in limbajul C se poate realiza repetarea unei instructiuni de un numar nedefinit de ori prin constructia while(1) instr; , ciclu din care se poate iesi cu break, rezulta urmatoarea varianta pentru codul final comun al functiilor expr() si rest():

Expr()

else if (simb=='-')

else break;

# include <ctype.h>

int simb;

main()

void corespunde(int t)

void eroare()

Observatie:

variabila simb a fost declarata de tip intreg si nu caracter, avand in vedere dezvoltarea ulterioara a programului in care atomii vor fi grupuri de caractere reprezentand numere, identificatori sau cuvinte cheie si simb va fi un numar veritabil ( atomii sunt codificati numeric)

Incorporarea tabelei de simboluri

Tabela de simboluri este o structura de date principala a compilatorulkui, ea contone informatii despre diferitele constructii ale programului sursa si in special despre identificatori. In general informatiile sunt detectate si inregistrate in fazele de analiza si se utilizeaza in fazele de sinteza, in special pentru generarea codului obiect. De exemplu la analiza lexicala cand se construieste un identificator se creaza inregistrarea corespunzatoare in TS si se introduce in acea inregistrare lexema identificatorului. In fazele urmatoare de analiza, intrarea se completeaza cu informatii suplimentare, de exemplu felul entitatii (constanta, tip, variabila), tipul sau, deplasamentul in memorie. Faza de generare de cod va utiliza aceste informatii pentru a genera codul obiect corect.

Interfata cu TS este asigurata de rutine care au urmatoarele 2 functii ptincipale: inregistrarea unei lexeme si regasirea unei lexeme introduse anterior.

Ca urmare sunt necesare urmatoarele doua operatii:

insereaza(s,t)- va scrie o noua inregistrare in tabela, in care introduce sirul s si atomul t reprezentand codlex si returneaza indicele sau pointerul intrarii din TS la acea inregistrare

cauta(s) - returneaza indicele sau pointerul intrarii in TS corepsunzator lui s sau 0 daca nu este gasit,

In aceasta maniera orice tentativa de inserare trebuie precedata de una de cautare.

Tratarea cuvintelor cheie

Poate fi tratata in aceeasi maniera ca si cuvintele utilizator. Pentru exemplu consideram atomii div si mod. Ei vor fi introdusi in TS la initializarea tabelei prin urmatoarele apelrui:

insereaza("div",div);

insereaza("mod",mod);

Daca procedam asa, roice apel ulterior cauta("div") va returna acest atom div introdus initial, ceea ce asigura ca div sa nu poata fi utilizat ca identificator obisnuit.