Devoir de compilation 1996

Un corrigé de ce devoir est disponible.

Présentation

On considère la grammaire ETF habituelle des expressions arithmétiques, avec les quatre opérateurs courants : addition, soustraction, multiplication, division. Outre les symboles d'opération, les symboles terminaux sont :

On ajoute à la grammaire les règles nécessaires pour :

L'objectif du devoir est de construire une représentation simplifiée de chaque expression valide, de telle sorte que deux expressions qui sont équivalentes par des transformations simples aient même représentation. Par exemple :

Par contre on n'effectue pas de transformation plus complexe :

La représentation utilisée est inspirée de celle utilisée par le logiciel Maple :

  1. Chaque représentation commence par un en-tête, qui indique le type de l'expression, et éventuellement la longueur de la représentation.

  2. Les constantes entières (resp. les constantes réelles) ont leur représentation naturelle (précédée d'un en-tête).

  3. La représentation d'un identificateur inclut un pointeur sur la représentation d'une valeur éventuelle.

  4. La représentation d'une constante rationnelle comporte, après l'en-tête, le numérateur et le dénominateur entiers.

  5. Une somme de termes est représentée par un tableau (de longueur variable), dont chaque entrée comporte :

    Exemple : 2(a+b) - 3x2 + 5/4 y2 est représenté par le tableau :

    En-tête : type = somme, longueur = 3
    pointeur vers a+b pointeur vers 2
    pointeur vers x2 pointeur vers -3
    pointeur vers y2 pointeur vers 5/4

  6. Un produit de facteurs est représenté par un tableau (de longueur variable), dont chaque entrée comporte : Un quotient est assimilé à un produit, avec un exposant négatif.

    Exemple : x2 (x+y)3 / z est représenté par le tableau :

    En-tête : type = produit, longueur = 3
    pointeur vers x pointeur vers 2
    pointeur vers x+y pointeur vers 3
    pointeur vers z pointeur vers -1

Enfin, comme en Maple, chaque expression (ou sous-expression) simplifiée est stockée une fois et une seule ; si bien que l'affectation d'une valeur à une variable modifie la valeur des expressions contenant cette variable, sans pour autant que les représentations de ces expressions soient modifiées.

Devoir

Réaliser, en utilisant lex et yacc (resp. flex et bison), un programme qui construit la représentation d'une expression selon les principes ci-dessus ; l'utilisateur entrera une expression par ligne, et le programme affichera la représentation interne de cette expression.

La gestion de la mémoire sera effectuée de façon statique, en réservant une place suffisante pour les différents types de données utilisés ; un pointeur sera une adresse dans l'une de ces zones, ou un indice. Evitez de passer la semaine à combattre des pointeurs fous !

L'énoncé du sujet comporte une ambiguïté fondamentale sur le type de simplifications effectuées : à vous d'examiner les choix possibles, et d'expliquer ceux que vous retenez.

Recommandations