Anexa C Anexa E
Anexa D

Atasarea rutinelor semantice unui analizor sintactic

Aceasta operatie va fi exemplificata pentru grupul de productii derivat din Sectiune_const (vezi Anexa B). Actiunile semantice presupun completarea intrarilor din TS corespunzatoare numelor de constante declarate in sectiunea const, ceea ce implica, printre altele, evaluari de expresii statice (v. Lucrarea nr.9).

Exemplele prezentate constituie modele utile si pentru cazurile cand rutinele semantice executa alte operatii ca: analiza de tipuri sau generare de cod.

D.1. Atasarea de rutine semantice unui analizor sintactic cu descendenti recursivi

In acest caz codul rutinelor semantice (sau apelurile spre ele) se insereaza direct in procedurile care alcatuiesc analizorul, in punctele care corespund marcajelor din productii:
 
Sectiune_const -> const Lista_decl_const
      epsilon
(P1.1)
(P1.2)
Lista_decl_const -> Declar_const |
       Lista_decl_constDeclar_const
(P1.3)

(P1.4)

Declar_const -> identificator = Expresie_statica ;
(P1.5)
Expresie_statica -> Termen_static |
      Expresie_statica Op_ad Termen_static
(P1.6)
(P1.7)
Termen_static -> Factor_static |
      Termen_static Op_mul Factor_static
(P1.8)
(P1.9)
Factor_static -> identificator |
     Constanta |
     ( Expresie_statica)
(P1.10)
(P1.11)
(P1.12)

Informatiile cu care se completeaza TS fie se preiau din variabile globale ale analizorului (actualizate la randul lor de alte rutine semantice), fie se transmit intre procedurile analizorului prin intermediul unor parametri de intrare-iesire.
 

procedure Sectiune_const is
   if  atom.cod_lexical = cheie_const then
     call ALEX
     call Lista_decl_const
  endif
end  Sectiune_const

procedure Lista_decl_const is
  call Declar_const
  while atom.cod_lexical = identificator do
    call Declar_const
  endwhile
end Lista_decl_const

