Construirea arborilor sintactici abstracti

Construirea arborilor sintactici abstracti

Utilizarea arborilor sintactici abstracti ca reprezentare intermediara permite ca procesul de traducere sa se faca separat de analiza sintactica. Prin aceasta separare se pot evita 2 categorii de restrictii care ar putea sa apara la tratarea impreuna a celor doua faze:

1. gramatica adecvata pentru analiza sintactica ar putea sa nu reflecte ierarhizarea constructiei unui limbaj de programare, asa cum ar fi necesara analizei semantice

ex: o procedura poate fi privita din punct de vedere sintactic ca o lista de instructiuni, in timp ce semantic este necesar sa se cunoasca fluxul instructiunilor

metoda de analiza sintactica aleasa impune ordinea in care sint considerate nodurile din arborele sintactic si aceasta ordine s-ar putea sa nu corespunda cu ordinea in care devin disponibile informatiile despre constructia programului.

Ex.: pentru C se evita problema prin construirea de arbori sintactici abstracti doar pentru partea de declaratii

Arbori sintactici abstracti

Reprezinta o forma condensata a arborilor sintactici obisnuiti, utila tot pentru reprezentarea constructiilor unui limbaj de programare.

Ex:

<instr> -> if B then <instr> else <instr>

arborele sintactic obisnuit: <instr>

if B then <instr> else <instr>

arborele sintactic abstract: if-then-else

B <instr> <instr>

In a.s.a. operatorii si cuvintele cheie nu apar ca si frunze ci sint asociate cu nodul interior care este parintele frunzelor.

Un alt model de simplificare tipica este eliminarea nodurilor inutile provocate de productiile singulare ( concentrarea lanturilor de productii singulare).

Ex:  E -> E + T | T

T -> T * F | F

F -> cifra

pentru propozitia 5 + 2 * 3

arbore sintactic obisnuit:

E

E + T

T T * F

F F 3

5 2

+

arbore sintactic abstract: 5 *

2 3

Traducerea dirijata de sintaxa se poate rezolva identic, indiferent daca se bazeaza pe arbori sintactici abstracti sau pe arbori sintactici obisnuiti, analiza semantica avand la baza atasarea la noduri a atributelor semantice corespunzatoare.

6.2.2. Construirea arborilor sintactici abstracti pentru expresii

Principial, operatia de construire a arborilor sintactici abstracti pentru o expresie este similara cu traducerea expresiei respective in forma postfix.

Metoda concreta: se construiesc subarborii pentru fiecare subexpresie incepand de la simplu la complex, creind cate un nod pentru fiecare operator si operand. Fiii unui nod operator vor fi tocmai radacinile subarborilor care reprezinta operanzii acelui nod. Nodurile arborilor sintactici abstracti pot fi implementate ca inregistrari cu urmatoarele campuri:

pentru un nod operator : un camp identifica operatorul si se numeste eticheta nodului, iar celelalte campuri sunt pointeri catre nodurile operanzilor.

pentru nod frunza: un camp identifica felul nodului si un al doilea camp va fi un atribut care poate fi o valoare, un pointer

Daca arborele sintactic abstract se utilizeaza in procesul de traducere semantica, nodurile pot contine si alte campuri suplimentare pentru a pastra valorile atributelor atasate nodului, sau poiteri spre aceste valori.

Crearea nodurilor arborilor sintactici abstracti pentru expresii cu operatori binari si operanzi numere si identificatori se face apeland urmatoarele functii:

(fiecare functie creaza nodul si intoarce un pointer spre nodul creat)

nod(op,stanga,dreapta) - creaza un nod operator cu eticheta op si doua campuri continand pointeri la nodurile operanzi

frunza(id, intrare) - creaza un nod identificator, al doilea camp fiind pointer spre tabela de simboluri unde se gaseste inregistrat identificatorul

frunza (num, val) - creaza un nod numar cu eticheta num, iar al doilea camp contine valoarea numarului

Consideram expresia a - 4 + c si construim arborele sintactic utilizand procedurile de mai sus:

+

p5

p3 p4

p1 p2 TS

TS

Notand cu p1..p5 pointerii la nodurile din arbore si cu int_a, int_c pointerii la identificatorii a si c in tabela de simboluri, arborele de mai sus este construit prin urmatoarea secventa de apeluri ale functiilor nod si frunza:

p1 := frunza (id, int_a);

p2 := frunza (num, 4);

p3 := nod ( -, p1, p2);

p4 := frunza ( id, int_c);

p5 := nod (+, p3, p4);

Prin secventa de mai sus, arborele s-a construit bottom-up iar radacina arborelui final este p5.

Exemplu de definite dirijata de sintaxa prevazuta cu reguli semantice pentru construirea arborilor sintactici abstracti

