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. :
param a
param b
call add,2
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 :

FIXME à 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.

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

FIXME 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");
           }

Traduction des Expressions booléennes

Représentation arithmétique

Représentation par une position de quad

Problèmes

Utilisation de marqueurs

Traduction des structures de contrôle

Traduction des affectation avec référence à des tableaux


 
m1ilc/compil_7.txt · Dernière modification: 2010/01/03 18:15 par suitable