Traduzione cap.5 1

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 2

5.1 I linguaggi intermedi

analizzatoresintattico

controllatoresemantico

produttore di codiceintermedio

produttoredi 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 3

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

t1 <- _opp ct2 <- b _mul t1t3 <- _opp ct4 <- b _mul t3t5 <- t2 _plu t4 a <- t5

è rappresentato da :

t1 <- _opp ct2 <- b _mul t1t3 <- t2 _plu t2 a <- t3

Albero astratto, non ottimizzato

Grafo aciclico, ottimizzato

Temporari = nodi interni dell’albero o del grafo aciclico.

Traduzione cap.5 4

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 5

Regola AzioneE E +E E.place := NewTemp ;

E.code := E1 .code || E2 .code || Print (E . place ‘<-’ E1 . place ‘_plu’ E2 . place )

E E *E E.place := NewTemp ;E.code := E1 .code || E2 .code || Print (E . place ‘<-’ E1 . place ‘_mul’ E2 . place )

E – E E.place := NewTemp ;E.code := E1 .code || Print (E . place ‘<-’ ‘_opp’ E1 . place )

E (E ) E.place := E1 .place ; E.code := E1 .codeE id E.place := id.place ; E.code :=‘ ’

Qui, || disegna la concatenazione, NewTemp fabbrica una nuova variabile temporanea e Print stampa suoi argomenti.

Traduzione cap.5 6

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 { p := Look ( id.name ) ; if p <> nil then I.code := E .code || Print ( id.place ‘<-’ E.place )

else error } E E +E { E.place := NewTemp ; E.code := E1 .code || E2 .code ||

Print ( E . place ‘<-’ E1 . place ‘_plu’ E2 . place )}E (E ) { E.place := E1 .place ; E.code := E1 .code }E id { p := Look ( id.name ) ;

if p <> nil then begin E.place := id.place ; E.code :=‘ ’ end

else error }

Traduzione cap.5 7

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 8

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]:=Edove 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 conE id[E] {p := NewTemp ; E.place := NewTemp ; E.code := E1 .code ||

Print ( p ‘<-’ id.place ‘_plu’ E1 . place ) || Print ( E.place ‘<- *’ p ) }

I id[E ]:= E {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 9

Esempio:Supponiamo che T e U siano due tabelle, l’istruzione T[a + b] := U[b + T[c]] produce il codice:

t1 <- a _plu bt2 <- T _plu ct3 <- *t2t4 <- b _plu t3t5 <- U _plu t4t6 <- *t5t7 <- T _plu t1

*t7 <- t6

Traduzione cap.5 10

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 11

Azioni per un confronto.

E E > E

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 )

Regola

Azioni

Traduzione cap.5 12

Azioni per un while.

I while E do I

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 )

Regola

Azioni

Traduzione cap.5 13

Azioni per un if...then

I if E then IRegola

Azionip := NewLabel ;I.code := E .code ||

Print ( ‘if’E . place ‘_equ’ ‘0’ ‘goto’ p ) ||I1 . code ||Print ( p )

Traduzione cap.5 14

Azioni per un if...then..else

I if E then I else IRegola

Azionip := 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 15

Esempiowhile a > b do if c > d then a := 1 else b := 0

produce il codice:etiq7if a _leq b goto etiq1t1 <- 1goto etiq2etiq1t1 <- 0etiq2if t1 _equ 0 goto etiq8if c _leq d goto etiq3t2 <- 1goto etiq4etiq3t2 <- 0etiq4

if t2 _equ 0 goto etiq5a <- 1goto etiq6etiq5b <- 0etiq6goto etiq7etiq8

Questo è un poco pesante (grande numero di etichette).Si può ottimizzare il codice.

Traduzione cap.5 16

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 EAzioni

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 17

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 18

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 19

E E lor M E{ Back (E1.false , M.num ) ; E.true := Fusion (E1.true, E2.true ) ; E.false := E2.false }

E E land M E { Back (E1.true , M.num ) ; E.true := E2.true ; E.false := Fusion (E1.false, E2.false ) }

E not E { E.false := E1.true ; E.true := E1.false }E ( E ) { E.true := E1.true ; E.false := E1.false }E id oprel id { E.true := CreateList (numero ) ;

E.false := CreateList (numero + 1) ; Print ( ‘if ’ id 1.place oprel.op id2.place

‘ goto’ ) ; Print ( ‘goto’ ) }

E true { E.true := CreateList (numero ) ; Print ( ‘goto’ ) }

E false { E.true := CreateList (numero ) ; Print ( ‘goto’ ) }

M { M.num := numero }

Traduzione cap.5 20

Nell’esempio a < b or c < d and e < f si ottiene finalmente:

100 : if a _les b goto101 : goto 102102 : if c _les d goto 104103 : goto104 : if e _les f goto105 : goto

E.true vale {100, 104}E.false vale {103, 105}.I collegamenti di questeistruzioni saranno completatipiù 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 | AL L ; I | I

dove L è una lista di istruzioni e A un assegnamento.

Traduzione cap.5 21

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 22

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 ; M I {Back (L1.next, M.num ); L.next := I.next }

Si ottiene la grammatica seguente:

Traduzione cap.5 23

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 ; M I {Back (L1.next, M.num ); L.next := I.next }

Traduzione cap.5 24

if a < b lor c < d land e < f thenx := 1else begin

x := 0 ;u := 1

end ;while a < b do x := x + 1 ;

Così, il frammento:

produce :

100 : if a _les b goto 106101 : goto 102102 : if c _les d goto 104103 : goto 108104 : if e _les f goto 106105 : goto 108106 : x <- 1107 : goto 110

108 : x <- 0109 : u <- 1110 : if a < b goto 112111 : goto112 : t1 := x _plu 1113 : x <- t1114 : goto 110

Il risultato è la variabile L e L.next vale {111}.