Consideram o definitie S-atributata pentru gramatica expresiilor, continand identificatori si numere, iar ca operatori, operatorii + si -. Regulile semantice vor stabili apelurile functiilor nod si frunza care construiesc arborele sintactic abstract.

Productia Regulile semantice

E -> E1 + T E.p := nod( +, E1.p, T.p)

E -> E1 - T E.p := nod( -, E1.p, T.p)

E -> T E.p := T.p

T -> (E) T.p := E.p

T -> id T.p := frunza(id, id.intrare)

T -> num T.p := frunza( num, num.val)

Neterminalele E si T au cate un atribut sintetizat p, reprezentand pointerul spre subarborele corespunzator acelui neterminal.

Arborele sintactic adnotat obisnuit precum si arborele sintactic abstract sint urmatoarele:

E p

E p + T p

E p - T p id

T p num

+

-

id

id

num

4

id

c

a

Arborele sintactic obisnuit este punctat. Nodurile care contin neterminalele E si T utilizeaza atributul sintetizat p pentru a retine adresele nodurilor corespunzatoare din arborele sintactic abstract. Regulile semantice asociate cu ultimele 2 productii creaza noduri frunza in arborele sintactic abstract. Aceste noduri au etichetele id respectiv num, iar campurile id.intrare si num.val reprezinta atributele lexicale returnate de analizorul lexical odata cu atomii lexicali in cauza.

Observatii

arborele sintactic abstract continand in noduri atomii lexicali ai expresiei este un arbore construit fizic si reprezinta rezultatul traducerii, in timp ce arborele sintactic punctat poate exista si numai in sens figurativ;

aceasta definitie dirijata de sintaxa poate fi implementata atat prin metode ascendente cat si prin metode descendente; in cazul in care se utilizeaza o metoda ascendenta, evidenta valorii atributelor pentru noduri este tinuta in stiva de analiza.

Grafuri orientate aciclice

Reprezinta un caz particular de arbori sintactici abstracti, in care se memoreaza expresiile comune o singura data. Ca si arborele sintactic abstract, un graf orientat aciclic are cate un nod pentru fiecare subexpresie a expresiei. Nodurile interioare reprezinta operatorii, iar fii sai sint operanzii.

Diferenta consta in faptul ca un nod dintr-un graf orientat aciclic reprezentand o expresie comuna are mai multi parinti.

Exemplu: a+ a * ( b - c) + ( b - c) * d

+

+ *

* d

a -

b c

Nodul frunza a are doi parinti, corespunzator celor doua aparitii.

Definitia dirijata de sintaxa din subcapitolul anterior va construi un graf orientat aciclic in locul arborelui sintactic abstract daca se modifica operatorii pentru construirea nodurilor astfel:

* inainte de construirea unui nod nou se verifica daca nu exista deja un nod identic in arbore si in caz afirmativ, se va returna pointerul spre nodul gasit;

Presupunand ca functiile din $6.2.3. s-au modificat in mod coresounzator, secventa de apeluri pentru expresia de mai sus este:

p1 := frunza(id,a);

p2 := furnza(id,a);

p3 := frunza(id,b);

p4 := frunza(id,c);

p5 := nod(-,p3,p4);

p6 := nod(*,p2,p5);

p7 := nod(+,p1,p6);

p8 := frunza(id,b);

p9 := frunza(id,c);

p10:= nod(-,p8,p9);

p11:= frunza(id,d);

p12:=nod(*,p10,p11);

p13:= nod(+,p7,p12);

Implementarea statica si dinamica a arborilor sintactici abstracti (grafurilor orientate aciclice)

Implementarea statica se poate face cu un tablou continand cate un rand pentru fiecare inregistrare. Primul camp din inregistrare determina natura nodului.

Exemplu: i := i + 10

:=

+

id 10

pointer in TS pentru i

Indicele in tablou corespunzator unui nod poarta numele de numar de valoare al acelui nod.

Algoritmul urmator pentru construirea unui nod intr-un graf orientat aciclic pe baza numarului de valoare poate fi aplicat pentru ambele variante de implementare:

Se numeste semnatura unui nod operator tripletul <op,st,dr>; analog definim semnatura unui nod frunza: <id,pTS> respectiv <num, val>. Algoritmul primeste la intrare elementele semnaturii si furnizeaza la iesire un pointer spre un nod cu aceasta semnatura. Pentru aceasta mai intai se cauta intr-o evidenta a nodurilor daca nu exista deja creat un nod cu acea semnatura. Daca exista, se returneaza nodul anterior, daca nu exista se creaza un nod nou si se returneaza acesta. Procesul de cautare poate fi facut mai eficient utilizand mai multe subliste de noduri si o functie de hashing h pentru a determina sublista. h(op,dr,st) => numarul sublistei.

Sublistele pot fi simplu inlantuite iar inceputurile lor se pastreaza intr-un tablou.

