LFA - (si IFR) Compilatoare - Cap 4 - Contextul [pg33]-[pg47]

Sper ca v-ati pregatit Linux-urile, Flex-ul si Bison-ul, editorul de texte si dosarul Lab4. In acest dosar Lab4 copiati toate fisierele din dosarul Lab3 si vom continua constructia compilatorului.

Nota: Comozii vor dori sa lucreze pe vechile fisiere. Pt a dovedi participarea regulata la aceste lucrari de laborator voi cere tot setul de dosare de laborator.

Voi incepe cu niste motivatii ale prezentei acestui capitol pe care nu le veti intelege,presupun, daca nu faceti urmatorul experiment:

Scrieti programul Simple:

let
  integer x,x,y.
in
  write (z);
end

Si sa dezbatem putin: Este el un program corect ?

1) Programatorii vor spune plini de siguranta, Nu , cel putin pentru doua motive: are o variabila dublu declarata, x-ul si o variabila nedeclarata dar folosita, z-ul.

Dar daca compilati programul de mai sus, salvat de ex sub numele p2bad.sim:
$ ./simple p2bad.sim
sau
$ ./simple.exe p2bad.sim
Ce spune compilatorul ?
Cum interpretati acest lucru ?

2) Programul este corect in masura in care respecta regulile de sintaxa.Si le respecta. Are tot ce trebuie sa aiba conform gramaticii limbajului Simple.
Forma generala   let ... in ... end  declaratia  integer x,x,y.  apoi instructiunea write cu expresia (z) corecta in paranteza si ; la sfarsit.

Unde este problema ? Pai sunt doua, de aceeasi natura. Lipsesc verificarile declaratiilor variabilelor in dictionarul de variabile. Va trebui sa implementam asa numita "symbol table" tabela de simboluri.

Deschideti manualul de constructia compilatoarelor (in limba romana) la pagina 33, capitolul al 4-lea.

Ce facem de fapt in capitolul al IV-lea ? Implementam o forma simpla de tabela de simboluri, reflectand faptul ca in limbajul Simple, variabilele trebuiesc declarate (si numai odata) inainte de a fi folosite. Vor trebui facute doua verificari: Sa evitam dubla declarare cautand variabila in context si sa verificam din instructiuni.

Exista o mica problema: Analizor lexical trimite numai niste raspunsuri generice: return(NUMBER); return(IDENTIFIER); nu transmite si care ESTE EXACT acel identificator sau numar. Vor trebui facute niste modificari in fisierul simple.lex

Tema: Lucrati va rog capitolul al IV-lea din cartea de compilatoare, incepind de la pagina 33 -> pg 47.

Cateva explicatii vor fi totusi necesare, in plus:

La modulul tabela de simboluri, cu numele ST.h

[pg 34] *sym_table este pointerul la tabela de simboluri implementata ca lista simplu inlantuita, de elemente symrec, observati ca este initializata cu (symrec*)0.
[pg34] putsym e functia care pune un record nou in lista, sym_table va arata noul element iar pointerul din acesta va arata restul listei.

Exercitiu: Descifrati codul functiei putsym desenand (ca la cursul de structuri de date) elementele listei inlantuite si pointerii. Noroc ca e in carte explicat rand cu rand :))

[pg38] Inainte de paragraful "Modificarile analizorului sintactic ..."  Este un paragraf mai sus, care incepe cu "Observati .." si deasupra un return 0 in unele editii ale cartii.
Nu se poate ca o functie sa se termine cu:
return ptr;
return 0;}
Taiati-l pe return 0. Evident, functia de cautare getsym() returneaza pointer la elementul gasit, sau un zero rezultat din algoritm daca nu gaseste. Nu returneaza zero intotdeauna.

[pg 39]  Paragraf 2 de jos: Fraza "Simple.lex va fi modificat astfel": se va citi
"Simple.y va fi modificat astfel:". Modificam parserul facut cu Bison si salvat in fisierul simple.y.

[pg39] Dupa:
%start program

asigurati-va ca toti acei %token sunt:
%token INTEGER SKIP IF THEN ELSE FI WHILE DO END ASSGNOP 
(ca e INT sau INTEGER ca este ASSGNOP sau ASIGNOP de fapt nu conteza cum ii notati dar notati-i si folositi-i consecvent).

