Analizoare sintactice LALR(1) Analiza tipurilor

Tabela de simboluri. Analiza de domeniu





Rolul tabelei de simboluri in compilare

Tabela de simboluri (TS) este o structura de date destinata stocarii de informatii referitoare la identificatorii care apar intr-un text sursa , pe durata procesului de compilare.
Informatiile din TS sunt necesare pentru:

Informatii continute de TS
In cazul limbajelor sursa care definesc programe structurate pe blocuri (functii si/sau proceduri) care pot sa apara pe mai multe nivele de imbricare, in TS ar trebui sa apara , in principiu, urmatoarele informatii:

a, b, c : record x : tip1; y : tip2 end;


TS trebuie sa contina toti identificatorii din textul sursa VIZIBILI la un moment dat. De aceea, cand se detecteaza sfarsitul unui subprogram, intrarile din TS aferente parametrilor formali si variabilelor locale din subprogramul respectiv vor fi eliberate.
Se observa ca unele informatii din TS au sens doar pentru anumite categorii de simboluri. De aceea, o parte dintre campurile TS pot fi grupate in structuri de tip union (record cu variante). De exemplu: ADREL (care nu are sens pentru campuri de structuri) se poate grupa cu DEPLREC (care are sens doar pentru campuri de structuri).

Functii de acces la TS

Asupra TS se pot efectua doua operatii de baza :

Rezultatul returnat de functiile de acces la TS va fi utilizat in continuare pentru:
Indiferent de forma de organizare a TS, in cele ce urmeaza vom utiliza urmatoarele notatii:


Completarea informatiilor din TS

Modul de obtinere si completare a informatiilor in TS va fi ilustrat prin exemple, utilizand productii ale gramaticii propuse in Anexa B. Pe aceste productii vor fi marcate, cu ajutorul unor patratele numerotate, locurile in care diversele informatii devin disponibile in decursul analizei textului sursa, aratandu-se ce operatii trebuie efectuate in momentele respective. Pentru a evita confuziile, la grupurile de productii unde un anumit simbol gramatical apare de mai multe ori se numeroteaza fiecare aparitie a simbolului respectiv.
Trebuie precizat faptul ca pentru anumite campuri din TS este necesar sa se prevada cate o valoare speciala de initializare, care sa indice faptul ca, la un moment dat campurile respective sunt inca necompletate. Din aceasta categorie de campuri fac parte: VAL  si ADR_START. Cum, in mod normal, cele doua campuri pot contine doar valori pozitive, se poate adopta ca valoare de tip "undefined" valoarea -1.
In vederea completarii campurilor din TS referitoare la adrese, vom folosi urma toarele variabile:
 
ICOD -indice in tabela TAB_COD, actualizat de catre functiile de generare de cod (v. Lucrarea nr.11). Este o variabila globala a compilatorului si se utilizeaza pentru completarea campurilor INCDOM si ADR_START din TS;
VNIVEL -valoarea curenta a nivelului de imbricare. Este o variabila globala si se foloseste la completarea campului NIVEL, iar modul de actualizare a ei este dat aici;
VADREL -valoarea curenta a deplasamentului unei variabile locale sau parametru dintr-un bloc de program. Se utilizeaza pentru completarea campului ADREL si se va reprezenta ca variabila locala/atribut in procedurile de prelucrare a neterminalelor Declar_functie, Declar_procedura, respectiv Program_sursa;
IDEPLAS -valoarea curenta a deplasamentului unui camp dintr-o structura . Se utilizeaza pentru completarea campului DEPLREC si se va reprezenta ca variabila locala /atribut in procedurile de prelucrare a neterminalului Tip_struct;
VDIMV -dimensiunea spatiului alocat variabilelor unui bloc de program. Se utilizeaza pentru completarea campului DIM_VAR si se va reprezenta ca variabila locala /atribut Ón procedurile de prelucrare a neterminalului Sectiune_var;
VNRPAR -numarul de parametri ai unei functii/proceduri. Se utilizeaza pentru completarea campului NR_PAR si se va reprezenta ca variabila locala/atribut in procedurile de prelucrare a neterminalelor Declar_functie, respectiv Declar_procedura
ST_BLOC -o stiva in care se memoreaza indicii intrarilor din TS care contin numele blocurilor de program active din punct de vedere al compilarii la un moment dat; adaugarea unui element in aceasta stiva se face imediat dupa inserarea unui nume de functie/procedura in TS, iar eliminarea din stiva se opereaza la intalnirea sfarsitului unui subprogram. Rolul acestei stive este de a usura accesul la informatiile legate de numele unui subprogram pe durata compilarii corpului subprogramului respectiv.
VSTB -indicatorul varfului stivei ST_BLOC.

 
 

Inserari de simboluri

Declar_const -> identificator = Expresie_statica  ;

Se insereaza simbolul 'identificator' in TS; se completeaza campurile: Fie loc indicele intrarii din TS alocate la inserare. Se face observatia ca valoarea loc trebuie memorata intr-o variabila locala /atribut care se asociaza cu neterminalul Declar_const;
Se completeaza campul VAL al intrarii loc din TS, cu ajutorul valorilor atributelor Atrib_tip si Atrib_val, obtinute in urma prelucrarii neterminalului Expresie_statica, si anume: lui VAL i se atribuie rezultatul returnat de functia InsertConst (Atrib_tip, Atrib_val) (v. Lucrarea nr.1 si Anexa D).

 

