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:

• efectuarea verificarilor legate de respectarea concordantei tipurilor si a regulilor de vizibilitate (verificari semantice);
• generarea de cod.

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:

• NUME - referinta la sirul de caractere care formeaza identificatorul. Acest sir constituie de fapt cheia de cautare in TS.
• CLASA - categoria identificatorului, care poate fi: nume de program, nume de constanta (declarat in sectiunea const), nume de variabila simpla , nume de functie, nume de procedura , nume de parametru formal transmis prin adresa (declarat cu var in lista de parametri), nume de parametru formal transmis prin valoare, nume de tablou, nume de structura (record), nume de camp al unei structuri.
• TIP - tipul (simplu) declarat pentru variabilele simple, parametrii formali, elementele unui tablou, campurile unei structuri sau rezultatul returnat de o functie. Pentru limbajul dat in Anexa B, acest tip poate fi: intreg, real sau caracter.
• VAL - se utilizeaza pentru numele de constante (declarate in sectiunea const) si contine indicele spre TabCONST unde se afla valoarea atribuita constantelor respective.
• ADREL -adresa relativa fata de inceputul unitatii de program in care este declarat identificatorul. Se refera la variabilele declarate in sectiunea var si la parametrii formali.

In faza de executie a programului, fiecarei unitati (functie, procedura sau program principal) ii va corespunde cate un bloc de memorie in stiva de lucru. Acest bloc va servi pentru memorarea parametrilor si/sau a variabilelor locale, precum si pentru depunerea rezultatelor partiale ale calculelor. ADREL reprezinta deplasamentul locatiei rezervate unei variabile, fata de inceputul blocului alocat in stiva . Pentru prima variabila sau parametru formal dintr-o unitate de program ADREL este 0; pentru a k-a variabila din unitatea respectiva ADREL va avea o valoare egala cu necesarul de unitati de memorie al celor k-1 variabile declarate anterior. Consideram ca unitatea de memorie alocabila este un nod al stivei de lucru, de unde rezulta ca :
• pentru tipurile simple necesarul de memorie este: necesar(tip) = 1;
• pentru un tablou de forma
array [i1 . . i2] oftip;
unde i1 si i2 sunt numere intregi fara semn, necesarul de memorie este
(i2 - i1 +1)*necesar(tip);
• pentru o structura de forma
record c1: tip1; c2: tip2; . . . ; cn: tipn end;
necesarul de memorie este:
necesar(tip1)+necesar(tip2)+. . .+necesar(tipn); Exemplu: fie secventa sursa
 
program P;
const a = 3;
var b, c, d : integer;
e : array [3..10] of real;
f : char;
procedure PR(a : integer; b : char);
var x, y : record c1 : real; c2 : char end;
. . .
Variabilelor si parametrilor formali care apar in aceasta secventa le vor corespunde urmatoarele valori pentru ADREL:
• in programul principal: b - 0, c - 1, d - 2, e - 3, f - 11 (variabila e ocupa 8 unitati de memorie);
• in procedura PR: a - 0, b - 1, x - 2, y - 4.
Pentru numele de functii, campul ADREL se va completa cu valoarea -2. Aceasta valoare va fi necesara in faza de generare de cod, pentru situatiile in care membrul stang al unei atribuiri este un nume de functie (v. Lucrarea nr.11 si Anexa C).
• DEPLREC - deplasamentul unui camp de structura fata de inceputul structurii respective. Pentru primul camp dintr-o structura DEPLREC = 0, iar pentru restul campurilor calculul se face ca si pentru ADREL.
• NIVEL - reprezinta nivelul de imbricare la care se gaseste un identificator. Pentru domeniul de vizibilitate al programului principal nivelul este 1, pentru blocurile declarate in programul principal nivelul este 2 s.a.m.d. Pentru completarea campului NIVEL din TS, se poate utiliza o variabila globala care se initializeaza cu 1 si care se actualizeaza astfel:
• dupa ce s-a trecut de numele unui subprogram, variabila se incrementeaza cu 1;
• dupa ce s-a trecut de "end"-ul unui subprogram, variabila se decrementeaza cu 1.
• NR_PAR - se completeaza numai pentru nume de functii si proceduri si reprezinta numarul de parametri formali.
• DIM_VAR - se completeaza pentru numele de functii, proceduri si program principal si reprezinta numarul total de locatii din stiva de lucru necesare pentru memorarea variabilelor locale (NU si a parametrilor formali).
• ADR_START - se completeaza pentru numele de functii, proceduri si program principal si reprezinta adresa (indicele) in tabela de cod la care incepe corpul de instructiuni al unitatii de program respective.
• LISTA_PAR - se completeaza pentru numele de functii si proceduri si reprezinta o lista (sau pointer spre inceputul unei liste) avand cate un nod corespunzator fiecarui parametru formal. Nodurile acestei liste sunt de forma:

unde: 'tip_parametru' este tipul declarat al parametrului (asa cum apare in campul TIP din TS), iar 'tip_transmisie' poate fi 'prin valoare' sau 'prin adresa '. Lista este necesara pentru verificari legate de concordanta parametrilor, cand in textul sursa apar apeluri de subprograme.
• IND_MIN, IND_MAX - se completeaza pentru numele de tablouri si reprezinta valorile minima , respectiv maxima declarate pentru indice. Pentru simplificare presupunem ca indicii de tablouri pot fi numai de tip intreg.
• LISTA_REC - se completeaza in cazul numelor de campuri de structura si reprezinta o lista de referinte in TS, spre intrarile corespunzatoare numelor de structuri de care apartin campurile respective. De exemplu, presupunem ca in textul sursa apare o declaratie de forma:

