Generarea de cod virtual

Generarea codului virtual

Functii pentru generarea de cod

Functiile pentru generarea de cod realizeaza completarea tabelei de cod TAB_COD cu instructiuni ale limbajului virtual, date ca parametri.

La o executie, o functie de generare de cod depune in TAB_COD o instructiune virtuala. Ca parametri ai functiei trebuie sa se furnizeze codul instructiunii virtuale si eventualele argumente ale acesteia.

In cele ce urmeaza vom considera ca avem o singura functie de generare, numita GEN, care accepta numar variabil de parametri, iar explicatiile vor fi axate pe limbajul virtual din Anexa C. In acest caz, exemple de apeluri ale functiei GEN ar putea fi:

GEN (OUT)
GEN (CALL, adr_salt, nr_param, nivel)

Forma concreta de implementare a functiei GEN depinde de limbajul in care se scrie compilatorul. Cateva solutii posibile:

in limbajul C++: functii cu numar variabil de parametri, functii cu parametri avand atribuite valori initiale implicite (aceasta din urma solutie se poate aplica daca parametrii reali ai functiei GEN iau valori intr-un interval limitat cunoscut; de exemplu, se observa ca pentru limbajul prezentat in Anexa C toate argumentele instruct iunilor au valori >= -2 );
in limbajele Pascal si C: parametrii sa fie transmisi sub forma de tablou (sau pointer la un tablou), furnizandu-se si numarul elementelor ocupate ale tabloului (dupa modelul parametrilor _argc si _argv din C);
in oricare dintre limbajele care admit lucrul cu functii/proceduri: se pot scrie functii GEN separate pentru instructiunile cu 0, 1, 2, . . . argumente (de exemplu: GEN1(cod), GEN2(cod, arg1), GEN3(cod, arg1, arg2) etc);
in limbajele orientate pe obiecte se poate utiliza o configuratie de clase proiectata cu sablonul Strategy, unde metoda algoritmului sa fie GEN.

Indiferent de forma de implementare, comportamentul unei functii de generare de cod este cel descris mai jos:

procedure GEN(cod, arg₁, arg₂, . . . , arg_n) is
TAB_COD[ICOD] = cod
TAB_COD[ICOD + 1] = arg₁
TAB_COD[ICOD + 2] = arg₂
. . .
TAB_COD[ICOD + n] = arg_n
ICOD = ICOD + n + 1
end GEN

Variabila ICOD este o variabila globala a compilatorului (v. Lucrarea nr.8), ea indicand in orice moment prima intrare libera din TAB_COD. La initializarea variabilei ICOD se tine cont ca primele locatii din TAB_COD urmeaza sa contina informatii necesare executivului. In cazul masinii virtuale definite in Lucrarea nr.10 numarul acestor locatii este 3.

Obs: a nu se confunda variabila ICOD cu registrul NI; desi ambele joaca rol de indice in TAB_COD, ICOD este utilizata doar de compilator in procesul de completare a tabelei de cod (ea nici nu este vizibila in executiv), in timp ce NI este utilizat doar de executiv (nu este vizibil in compilator) pentru a parcurge tabela gata completata . ICOD baleiaza intrarile tabelei de cod in ordine fizica, pe cand NI evolueaza conform ordinii logice a instructiunilor programului

Exemple de apeluri ale functiei GEN

Modul in care se apeleaza functia GEN va fi ilustrat cu ajutorul marcajelor inserate in productii, pentru fiecare tip de instructiune a limbajului sursa dat in Anexa B. Integrarea rutinelor corespunzatoare marcajelor cu analizorul sintactico-semantic se realizeaza dupa modelul prezentat in Anexa D.

In rutinele ce vor fi prezentate mai jos se va evidentia doar partea de generare de cod, presupunandu-se ca verificarile semantice (de domeniu si de tipuri) sunt deja incluse in compilator.

Atribuiri

Instr_atrib -> Variabila :=Expresie₁
Variabila -> identificator₁ |

identificator₂[Expresie₂] |
identificator₃. identificator₄

loc1 = Cauta _TS (identificator₁)
if TS[loc1].CLASA = 'nume de functie' then
GEN(LODA,VNIVEL,TS[loc1].ADREL)
else
GEN(LODA, TS[loc1].NIVEL, TS[loc1].ADREL)
endif

Obs: in cazul in care membrul stang al unei atribuiri este un nume de functie, adresa lui se calculeaza fata de blocul curent din stiva de lucru (v. Anexa C, § C.6).

