Description générale

On veut réaliser une petite calculette permettant d'évaluer des expressions arithmétiques contenant éventuellement des variables. Les expressions seront données en notation polonaise postfixées. Pour pouvoir utiliser des variables, on rajoute àla calculette une instruction permettant d'associer la dernière valeur calculée àune variable (un nom) ainsi qu'une instruction permettant de visualiser le contenu d'une variable.

L'interaction avec la calculette se fait par l'entrée standard (le clavier) Chaque ligne de commandes est terminée par un point (.)
L'utilisateur demande l'évaluation d'une expression entre tapant une ligne au format suivant :   ? expr .
L'utilisateur demande àla calculette de mémoriser le résultat de la dernière évaluation en tapant une ligne au format suivant :   ! var .
L'utilisateur demande l'affichage du contenu d'une variable en tapant une ligne au format :   $ var .
L'utilisateur quitte l'application en tapant simplement un point.

En cas d'occurence d'un caractère erroné, la calculette ignorera tous les caractères lus jusqu'àretrouver le caractère de fin de ligne de commande (le point) Les erreur dues àdes expressions mal formées sont plus délicates àgérer. Nous laissons l'examen et le traitement de ce problème àvotre sagacité.

L'interface entre la ligne de commande entrée par l'utilisateur (une suite de caractères) et le processus d'évaluation (et de mémorisation) est réaliséen utilisant l'analyseur lexical lex
L'analyseur découpe la ligne de commande en unités syntaxiques (ou lexèmes) auxquelles sont associées, dans le processus d'évaluation, un certain nombre d'actions.

1 Principe d'évaluation d'une expression

L'évaluation d'une expression postfixée est réalisée àl'aide d'une pile destinée àrecevoir les valeurs entières lues au clavier, les résultats intermédiaires ainsi que le résultat final.

Le principe d'évaluation est le suivant : on empile les entiers et les valeur des variables rencontrées lors de la lecture de l'expression ; lorsque l'on rencontre un opérateur, ses arguments se trouvent sur la pile, on leur applique donc l'opération correspondante ; on remplace, sur la pile, les arguments par le résultat obtenu.
Par exemple, lévaluation de 2 m1 + 4 + se décompose en :

- Empiler 2 puis la valeur de la variable m1 (disons 3)

- Calculer 2+3 (les valeurs 2 et 3 sont récupérées sur la pile)

- Dépiler 2 et 3, puis empiler 5

- Empiler 4

- Calculer 5+4

- Dépiler 5 et 4, puis empiler 9

2 L'architecture de la calculette

La mémoire de la calculette est un nombre fini de variables nommées, pour se faciliter la vie, de façon uniforme : m1, m2, m3, .. Elle est concrètement implantée comme un tableau d'entiers appelémem. La variable m1 sera en mem[1], la variable m2 en mem[2], etc... L'accés, en lecture et écriture àcette mémoire seront réaliser par l'accés et la modification des éléments du tableau. La première case mémoire (mem[0]) sera réservée àusage interne comme variable tampon.
La pile sera également un tableau d'entiers appeléstack. On définira les primitives d'empilement push, de dépilement pop, d'accés au deux premier élément de la pile top. On définira également un prédicat is_empty indiquant si la pile est vide ou non.

L'architecture logicielle de la calculette peut être spécifée sous forme d'un automate àcinq états :

WAIT: La calculette est en attente d'une commande ;
DISCMD: Pour affichage du contenu d'une variable ;
STOCMD: Pour sauvegarde du dermier résultat calculé(m[0]) dans une variable ;
EVALCMD: Pour évaluation d'un expression.
SKIP: Oubli des erreurs de saisie.

Une ligne de commande est analysée (par l'analyseur lexicale) en sept unités lexicales différentes :

DOT: Le point qui termine une ligne de commande ;
QMARK: Le point d'interrogation qui commence une ligne de commande d'évaluation ;
EXMARK: Le point d'exclamation qui commence une ligne de commande de sauvegarde ;
DOLLAR: Le ``dollar'' ($) qui commence une ligne de commande d'affichage du contenu d'une variable ;
OP: Un symbole d'opérateur arithmétique ;
NUM: Une constante entière en notation décimale ;
VAR: Un nom de variable.

On décrit alors schématiquement le comportement de la calculette selon l'unitélexicale courante et les cinq états possibles :

DOT

WAIT: Quitter l'application.
EVALCMD: Stocker le résultat du calcul dans mem[0] et afficher.
sinon: Repasser àl'état WAIT.

QMARK

WAIT: Passer àl'état EVALCMD.
SKIP: Ne rien faire.
sinon: Afficher un message d'erreur puis passer àl'état SKIP.

EXMARK

WAIT: Passer àl'état STOCMD.
SKIP: Ne rien faire.
sinon: Afficher un message d'erreur puis passer àl'état SKIP.

DOLLAR

WAIT: Passer àl'état DISCMD.
SKIP: Ne rien faire.
sinon: Afficher un message d'erreur puis passer àl'état SKIP.

OP

EVALCMD: Evaluer l'application de l'opérateur àses arguments, mettre àjour la pile.
SKIP: Ne rien faire.
sinon: Afficher un message d'erreur puis passer àl'état SKIP.

NUM

EVALCMD: Empiler.
SKIP: Ne rien faire.
sinon: Afficher un message d'erreur puis passer àl'état SKIP.

VAR

DISCMD: Afficher.
EVALCMD: Empiler le valeur de la variable.
SKIP: Ne rien faire.
STOCMD: Sauver dans la variable la dernière valeur calculée (mem[0]).
sinon: Afficher un message d'erreur puis passer àl'état SKIP.

sinon

SKIP: Ne rien faire.
sinon: Afficher un message d'erreur puis passer =`a l'état SKIP.

3 Travail àfournir

Définir un petit module de gestion de pile àl'aide d'un fichier d;interface stack.h et d'un fichier d'implantation stack.c. Le fichier d'interface contiendra :
- La définition du type des piles : stack
- définition des primitives
  stack new_stack(); (création d'une nouvelle pile)
  void push(int, stack); (empiler)
  int top(stack); (valeur du sommet de pile)
  void pop(stack); (dépiler)
Définir un fichier d'interface cal.h contenant :
- la définition du type lexical_values des valeurs associées aux unités lexicales OP, NUM ou VAR;
- la définition du type (énuméré) states représentant les différents états de la calculette ;
- les variables nécessaires.
Définir le fichier d'application cal.lex
Définir le fichier Makefile nécessaire àla compilation de l'application.

This document was translated from L^AT_EX by H^EV^EA.