Génération de code intermédiaire

Code intermédiaire

Traduction des déclarations

Instructions d'affectation

Expressions booléennes

Appels de procédures

Introduction

Constitue la fin de la partie frontale du compilateur

Indépendant de la machine cible

Avantages de séparer code intermédiaire et code final :

possibilité de réutiliser le générateur de code intermédiaire pour des machines différentes

possibilité d'améliorer le code intermédiaire indépendamment de la machine cible

Peut être incorporé à l'analyseur (traducteur)

... codefinal

analyseursyntaxique

contrôleur de types

générateur de code

intermédiaire

générateur de code

final

Code intermédiaire

Les arbres syntaxiques sont déjà presque du code intermédiaire

Rappel : arbre syntaxique de a := b-4+c

-

+

id num 4

id

entrée pour b

entrée pour c

. .

. .

.

.

:= . .

id

entrée pour a

.

tmp1 := b - 4

tmp2 := tmp1 + c

a := tmp2

Code intermédiaireRappel : une grammaire attribuée qui construit l'arbre syntaxique

d'une instruction d'affectation

S --> id = E S.ptr := makeNode('=',

makeLeaf(id, id.entry), E.ptr)

E --> E + E E.ptr := makeNode('+', E1.ptr, E2.ptr)

E --> E * E E.ptr := makeNode('*', E1.ptr, E2.ptr)

E --> - E E.ptr := makeNode(unaryMinus, E1.ptr)

E --> ( E ) E.ptr := E1.ptr

E --> id E.ptr := makeLeaf(id, id.entry)

Code à trois adressesProche d'un langage d'assemblage

Utilise des noms symboliques (ex. add ou +) et des sauts

Forme générale : x := y op z

où op est un opérateur. Les trois adresses sont celles de x, y et z.

Instructions d'affectation

x := y op z x := op y

Instructions de saut

inconditionnel goto L

conditionnel if x relop y goto L

Instructions indicées

x := y [ i ] x [ i ] := y

ExempleUne grammaire attribuée qui engendre du code à trois adresses

On utilise des noms temporaires pour l'évaluation des expressions

Attributs des noeuds E

E.place contient le nom lié à l'adresse qui contiendra la valeur de E à l'exécution

E.code contient une séquence d'instructions en code intermédiaire

Cette séquence est le résultat de la traduction de E

newtemp() engendre un nouveau nom temporaire à chaque appel

gen() engendre une instruction de code à trois adresses

L'opérateur || représente la concaténation

Exemple : expressionsS --> id = E S.code := E.code || gen(id.place, ':=', E.place) ;

E --> E + E E.place := newtemp() ;

E.code := E1.code || E2.code ||

gen(E.place, ':=', E1.place, '+', E2.place) ;

E --> E * E E.place := newtemp() ;

E.code := E1.code || E2.code ||

gen(E.place, ':=', E1.place, '*', E2.place) ;

E --> - E E.place := newtemp() ;

E.code := E1.code ||

gen(E.place, ':=', unaryMinus, E1.place) ;

E --> ( E ) E.place := E1.place ; E.code := E1.code ;

E --> id E.place := id.place ; E.code := ' ' ;

Exemple : contrôle

S --> while ( E ) S S.begin := newlabel() ;

S.after := newlabel() ;

S.code := gen(S.begin, ':') || E.code ||

gen('if', E.place, '=', '0', 'goto', S.after) ||

S1.code || gen('goto', S.begin) ||

gen(S.after, ':') ||

newlabel() engendre une nouvelle étiquette d'instruction à chaque appel

Les étiquettes d'instructions servent de cible pour les sauts

Code à trois adressesL'implémentation du code à trois adresses peut se faire par

quadruplets

op, arg1, arg2, résultat

op arg1 arg2 résultat

(0) unaryMinus c t1

(1) * b t1 t2

(2) unaryMinus c t3

(3) * b t3 t4

(4) + t2 t4 t5

(5) := t5 a

Code à trois adressesou par triplets

