Buna ziua si bun venit la ora de compilatoare ...
Pregatiti-va manualul de compilataore, capitolul,4 , inainte de implementare discutam despre Context si implementarea sa Tabela de Simboluri.
Context
Notiunea de context este cunoscuta de lingvisti. Sa zicem ca spunem cuiva: "Ne vedem la ora stabilita." Ce semnificatie are "ora stabilita" ?Dar intreaga fraza ?
Este clar ca mai inainte s-a discutat o ora.
Ceva similar exista si la limbajele de programare, cand un compilator compileaza un program.
Ce face instructiunea: print(x); Tipareste un numar sau scrie "Hello world" ?
Depinde de ceva ? De ce ? De tipul si valoarea variabilei x. Se spunde ca depinde de "contextul declararii si folosirii ei".
Intrebare: Par a fi doua feluri de context ?
Raspuns: Da.
Variabila este intai declarata si apoi este folosita. In ambele cazuri compilatorul va face verificari. Vom face :
-o verificare in momentul declararii
-si una in momentul folosirii.
Sa vedem ce am putea verifica. Fie programul in limbajul Simple (salvati-l ca p2bad.sim):
let
integer x,y,y.
in
write(z);
end
Va trebui sa implementam in compilatorul nostru doua verificari (cel putin):
- una care sa verifice declaratia de variabila, atunci cand declaram o variabila noua. Sa verifice daca ea se potriveste, este in regula, nu se "contrazice" cu alta deja existenta.
- o verificare care sa se faca in momentul folosirii variabilei, deoarece folosirea unei variabile poate sa fie incorecta, in cel mai rau caz variabila poate sa nu existe, in cel mai bun poate sa nu fie de tipul cerut.
Dar stie compilatorul dinainte despre fiecare variabila, cum se numeste si ce tip are ? Nu. Invata din citirea programelor, invata din parcurgerea declaratiilor (mai exact) si ceea ce invata stocheaza intr-un fel de dictionar de variabile, numit tabela de simboluri.
Tabela de simboluri
Evident, compilatorul parcurge declaratiile, afla de la programator:
- cum se numesc variabilele,
- ce tip au (daca limbajul nu este limbaj monotip, ca Lisp si Simple).
- apoi intr-o faza ulterioara poate adauga noi informatii: in faza de generare de cod va adauga, de exemplu, adresa unde e alocata variabila pe stiva.
Exercitiu: Cautati pe google images o imagine (sunt zeci) pentru Symbol table si veti avea o idee cum poate sa arate aceasta, ca o lista sau ca un arbore sau ca o tabela hash alcatuita din niste record-uri.
Exercitiu: Desenati asa cum ati facut la Cursul structuri de date, o:
- lista simplu inlantuita in care fiecare element mai poarta o informatie
- un arbore binar de cautare in care fiecare element mai poarta o informatie
- o tabela hash fiecare element mai poarta o informatie.
Daca lucrati la un compilator profesional, viteza de cautare in tabela de simboluri devine importanta, deci cu cat structura de dte permite un acces mai rapid cu atat mai bine.
Tabela Hash
Intrucat este posibil sa nu o fi intalnit la cursul de structuri de date, explic cum lucreaza o tabela hash si ce este:
- este o tabela (vector) de (211 sau alt nr, prim de preferat) de pointeri la liste de recorduri.
Scopul acestei impartiri este sa rupem o lista in mai multe bucati accesabile separat.
- e insotita de o functie de calcul a valorii hash (poate fi chiar un hash criptografic care foloseste o functie de criptare modificata). Functia trebuie sa aiba dispersie mare in sensul ca pentru denumiri de variabile usor diferite x,Y,X1, Y1 samd sa produc indici dispersati distinct.
Cum se pun date in ea:
1) Calculez functia hash pt stringul dat "X2D2". Sa zicem ca da 209
2) Ma duc in tabela si inserez in lista din pozitia 209 , (la inceput, e mai rapid)
elementul care contine "X2D2"
Cum caut date in ea:
1) Calculez functia hash pt stringul dat "X2D2". Sa zicem ca da 209
2) Ma duc in tabela sa caut pe lista din pozitia 209,
elementul care contine "X2D2". Cu o dispersie buna, cautarea va fi pe o lista de unu,doua elemente, iar cand tabela este populata, cautarea va fi de circa 200 ori mai rapida ca pe o lista care ar fi rezultat din concatenarea listelor.
v[0]---> |------------------| |------------------|
| X | .--------------------> | Y | null |
|------------------| |------------------|
v[1]---> |------------------|
| A | null |
|------------------|
v[2]---> |------------------| |------------------|
| RI | .--------------------> | R2 | null |
|------------------| |------------------|
....
v[211]---> |------------------| |------------------|
| X2 | .--------------------> | BETA | null |
|------------------| |------------------|
Lista inlantuita
Este lista pe care o vom folosi la compilatorul limbajului Simple.
Pointerul
sym_table
[]---> |------------------| |------------------|
| X | .--------------------> | Y | null |
|------------------| |------------------|
Implementarea tabelei de simboluri [pg 34] (Cautati struct symrec )
In cazul nostru, deocamdata, recordul listei care este tabela de simboluri are doar doua campuri:
char * name;
struct symrec * next;
[]---> |------------------| |----------------------------|
| name | next----------------> | name | next= null |
|------------------| |----------------------------|
Primul record Al doilea si ultimul record.
Practic: In dosarul Lab4 copiati tot ce este lin Lab3 si salvati fisierul ST.h ... vor urma modificari la alte fisiere.
In ST.h adaugati toto codul care contine:
struct symrec [pg 34]
declaratiile in avans ale functiilor putsym si getsym
codul functiilor putsym si getsym [pg 34 si pg 36]
Exercitiu: Cititi explicatia codului functiei putsym si explicati codul functiei getsym. (Astept e-mailuri.)
Intrebare de control: Ce face putsym in tabela de simboluri ?
Intrebare de control: Ce face getsym in tabela de simboluri ?
In final obtineti o implementare a tabelei de simboluri cum este cea de la pg 37. (fara return 0; de la final, lasati return ptr)
Intrebare de control: La ce serveste pointerul ptr in functia putsym ?
Modificari ale analizorului sintactic [pg 38]
Explic in plus: Bison are un mecansim special ca odata cu sintaxa sa manipuleze si niste valori asociate elementelor din regulile sintactice. Sunt numite valori semantice, deoarece ele sunt sensul sintaxei. De exemplu acestea ar putea fi codurile masina ale acelor elemente, la un compilator sau valoarea subexpresiilor in cazul unui interpretor.
Noi le vedem si le scriem in cod ca pe niste variabile, cu $ (sa stie si cei care programeaza Web de unde vin variabilele cu nume cu $ ... de la Bison !!).
Astfel, (urmariti ideea,) pentru o regula sintactica:
<command> -> write <exp>
Am putea avea:
$$ $1 $2
Unde $1 sa fie codul masina al lui write, $2 sa fie codul masina al expresiei, iar codul masina al intregului write sa fie $$ = $2 concatenat cu $1 deoarece codul final presupune sa calculam intai expresia apoi sa o afisam.
Nota: Veti vedea ca la compilatorul de Simple nu mai folosim $$ ci doar stocam rand pe rand codurile produse in memorie, sarim peste ce nu avem (backpatching) si revenim cand e disponibila bucata lipsa.
Aceste variabile speciale trebuiesc:
- cumva declarate pt Bison (daca le folosim)
- cumva accesate din C-ul in care programam.
Din acest motiv declaram la pg 39 variabila atasata identifictorului:
% token <id> IDENTIFIER
Nu uitati acest <id> , lipsa lui va duce la erori C foarte criptice, produse de codul generat !
Abia acum implementam cele doua verificari de care spuneam la inceput (vezi functiile install si context_check - pg 45).
Ce fac ele in tabela de simboluri ?
Install() verifica daca o variabile e deja declarata, da mesaj de eroare in acest caz si o pune intabela pe tacute daca nu este declarata.
Context_check() verifica daca o variabila este declarata.
Studiu: Studiati felul cum sunt scrise aceste functii, le-ati inteles ?
Ca efect al modificarilor analizorului sintactic, obtineti noul fisier simple.y.
[pg 44-45-46].
Dar numele variabilelor nu ajung , nu vin, de nicaieri in tabela de simboluri, deoarece codul Lex/Flex nu le transmite, va amintiti ca Lex/Flex avea doar iundicatia sa faca un {return(IDENTIFIER);} , (IDENTIFIER fiind o constanta care nu spune nimic despre numele variabilei), cand gaseste o variabila ?
Din acest motiv se fac:
Modificarile scannerului
Adaugati recordul semantic, locul unde se vor stoca aceste variabile ...
% union {char * id;
}
Nota: daca ati trisat si ati copiat cu copy paste codul de la pagina 45, atunci modificarea este deja facuta.
Acum modificarile scannerului : Vedeti codul bold de la pagina 44, in dreptul lui:
{ID} {yylval.id = (char*) strdup(yytext);
return (IDENTIFIER); }
Fisierul final Simple.lex va arata ca la pagina 44.
Practica: Reconstruiti compilatorul si recompilati cu el fisierul p2bad.sim.
Trimiteti outputul pentru confirmare.
Gata pentru azi...
Blogarea va continua dupa ora 13, reveniti daca aveti alta ora.
Continuam ...
Pentru a primi automat actualizari in caz ca nu sunteti pe lista, va puteti inscrie ca followers la blog. Dar nu garantez pt felul cum blogul trimite mesaje.
Niciun comentariu:
Trimiteți un comentariu