Génération de code intermédiaire
Formes Possibles
Les différentes formes possibles de code intermédiaire sont
- arbre de syntaxe abstraite
- notation polonaise inversée (forme linéaire de l'arbre de syntaxe)
- un code à trois adresses : une séquence d'instructions étiquettée dont chaque intruction utilise au plus 3 adresses de variables de référence
Un exemple représentatif:
x := y op z
où x,y, et z sont des noms de variables qui proviennent du texte source, ou des noms de variables temporaires générées par la compilation, et op est un opérateur quelconque.
| Catalogue des instructions à trois adresses | |
|---|---|
| Instruction | Sens |
| x := y op z | affectation et opération binaire |
| x := op y | affectation et opération unaire |
| y := y | affectation |
| goto l | branchement inconditionnelle, ou l est un étiquette |
| if x rel y goto l | branchement conditionnel, où rel est un opérateur relationnel binaire (<, >, = , etc). |
| param x call y, n | x est le nom d'un argument, y est le nom d'une fonction ou procédure, n est le nombre d'arguments. Ex. : |
| x := *y *x := y x:= &y | affectations avec des pointeurs |
| x := y[i] x[j] := y | affectation avec indices de tableaux |
Implantations du code à 3 adresses
Ces instructions à trois adresses constituent une forme abstraite du code intermédiaire. Classiquement, ces instructions sont représentées par une structure à plusieurs champs : quadruplets, triplets, triplets indirectes.
- quadruplets :
(op, arg1, arg2, cible). Lorsqu'il n'y a qu'un argument, ou pas d'argument, on met un blanc à la place. Idem pour l'opérateur dans le cas d'un branchement inconditionnel. - triplets : l'étiquette de l'instruction sert à référencer le résultat (cible)
- triplets indirects : le code intermédiaire est la liste des pointeurs sur les triplets.
Exemple : A := -B*(C+D)
| Code à 3 adresses | Quadruplets | Triplets |
|---|---|---|
| T1 := -B | ( '-' , B, _, T1) | [0] ( '-', B, _ ) |
| T2 := C+D | ( '+', C, D, T2) | [1] ('+', C, D) |
| T3 := T1 * T2 | ('*', T1, T2, T3) | [2] ('*', [0], [1] ) |
| A := T3 | (':=', T3, _ ,A) | [3] (':=',[2], _ ) |
Un branchement conditionnel nécessite deux instruction triplets:
[0] (rel, x, y) [1] (ifgoto, [0], l )
Traduction de affectations
Opérands de type entier
Pour les variables (et constantes) de type entier, leur entrée dans la table des symbole doit comprendre un pointeur vers l'emplacement de stockage de la valeur. On y accèdera par E.ptr.
Posons une grammaire d'entier pour illustrer :
| S → id := E |
| E → E * E |
| E → E + E |
| E → -E |
| E → ( E ) |
| E → id |
Nous aurons besoin de deux fonctions pour ce travail, auxquelles nous ferons appel dans les actions de réduction :
- gencode(op, arg1, arg2, cible ) qui génère un quadruplet
- newmp() qui malloc une variable temporaire et retourne le pointeur dans la table des symboles.
Voici comment on les utilise pour réaliser des actions de façon schématique (on aurait de $1,$2, etc dans yacc/bison au lieu des non-terminaux :
à vérifier et finir ce tableau, ce n'est pas claire (pour moi, maintenant) pourquoi on adresse T directement et pas par T.ptr, sinon on risque de l'oublier et avoir des fuites de mémoire, je crains.
| N° | Règle | Action |
|---|---|---|
| 1 | S → id := E | { gencode( :=, E.ptr, id_ptr);} |
| 2 | E → E * E | { T = newtmp(); gencode('*', $1.ptr, $3.ptr, T); |
| 3 | E → E + E | |
| 4 | E → -E | |
| 5 | E → ( E ) | |
| 6 | E → id |
Gros exemple (page 4bis du 19/10) à rajouter.
Opérands de types différents
Dans ce cas, il convient de vérifier la cohérence sémantique des types. Pour cela, nous regarderons E.type (ou E→type) pour connaitre le type de l'expression E.
id := E { if (id->type == E->type)
then gencode (':=', id->ptr, E->ptr)
else if (id->type==real && E->type ==int)
then {
T=newtmp();
gencode(':=', int2real(E->ptr), , T->ptr);
gencode(':=', T.ptr, , id->ptr);}
else error("affectation de types incompatibles");
}
