MASTER 1ère année

Travaux Pratiques de

Compilation

sujet n°3

(Génération de code intermédiaire)

Pour ce TP, on utilise un langage permettant d’écrire des affectations, des instructions conditionnelles, des boucles ainsi que des séquences d’instructions, dont la grammaire est la suivante (le numéro associé à chaque règle servira vers la fin du TP) :

stmt → ID ASSIGN expr                               (2)

            | WHILE cond DO stmtlist DONE                  (6)

           | IF cond THEN stmtlist ENDIF                  (5)

      

      stmtlist → stmtlist stmt                            (7)

               | stmt                                     (4)

Les expressions sont limitées aux identificateurs (tous de type entier) et aux constantes entières :

expr → ID                                           (1)

           | NUM                                          (1)

Les conditions sont formées à partir de constantes, de comparaisons (égalité d’une variable à une valeur) et des opérateurs habituels :

cond → ID EQUAL NUM                                 (8)

           | TRUE                                         (3)

           | FALSE                                        (3)

           | con OR cond                                  (9)

           | cond AND cond                                (9)

           | NOT cond                                     (9)

           | OPAR cond CPAR                               (9)

Le but du TP est de générer du code à 3 adresses (représenté par des quadruplets) pour ce langage. Voici le fichier lex. Reste à écrire le fichier yacc.

On procédera de la façon suivante :

Écrire la grammaire avec des actions vides et résoudre les éventuels conflits. Ajouter aussi des marqueurs aux bons endroits dans la grammaire pour préparer la traduction. Ajouter un programme principal qui ne fait pour l'instant qu'un appel à la fonction yyparse(), juste pour tester votre grammaire.

Définir une structure de données pour représenter la table des symboles. Vous pouvez utiliser (en première approximation) un tableau dont chaque élément est une structure à 2 champs : Un champ qui indique le type de symbole (pour ce langage, il n'y a que 2 types de symbole : les identificateurs et les constantes) et un champ qui est soit une chaîne d'au plus 8 caractères (le nom pour un identificateur), soit un entier (la valeur pour une constante entière). Définir les fonctions d'ajout et de recherche d'un symbole dans la table, ces fonctions retournent un pointeur (éventuellement NULL) dans la table. Écrire une fonction qui affiche le contenu de la table des symboles.

Définir une structure de données pour représenter le code à 3 adresses (la liste de quadruplets). Vous pouvez utiliser un simple tableau CODE dont chaque élément est un quadruplet : une structure à 4 champs. Le premier champ indique quel est le type d'instruction (pour ce langage, les instructions utilisées sont la copie x := y, le branchement inconditionnel goto l et le branchement conditionnel if x = y goto l), les 3 autres champs sont soit NULL si le champ n'est pas utilisé, soit une adresse (puisqu'on représente du code à 3 adresses). Une adresse est soit un pointeur dans la table des symboles (le cas de x ou y), soit une position de quad (le cas de l). Une position de quad est l'indice d'un élément dans le tableau CODE. (Pour représenter un quad incomplet, on peut mettre à NULL, l'adresse qui correspond à la position de quad.) Définir la fonction gencode qui génère un quadruplet et incrémente la variable globale nextquad. Définir une fonction qui affiche le code.

Définir une structure de données pour représenter une liste de positions de quad. Vous pouvez utiliser cette implémentation des listes chaînées en C. Vous devrez instancier le type T des éléments de liste. Chaque élément d'une liste de positions de quad est l'indice d'un élément du tableau CODE. Définir la fonction complete qui complète tous les quads (incomplets) dont la liste est donnée en argument.

Ajouter à votre fichier yacc la déclaration des types des terminaux et non-terminaux de la grammaire. Il y a les types des terminaux (chaîne de caractères pour ID et nombre entier pour NUM) et les types des non-terminaux et de leur attributs (stmt, stmtlist, cond, expr et les marqueurs). Vous pouvez utilisez des structures à l'intérieur de l'union pour définir le type de chaque attribut. Par exemple, vous pouvez écrire quelque chose comme :

%union { long int intval; ... struct { struct symbol * ptr; } exprval;

... }
... %token <intval> NUM ... %type <exprval> expr ...

pour déclarer que le terminal NUM a une valeur de type long int et le non-terminal expr a un atttribut .ptr de type pointeur dans la table des symboles.

Compléter votre programme principal pour qu'il affiche à la fin la table des symboles et le code.

Écrire les actions (vous avez tous les éléments, il faut les combiner ensemble). Procédez de façon incrémentale : ajoutez les actions dans l'ordre indiqué par le numéro associé à chaque règle.