op, arg1, arg2

en utilisant les noms des triplets comme nom du résultat

op arg1 arg2

(0) unaryMinus c

(1) * b (0)

(2) unaryMinus c

(3) * b (2)

(4) + (1) (3)

(5) := a (4)

Traduction des déclarations

On suppose que les déclarations sont groupées au début des fonctions

Adresses relatives liées aux noms locaux : variable deplct

Attributs des noeuds T (type)

T.type représente le type simple ou complexe (expression de type)

T.taille représente la place mémoire occupée par les objets du type

Schéma de traduction

Traduction des déclarationsP --> { sommet := new Env() ; deplct := 0 ; } D

D -->

D --> T id ; { sommet.mettre(id.name, T.type, deplct) ;

deplct += T.taille ; } D

T --> B { t := B.type ; w := B.taille ;

C { T.type := C.type ; T.taille := C.taille ; }

B --> int { T.type := entier ; T.taille := 4 ; }

B --> float { T.type := flottant ; T.taille := 8 ; }

C --> { C.type := t ; C.taille := w ; }

C --> [ num ] C {C.type := tableau(num.val, C1.type) ;

C.taille := num.val * C1.taille ; }

Table des symboles

Mémorise les informations sur les identificateurs contenus dans le programme

À un instant donné de la compilation, et donc à un point donné du code source, la table des symboles indique ce qui est connu sur chaque identificateur du programme dans cet environnement

Le contenu de la table des symboles évolue pendant la compilation

Quand on entre dans une boucle, on ajoute de nouvelles variables locales, et on les enlève quand on sort

Table des symboles

Entrées de la table des symboles

Correspondent à des déclarations

Si un même nom est déclaré plusieurs fois, il a plusieurs entrées

Opérations sur la table des symboles

- consultation de l'entrée correspondant à un identificateur

- insertion d'une nouvelle entrée

- empiler/dépiler un bloc d'entrées correspondant à un bloc du code source

On peut voir chaque bloc d'entrées comme une table de symboles séparée

Traduction des déclarationsUne grammaire plus complète avec les fonctions emboîtées

(comme en Pascal) ou les blocs (comme en C)

On construit une table des symboles séparée pour chaque fonction en-tête 0

a

x

readarray

exchange

quicksort

sort

en-têtereadarray en-têteexchange

en-tête

k

v

partition

quicksort

en-tête

i

j

partition

Traduction des déclarationsnew Env() crée une nouvelle table des symboles et renvoie un

pointeur sur elle

Env.empiler(table) empile une table terminée

table.mettre(nom, type, deplct) crée une entrée dans table

On utilise deux piles parallèles :

Env pour les tables des blocs

Depl pour les déplacements correspondants

Traduction des déclarationsP --> M BlocM --> ε sommet = null ; deplct = 0 ;Bloc --> { N D ; S } sommet = Env.depiler() ;

deplct= Depl.depiler() ;N --> ε Env.empiler(sommet) ; sommet = new Env

;Depl.empiler(deplct) ; deplct = 0 ;

D --> T id ; sommet.mettre(id.name, T.type, deplct) ;deplct +=T.type ;

DD --> εS --> S IS --> εI --> Bloc

Traduction des déclarationsP --> M D ; S addWidth(top(tables), top(offsets) ;

pop(tables) ; pop(offsets) ;M --> ε t := makeTable(0) ;

push(t, tables) ; push(0, offsets) ;D --> D ; DD --> id ( ) { N D ; S }

t := top(tables) ; addWidth(t, top(offsets));pop(tables) ; pop(offsets) ;enterFunc(top(tables, id.name, t) ;

D --> T identer(top(tables), id.name, T.type, top(offsets)) ;top(offsets) +=T.type ;

N --> ε t := makeTable(top(tables)) ;push(t, tables) ; push(0, offsets) ;

Traduction des déclarationsOn peut ajouter les types structures ou classes

T --> struct { L D } T.type := structure(sommet) ;T.taille := deplct ;sommet = Env.depiler() ; deplct= Depl.depiler() ;

L --> ε Env.empiler(sommet) ; sommet = new Env() ;

Depl.empiler(deplct) ; deplct = 0 ;

Traduction des déclarationsOn peut ajouter les types enregistrements, dont la traduction

est très semblable à celle des déclarations de fonctions

T --> struct { L D }T.type := struct(top(tables)) ;T.width := top(offsets);pop(tables) ; pop(offsets) ;

L --> ε t := makeTable(0) ;push(t, tables) ; push(0, offsets) ;

Affectations

Un schéma de traduction pour traduire les affectations

Le schéma crée et utilise des noms temporaires

lookup(name) consulte la table des symboles

emit() écrit une instruction de code à trois adresses

L'ordre des instructions correspond à l'ordre dans lequel elles ont été écrites

S --> id = E p := lookup(id.name) ;

if (p) emit(p, ':=', E.place) else error() ;

E --> E + E E.place := newtemp() ;

emit(E.place, ':=', E1.place, '+', E2.place) ;

E --> E * E E.place := newtemp() ;

emit(E.place, ':=', E1.place, '*', E2.place) ;

E --> - E E.place := newtemp() ;

emit(E.place, ':=', unaryMinus, E1.place) ;

E --> ( E ) E.place := E1.place ;E --> id p := lookup(id.name) ;

if (p) E.place := p else error() ;

Affectations

Adaptation au cas où les fonctions emboîtées sont autorisées

On peut utiliser la grammaire précédenteP --> D ; SD --> D ; DD --> id ( ) { D ; S }D --> T id

Il faut raffiner la fonction lookup()

On consulte d'abord la table de la fonction en cours en utilisant la pile de tables (nom local)

Si le nom n'est pas local, on consulte la table de la fonction englobante, etc.

Adressage des éléments de tableaux

L'adresse de a[i] est

base + (i - low) w

où low est la borne inférieure des indices, base l'adresse relative du début du tableau et w la taille des éléments

En séparant la partie qui peut être calculée à la compilation

i w + base - low w

Dans une instruction de code à trois adresses x := y [ z ],

base - low w correspond à y et i w à z

En langage C, a[i] est équivalent à *(a+i) et low = 0

L'expression se réduit à

i w + base

Tableaux à plusieurs dimensionsLes éléments peuvent être rangés

- ligne par ligne comme en C et en Pascal (exemple ci-dessous)

- colonne par colonne comme en Fortrana[0][0]

a[0][1]

a[0][2]

a[1][0]

a[1][1]

a[1][2]

a[i][j] j = 0 j = 1 j = 2

i = 0 base base+w base+2w

i = 1 base+3w base+4w base+5w

C'est le dernier indice qui varie le plus vite

Tableaux à plusieurs dimensionsDans un tableau à deux dimensions rangé ligne par ligne, les i1

premières lignes contiennent (i1 - low1) n2 éléments, où n2 est le nombre des valeurs possibles de i2

Adresse de a[i1][i2] :

base + ((i1 - low1) n2 + i2 - low2) w

En séparant la partie qui peut être calculée à la compilation

(i1 n2 + i2) w + base - (low1 n2 + low2) w

On généralise à k dimensions

((...((i1 n2 + i2) n3 + i3)...) nk + ik) w

+ base - ((...(low1 n2 + low2) n3 + low3)...) nk + lowk) w

La deuxième ligne peut être calculée à la compilation

Tableaux à plusieurs dimensions

En C, la deuxième ligne de la formule se réduit à

+ base

Pour traduire les références de tableau, on engendre le code qui calcule la première ligne

ek w

avec ek= (...((i1 n2 + i2) n3 + i3)...) nk + ik

On utilise la récurrence :

e1 = i1

ek= ek-1 nk + ik

Tableaux à plusieurs dimensions

Une grammaire simple :

L --> id [ Elist ] | id

Elist --> Elist ] [ E | E

mais l'attribut donnant nk sera hérité : il est obtenu à partir du nom du tableau et transmis de haut en bas par les noeuds Elist

Une version où l'attribut est synthétisé :

L --> Elist ] | id

Elist --> Elist ] [ E | id [ E

L'attribut donnant nk obtenu à partir du nom du tableau peut être transmis de bas en haut par les noeuds Elist

TableauxS --> L = E

E --> E + E

E --> ( E )

E --> L

L --> Elist ]

L --> id

Elist --> Elist ] [ E

Elist --> id [ E

Attributs

L.place est l'entrée dans la table des symboles (contient l'adresse du tableau)

L.offset contient l'adresse relative de l'élément dans le tableau

S --> L = E if (L.offset)

emit(L.place, '[', L.offset, ']', ':=', E.place) ;

else emit(L.place, ':=', E.place) ;

E --> E + E ...

E --> ( E ) ...

E --> L if (L.offset) {

E.place := newtemp() ;

emit(E.place, ':=', L.place, '[', L.offset, ']', ) ; }

else E.place = L.place ;

L --> Elist ] L.place := newtemp() ; L.offset := newtemp() ;