Declar_var -> Lista_id1 : Tip ;
Lista_id  -> identificator | Lista_id2 , identificator 
Tip  -> Tip_simplu | Tip_tablou | Tip_struct 
Tip_tablou -> array [Expresie_statica .. Expresie_statica ] of Tip_simplu
Tip_struct -> record  Lista_campuri end
Lista_campuri -> Decl_simpla  | Lista_campuri ; Decl_simpla 
Decl_simpla -> Lista_id3 : Tip_simplu
Tip_simplu -> integer | real | char
Se insereaza simbolul 'identificator' in TS; se completeaza campul NIVEL - cu valoarea curenta a variabilei VNIVEL; se contorizeaza identificatorii care apar in Lista_id1 (valoarea acestui contor va constitui un atribut al neterminalului Lista_id ).

Pentru toti identificatorii din Lista_id1 inserati se completeaza campurile:

Pentru toti identificatorii din Lista_id1 inserati se completeaza campurile:

Pentru toti identificatorii din Lista_id1 inserati se completeaza campul CLASA - cu 'nume structura '.

Pentru toti identificatorii din Lista_id3 inserati se completeaza campurile:

Pentru toti identificatorii din Lista_id1 inserati se completeaza campurile: DEPLREC si LISTA_REC.

Pentru toti identificatorii din Lista_id1 inserati se completeaza campul ADREL.

Declar_functie -> function Antet_subprog : Tip_simplu   ; Bloc  ;
Antet_subprog  -> identificator  Param_formali
Param_formali  -> epsilon | (Lista_param_form  )

Lista_param_form  -> Declar_paramLista_param_form ; Declar_param
Declar_param -> Declar_simpla   | var Declar_simpla   
Bloc -> Sectiune_const  Sectiune_var   Sectiune_decl_subprog    Instr_comp

 

  Se insereaza simbolul 'identificator' in TS; se completeaza campurile: apoi se depune in stiva ST_BLOC indicele intrarii in TS unde s-a facut inserarea.
Pentru toti identificatorii din Lista_id (neterminal care apare in productia Decl_simpla) se completeaza campurile:
Ca si la  , dar campul CLASA se completeaza cu 'nume parametru de intrare-iesire' (adica parametru transmis prin adresa ).
  Pentru toti identificatorii din Lista_param_form se completeaza campul ADREL.
Pentru numele functiei se completeaza campurile TIP, NR_PAR si LISTA_PAR .
Pentru numele functiei se completeaza campul DIM_VAR.
Pentru numele functiei se completeaza campul ADR_START - cu valoarea curenta a variabilei ICOD.
Se decrementeaza variabila VNIVEL si se elibereaza spatiul din TS ocupat de parametrii si variabilele locale ale functiei; se elimina elementul din varful stivei ST_BLOC.

Pentru proceduri si pentru numele programului principal se procedeaza ca si in cazul functiilor, cu observatia nu intereseaza campurile TIP si ADREL.

Referiri ale simbolurilor

Referirea simbolurilor apare in sirurile derivate din neterminalele Apel_proc, Variabila, Factor_static si Factor. In principiu, orice aparitie a atomului identificator in productiile respective trebuie sa fie insotita de o cautare in TS, in sens descrescator al valorii campului NIVEL. Daca operatia se termina cu esec, se va semnala o eroare de tipul 'identificator nedeclarat'. Daca simbolul este gasit, cade in sarcina analizorului semantic sa verifice daca atributele simbolului corespund contextului in care a avut loc referirea (v. Lucrarea nr.9).
 

Tehnici de organizare a TS

In cazul organizarii TS ca stiva , atat ordinea logica cat si cea fizica a simbolurilor in tabela coincid cu ordinea de aparitie in textul sursa. Eliberarea spatiului din tabela la intalnirea sfarsitului unui bloc se face simplu: se parcurge stiva spre baza pana la intalnirea primului simbol pentru care campul NIVEL are o valoare mai mica decat simbolul din varf. De asemenea este simplificata si operatia de completare a unor campuri din tabela pentru care informatiile necesare se obtin mai departe de locul in care au aparut simbolurile in cauza.
Dezavantajul acestui mod de organizare l-ar putea constitui timpul de cautare, in situatiile in care in TS se afla foarte multe simboluri, deoarece cautarea trebuie facuta secvential.

Tabela hashing permite cautarea rapida a simbolurilor. In functie de structura de date concreta aleasa pentru implementare, eliberarea spatiului alocat blocurilor devenite 'inactive' din punct de vedere al domeniului de vizibilitate, se poate face rapid (si anume, daca se aloca pentru fiecare nivel de imbricare cate o tabela de chei hashing separata). Completarea retroactiva a unor campuri din TS este simplificata daca ordinea fizica in care sunt plasate simbolurile coincide cu ordinea lor textuala . In caz contrar, sunt necesare variabile suplimentare pentru a memora locatiile din TS unde se afla simbolurile implicate.
Fata de stiva, tabela hashing prezinta dezavantajul ca ocupa mai mult spatiu, din cauza campurilor de legatura. Alegerea formei de organizare a TS va fi dictata de criteriile de performanta impuse compilatorului (timp sau spatiu).

Desfasurarea lucrarii

Se va implementa o TS cu structura descrisa in paragraful Informatii continute de TS, precum si functiile de acces la ea. Tehnica de organizare va fi indicata de catre conducatorul lucrarii. Pentru apelarea functiilor de acces la TS trebuie scrise secvente de cod (rutine semantice) care realizeaza actiunile descrise in paragraful Inserari de simboluri, corespunzator fiecarui marcaj. Asamblarea rutinelor semantice cu analizoarele sintactice proiectate in cadrul lucrarilor anterioare, precum si modul de gestionare a informatiilor necesare completarii TS sunt prezentate cu ajutorul unor modele in Anexa D.
Pentru testarea corectitudinii modulului de gestiune a TS se vor tipari informatiile completate in TS la fiecare simbol inserat, iar in cazul referirilor de simboluri se va tipari rezultatul returnat de functia de cautare.

Analizoare sintactice LALR(1) Analiza tipurilor