*fie loc2 indicele intrarii din TS corespunzatoare lui identificator₂
*genereaza secventa de verificare a indicelui
*genereaza secventa de incarcare a adresei elementului de tablou
Obs: in acest punct, in faza de executie a programului, tocmai a avut loc evaluarea expresiei de la indice; deci, in varful stivei de lucru se afla rezultatul acestei expresii, rezultat pe care se bazeaza calculul adresei pentru elementele de tablou.

Secventa de verificare a indicelui este:

COPY
LODI Insert_const( 'intreg', TS[loc2].IND_MIN)
LES
FJP ICOD+4
ERR nr_mesaj_depasire_limita_inferioara_indice
COPY
LODI Insert_const( 'intreg', TS[loc2].IND_MAX )
GRT
FJP ICOD+4
ERR nr_mesaj_depasire_limita_superioara_indice
Secventa de incarcare a adresei elementului de tablou este:

LODI Insert_const( 'intreg', TS[loc2].IND_MIN )
SUB
LODA TS[loc2].NIVEL TS[loc2].ADREL
ADD

*fie loc3 si loc4 indicii in TS unde se afla identificator₃, respectiv identificator₄
*genereaza secventa de incarcare a adresei campului de structura
Secventa de incarcare a adresei de camp este:

LODA TS[loc3].NIVEL TS[loc3].ADREL
LODI Insert_const( 'intreg', TS[loc4].DEPLREC )
ADD

*fie tipv si tipe_1 tipurile determinate pentru Variabila, respectiv Expresie₁
if tipv <> tipe_1 then
*genereaza secventa de conversie a valorii din varful stivei (valoarea expresiei)
endif
GEN(STO)
Tinand cont de restrictiile privitoare la tipuri, formulate in Lucrarea nr.9, rezulta ca singura situatie admisa in care tipv <> tipe_1 este cea in care tipv = 'real' si tipe_1 = 'intreg'. In consecinta, secventa de conversie este:
CONV 'real' 0

Conditii si expresii

Conditie ->Expr_logica |

     not Expr_logica

Expr_logica -> Expr_rel |

Expr_logica Op_log Expr_rel

Expr_rel -> Expresie₁Op_rel Expresie₂ |

    ( Conditie )

Expresie -> Termen₁ |

   Expresie₃Op_ad Termen₂

Termen -> Factor₁ |

Termen₃Op_mul Factor₂

Factor -> identificator₁ |

Constanta |
identificator₂[Expresie₁] |
identificator₃.identificator₄ |
identificator₅( Lista_expresii) |
( Expresie )

Vom utiliza urmatoarele notatii:

loc_i - indicele intrarii din TS corespunzatoare lui identificator_i;
tipe_i, tipt_i si tipf_i - tipurile determinate pentru Expresie_i, Termen_i si respectiv Factor_i (i=1..3).

GEN( NOT )

if Op_log = cheie_and then

GEN(AND)

else

GEN(OR)

endif

if tipe_1 <> tipe_2 then
if tipe_1 = 'intreg' then
GEN(CONV, 'real', 1)
else
GEN(CONV, 'real', 0)
endif
endif
select Op_rel of
> : GEN(GRT)
< : GEN(LES)
>= : GEN(GEQ)
<= : GEN(LEQ)
= : GEN(EQU)
<> : GEN(NEQ)
endselect

if tipe_3 <> tipt_2 then
if tipe_3 = 'intreg' then
GEN(CONV, 'real', 1)
else
GEN(CONV, 'real', 0)
endif
endif
ifOp_ad = op_plus then
GEN(ADD)
else
GEN(SUB)
endif

Ca si , dar se aplica operatiile de inmultire/impartire.

loc_1 = Cauta _TS(identificator₁)
select TS[loc_1].CLASA of
'nume de constanta ':
GEN(LODI, TS[loc_1].VAL)
'nume variabila simpla ','nume parametru formal':
GEN(LOD, TS[loc_1].NIVEL, TS[loc_1].ADREL) (**)
'nume de functie':
*se procedeaza ca la si

endselect

GEN(LODI, atom.atribut )
Aici, atomul este o constanta, deci atributul completat de ALEX este indicele in TAB_CONST unde se afla valoarea constantei.

loc_2 = Cauta _TS(identificator₂)
*genereaza secventa de verificare a indicelui
*genereaza secventa de incarcare a valorii elementului de tablou (**)
Incarcarea valorii elementului de tablou este realizata de secventa:

LODI Insert_const('intreg', TS[loc_2].IND_MIN)
SUB
MVRX
LODX TS[loc_2].NIVEL TS[loc_2].ADREL

