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 :
-
les identificateurs :
un identificateur est constitué
d'une lettre suivie de lettres ou de chiffres ;
-
les constantes entières positives ;
-
les constantes réelles positives.
On ajoute à la grammaire les règles nécessaires pour :
-
utiliser des exposants entiers positifs :
(a+b)^2 est une expression valide, mais pas
x^n ;
-
exprimer des affectations :
x = a*(b+c) est une expression valide.
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 :
-
a + b + c + a équivaut à
2a + b + c ;
-
x + 0 et 1 * x équivalent à x ;
Par contre on n'effectue pas de transformation plus complexe :
-
(a + b)2 n'équivaut pas à
a2 + 2ab + b2.
La représentation utilisée est inspirée de celle utilisée par le logiciel
Maple :
-
Chaque représentation commence par un en-tête,
qui indique le type de l'expression,
et éventuellement la longueur de la représentation.
-
Les constantes entières (resp. les constantes réelles)
ont leur représentation naturelle
(précédée d'un en-tête).
-
La représentation d'un identificateur inclut un pointeur
sur la représentation d'une valeur éventuelle.
-
La représentation d'une constante rationnelle comporte,
après l'en-tête, le numérateur et le dénominateur entiers.
-
Une somme de termes est représentée par un tableau
(de longueur variable), dont chaque entrée comporte :
-
un pointeur sur la représentation d'un des termes de la somme,
-
un pointeur sur un coefficient,
qui est une constante entière, réelle, ou rationnelle.
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
|
-
Un produit de facteurs est représenté par un tableau
(de longueur variable), dont chaque entrée comporte :
-
un pointeur sur la représentation d'un des facteurs du produit,
-
un pointeur sur un exposant,
qui est une constante entière
positive ou négative
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