Erori ciudate veti obtine daca uitati asazisul record semantic !
%token <id> IDENTIFIER

Aici explicam Bisonului ca fiecare IDENTIFIER va avea undeva intr-o structura de date un camp numit .id care ii corespunde. De ce ?

Noi am vrea sa punem in tabela de simboluri id-ul, numele fiecarei variabile. Dar analizorul lexical spunde doar ca a gasit un IDENTIFIER nu ofera odata cu el si o "sacosa" pardon, camp dintr-o structura de date  in care sa stocam acest identificator, de exemplu fie el "R2D2".

In regulile gramaticale pe care le manipuleaza Bison-ul aveti linga fiecare terminal sau neterminal din regula o variabila $i unde i este pozitia elementului terminal sau neterminal in partea dreapta a regulii.

Exemplu: Pt o regula:
<exp> -> <stanga> + <dreapta>   Bison va producecand foloseste regula 3 variabile:
$$                 $1        $2       $3
Daca de exemplu  $1 este valoarea expresiei din stanga si $3 este valoarea expresiei din dreapta va trebui sa calculam pe $$ ca fiind suma valorilor lor.

Exemplul 2, [pg 40]. Daca intr- declaratie scrisa in codul Bison
declarations : /*empty*/
          | INTEGER id_seq IDENTIFIER '.'     {install($3);}

...inseamna ca i-am spus Bisonului ce sa faca dupa ce a parcurs declaratia si a trecut de '.'-ul ei final: Sa execute codul din acolada si sa apeleze functia install( $3) de instalare a valorii semantice asociate celui de-al treilea element din regula.... numaram ... acesta este IDENTIFIER.

Astfel punem in tabela de simboluri IDENTIFICATORUL care este valoarea semantica asociata unui atom IDENTIFIER.

Exemplul 3 [pg 40]: Daca atomii lexicali care sunt numerele in practica sunt numiti prin token-ul NUMBER este corecta regula:

exp: INT
  | IDENTIFIER {context_check($2); }        eroare la pg 40 , ultimul rand.

Corect:

exp : NUMBER          
 | IDENTIFIER {context_check($1); }

De ce ? In expresiile aritmetice intalnesti numere nu cuvantul "integer" care aparea in declaratii. Si daca o expresie este un identifier, regula are o parte stanga , exp, si o parte dreapta IDENTIFIER  deci nu are sens sa vorbim de lementul al 2-lea din partea dreapta a regulii:

<exp>  ->  IDENTIFIER                             (ok, am scris-o cu alta notatie).
    1                     1              2-nu este.

Cititi pina la pg 41:


Modificarile scanner-ului [pg 41]:

Deoarece codul generat de Lex nu ofera si numele concret al identificatorilor ,
se declara intai locul unde este stocat [pg 42]:

%union  {char * id;                           --- este acelasi id din linia %token <id> ...
}

si astfel variabila Yacc/Bison yylval va avea un camp .id  in care vom putea scrie , din codul pentru Lex, numele variabilei asa cum e el in textul de intrare. 

De data aceasta, cand codul generat de Lex/Flex gaseste un {ID} nu mai face doar {return(IDENTIFIER);} ci :

{ID }  { yylval.id = (char *) strdup(yytext);
              return(IDENTIFIER);}

Adica face o dup-licare de str-ing pe care il ia din variabila yytext de-a Bison-ului/Yacc-ului si il copie in yylval.id. Mda, de fapt copie pointeru.

Va rog cititi pe cont propriu despre reprezentarea intermediara. [pg 43 si urmatoarele] si sa terminati lucrarea din capitolul 4.

Validarea partii practice:

Refaceti compilatorul si compilati iar: p2bad.sim

let
  integer x,x,y.
in
  write (z);
end

Ar trebui sa obtineti doua mesaje de eroare:
x is already defined
z is an undeclared identifier.

Acum e in regula, nu-i asa ?

Final C4. Ne vedem miercuri la o reluare C4 cu cei de la zi, care nu au lucrat azi luni aceasta lucrare.