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:
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 :
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. |
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;
- CLASA - cu 'nume de constanta',
- NIVEL - cu valoarea curenta a variabilei VNIVEL si
- VAL - cu valoarea -1.
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 ;, 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 ).
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 | charPentru toti identificatorii din Lista_id1 inserati se completeaza campurile:
- CLASA - cu 'nume variabila simpla ' si
- TIP - cu valoarea obtinuta prin prelucrarea neterminalului Tip_simplu.
Pentru toti identificatorii din Lista_id1 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_id1 inserati se completeaza campul CLASA - cu 'nume structura '.
, Pentru toti identificatorii din Lista_id3 inserati se completeaza campurile:
- CLASA - cu 'nume camp' si
- TIP - cu valoarea obtinuta prin prelucrarea neterminalului Tip_simplu.
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 ;Se insereaza simbolul 'identificator' in TS; se completeaza campurile:
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
apoi se depune in stiva ST_BLOC indicele intrarii in TS unde s-a facut inserarea.
- 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;
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
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.