loc_3 = Cauta _TS(identificator₃)
loc_4 = Cauta _TS(identificator₄)
*genereaza secventa de incarcare a valorii campului (**)

Secventa de incarcare a valorii campului de structura este:
LODI Insert_const('intreg', TS[loc_4].DEPLREC)
MVRX
LODX TS[loc_3].NIVEL TS[loc_3].ADREL

Obs: daca in procedura Factor se ajunge din Lista_expresii, adica este vorba despre un parametru de apel, iar parametrul respectiv este transmis prin adresa , in liniile notate cu (**) in loc de 'incarcare valoare' se va genera 'incarcare adresa'.

loc_5 = Cauta _TS(identificator₅)
GEN(RBM, TS[loc_5].DIM_VAR, 2)

if TS[loc_5].ADR_START < 0 then
GEN(FCALL, loc_5, TS[loc_5].NR_PAR, TS[loc_5].NIVEL)
else
GEN(CALL,TS[loc_5].ADR_START,TS[loc_5].NR_PAR, TS[loc_5].NIVEL)
endif

Obs: se constata ca rutinele de generare de cod, in anumite cazuri, depind de contextul in care este tratat simbolul gramatical de care sunt atasate. Acest lucru se intampla mai ales la neterminalele care apar in secvente derivate din Expresie si Variabila. De aceea, acestor neterminale trebuie sa li se asocieze niste atribute (parametri) care sa indice contextul in care sunt folosite. De exemplu, daca Expresie apare ca element in lista de parametri a unui apel de subprogram, este nevoie sa se cunoasca numarul de ordine al expresiei in cadrul listei.

Blocuri de program

Program_sursa -> program identificator ; Bloc .
Bloc -> Sectiune_const Sectiune_var Sectiune_decl_subprog Instr_comp

*initializare ICOD si TAB_ERR

loc = ST_BLOC[VSTB]
if VNIVEL > 1 then
i = TS[loc].INCDOM
while i < ICOD do
if TAB_COD[i] = FCALL and TAB_COD[i+1] = loc then
TAB_COD[i] = CALL
TAB_COD[i+1] = TS[loc].ADR_START
endif
*incrementeaza i cu n = (nr. argumentelor instr TAB_COD[i]) + 1
endwhile
else
*initializeaza primele 3 locatii din TAB_COD cu: TS[loc].ADR_START, TS[loc].DIM_VAR si indicele primei locatii libere din TAB_ERR
endif
Obs: rutina de mai sus va fi apelata dupa ce a avut loc completarea campului TS[loc].ADR_START (v. Lucrarea 8).

if VNIVEL > 1 then
GEN(RET)
else
GEN(STOP)
endif

Instructiunea if

Instr_if -> if Conditie then Instr Ramura_else
Ramura_else -> epsilon |

else Instr

et1 = ICOD
GEN(FJP, 0)

TAB_COD[et1 + 1] = ICOD

et2 = ICOD
GEN(UJP, 0)
TAB_COD[et1 + 1] = ICOD

TAB_COD[et2 +1] = ICOD

Instructiunea while

Instr_while -> while Conditie do Instr

et1 = ICOD

et2 = ICOD
GEN(FJP, 0)

GEN(UJP, et1)
TAB_COD[et2 + 1] = ICOD

Instructiunea repeat

Se propune studentilor ca exercitiu.

Instructiunea for

Instr_for -> for Variabila := Expresie₁ Sens Expresie₂ Pas do Instr
Sens -> to |
downto
Pas -> epsilon |
stepExpresie₃

Pentru instructiunea for generarea de cod corespunzatoare simbolului Variabila (contorul instructiunii) se face la fel ca pentru instructiunea de atribuire. In plus, insa, este necesar sa se retina indicele (indicii) din TS in care se afla simbolurile ce compun variabila.

GEN(STO) //initializare contor cu valoarea Expresie₁

et1 = ICOD
GEN(COPI)
*genereaza secventa de incarcare a valorii variabilei contor
if sens = cheie_to then
GEN(GEQ)
else
GEN(LEQ)
endif
et2 = ICOD
GEN(FJP, 0) //la depasirea valorii Expresie₂ se paraseste bucla
et3 = ICOD
et4 = ICOD
GEN(UJP, 0)

if et3 = et4 then
ICOD = et3 //daca nu exista clauza step se elimina instructiunea UJP de la

//adresa et3

else
TAB_COD[et3 + 1] = ICOD //completare argument instructiune UJP de la