Daca nodul nu se gaseste in sublista respectiva se creaza un nod nou care se va introduce in aceasta sublista unde va fi gasit cu siguranta la eventualele cautari ulterioare.

6.3. Evaluarea ascendenta a definitiilor S-atributate

Implementarea unei translatari nu se poate realiza pentru o definitie dirijata de sintaxa arbitrara. Algoritmii din acest domeniu se refera la clase de definitii dirijate de sintaxa particulare, care acopera insa domeniul limbajelor de programare uzuale. Un prim exemplu de astfel de clase particulare pentru care exista metode de traducere eficiente sint definitiile S atributate.

Pentru o definitie dirijata de sintaxa, analiza sintactica ascendenta poate evalua atributele sintetizate in timpul analizei sirului de intrare. Pe masura ce sint evaluate, atributele semantice care sint asociate cu simbolurile gramaticale se pot pastra chiar in stiva de analiza. Valorile noilor atribute sintetizate se calculeaza la fiecare reducere pe baza valorilor atributelor simbolurilor aflate in partea dreapta a productiei, atribute care se gasesc in acel moment in locatii consecutive in varful stivei. Noile atribute sint calculate corespunzator cu simbolul din partea stanga a productiei, cel care va ramane in varful stivei dupa reducere. In consecinta, stiva va fi extinsa cu campuri suplimentare pentru a pastra si valorile atributelor semantice.

Considerand situatia frecventa din practica in care unui simbol gramatical i se asociaza cel mult un atribut sintetizat, stiva analizorului sintactic (notat cu 'Stare'), care deja contine starile, se extinde cu un tablou suplimentar pentru valorile atributelor.

Stare valoare

x x.X

y y.Y

varf => z z.Z

In principiu, daca simbolul din stare_i este A atunci val_i contine atributul sintetizat al lui A, calculat si asociat cu simbolul la nodul respectiv din arborele sintactic. Daca un simbol nu are (intamplator) atribut sintetizat, locatia corespunzatoare din tabela val exista, dar nu este definita.

Atributele sintetizate se evalueaza inainte de fiecare reducere. De exemplu, consideram urmatoarea productie cu regula semantica asociata:

A -> XYZ A.a := f(X.x,Y.y, Z.z)

Inainte de reducere, val[vs]=Z.z;. val[vs-2]:=X.x. Cand se ajunge la reducere, se calculeaza valoarea A.a, se face reducerea adica varful stivei scade cu 2, se pune in varful stivei A iar in stiva val[vs] se memoreaza A.a.

Productia Reguli semantice Fragmente de cod

L-> E nl  tipareste E.val tipareste (val[vs-1])

E-> E1 + T E.val := E1.val + T.val val[nvs]:= val[vs-2]+val[vs];

E-> T E.val := T.val

T-> T1 * F  T.val := T1.val * F.val val[nvs]:= val[vs-2]* val[vs]

T-> F  T.val := F.val

F-> (E) F.val := E.val val[nvs]:=val[vs-1];

F-> cifra F.val := cifra.lexval

Valoarea atributului cifra, este furnizata de analizorul lexical prin lexval, ceea ce presupune ca atunci cand analizorul sintactic deplaseaza o cifra din intrare in stiva, in stare[vs] se va inregistra atomul cifra , iar in val[vs] valoarea atributului sau.

Pentru evaluarea atributelor semantice, analizorul sintactic trebuie completat cu executarea fragmentelor de cod corespunzatoare fiecarei productii. Aceste fragmente sint executate in analizor imediat inainte de a face reducerea, lucru posibil deoarece fiecare reducere determina productia ce trebuie aplicata iar evaluarea este asociata cu productia.

Fragmentele de cod s-au obtinut direct din regulile semantice, inlocuind numele atributelor cu pozitii in stiva val. Acele productii a caror aplicare la reducere nu determina modificari in stiva val, nu au asociate fragmente de cod.

Din fragmentele de cod nu rezulta felul in care se prelucreaza variabilele vs si nvs, deoarece modificarile lor sint in functie de procesul de reducere, facand parte din analiza sintactica propriu-zisa. In principiu, daca se reduce o productie cu r simboluri in partea dreapta, nvs:=vs-r+1;

Consideram sirul de intrare

3 * 5 + 4 nl

Stiva Stare se completeaza cu simbolurile gramaticale corespunzatoare, iar in locul atomului cifra se va pune chiar valoarea cifrei.

Intrare  stare sau val productia

simbol gram.

3*5+4nl - -

*5+4nl  3 3

*5+4nl  F 3 F -> cifra

*5+4nl  T 3 T -> F

5+4nl T* 3_

+4nl T*5 3_5

+4nl T*F 3_5 F -> cifra

+4nl T 15 T -> T * F

+4nl E 15 E -> T

4nl E+ 15_

nl E+4 15_4

nl E+F 15_4 F -> cifra

nl E+T 15_4 T -> F