CAP.5 LA PRODUZIONE DI
CODICE
• 5.1 I languaggi intermedi
• 5.2 Le instruzioni di assegnamento
• 5.3 I collegamenti e le espressioni
booleane
• 5.4 La ripresa indietro
Traduzione cap.5 1
5.1 I linguaggi intermedi
analizzatore
sintattico
controllatore
semantico
produttore di codice
intermedio
produttore
di codice
Vantaggi: separare la parte frontale dalla parte finale,
portabilità migliorata, facilità di ottimizazzione.
Rappresentazione di un programma con un albero astratto o
con un grafo aciclico orientato.
Qui, questi alberi saranno rappresentati da un pseudo-codice,
il codice con tre indirizzi, ben adattato alle strutture di
controllo embricate e alle espressioni algebriche.
Codice di bassissimo livello.
Traduzione cap.5 2
Istruzioni x <- y op z dove x, y et z sono costanti o
nomi espliciti o prodotti dal compilatore stesso (temporanei)
e op è un operatore qualsiasi (rappresentato da _nome).
Esempio:
a := b * - c + b * - c
è rappresentato da :
t1
t2
t3
t4
t5
a
<<<<<<-
_opp c
b _mul t1
_opp c
b _mul t3
t2 _plu t4
t5
t1
t2
t3
a
<<<<-
_opp c
b _mul t1
t2 _plu t2
t3
Grafo aciclico, ottimizzato
Albero astratto, non ottimizzato
Temporari = nodi interni dell’albero o del grafo aciclico.
Traduzione cap.5 3
Varie istruzioni, con etichette simboliche se necessario,
per controllare il flusso.
• Assegnamento x <- y op z
• Assegnamento x <- op y
• Copia x <- y
• Collegamento incondizionale goto L
• Collegamento condizionale if x oprel y goto L
• Puntatori e indirizzi x <- &y et x <- *y et *x <- y
• Etichette etiq (niente operazione)
Vediamo come produrre codice a tre indirizzi con un traduttore
diretto dalla sintassi.
Traduzione cap.5 4
Qui, || disegna la concatenazione, NewTemp fabbrica una nuova
variabile temporanea e Print stampa suoi argomenti.
Regola
E  E +E
E  E *E
E–E
E  (E )
E  id
Azione
E.place := NewTemp ;
E.code := E1 .code || E2 .code ||
Print (E . place ‘<-’ E1 . place ‘_plu’ E2 . place )
E.place := NewTemp ;
E.code := E1 .code || E2 .code ||
Print (E . place ‘<-’ E1 . place ‘_mul’ E2 . place )
E.place := NewTemp ;
E.code := E1 .code ||
Print (E . place ‘<-’ ‘_opp’ E1 . place )
E.place := E1 .place ; E.code := E1 .code
E.place := id.place ; E.code :=‘ ’
Traduzione cap.5 5
5.2 Le istruzioni di assegnamento
Interazione con la tabella dei simboli.
Nelle istruzioni, invece di utilizzare i nomi, si ricerca nella
tabella dei simboli se questo nome già esiste. Se è il caso,
viene ritornato suo indice. Si no, un errore è segnalato.
Qui segue una parte della grammatica attribuita per gli assegnamenti :
I  id:=E
E  E +E
E  (E )
E  id
{ p := Look ( id.name ) ;
if p <> nil then
I.code := E .code || Print ( id.place ‘<-’ E.place )
else error }
{ E.place := NewTemp ; E.code := E1 .code || E2 .code ||
Print ( E . place ‘<-’ E1 . place ‘_plu’ E2 . place )}
{ E.place := E1 .place ; E.code := E1 .code }
{ p := Look ( id.name ) ;
if p <> nil then begin
E.place := id.place ; E.code :=‘ ’ end
else error }
Traduzione cap.5 6
Ottimizazzione dell’uso delle variabili temporanee.
Si possono reutilizzare variabili temporanee. Infatti, queste
sono "liberate" dopo la loro uso come argomento di una
operazione. Si può dunque modificare la funzione NewTemp
per ritornare la prima variabile temporanea libera.
Assegnamento degli elementi delle tabelle
Supponiamo che le tabelle abbiano una sola dimensione,
con indici da 0 fino a n – 1. Una tabella è dichiarata come
T[n].
Traduzione cap.5 7
Due tipi di costruzione utilizzano elementi di tabelle:
E id[E]
dove in elemento di una tabella è utilizzato invece di un identificatore
in un’espressione, e
I id[E]:=E
dove si realizza un assegnamento a un elemento di una tabella.
Infatti, l’indice indica solo uno spostamento dell’indirizzo in memoria.
T[5] è dunque sinonimo di *(T+5)(o, più esattamente trasformato).
Questo è realizzato con
E id[E]
I  id[E ]:= E
{p := NewTemp ; E.place := NewTemp ; E.code := E1 .code ||
Print ( p ‘<-’ id.place ‘_plu’ E1 . place ) ||
Print ( E.place ‘<- *’ p ) }
{p := NewTemp ; I.code := E1 .code || E2 .code ||
Print ( p ‘<-’ id.place ‘_plu’ E1 . place ) ||
Print (‘*’ p ‘<-’ E2 . place ) }
(Le verificazioni della presenza nella tabella dei simboli
sono state omesse)
Traduzione cap.5 8
Esempio:
Supponiamo che T e U siano due tabelle, l’istruzione
T[a + b] := U[b + T[c]] produce il codice:
t1
t2
t3
t4
t5
t6
t7
*t7
<<<<<<<<-
a _plu
T _plu
*t2
b _plu
U _plu
*t5
T _plu
t6
b
c
t3
t4
t1
Traduzione cap.5 9
5.3 I collegamenti e le espressioni booleane
Grammatica utilizzata per espressioni booleane:
E  E or E | E and E | not E | ( E ) | E oprel E | true | false
Convenzione numerica (1 = true, 0 = false)
Supponiamo che abbiamo operazioni corrispondenti nel codice
a tre indirizzi (_or _and _not e per operatori relazionali come
_equ).
La valutazione delle espressioni booleane non presenta differenze
con quella delle espressioni algebriche (Se si vuole una distinzione
tra numeri e valori logici, è meglio usare un’altro simbolo invece
del E).
Abbiamo bisogno di un construttore di etichette simboliche
NewLabel.
Traduzione cap.5 10
Azioni per un confronto.
Regola
E  E > E
Azioni
p := NewLabel ; q := NewLabel ; E.place := NewTemp ;
E.code := E1 . code || E2 . code ||
Print ( ‘if’ E1 . place ‘_leq’ E2 . place ‘goto’ p ) ||
Print ( E.place ‘<- 1’ ) ||
Print ( ‘goto’ q ) ||
Print ( p )
Print ( E.place ‘<- 0’ ) ||
Print ( q )
Traduzione cap.5 11
Azioni per un while.
Regola
I  while E do I
Azioni
p := NewLabel ; q := NewLabel ;
I.code := Print ( p ) ||
E .code ||
Print ( ‘if’E . place ‘_equ’ ‘0’ ‘goto’ q ) ||
I1 . code ||
Print ( ‘goto’ p ) ||
Print ( q )
Traduzione cap.5 12
Azioni per un if...then
Regola
I  if E then I
Azioni
p := NewLabel ;
I.code := E .code ||
Print ( ‘if’E . place ‘_equ’ ‘0’ ‘goto’ p ) ||
I1 . code ||
Print ( p )
Traduzione cap.5 13
Azioni per un if...then..else
Regola
I  if E then I else I
Azioni
p := NewLabel ; q := NewLabel ;
I.code := E .code ||
Print ( ‘if’E . place ‘_equ’ ‘0’ ‘goto’ p ) ||
I1 . code ||
Print ( ‘goto’ q ) ||
Print ( p ) ||
I2 . code ||
Print ( q )
Traduzione cap.5 14
Esempio
while a > b do if c > d then a := 1 else b := 0
produce il codice:
etiq7
if a _leq b goto etiq1
t1 <- 1
goto etiq2
etiq1
t1 <- 0
etiq2
if t1 _equ 0 goto etiq8
if c _leq d goto etiq3
t2 <- 1
goto etiq4
etiq3
t2 <- 0
etiq4
if t2 _equ 0 goto etiq5
a <- 1
goto etiq6
etiq5
b <- 0
etiq6
goto etiq7
etiq8
Questo è un poco pesante (grande numero di etichette).
Si può ottimizzare il codice.
Traduzione cap.5 15
Certe volte si utilizza un metodo di valutazione pigra delle
congiunzioni o disgiunzioni. In questa, se il valore dell’espressione
non necessita il calcolo del secondo termine dell’espressione,
non viene calcolata.
E  E land E
Azioni
p := NewLabel ; q := NewLabel ;
E.code := E1 .code ||
Print ( ‘if’ E1 . place ‘_equ’ ‘0’ ‘goto’ p ) ||
E2 . code ||
Print ( ‘if’ E2 . place ‘_equ’ ‘0’ ‘goto’ p ) ||
Print ( E.place ‘<- 1’ ) ||
Print ( ‘goto’ q ) ||
Print ( p ) ||
Print ( E.place ‘<- 0’ ) ||
Print ( q )
Traduzione cap.5 16
5.4 La ripresa indietro
L’ottimizzazione delle etichette può essere realizzato in un secondo
passo sul codice a tre indirizzi prodotto.
Si può anche evitare completamente l’uso di etichette simboliche
colla tecnica di ripresa indietro.
Come si vede nell’esempio precedente, le etichette non sono create
secondo l’ordine nel quale sono utilizzate nel codice. Certi
collegamenti devono di più essere fatti verso istruzioni non ancora
scritte.
Nella tecnica di ripresa indietro, i collegamenti sono lasciati
provvisoriamente indeterminati e vengono completati quando si
produce il codice dell’istruzione di destinazione. Questi
collegamenti sono gestiti come liste di numeri di istruzioni.
(supponiamo qui che ogni istruzione ha un numero proprio).
Traduzione cap.5 17
Questo permette anche di non scrivere i pezzi di codice in modo
separato, ma direttamente su una fila, lasciando però righe di
goto incomplete.
Per gestire le liste, abbiamo
• CreateList ( i ) fabbrica una nuova lista che contiene i e ritorna un
puntatore verso essa;
• Fusion ( p1, p2 ) concatena due liste e ritorna un puntatore;
• Back ( p, i ) inserisce i come etichetta in tutte le istruzioni
della lista p, poi libera lo spazio occupato da p.
• Una variabile globale numero contiene il numero della prossima
istruzione da produrre.
Un altro vantaggio è che la grammatica prodotta è sempre
S-attribuita.
Ogni espressione booleana ha due attributi E.true e E.false che sono
liste di istruzioni da riprendere più tardi.
Traduzione cap.5 18
E  E lor M E
E  E land M E
E  not E
E(E)
E id oprel id
E true
E false
M
{ Back (E1.false , M.num ) ;
E.true := Fusion (E1.true, E2.true ) ; E.false := E2.false }
{ Back (E1.true , M.num ) ;
E.true := E2.true ; E.false := Fusion (E1.false, E2.false ) }
{ E.false := E1.true ; E.true := E1.false }
{ E.true := E1.true ; E.false := E1.false }
{ E.true := CreateList (numero ) ;
E.false := CreateList (numero + 1) ;
Print ( ‘if ’ id 1.place oprel.op id2.place
‘ goto’ ) ;
Print ( ‘goto’ ) }
{ E.true := CreateList (numero ) ;
Print ( ‘goto’ ) }
{ E.true := CreateList (numero ) ;
Print ( ‘goto’ ) }
{ M.num := numero }
Traduzione cap.5 19
Nell’esempio a < b or c < d and e < f si ottiene finalmente:
100
101
102
103
104
105
:
:
:
:
:
:
if a
goto
if c
goto
if e
goto
_les b goto
102
_les d goto 104
_les f goto
E.true vale {100, 104}
E.false vale {103, 105}.
I collegamenti di queste
istruzioni saranno completati
più tardi.
Si nota che abbiamo utilizzato la valutazione pigra. Implementare
la valutazione normale è un pò più complicato.
Ora, la traduzioni dei collegamenti condizionali.
I  if E then I | if E then I else I | while E do I | begin L end | A
L L ; I | I
dove L è una lista di istruzioni e A un assegnamento.
Traduzione cap.5 20
Per la traduzione, si utilizzano due liste L.next et I.next che
contengono i numeri delle istruzioni che contengono
un collegamento verso l’istruzione che segue L o I.
Caso del while do :
I  while M E do M I
{ Back ( E.true, M2.num ) ;
Back (I1.next, M1.num ) ;
Print ( ‘goto’ M1.num ) ;
I.next := E.false }
Caso del if then else :
I  if E then M I N else M I { Back ( E.truei, M1.num ) ;
Back ( E.false, M2.num ) ;
I.next := Fusion (I1.next, N.next, I2.next ) }
Il marchio N serve a passare sopra il secondo I.
N
{ N.next := CreateList (numero ) ;
Print ( ‘goto’ ) }
Traduzione cap.5 21
L’assegnamento inizializza I.next e produce il codice adeguato:
I  id:=E
{ I.next := CreateList ( ) ;
Print ( id.place ‘<-’ E.place ) }
Per la riduzione in una lista :
LL;MI
{Back (L1.next, M.num );
L.next := I.next }
Si ottiene la grammatica seguente:
Traduzione cap.5 22
I  if E then M I
{ Back ( E.true, M.num ) ;
I.next := Fusion (E.false, I1.next ) }
I  if E then M I N else M I { Back ( E.true, M1.num ) ;
Back ( E.false, M2.num ) ;
I.next := Fusion (I1.next, N.next, I2.next ) }
I  while M E do M I
{ Back ( E.true, M2.num ) ;
Back (I1.next, M1.num ) ;
Prod ( ‘goto’ M1.num ) ;
I.next := E.false }
M
{ M.num := numero }
N
{ N.next := CreateList (numero ) ;
Prod ( ‘goto’ ) }
I  begin L end
{ I.next := L.next }
I  id:=E
{ I.next := CreateList ( ) ;
Print ( id.place ‘<-’ E.place ) }
LL;MI
{Back (L1.next, M.num );
L.next := I.next }
Traduzione cap.5 23
Così, il frammento:
if a < b lor c < d land e < f then
x := 1
else begin
x := 0 ;
u := 1
end ;
while a < b do x := x + 1 ;
produce :
100
101
102
103
104
105
106
107
:
:
:
:
:
:
:
:
if a
goto
if c
goto
if e
goto
x <goto
_les b goto 106
102
_les d goto 104
108
_les f goto 106
108
1
110
108
109
110
111
112
113
114
:
:
:
:
:
:
:
x <- 0
u <- 1
if a < b goto 112
goto
t1 := x _plu 1
x <- t1
goto 110
Il risultato è la variabile L e L.next vale {111}.
Traduzione cap.5 24