procedure Declar_const is
  if atom.cod_lexical = identificator then
    loc = Insert_TS (atom.atribut)                 //rezolvare
    TS[loc].CLASA = 'nume de constanta'        //marcaj
    TS[loc].NIVEL = VNIVEL                          //1
    call ALEX
    if atom.cod_lexical = op_egal then
      call ALEX
      call Expresie_statica(Atrib_tip, Atrib_val)
      TS[loc].VAL = Insert_const( Atrib_tip, Atrib_val//rezolvare
                                                                                               //marcaj 2
      if atom.cod_lexical = pct_virg then
        callALEX
      else
        *eroare 'lipseste ;'
      endif
    else
      *eroare 'lipseste ='
    endif
  else
    *eroare 'declaratie eronata '
  endif
end Declar_const

Obs: variabilele loc, Atrib_tip si Atrib_val reprezinta variabile locale ale procedurii Declar_const.
 
procedure Expresie_statica (in-out Atrib_tip, in-out Atrib_val) is
  call Termen_static (Atrib_tip, Atrib_val)
  while atom.cod_lexical = cod_op_add do
   opad = atom          //rezolvare marcaj 3
    call ALEX
    call Termen(Atrib_tip1, Atrib_val1)
   if Atrib_tip1  <> Atrib_tip then
     if Atrib_tip = 'caracter' sau Atrib_tip1 = 'caracter' then
       *eroare 'tipul operanzilor incompatibil cu operatia' 
     else
       if Atrib_tip = 'intreg' then                             //rezolvare
         Atrib_tip = 'real'
       endif                                                                   //marcaj
       if opad.atribut = '+' then
         Atrib_val = Atrib_val + Atrib_val1
       else                                                                      // 4
         Atrib_val = Atrib_val - Atrib_val1 
       endif
     endif
  endif
  endwhile
end Expresie_statica
Procedura Termen_static este similara cu Expresie_statica, daca se fac inlocuirile: Obs: eroarea de tip 'constanta nedefinita ' apare in situatii de genul:

const a = a + 1;


D.2. Atasarea de rutine semantice unui analizor sintactic de tip LL

Pentru acest analizor marcajele pot fi considerate ca o categorie de simboluri gramaticale speciale, care nu se iau insa in considerare in faza de generare a tabelei de analiza, ci abia in procesul de analiza a textului sursa. Cand aceste simboluri ajung in varful stivei de analiza, prelucrarea lor consta in executia actiunilor semantice corespunzatoare, urmata de eliminarea lor din stiva. Astfel, procedura de analiza poate fi scrisa sub forma:
 

procedure ASIN_LL is
  *initializeaza stiva cu simbolul $ si cu radacina gramaticii
  sp = 2
  call ALEX
  repeat
    X = stiva[sp]
    if X este terminal then
      if  X = atom  then
        sp = sp - 1
        if atom <> $ then
         callALEX
        endif
      else
        *semnaleaza eroare
      endif
    else
      if X este marcaj then
        *executa rutina semantica asociata cu marcajul
        *extrage X din stiva
      else
        i = TABSIN [X, atom]
        if i <> 0 then
          *extrage X din stiva
          *depune īn stiva sirul simbolurilor din membrul drept  al productiei indicate de i, incepand cu simbolul cel mai din dreapta
        else
          *semnaleaza eroare
        endif
      endif
    endif
  until atom = $
end ASIN_LL


Observatii:

Cu aceste observatii, productiile si marcajele necesare sunt:
 
  Sectiune_const -> const Lista_decl_const
       epsilon
(P2.1)
(P2.2)
 
Lista_decl_const

-> Declar_const A
 

(P2.3)
 
A

 -> Declar_const A |
       epsilon
 

(P2.4)
(P2.5)
 
Declar_const

->  identificator = Expresie_statica  ;
 

(P2.6)
 
Expresie_statica

-> Termen_static
 

(P2.7)
 
B

->  Op_ad Termen_static  B |
       epsilon
 

(P2.8)
(P2.9)
 
Termen_static

-> Factor_static C
 

(P2.10)
 
C

->  Op_mul Factor_static  C |
        epsilon
 

(P2.11)
(P2.12)
 
Factor_static

->  identificator |
       Constanta|
     ( Expresie_statica)
 

(P2.13)
(P2.14)
 
(P2.15)

Informatiile de completat in TS, care la analizorul cu descendenti recursivi erau transmise prin parametrii procedurilor, aici sunt vehiculate prin intermediul unei stive de atribute. Pentru a ilustra modul de tratare a marcajelor si de gestionare a stivei de atribute, vom considera ca se analizeaza urmatoarea secventa dintr-un text sursa :

const a = 10; b = a + 4;

care este construita in conformitate cu productiile din grupul Sectiune_const.

Descrierea procesului de analiza va cuprinde, la fiecare pas:

Se vor utiliza urmatoarele notatii:
ST_AN - stiva de analiza;
sp - indicatorul varfului stivei ST_AN;
ST_AT - stiva de atribute;
VT - indicatorul varfului stivei ST_AT;
SI - sirul de intrare.
In momentul in care analiza textului sursa ajunge la secventa considerata mai sus, in mod normal, in varful stivei ST_AN ar trebui sa se afle neterminalul Sectiune_const. Din acest punct, analiza decurge dupa cum urmeaza :
 
Nr.crt Operatie + rutina semantica Continut
ST-AN
Continut
ST-AT
Continut
SI
D.2.1. derivare Sectiune_const cf. productie (P2.1) Lista_decl_const 
const
  const a = 10; b = a + 4;
D.2.2. reducere Lista_decl_const    a = 10; b = a + 4;
D.2.3. derivare Lista_decl_const cf. productie (P2.3) A
Declar_const
  a = 10; b = a + 4;
D.2.4. derivare Declar_const cf. productie (P.2.6)
;

Expresie_statica 
=
identificator
  a = 10; b = a + 4;
D.2.5. tratare marcaj  cf. rutinei:
loc_TS = Insert_TS(atom.atribut)
TS[loc_TS].CLASA = 'nume de constanta'
TS[loc_TS].NIVEL = VNIVEL
Push(ST_AT, loc_TS)

;

Expresie_statica 
=
identificator
loc_TS a = 10; b = a + 4;
D.2.6. reducere
;

Expresie_statica 
=
loc_TS = 10; b = a + 4;
D.2.7. reducere
;

Expresie_statica 
loc_TS 10; b = a + 4;
D.2.8. derivare Expresie_statica cf. productie (P2.7)
;


Termen_static
loc_TS 10; b = a + 4;
D.2.9. derivare Termen_static  cf. productie (P2.10)
;



Factor_static
loc_TS 10; b = a + 4;
D.2.10. derivare Factor_static  cf. productie (P2.14)
;



Constanta
loc_TS 10; b = a + 4;
D.2.11. tratare marcaj  cf. rutinei:
ltc = atom.atribut
Push(ST_AT, TAB_CONST[ltc].TIP_CONST)
Push(ST_AT, TAB_CONST[ltc].VAL_CONST)

;



Constanta
loc_TS 
tip_const 
val_const
10; b = a + 4;
D.2.12. reducere
;


loc_TS 
tip_const 
val_const
; b = a + 4;
D.2.13. derivare C cf. productie (P2.12)
;

loc_TS 
tip_const 
val_const
; b = a + 4;
D.2.14. derivare B cf. productie (P.2.9)
;
loc_TS 
tip_const 
val_const
; b = a + 4;
D.2.15. tratare marcaj cf. rutinei:
lts = ST_AT[VT - 2]
tip = ST_AT[VT - 1]
val = ST_AT[VT]
TS[lts].VAL = Insert_const(tip, val)
*executa de 3 ori Pop(ST_AT)

;
  ; b = a + 4;
D.2.16. reducere   b = a + 4;
D.2.17. derivare A cf. productie (P2.4)
Declar_const
  b = a + 4;
D.2.18. ca si D.2.4.
;

Expresie_statica 
=
identificator
  b = a + 4;
D.2.19. ca si D.2.5.
;

Expresie_statica 
=
identificator
loc_TS b = a + 4;
D.2.20. ca si D.2.6.
;

Expresie_statica 
=
loc_TS = a + 4;
D.2.21. ca si D.2.7.
;

Expresie_statica
loc_TS a + 4;
D.2.22. ca si D.2.8.
;


Termen_static
loc_TS a + 4;
D.2.23. ca si D.2.9.
;



Factor_static
loc_TS a + 4;
D.2.24. derivare Factor_static cf. productie (P.2.13)
;



identificator
loc_TS a + 4;
D.2.25. tratare marcaj  cf. rutinei:
loc = Cauta _TS(atom.atribut)
if loc < 0 then
  *eroare 'simbol nedeclarat'
else
  ifTS[loc].VAL < 0 then
    *eroare 'constanta nedefinita '
  else
    if  TS[loc].CLASA <> 'nume constanta' 
    then
      *eroare 'simbol nepermis in expresii 
         statice'
    else
      ltc = TS[loc].VAL
      Push(ST_AT
                TAB_CONST[ltc].TIP_CONST)
      Push(ST_AT
               TAB_CONST[ltc].VAL_CONST)
    endif
  endif
endif

;



identificator
loc_TS 
tip_const 
val_const
a + 4;
D.2.26. reducere
;


loc_TS 
tip_const 
val_const
+ 4;
D.2.27. ca si D.2.13.
;

loc_TS 
tip_const 
val_const
+ 4;
D.2.28. derivare B cf. product ie (P.2.8)
;

B

Termen_static 
Op_ad
loc_TS 
tip_const 
val_const
+ 4;
D.2.29. tratare marcaj  cf. rutinei:
Push(ST_AT, atom)

;

B

Termen_static 
Op_ad
loc_TS 
tip_const 
val_const
op_ad
+ 4;
D.2.30. reducere
;

B

Termen_static 
loc_TS 
tip_const 
val_const
op_ad
4;
D.2.31. ca si D.2.9.
;

B


Factor_static
loc_TS 
tip_const 
val_const
op_ad
4;
D.2.32. ca si D.2.10.
;

B


Constanta
loc_TS 
tip_const 
val_const
op_ad
4;
D.2.33. ca si D.2.11.
;

B


Constanta
loc_TS 
tip_const 
val_const
op_ad
tip_const 
val_const
4;
D.2.34. ca si D.2.12.
;

B

loc_TS 
tip_const 
val_const
op_ad
tip_const 
val_const
 ;
D.2.35. ca si D.2.13.
;

B
loc_TS 
tip_const 
val_const
op_ad
tip_const 
val_const
 ;
D.2.36. tratare marcaj  cf. rutinei:
op = ST_AT[VT - 2]
tip1 = ST_AT[VT -1]
tip2 = ST_AT[VT - 4]
if  tip1 = 'caracter' or  tip2 = 'caracter' 
then
  *eroare 'tip incompatibil cu operatia'
else
  if op = op_plus  then
    val = ST_AT[VT - 3] + ST_AT[VT]
  else
    val = ST_AT[VT - 3] - ST_AT[VT]
  endif
  if tip1 = 'real' or  tip2 = 'real' then
    tip = 'real'
  else
    tip = tip1
  endif
  *elimina 5 noduri din varful stivei ST_AT
  Push(ST_AT, tip)
  Push(ST_AT, val)
endif

;

B
loc_TS 
tip_const 
val_const
 ;
D.2.37. ca si D.2.14.
;
loc_TS 
tip_const 
val_const
 ;
D.2.38. ca si D.2.15.
;
   ;
D.2.39. ca si D.2.15.    

Obs:  in prezentarea rutinelor semantice din acest paragraf simbolurile Constanta si Op_ad au fost tratate ca terminale. Acest lucru este posibil daca , la nivelul analizorului lexical, se face o grupare a unor atomi in clase (de exemplu, operatorii '+' si '-' se grupeaza in clasa operatorilor aditivi - v. Lucrarea nr.1).
 
 

D.3. Atasarea de rutine semantice unui analizor sintactic de tip LALR(1)

La acest tip de analizor rezolvarea marcajelor poate avea loc doar la efectuarea operatiilor de reducere. De aceea, are sens sa se puna marcaje numai la capatul din dreapta al productiilor. Cu alte cuvinte, marcajele sunt atasate mai degraba productiilor decat simbolurilor gramaticale.
Daca se doreste executia unor actiuni semantice "in mijlocul" unor productii, iar marcajul corespunzator este atasat unui terminal, solutia este crearea unui neterminal suplimentar care sa deriveze spre terminalul respectiv (v. P3.5, P3.6).
Si la analizoarele LR se va lucra cu o stiva de atribute, dar, spre deosebire de analizoarele LL, evolutia acestei stive este paralela cu cea a stivei de analiza ; si anume: la deplasare, automat in stiva de atribute se creaza un nou nod care va contine, de regula, partea de atribut (daca exista) a atomului inserat in stiva de analiza (in aceasta din urma se depune partea de cod lexical); la reducere, daca nu exista rutina semantica asociata productiei implicate, ajustarea stivei de atribute se face la fel ca pentru stiva de analiza, iar in nodul creat in varf se depune o valoare oarecare (de ex. 0); daca exista rutina semantica, atunci aceasta va dicta modul de ajustare a stivei de atribute. In practica, cele doua stive se pot combina intr-una singura, implementand stiva de analiza in asa fel, incat in nodurile acesteia sa se poata memora, pe langa simboluri gramaticale si atributele necesare.
In cele ce urmeaza vom lua ca exemplu acelasi sir de intrare ca in § D.2 si vom utiliza aceleasi notatii pentru stive. In cazul stivei de atribute vom considera ca nodurile pot contine un numar variabil de valori. Unele noduri ale stivei de atribute (cu precadere cele din dreptul terminalelor din stiva de analiza) nu contin atribute propriu-zise. Vom considera ca aceste noduri au acelasi continut ca si nodurile corespunzatoare din stiva de analiza, adica simboluri gramaticale.
Avand in vedere observatiile de mai sus, algoritmul de analiza devine:
 

procedure  ASIN_LR is
  *initializeaza stiva de analiza cu perechea < $, 0 >
  *initializeaza stiva ST_AT cu 0
  sp = 1
  VT = 1
  call ALEX
  repeat
    *fie i numarul starii din varful stivei de analiza
    act = ACTIUNE [i, atom]
    if act = 'deplaseaza j' then
      sp = sp + 1
      VT = VT + 1
      *pune in stiva de analiza perechea < atom, j >
      *pune in stiva de atribute atom.atribut
      call ALEX
    else
      if act = 'reducere A -> a ' then
        *fie k lungimea sirului a
        if *productia are marcaj atasat then
          *executa rutina corespunzatoare marcajului
        else
          VT = VT - k + 1
          ST_AT[VT] = 0
        endif
        sp = sp - k + 1
        j = SALT [i, A]
        *pune in stiva de analiza perechea < A, j >
      else
        if act <> 'accept' then
          *semnaleaza eroare
        endif
      endif
    endif
  until act = 'accept'
end ASIN_LR


Se mai face observatia ca analizoarele de tip LR nu necesita eliminarea recursivitatii stangi.
Cu acestea, productiile si marcajele necesare pentru exemplul luat in considerare sunt:
 
  Sectiune_const -> const Lista_decl_const
       epsilon
(P3.1)
(P3.2)
  Lista_decl_const -> Declar_const |
      Lista_decl_const  Declar_const
(P3.3)
(P3.4)
  Declar_const -> Nume_const = Expresie_statica
(P3.5)
  Nume_const -> identificator 
(P.3.6)
  Expresie_statica -> Termen_static |
      Expresie_statica Op_ad Termen_static 
(P3.7)
(P3.8)
  Termen_static -> Factor_static |
      Termen_static Op_mul Factor_static 
(P3.9)
(P3.10)
  Factor_static -> identificator  |
      Constanta  |
      ( Expresie_statica
(P3.11)

(P3.12)

(P3.13)

La momentul in care analiza textului sursa ajunge la secventa propusa, in varful stivei de analiza ar trebui sa se afle o stare care, in combinatie cu atomul const de la intrare, sa determine o operatie de deplasare.
Facem urmatoarele observatii:

Nr.crt Operatie + rutina semantica Continut
ST-AN
Continut
ST-AT
Continut
SI
D.3.1. deplasare const const  a = 10; b = a + 4;
D.3.2. deplasare const
identificator
const
car_atom
 = 10; b = a + 4;
D.3.3. reducere prin (P3.6) si tratare marcaj  cf. rutinei:
loc_TS = Insert_TS(atom.atribut)
TS[loc_TS].CLASA = 'nume de constanta'
TS[loc_TS].NIVEL = VNIVEL
Pop(ST_AT)
Push(ST_AT, loc_TS)
const
Nume_const
const
loc_TS
 = 10; b = a + 4;
D.3.4. deplasare const
Nume_const
cod_op_rel
const
loc_TS
op_egal
 10; b = a + 4;
D.3.5. deplasare
obs: prin loc_TC s-a notat locul din TabCONST in care s-a inserat constanta din text;
const
Nume_const
cod_op_rel
cod_nr_int
const
loc_TS
op_egal
loc_TC
 ; b = a + 4;
D.3.6. reducere prin (P3.12) si tratare marcaj  cf. rutinei:
loc_TC = Pop(ST_AT)
tip = TAB_CONST[loc_TC].TIP_CONST
val = TAB_CONST[loc_TC].VAL_CONST
Push(ST_AT, tip)
Push(ST_AT, val)
const
Nume_const
cod_op_rel
Factor_static
const
loc_TS
op_egal
tip
val
 ; b = a + 4;
D.3.7. reducere prin (P3.9) const
Nume_const
cod_op_rel
Termen_static
const
loc_TS
op_egal
tip
val
 ; b = a + 4;
D.3.8. reducere prin (P3.7) const
Nume_const
cod_op_rel
Expresie_statica
const
loc_TS
op_egal
tip
val
 ; b = a + 4;
D.3.9. deplasare const
Nume_const
cod_op_rel
Expresie_statica
pct_virg
const
loc_TS
op_egal
tip
val
pct_virg
 b = a + 4;
D.3.10. reducere prin (P3.12) si tratare marcaj  cf. rutinei:
Pop(ST_AT)
val = Pop(ST_AT)
tip = Pop(ST_AT)
Pop(ST_AT)
loc_TS = Pop(ST_AT)
TS[loc_TS].VAL = Insert_const(tip, val)
Push(ST_AT, 0)
const
Declar_const
const
0
 b = a + 4;
D.3.11. reducere prin (P3.3) const
Lista_decl_const
const
0
 b = a + 4;
D.3.12. ca si D.3.2.  const
Lista_decl_const
identificator
const
0
car_atom
 = a + 4;
D.3.13. ca si D.3.3. const
Lista_decl_const
Nume_const
const
0
loc_TS
 = a + 4;
D.3.14. ca si D.3.4. const
Lista_decl_const
Nume_const
cod_op_rel
const
0
loc_TS
op_egal
 a + 4;
D.3.15. ca si D.3.5. const
Lista_decl_const
Nume_const
cod_op_rel
identificator
const
0
loc_TS
op_egal
loc_TS
 + 4;
D.3.16. reducere prin (P.3.11) si tratare marcaj  cf. rutinei:
loc = Cauta _TS(Pop(ST_AT))
if loc < 0 then
  *eroare 'simbol nedeclarat'
else
  if TS[loc].VAL < 0  then
    *eroare 'constanta nedefinita '
  else
    if TS[loc].CLASA <> 'nume de constanta ' 
    then
      *eroare 'simbol nepermis in expresii statice'
    else
      ltc = TS[loc].VAL
      tip = TAB_CONST[ltc].TIP_CONST
      val = TAB_CONST[ltc].VAL_CONST
     Pop(ST_AT)
     Push(ST_AT,  tip)
     Push(ST_AT,  val)
    endif
  endif
endif
const
Lista_decl_const
Nume_const
cod_op_rel
Factor_static
const
0
loc_TS
op_egal
tip
val
 + 4;
D.3.17. ca si D.3.7. const
Lista_decl_const
Nume_const
cod_op_rel
Termen_static
const
0
loc_TS
op_egal
tip
val
 + 4;
D.3.18. ca si D.3.8. const
Lista_decl_const
Nume_const
cod_op_rel
Expresie_statica
const
0
loc_TS
op_egal
tip
val
 + 4;
D.3.19. deplasare const
Lista_decl_const
Nume_const
cod_op_rel
Expresie_statica
cod_op_ad
const
0
loc_TS
op_egal
tip
val
op_plus
  4;
D.3.20. ca si D.3.5. const
Lista_decl_const
Nume_const
cod_op_rel
Expresie_statica
cod_op_ad
cod_nr_int
const
0
loc_TS
op_egal
tip
val
op_plus
loc_TC
 ;
D.3.21. ca si D.3.6. const
Lista_decl_const
Nume_const
cod_op_rel
Expresie_statica
cod_op_ad
Factor_static
const
0
loc_TS
op_egal
tip
val
op_plus
tip
val
 ;
D.3.22. ca si D.3.7. const
Lista_decl_const
Nume_const
cod_op_rel
Expresie_statica
cod_op_ad
Termen_static
const
0
loc_TS
op_egal
tip
val
op_plus
tip
val
 ;
D.3.23. reducere prin (P.3.8) si tratare marcaj  cf. rutinei:
val2 = Pop(ST_AT)
tip2 = Pop(ST_AT)
op = Pop(ST_AT)
val1 = Pop(ST_AT)
tip1 = Pop(ST_AT)
if tip1 = 'caracter' or tip2 = 'caracter' then
  *eroare 'tip incompatibil cu operatia'
else
  if op = op_plus  then
    val = val1 + val2
  else
    val = val1 - val2
  endif
  if tip1 = 'real' or tip2 = 'real' then
    tip = 'real'
  else
    tip = tip1
  endif
  Push(ST_AT, tip)
  Push(ST_AT,  val)
endif
const
Lista_decl_const
Nume_const
cod_op_rel
Expresie_statica
const
0
loc_TS
op_egal
tip
val
 
 ;
D.3.24. ca si D.3.9. const
Lista_decl_const
Nume_const
cod_op_rel
Expresie_statica
pct_virg
const
0
loc_TS
op_egal
tip
val
pct_virg
 
D.3.25. ca si D.3.10. const
Lista_decl_const
Declar_const
const
0
0
 
D.3.26. reducere prin (P3.4)  const
Lista_decl_const
const
0
 
D.3.27. reducere prin (P3.1) Sectiune_const 0  

Rutina atasata marcajului  este similara celei atasate marcajului , dar corespunde operatiilor de inmultire/impartire care implica verificari legate de impartirea cu 0.

Rutina atasata marcajului  este urmatoarea:

Pop(ST_AT) //se elimina ')'
tip = Pop(ST_AT)
val = Pop(ST_AT)
Pop(ST_AT) //se elimina '('
Push(ST_AT, tip)
Push(ST_ATval)
 

Anexa C Anexa E