CAP.4 LA TRADUZIONE
•
•
•
•
•
4.1 Le grammatiche con attributi
4.2 Le grammatiche S-attribuite
4.3 Le grammatiche L-attribuite
4.4 La traduzione discendente
4.5 La valutazione ascendente degli attributi
ereditati
• 4.6 La valutazione ricorsiva
Traduzione cap4 1
4.1 Le grammatiche con attributi
Ogni variabile ha degli attributi.
Azioni che permettono il calcolo di questi attributi sono incluse
nelle regole.
Esempio:
Regola
A  E$
E  E +T
ET
T  T *F
TF
F  (E )
Fn
Azioni
print(E.val)
E.val := E1.val + T.val
E.val := T.val
T.val := T1.val * F.val
T.val := F.val
F.val := E.val
F.val := n.vallex
Grammatica con attributi per un calcolatore
Traduzione cap4 2
Situazione generale:
Regola A   e azioni b := f(c1, c2 ,..., ck).
Attributi:
• ereditati: se b è un attributo di un simbolo che appare in , e se i ci
sono attributi di simboli in  o di A ;
• sintetizzati: se b è un attributo di A, e se i ci sono attributi di
simboli in  o attributi ereditati di A.
Nell’esempio, tutti gli attributi sono sintetizzati.
Albero decorato: albero sintattico al quale vengono aggiunti gli
attributi e i loro valori.
Problema: ordine della valutazione degli attributi. Se tutti sono
sintetizzati, la valutazione si può fare dalle foglie verso il radice.
Traduzione cap4 3
Esempio: 3 * 5 + 4$
Freccie : grafo di dipendenze,
impone l’ordine della valutazione.
A print(19)
E val = 19
E val = 15
$
T val = 4
+
T val = 15
T val = 3
F val = 4
F val = 5
*
F val = 3
n vallex= 4
n vallex= 5
n vallex= 3
Traduzione cap4 4
Attributi ereditati:
Esempio: Dichiarazione di variabili in C
Regola
D  TL
T  int
T  real
L  L , id
L  id
Azioni
L.he := T.type
T.type := integer
T.type := real
L1.he := L.he
addtype(id.ent, L.he)
addtype(id.ent, L.he)
L’attributo L.he è ereditato; gli altri sono sintetizzati.
Traduzione cap4 5
Esempio: real id1, id2, id3
D
T type = real
real
he = real L addtype
he = real L addtype
he = real L addtype
,
,
id3 ent = 3
id2 ent = 2
id1 ent = 1
La valutazione è possibile perchè il grafo delle dipendenze
è aciclico. Valutazione dedotta da un ordine topologico.
Traduzione cap4 6
4.2 Le grammatiche S-attribuite
Si dice che una grammatica è S-attribuita quando tutti gli
attributi sono sintetizzati.
L’analisi ascendente è particolarmente adatta alla valutazione
degli attributi di una grammatica S-attribuita.
A ogni stato corrisponde un simbolo col quale si raggiunge
questo stato. L’attributo sintetizzato di questo simbolo può
essere messo nella pila accanto allo stato corrispondente.
Gli attributi necessari per il calcolo si trovano già nella pila,
a distanza conosciuta dalla cima di essa.
Se c’è la regola A  XYZ con azione A.a := f(X.x, Y.y, Z.z),
prima della riduzione, i valori X.x, Y.y, Z.z sono
val[top – 2], val[top – 1] et val[top]; Dopo riduzione, si
mette A.a come nuovo val[ntop].
Traduzione cap4 7
Esempio: espressioni aritmetiche e calcolatrice.
Regole
0 A  E$
1 E  E +T
2ET
3 T  T *F
4TF
5 F  (E )
6Fn
Azioni
print(val[top])
val[ntop] := val[top – 2] + val[top]
val[ntop] := val[top – 2] * val[top]
val[ntop] := val[top – 1]
val[ntop] := n.vallex
L’indice top è quello della cima della pila prima della riduzione.
L’indice ntop è quello della cima della pila dopo la riduzione.
L’automa LR è quello che è già stato costruito. Il valore numerico
è ritornato dall’analizzatore lessicale.
Per le regole 2 e 4, ntop = top e val[ntop] = val[top].
Non c’è dunque niente da fare.
Traduzione cap4 8
Esempio: (3 + 2) * 4 $
Stat
Valore
0
04
045
043
042
048
0486
04865
04863
04869
048
0 4 8 11
03
02
*
**
**3
**3
**3
**3
**3*
**3*2
**3*2
**3*2
**5
**5*
*5
*5
Parte non
tradotta
(3 + 2) * 4 $
3 + 2) * 4 $
+ 2) * 4 $
+ 2) * 4 $
+ 2) * 4 $
+ 2) * 4 $
2) * 4 $
)*4$
)*4$
)*4$
)*4$
*4$
*4$
*4$
Stato
Valore
027
0275
0 2 7 10
02
01
*5*
*5*4
*5*4
*20
*20
print(20)
Parte non
tradotta
4$
$
$
$
$
Il * segnala che non esiste un
attributo corrispondente.
La struttura de dati adeguata è
una pila di record(stato, attributo)
Traduzione cap4 9
4.3 Le grammatiche L-attribuite
Gli attributi ereditati dipendono solo dagli attributi ereditati della
variabile alla sinistra della regola, e dagli attributi (sintetizzati o
ereditati) delle variabili che appaiono prima. Gli attributi
sintetizzati possono dipendere da tutti gli altri attributi.
Così, il calcolo degli attributi si può fare mediante un percorso
in profondità dell’albero di derivazione, con precedenza a sinistra.
h A s
h B s
h C s
h D s
(Certe freccie non sono indicate)
Traduzione cap4 10
Schemi di traduzione:
Le azioni vengono inserite nelle regole:
1. Un attributo ereditato di una variabile in parte destra di regola
è calcolato con un’azione inserita prima di questa variabile;
2. Un’azione non può referirsi a un simbolo che appare alla destra
di questa azione;
3. Un attributo sintetizzato della variabile alla sinistra della regola
è calcolato dopo che tuttli gli argomenti dei quali dipende sono
stati calcolati (è il caso se l’azione è inserita alla fine della regola)
Le grammatiche L-attribuite possono essere convertite in schemi di
traduzione.
Traduzione cap4 11
Esempio 1: dichiarazione di variabili
D  T{L.he := T.type}L
T  int{T.type := integer}
T  real{T.type := real}
L  {L1.he := L.he}L , id{addtype(id.ent, L.he)}
L  id{addtype(id.ent, L.he)}
Traduzione cap4 12
Esempio 2: il linguaggio di tipografia TeX
E’ un linguaggio di descrizione di formule matematiche.
L’oggetto di base è la scatola B. I suoi attributi sono la taglia di base
dei caratteri che contiene, B.ps, attributo ereditato dall’ambiente e
sua altezza B.ht, attributo sintetizzato.
Utilizzeremo le funzioni shrink che diminuisce la taglia
proporzionalmente a una scala (per gli indici) e disp che calcola
l’altezza di una scatola con un indice (come E1 nel esempio).
Per esempio, E _ 1 .val specifica, in un ambiente di 12
punti, la composizione seguente:
E
1
.val
Traduzione cap4 13
Si possono costruire la grammatica L-attribuita e lo schema di
traduzione corrispondente:
Regola
SB
B  BB
B  B _B
T  text
Azioni
B.ps := 10
S.ht := B.ht
B1.ps := B.ps
B2.ps := B.ps
B.ht := max(B1.ht, B2.ht)
B1.ps := B.ps
B2.ps := shrink(B.ps)
B.ht := disp(B1.ht, B2.ht)
B.ht := text.h * B.ps
Schema di traduzione
S
{B.ps := 10}
B {S.ht := B.ht}
B
{B1.ps := B.ps}
B
{B2.ps := B.ps}
B
{B.ht := max(B1.ht, B2.ht)}
B
{B1.ps := B.ps }
B
_ {B2.ps := shrink(B.ps)}
B {B.ht := disp(B1.ht, B2.ht)}
T  texte{B.ht := text.h * B.ps}
Traduzione cap4 14
4.4 La traduzione discendente
Implementazione della traduzione discendente per le grammatiche
S-attribuite.
Problema: Eliminazione della ricorsività a sinistra.
Grammatica risultata L-attribuita, sotto la forma di uno schema
di traduzione, con una nuova variabile.
Principio:
A  AY
{A.a := g(A1.a, Y.y)}
AX
{A.a := f(X.x)}
Grammatica modificata:
A X
R
R Y
R
R 
{R.he := f(X.x)}
{A.a := R.s}
{R1.he := g(R.he, Y.y)}
{R.s := R1.s}
{R.s := R.he}
Traduzione cap4 15
Esempio:
E  E +T
E  E –T
ET
T  (E)
Tn
{E.val := E1.val + T.val}
{E.val := E1.val – T.val}
{E.val := T.val}
{T.val:= E.val}
{T.val := n.val}
Dopo modifiche:
E T
R
R  +T
R
R  –T
R
R 
T  (E)
Tn
{R.he := T.val}
{E.val := R.s}
{R1.he := R.he + T.val}
{R.s := R1.s}
{R1.he := R.he – T.val}
{R.s := R1.s}
{R.s := R.he}
{T.val:= E.val}
{T.val := n.val}
Traduzione cap4 16
Valutazione di 9 – 5 + 2 :
E val=6
T val=9
he=9 R s=6
–
n val=9
T val=5
he=4 R s=6
+
n val=5
T val=2
n val=2
he=6 R s=6