//adresa et3 cu adresa de inceput a corpului buclei

endif

*genereaza secventa de incarcare a adresei variabilei contor
*genereaza secventa de incarcare a valorii variabilei contor
if et3 < et4 then
GEN(UJP, et5) //daca exista clauza step se sare la evaluarea lui Expresie₃
TAB_COD[et4 + 1] = ICOD
else
GEN(LODI, Insert_const( 'intreg', 1))
endif
if sens = cheie_to then //secventa
GEN(ADD) //de
else //actualizare
GEN(SUB) //contor
endif //cu valoarea
GEN(STO) //pasului
GEN(UJP, et1) //salt la testul contor vs. Expresie₂
TAB_COD[et2 + 1] = ICOD //completarea argumentului instructiunii FJP de la

//et2 cu adresa secv. de terminare bucla GEN(RED)

sens = atom

et5 = ICOD //adresa secv. de evaluare Expresie₃

et4 = ICOD //daca exista clauza step se sare
GEN(UJP, 0) //la secventa de actualizare a contorului

Instructiunea read

Instr_read -> read(Lista_variab)
Lista_variab -> Variabila |

Lista_variab , Variabila

Generarea de cod pentru Variabilase realizeaza ca si la instructiunea de atribuire. Vom nota cu tipv tipul determinat pentru variabila .

GEN(INP, tipv)
GEN(STO)

Instructiunea print

Instr_print -> print(Lista_elem)
Lista_elem -> Element | Lista_elem , Element
Element -> Expresie |

const_sir

GEN(OUT)

sir = atom.atribut
* l = lungimea sirului
for i = 1 . . l do
GEN(LODI, Insert_const( 'caracter', sir[i] ))
GEN(OUT)
endfor

Instructiunea case

Instr_case -> case   Expresie ofLista_altern end
Lista_altern -> Lista_ramuri |

   Lista_ramuri otherwise: Instr

Lista_ramuri -> Ramura |

Lista_ramuri Ramura

Ramura ->   Lista_val :   Instr ;
Lista_val -> Constanta   |

        Lista_val , Constanta

In cazul instructiunii case se impune de la inceput o limita maxima a numarului de alternative (ramuri). Acest lucru este practicat de altfel in limbajele dotate cu o asemenea instructiune, deoarece rezultatul expresiei care se testeaza poate apartine doar unui tip scalar (caracter, enumerare, intreg reprezentabil pe un octet), tip a carui cardinalitate, dupa cum se stie este limitata.

Vom utiliza urmatoarele notatii:

nr_ram: numarul maxim de ramuri impus (exclusiv ramura otherwise);
Tab_case: un tablou cu nr_ram elemente; un element Tab_case[j] va contine adresa in TAB_COD a sfarsitului instructiunii de pe ramura j.

ram = 0

lg_ram = lg_ram + 1

GEN(COPI) //secventa care

GEN(LODI, atom.atribut) //se repeta pentru

GEN(NEQ) //fiecare constanta

GEN(FJP, 0) //din Lista_val

GEN(UJP, 0) //daca Expresie nu este egala cu nici o constanta din lista, se sare

//la urmatoarea ramura

prim_i = ICOD

et = prim_r + 5 //locul argumentului primei instructiuni FJP de pe ramura

for i = 1 .. lg_ram do //completarea argumentelor tuturor

TAB_COD[et] = prim_r //instructiunilor FJP de pe ramura ,

et = et + 6 // cu adresa secventei corespunz.

endfor //lui Instr

Tab_case[ram] = ICOD

GEN(UJP, 0) //dupa executia instr. de pe o ramura se sare la prima instr. de

//dupa case

TAB_COD[prim_i - 1] = ICOD //completarea argum. instr. UJP de la

ram = ram + 1

lg_ram = 0

prim_r = ICOD

ifTab_case[ram] = (ICOD - 2) then //daca nu exista ramura

ICOD = ICOD - 2 //otherwise, se elimina

ram = ram - 1 //instr UJP de la sfarsitul ultimei ramuri

endif

for i = 1 .. ram do //completare argum. pentru

TAB_COD[Tab_case[i] + 1] = ICOD //instr. UJP de la

endfor

GEN(RED)

Desfasurarea lucrarii

Se vor implementa rutinele de generare a codului virtual, conform celor prezentate in paragraful de mai sus, si se vor atasa la compilatorul realizat in cadrul lucrarilor anterioare. Pentru adaugarea rutinelor la compilator se vor utiliza modelele prezentate in Anexa D.