emit(L.place, ':=', const(Elist.array)) ;

emit(L.offset, ':=', width(Elist.array), '*',

Elist.place) ;

L --> id L.place := id.place ; L.offset := 0 ;

Elist --> Elist ] [ E t := newtemp() ; m := Elist1.ndim + 1 ;

emit(t, ':=', Elist1.place, '*',

limit(Elist1.array, m)) ;

emit(t, ':=', t, '+', E.place) ; Elist.ndim := m ;

Elist.array := Elist1.array ; Elist.place := t ;

Elist --> id [ E Elist.ndim := 1 ; Elist.array := id.place ;

Elist.place := E.place ;

const() donne l'adresse du tableau connue à la compilation

width() donne w limit() donne nm

Expressions booléennes

Les expressions booléennes sont souvent employées dans des conditions d'instructions de contrôle : if, while, for

Grammaire

E --> E or E | E and E | not E | ( E ) | id relop id | true | false

Méthodes de traduction

1. Comme les expressions arithmétiques

2. Par sauts (évaluation paresseuse)

Évaluation arithmétique0 représente faux, 1 représente vrai

Code source

b or x < y

Code intermédiaire

100 : t := b

101 : if x < y goto 104

102 : u := 0

103 : goto 105

104 : u := 1

105 : v:= t or u

Si b vaut vrai, on exécute quand même les instructions 101 et 105

Évaluation paresseuse

On évite de calculer toutes les sous-expressions quand ce n'est pas nécessaire

Dès qu'on peut déduire la valeur de l'expression à partir de la valeur d'une sous-expression, on fait un saut pour court-circuiter la fin

Première version

On suppose qu'on sait vers quelles étiquettes il faut sauter quand on a trouvé la valeur de E : E.vrai si la valeur est vraie, E.faux si elle est fausse

Évaluation paresseuse

Dans le code intermédiaire qui traduit E, certaines instructions peuvent contenir un saut inconditionnel vers E.vrai ou vers E.faux

E

E.vrai E.faux

E

E

E.vrai E.faux

E

E

E.vrai E.faux

E --> E and E E --> E or E

E.vrai E.faux E.vrai E.faux

ExempleCode source a < b or c < d and e < f

Code intermédiaire

if a < b goto Evrai

goto E1

E1: if c < d goto E2

goto Efaux

E2: if e < f goto Evrai

goto Efaux

Difficulté si on ne connaît pas la valeur de Evrai et Efaux

RéalisationProblème

En général, les instructions cibles E.vrai et E.faux sont engendrées après la traduction de E

Solutions1. Opérer en deux passesPremière passe : les étiquettes sont des noms temporaires

Deuxième passe : on les remplace par les adresses des instructions

2. Reprise arrièreDans E.vrai, on ne met plus le nom de l'instruction cible, mais la

liste des sauts vers l'instruction cibleQuand on engendre ces sauts, on les laisse incompletsDès qu'on connaît le numéro de l'instruction cible, on les complète

Reprise arrière : exemple

100 : if a < b goto

101 : goto 102

102 : if c < d goto 104

103 : goto

104 : if e < f goto

105 : goto

E.v={100,104}E.f={103,105}

E.v={100}E.f={101} or

and

a < b

M.next=102

E.v={104}E.f={103,105}

E.v={102}E.f={103}

c < d

M.next=104E.v={104}E.f={105}

e < f

ε

ε

Reprise arrière

makeList(i) crée une nouvelle liste chaînée d'instructions de saut contenant seulement i

merge(p, q) concatène deux listes chaînées d'instructions

backpatch(p, i) complète les instructions de saut contenues dans la liste p en leur donnant pour cible l'instruction i

E.vrai contient la liste des sauts incomplets qui doivent être exécutés dès qu'on sait que E est vraie

De même pour E.faux

E.vrai et E.faux seront des attributs synthétisés

Grammaire

On ajoute à la grammaire précédente un marqueur M qui sert à sauvegarder le numéro de la prochaine instruction dans un attribut M.next

Ce numéro est conservé dans next, mis à jour par emit()

E --> E or M E E --> E and M E

E --> not EE --> ( E )

E --> id relop id E --> true

E --> falseM --> ε

Schéma de traductionE --> E or M E backpatch(E1.f, M.next) ; E.f := E2.f ;

E.v := merge(E1.v, E2.v) ;

E --> E and M E backpatch(E1.v, M.next) ; E.v := E2.v ;

E.f := merge(E1.f, E2.f) ;

E --> not E E.v := E1.f ; E.f := E1.v ;

E --> ( E ) E.v := E1.v ; E.f := E1.f ;

E --> id relop id E.v := makeList(next) ;

emit('if', id1.place, relop, id2.place, 'goto') ;

E.f := makeList(next) ; emit('goto') ;

E --> true E.v := makeList(next) ; emit('goto') ;

E --> false E.f := makeList(next) ; emit('goto') ;

M --> ε M.next = next ;

Instructions de contrôle

S --> if ( E ) S | if ( E ) S else S | while ( E ) S

E.code

S1.code

si-alors

...

...

E.v E.f

si-alors-sinon

...

...

E.v E.fE.code

S1.code

goto

S2.code

...

E.code

S1.code

goto

tant que

...

E.v E.f

...

...

Instructions de contrôleS --> if ( E ) S | if ( E ) S else S | while ( E ) S | { L } | A

L --> L ; S | S

A représente une affectation

Une instruction S peut contenir des sauts vers la première instruction à exécuter après S

Ces sauts sont engendrés incomplets et listés dans S.suivant

De même pour L et L.suivant

On ajoute des marqueurs M et N

Schéma de traductionS --> if ( E ) M S backpatch(E.v, M.next) ;

S.suivant := merge(E.f, S1.suivant) ;

M --> ε M.next := next ;

S --> while ( M E ) M S backpatch(E.v, M2.next) ;

backpatch(S1.suivant, M1.next) ;

S.suivant := E.f ; emit('goto', M1.next) ;

S --> if ( E ) M S else N S backpatch(E.v, M.next) ;

backpatch(E.f, N.next) ;

S.suivant := merge(S1.suivant, N.suivant,

S2.suivant) ;

N --> ε N.suivant := makeList(next) ; emit('goto') ;

N.next := next ;

Schéma de traduction

S --> { L } S.suivant := L.suivant ;

S --> A S.suivant := makelist() ;

L --> L ; M S backpatch(L.suivant, M.next) ;

L.suivant := S.suivant ;

L --> S L.suivant := S.suivant ;

ExempleCode source while (a < b) if (c < d) x = y + z ;

Code intermédiaire

100 : if a < b goto 102

101 : goto 107

102 : if c < d goto 104

103 : goto 100

104 : t := y + z

105 : x := t

106 : goto 100

107 :