Traduzione cap4 17
Metodo generale.
Dato: Uno schema di traduzione non ricorsivo a sinistra,
associato a una grammatica L-attribuita. Si suppone
che ogni variabile ha un solo attributo sintetizzato.
Risultato: Codice per un traduttore.
Metodo:
1. A ogni variabile A vienne associata una funzione che ritorna
il valore dell’attributo sintetizzato di A. I suoi parametri sono gli
attributi ereditati di A. Per ogni attributo di ogni variabile che
appare in parte destra di una produzione di A, si dichiara una
variabile locale.
2. Il codice di A fa la scelta della regola dipendente dal simbolo di
previsione (grammatica LL(1)).
Traduzione cap4 18
3. La parte del codice associata a una regola di riscrittura di A contiene:
(a) Per un terminale (unità lessicale) X con attributo sintetizzato
X.x, salvare il suo valore nella variabile locale dichiarata per
questo attributo. Verificare poì la validità di questo terminale
leggendo il testo all’ingresso.
(b) Per una variabile B, assegnare c := B(b1, b2 ,..., bk) dove
b1, b2 ,..., bk sono le variabili locali create per gli attributi
ereditati di B e c è quella creata per l’attributo sintetizzato di B.
(c) Per un’azione, copiare suo codice dove appare nello schema,
sostituendo ogni referenza a un attributo con la variabile
locale associata. L’ultima azione (che ritorna il valore
dell’attributo sintetizzato di A) indica il valore ritornato dalla
funzione A.
Traduzione cap4 19
Esemple : grammatica precedente, aumentatta con A  E$
function E() ;
var tval, rhe, rs : integer ;
begin tval := T() ; rhe := tval ; rs := R(rhe) ; E := rs
end ;
function R(x : integer) ;
var tval, r1he, r1s : integer ;
begin
if prevision = ‘+’ then {regola R > +TR}
begin match(‘+’) ; tval := T(); r1he := x + tval ; r1s := R(r1he) ; R := r1s
end
else if prevision = ‘–’ then {regola R > –TR}
begin match(‘–’) ; tval := T(); r1he := x – tval ; r1s := R(r1he) ; R := r1s
end
else R := x {regola R > epsilon}
end;
Traduzione cap4 20
functionT() ;
var eval, nval: integer ;
begin
if prevision = ‘(‘ then {regola T > (E)}
begin match(‘(‘) ; eval := E() ; match(‘)’) ; T := eval
end
else if prevision = number then {regola T > n}
begin nval := number_val ; match(number) ; T := nval
end
else writeln(‘syntactic error’)
end ;
procedure A ;
var eval : integer ;
begin eval := E() ; match(‘$’) ; println(eval)
end ;
Questo codice può essere ottimizzato. Attento all’ordine di valutazione!
Traduzione cap4 21
4.5 La valutazione ascendente degli attributi ereditati
Problema: le azioni possono essere effettuate solamente
in fine di regola, quando si riduce. Il metodo presentato qui
permette di trattare tutte le grammatiche L-attribuite
associate a una grammatica LL(1), e un certo numero di
altre grammatiche LR(1) (però non tutte!) con un analisi
ascendente.
Eliminazione delle azioni interne
Vanno inserite variabili speciali, i marchi, che si riscrivano solo
come parola vuota. Il loro uso è solo di prendere in conto le
azioni interne.
Traduzione cap4 22
Esempio:
Schema di traduzione che stampa la forma postfissa di
un'espressione con somme e differenze.
E  TR
R  +T{print('+')}R | – T{print(' – ')}R | 
T  n {print(n.val)}
Diventa:
E  TR
R  +TMR | – TNR | 
M  {print('+')}
N  {print(' – ')}
T  n {print(n.val)}
Così, le azioni possono essere effettuate immediatamente prima
della riduzione.
Traduzione cap4 23
Attributi ereditati presenti sulla pila di analisi
Caso frequente: attributo ereditato = copia di un attributo
sintetizzato già presente sulla pila. Si può dunque utilizzare
quest'attributo invece dell'attributo ereditato.
Esempio: dichiarazione di tipo di variabili.
D T
{L.he := T.type}
L
T  int {T.type := integer}
T  real {T.type := real}
L
{L1.he := L.he}
L , id {addtype(id.ent, L.he)}
L  id
{addtype(id.ent, L.he)}
Qui, L.he è sempre una copia di T.type, che si trova
immediatamente prima nella pila.
Traduzione cap4 24
Per simplicità, i numeri degli stati sono sostituiti da variabili.
stato
testo
int
T
Tp
TL
TL,
TL,q
TL
TL,
TL,r
TL
D
int p,q,r
p,q,r
p,q,r
,q,r
,q,r
q,r
,r
,r
r
regola
T  int
L  id
L  L,id
L  L,id
D  TL
Traduzione cap4 25
Programma associato:
Regola
D  TL
T  int
T  real
L  L , id
L  id
Istruzioni
val[ntop] := integer
val[ntop] := real
addtype(val[top], val[top – 3] )
addtype(val[top], val[top – 1] )
Questo è reso possibile perchè si sà dove si trova nella pila l'attributo
ereditato necessario.
Esempio:
Regola
S  aAC
S  bABC
Cc
Azioni
C.h := A.s
C.h := A.s
C.s := g(C.h)
C.h est une copia di A.s.
Ma non si sà se il valore necessario
nell'ultima regola si trova a val[top – 1]
oppure a val[top – 2].
Traduzione cap4 26
Regola
S  aAC
S  bABMC
Cc
M
Azioni
C.h := A.s
M.h := A.s ; C.h := M.s
C.s := g(C.h)
M.s := M.h
In questo modo, il valore di C.h è sempre il valore dell'attributo
sintetizzato della variabile immediatamente alla sinistra di C. Si
trova dunque sempre a top – 1 quando se ne bisogna in
C.s := g(C.h).
Regola
S  aAC
S  bABMC
Cc
M
Istruzioni
val[ntop] := g(val[top – 1])
val[ntop] := val[top – 1]
Traduzione cap4 27
si possono utilizzare marchi quando le regole non sono
soltanto regole di copia.
Esempio:
S  aAC
diventa:
C.h := f(A.s)
S  aAMC
M
M.h := A.s ; C.h := M.s
M.s := f(M.h)
Esempio: Ritorniamo a TeX, con marchi incorporati.
Traduzione cap4 28
Originale
Regola
SB
B  BB
B  B _B
T  text
Azioni
B.ps := 10
S.ht := B.ht
B1.ps := B.ps
B2.ps := B.ps
B.ht := max(B1.ht, B2.ht)
B1.ps := B.ps
B2.ps := shrink(B.ps)
B.ht := disp(B1.ht, B2.ht)
B.ht := text.h * B.ps
Con marchi
Regola
S  LB
L
B  BMB
B  B_NB
B  text
M
N
Azioni
B.ps := L.s
S.ht := B.ht
L.s := 10
B1.ps := B.ps
M.h := B.ps
B2.ps := M.s
B.ht := max(B1.ht, B2.ht)
B1.ps := B.ps
N.h := B.ps
B2.ps := N.s
B.ht := disp(B1.ht, B2.ht)
B.ht := text.h * B.ps
M.s := M.h
N.s := shrink(N.h)
Traduzione cap4 29
Programma:
Regola
S  LB
L
B  BMB
B  B sub NB
B  texte
M
N
Istruzioni
val[ntop] := val[top]
val[ntop] := 10
val[ntop] := max(val[top – 2] , val[top])
val[ntop] := disp(val[top – 3] , val[top])
val[ntop] := val[top] * val[top – 1]
val[ntop] := val[top]
val[ntop] := shrink(val[top – 1])
Algoritmo generale:
Dato: Grammatica L-attribuita, LL(1);
(può fallire se solo LR(1))
Risultato: Programma per un traduttore ascendente.
Regole della forma: A  X1X2 ... Xn; supponiamo un solo attributo ereditato per ogni variabile, A.h e un solo attributo sintetizzato per simbolo, X.s.
Traduzione cap4 30
Regola
Azioni
A  X1X2 ... Xk ... Xn ; ..., Xk.h := fk(A.h,..., Xi.h, Xi.s,..., Xk -1.h, Xk -1.s), ... ,
A.s := g(A.h,..., Xi.h, Xi.s,...)
Si sostituisce con: A  M1X1M2X2 ... Mn Xn ; L'attributo Xk.h è
sostituito da un attributo sintetizzato Mk.s.
Regole
Azioni
A  M1X1M2X2 ... MkXk ... MnXn ;
..., Mk.h := fk(A.h,..., Mi.s, Xi.s,..., Mk -1.s, Xk -1.s),
Xk.h := Mk.s,...
A.s := g(A.h,..., Mi.s, Xi.s,...)
Mk ;
Mk.s := Mk.h
Si può dimostrare che l'attributo ereditato A.h si trova sulla pila sempre
immediatamente alla sinistra della posizione associata a M1.
Traduzione cap4 31
Infatti, Xk.h serve solo per calcolare Xk.s ed è una copia dell'attributo
che precede immediatamente.
Quando  è ridotto in Mk, si trova A.h a val[top – 2k + 2], poi
M1.s a val[top – 2k + 3], X1.s a val[top – 2k + 4] ecc.
Regole
A  M1X1M2X2 ... MkXk ... MnXn ;
Istruzioni
val[ntop] := g(val[top – 2n + 1],..., val[top – 2n – 1 + 2k], val[top – 2n + 2k],
..., val[top – 1], val[top])
Mk  ; val[ntop] := fk(val[top – 2k + 2],..., val[top – 2k + 1 + 2i], val[top – 2k + 2 + 2i],
..., val[top – 1], val[top])
Rimarchi: Se Xk non ha attributi ereditati (caso frequente),
è inutile introdurre Mk.
Si può spesso fare a meno di M1, soprattutto se l'attributo X1.h
è una copia di A.h.
In questi casi, i valori precedenti delle posizioni degli attributi non sono
più validi e devono essere modificati in modo adatto.
Traduzione cap4 32
4.6 La valutazione ricorsiva
Certe volte, la valutazione non si può fare in un solo passo.
In questo caso, l'albero di analisi vienne costruito esplicitamente
e la valutazione degli attributi si può fare se il grafo di
dipendenza degli attributi è aciclico.
Gli attributi possone essere valutati in modo ricorsivo se possono
essere valutati nello stesso ordine in tutte le produzioni di ogni
variabile.
Nell'esempio seguente, ci sono due attributi sintetizzati s e t e uno
ereditato h. Il contesto è quello del sovraccarico dei tipi di un
identificatore in ADA. Il primo, s, rappresenta l'insieme dei tipi
possibili, h è l'informazione contestuale e t è il tipo finale
dedotto dai primi due.
Traduzione cap4 33
Regola
SE
E  EE
E  id
Azione
E.h := g(E.s)
S.s := E.t
E.s := fs(E1.s, E2.s)
E1.h := fh1(E.h)
E2.h := fh2(E.h)
E.t := ft(E1.t, E2.t)
E.s := id.s
E.t := l(E.h)
Grafi di dipendenze
S
h
h
h
E s
s
E
E
t
s
s
t
t
h E
s
t
Gli attributi di E possono sempre
h E
s t
essere valutati nell'ordine s, h, t.
Quindi, la funzione per calcolare
E.t deve avere un parametro per
id s
E.h.
Da dove risulta il codice seguente, nel quale n disegna un nodo
dell'albero di analisi e Figlio(n,i) è il i-iesimo figlio di n.
Traduzione cap4 34
function Es(n) ;
begin case la regola al nodo n equals
E  EE : s1 := Es(Figlio(n,1)) ; s2 := Es(Figlio(n,2)) ; return fs(s1,s2) ;
E  id : return id.s ;
other : Errore
end case
end function ;
function Et(n, h) ;
begin case la regola al nodo n equals
E  EE : h1 := fh1(h) ; t1 := Et(Figlio(n,1), h1) ;
h2 := fh2(h) ; t1 := Et(Figlio(n,2), h2) ; return ft(t1,t2) ;
E  id : return l(h) ;
other : Errore
end case
end function ;
function Ss(n) ;
begin s := Es(Figlio(n,1)) ; h := g(s) ; t := Et(Figlio(n,1),h) ; return t
end function ;
Traduzione cap4 35