Pentru campurile x si y LISTA_REC va contine referintele spre intrarile din TS corespunzatoare simbolurilor a, b si c. Aceasta lista este necesara pentru a verifica daca , intr-o referire de forma r.c, c este camp al lui r.
• INCDOM - se completeaza in cazul numelor de subprograme si reprezinta valoarea curenta a indicelui in tabela de cod la momentul intalnirii declaratiei subprogramului respectiv. Aceasta informatie va fi necesara in faza generarii de cod, pentru rezolvarea unor apeluri de forma:
procedure P1( . . . );
. . .
procedure P2( . . . );
. . .
begin {P2}
. . .
P1( . . . );
. . .
end; {P2}
. . .
begin {P1}
. . .
end; {P1}
Dupa cum se vede, apelul procedurii P1 apare in text inainte ca in TS sa se fi completat adresa de start a lui P1 (aceasta adresa se va completa la momentul intalnirii "begin"-ului procedurii).

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 :

• a.Cautarea unui identificator. Cheia de cautare este sirul de caractere care compun identificatorul. Cautarea se va face intotdeauna in sens descrescator al nivelului de imbricare (campul NIVEL) si se va opri la prima aparitie a simbolului cautat sau la epuizarea tabelei. Functia de cautare, pe care o vom nota Cauta _TS va returna indicele intrarii in TS la care s-a gasit simbolul, respectiv o valoare negativa , daca simbolul nu exista in TS.

Operatia de cautare este invocata cand in textul sursa se intalneste o referire la un simbol, precum si inaintea unei inserari in TS. In primul caz, daca simbolul nu este gasit, se va considera ca a aparut o eroare de tipul "simbol nedeclarat".
• b.Inserarea unui identificator. Aceasta operatie este efectuata cand in textul sursa se intalnesc declaratii de simboluri (numele programului principal, constante, variabile, functii, proceduri si parametri formali). Inainte de inserare se va efectua o cautare a simbolului de inserat, pentru a se detecta eventualele declaratii multiple. Daca un simbol mai este declarat o data in acelasi bloc, se va semnala o eroare de tip "identificator multiplu declarat". Exceptie de la aceasta regula vor face numele de campuri de structuri, in sensul ca:
  • se permit situatii in care un nume de camp coincide cu un nume de variabila simpla , de tablou sau de functie/procedura declarate in acelasi bloc ca si structura in cauza;
  • de asemenea se permite ca doua campuri care apar in structuri diferite sa aiba acelasi nume; in acest caz se vor crea intrari distincte in TS pentru cele doua campuri.
  NU se permite, insa , ca in aceeasi structura sa apara doua campuri cu acelasi nume.

Functia de inserare, pe care o vom nota Insert_TS primeste ca parametru identificatorul de inserat si returneaza indicele intrarii din TS alocate identificatorului respectiv.

• TS[i] - pentru a referi intrarea cu indicele i din TS;
• TS[i].nume_camp - pentru a referi campul nume_camp al intrarii de indice i din TS.

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

Declaratii de constante

Se insereaza simbolul 'identificator' in TS; se completeaza campurile:

• CLASA - cu 'nume de constanta',
• NIVEL - cu valoarea curenta a variabilei VNIVEL si
• VAL - cu valoarea -1.

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).

Declaratii de variabile

Declar_var -> Lista_id₁ : Tip ;
Lista_id  -> identificator | Lista_id₂ , 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_id₃ : 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_id₁ (valoarea acestui contor va constitui un atribut al neterminalului Lista_id ).

Pentru toti identificatorii din Lista_id₁ inserati se completeaza campurile:

• CLASA - cu 'nume variabila simpla ' si
• TIP - cu valoarea obtinuta prin prelucrarea neterminalului Tip_simplu.

Pentru toti identificatorii din Lista_id₁ inserati se completeaza campurile:

• CLASA - cu 'nume tablou',
• TIP, IND_MIN si IND_MAX - cu atributele obtinute prin prelucrarea neterminalului Tip_tablou.

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

,  Pentru toti identificatorii din Lista_id₃ inserati se completeaza campurile:

• CLASA - cu 'nume camp' si
• TIP - cu valoarea obtinuta prin prelucrarea neterminalului Tip_simplu.

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

Pentru toti identificatorii din Lista_id₁ inserati se completeaza campul ADREL.

Declaratii de functii

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

Lista_param_form  -> Declar_param |  Lista_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:

• NIVEL - cu valoarea VNIVEL (apoi se incrementeaza VNIVEL),
• CLASA - cu 'nume functie',
• INCDOM - cu valoarea curenta a variabilei ICOD,
• ADREL si ADR_START - cu valoarea -1;

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:

• CLASA - cu 'nume parametru de intrare' (transmis prin valoare) si
• TIP - cu valoarea obtinuta prin prelucrarea neterminalului Tip_simplu.

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

Stiva

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

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.