TD 7    Calculatrice infixe

Le TD est consacré à l'analyse syntaxique et consistera à étendre les capacités de la calculatrice du TD précédent. Le minimum à atteindre est la résolution de l'exercice 1. Il est de plus fortement conseillé de finir l'exercice 2 pour se préparer au DM 2.

Avant de partir, déposez vos programmes en tapant dans une fenêtre xterm la commande :

/users/profs/info/Depot/INF_431/deposer [pgms] TD_7 [gpe]

[pgm] doit être remplacé par la liste des noms des fichiers contenant vos programmes et [gpe] doit être remplacé par votre numéro de groupe.

Exercice 1. Lire des arbres

Le but est maintenant de lire des expressions infixes comme 1 + (2 - 3) * 4 et d'en construire l'arbre de syntaxe abstraite associé :

Le problème à résoudre aujourd'hui consiste donc à construire un arbre à partir d'une suite de lexèmes, ce que l'on appelle de l'analyse syntaxique. Vous devez pour cela utiliser l'analyseur lexical que vous avez programmé au TD 5.

Le flot de caractères lus en entrée est transformé en flot de lexèmes par l'analyseur lexical puis en flot d'arbres (que nous appellerons termes) par l'analyseur syntaxique.

Exercice 1.0 Quelques lexèmes supplémentaires

Étendre votre analyseur lexical pour reconnaître de plus les lexèmes parenthèse gauche (, parenthèse droite ), et point virgule ;. (On pourra définir des constantes PARG, PARD et PTVIRG.)

Par exemple, l'exécution de echo "1 + (2 - 3) * 4" | java AnalyseLex doit donner :

Entier(1)
+
(
Entier(2)
-
Entier(3)
)
*
Entier(4)
FinDeFichier

Rappelons que la commande echo écrit sur sa sortie standard ses arguments (ici 1 + (2 - 3) * 4) et que la barre verticale | indique de rediriger cette sortie standard vers l'entrée standard de java AnalyseLex.

On aurait pu aussi passer par un fichier input.txt avec la commande echo "1 + (2 - 3) * 4" > input.txt ; java AnalyseLex < input.txt. Le ; sépare la commande en deux parties à éxécuter consécutivement. Le > de la première partie indique de rediriger la sortie de echo "1 + (2 - 3) * 4" dans le fichier input.txt qui est créé (ou écrasé s'il existe). Le < de la deuxième partie indique que l'entrée standard de java AnalyseLex doit être lue depuis le fichier input.txt.

Exercice 1.1 Un arbre : des termes

Pour représenter les arbres, définir une classe Terme qui définit un noeud de l'arbre. Un terme a une nature (nombre, ou addition, ou soustraction ou multiplication ou division), éventuellement une valeur associée de type double pour les nombres, et éventuellement deux fils (si c'est un noeud interne).

Style objet : Si vous vous sentez à l'aise avec le style objet, vous pouvez suivre la programmation par objet des arbres de syntaxe abstraite vue au cours 7 (voir planche 29). Vous définirez alors une classe abstraite Terme avec une série de classes TNombre, TAdd,... pour représenter les différentes natures de terme. On pourra s'inspirer de la définition de Lexeme dans la solution objet du TD 5. Pour suivre cette voie, consulter la version objet de l'exercice 1.1.

Style non objet : l'énoncé ci-dessous est rédigé dans un style non objet avec un champ nature pour coder la nature des termes dans un style plus proche du cours 6.

À partir de l'exercice 1.2, l'énoncé vous laisse le choix du style.

Pour coder la nature, on pourra prendre les constantes :

   final static int T_NBRE=1, T_ADD=2, T_SOUSTR=3, T_MULT=4, T_DIV=5 ;

Écrire deux constructeurs, un pour construire une feuille de l'arbre (toujours un nombre) et un pour construire un noeud interne de l'arbre (addition, soustraction, multiplication ou division). Pour tester vos fonctions, vous pourrez ainsi utiliser le terme test suivant :

    Terme inter = new Terme (T_SOUSTR, new Terme (2.0), new Terme (3.0)) ;
    Terme test = new Terme (T_ADD, new Terme (1.0), new Terme (T_MULT, inter, new Terme (4.0))) ;

Écrire une fonction versChaine qui renvoie une représentation sous forme de chaîne de caractères de l'expression associée à un arbre. Ainsi, un appel à System.out.println (versChaine (test)) doit afficher quelque chose comme (1.0 + ((2.0 - 3.0) * 4.0)) (on ne cherchera pas à minimiser le nombre de parenthèses). (Pour transformer une variable d de type double en String, on pourra utiliser ("" + d).)

Écrire une fonction calcule pour calculer la valeur d'un arbre (le résultat du calcul associé à l'arbre). Un appel à System.out.println (calcule (test)) doit afficher -3.0.

Il faut inclure une procédure main dans votre classe Terme pour tester si elle fonctionne bien. On inclura notamment les tests ci-dessus.

Exercice 1.2 Des lexèmes vers un arbre : la grammaire

Votre analyseur lexical transforme ce qui est tapé au clavier en une suite de lexèmes qui sera interprétée par votre analyseur syntaxique comme une suite de termes selon la grammaire suivante :

    expression -> produit + expression
    expression -> produit - expression
    expression -> produit

    produit    -> facteur * produit
    produit    -> facteur / produit
    produit    -> facteur

    facteur    -> Nombre
    facteur    -> ( expression )

Ce qui peut se lire ainsi : il y a trois possibilités pour lire une expression ; dans tous les cas, il faut d'abord lire un produit. Ensuite si le lexème courant est +, on le consomme puis on lit une expression. Si le lexème courant est -, on le consomme puis on lit une expression. Si c'est un autre lexème, l'expression se réduit au produit lu. Pour lire un produit, les règles sont similaires. Pour lire un facteur, soit on lit un nombre, soit on lit une parenthèse ouvrante, puis une expression, puis une parenthèse fermante. (C'est ce qu'on appelle la méthode récursive descendante.)

Écrire une classe AnalyseSynt avec une fonction permettant de lire un facteur (et renvoyant le terme associé), une fonction permettant de lire un produit et une fonction permettant de lire une expression.

De manière similaire à l'analyse lexicale, on prendra des décisions uniquement en fonction du lexème courant lexCourant. Une fonction avancerLexeme () permettra de « consommer » le lexème courant en appelant la fonction lireLexeme() de votre analyseur lexical et en plaçant le lexème renvoyé dans lexCourant.

Un point délicat réside dans la consommation des lexèmes. Il faut retenir qu'une fois un terme lu (et sur le point d'être renvoyé par une des trois fonctions ci-dessus), tous ses lexèmes le composant doivent avoir été consommés. De la même manière, avant d'appeler la fonction qui va lire un terme par exemple, il faut que lexCourant contienne bien le premier lexème de ce terme.

Dans une fonction avec plusieurs cas, il important de ne pas laisser un cas en suspens même si ce cas n'est pas sensé arriver. On provoquera une erreur (avec throw new Error ("Message d'erreur")) chaque fois qu'un cas inattendu est rencontré.

En faire ensuite une calculatrice infixe qui affiche l'expression et le résultat du calcul pour chaque arbre lu. Voici un exemple d'exécutions :

Exercice 1.3 Interactivité et point virgule

Noter que la détection de la fin d'une expression intervient quand le lexème suivant l'expression est lu, ce qui rend l'interactivité de la calculatrice un peu anormale : en exécutant java AnalyseSynt, on peut obtenir :

1 + (2 -3) * 4
1
   (1.0 + ((2.0 - 3.0) * 4.0)) = -3.0
2
   1.0 = 1.0

Pour résoudre cela, on pourra considérer le point virgule (lexème de nature Lexeme.L_PTVIRG) comme un séparateur qui permet d'indiquer la fin d'une expression (comme les espaces pour l'analyse lexicale). Dans la boucle principale, on passe au lexème suivant tant que le lexème courant est Lexeme.PTVIRG. Ensuite, si le lexème courant est Lexeme.FIN_FICHIER, on arête. Enfin, on lit une expression, on l'affiche et on la calcule avant de passer à l'itération suivante de la boucle. Voici un exemple des bienfaits du point virgule :

1 + (2 -3) * 4 ;
   (1.0 + ((2.0 - 3.0) * 4.0)) = -3.0
1+1 2+2 3+3 ;
   (1.0 + 1.0) = 2.0
   (2.0 + 2.0) = 4.0
   (3.0 + 3.0) = 6.0

Question piège : votre calculatrice comprend-t-elle 1-2-3 ? (Ce problème vient de la non associativité de la soustraction, voir dans le supplément le développement de cette épineuse question.)

Une solution.

Exercice 2. Des variables

Le but ici est de compléter la calculatrice pour pouvoir utiliser des variables. Voici un exemple d'utilisation (les lignes commençant par des espaces sont affichées par le programme en réponse aux autres lignes tapées au clavier) :

set x = 2-3;
   Stockage de x = (2.0 - 3.0) = -1.0
eval x ;
   Evaluation de x = -1.0
set y = x*4 ; eval 1+y ;
   Stockage de y = (x * 4.0) = -4.0
   Evaluation de (1.0 + y) = -3.0

Exercice 2.1 Plus de lexèmes et de règles de grammaire

Étendre votre analyseur lexical pour reconnaître de plus le lexème égal =. (On pourra définir une constante EGAL dans la classe Lexeme.)

Les mots set et eval seront regroupés sous un même type de lexème MOT_CLE et un nouveau champ valeurMot (de type String) stockera le mot. Pour rendre le programme plus extensible, on utilisera un tableau pour stocker les mots clé reconnus. Une fonction estMotCle permettra de tester si un mot donné est un mot clé.

Toute suite de lettre qui n'est pas un mot clé sera considérée comme une variable, lexème de nature VAR. Le nom de la variable sera stocké dans le champ valeurMot.


Notons qu'un Terme peut maintenant être une variable (il faudra rajouter une constante T_VAR et un constructeur associé). La fonction qui permet de lire un facteur peut maintenant lire aussi une variable :

    facteur    -> Variable
    facteur    -> Nombre
    facteur    -> ( expression )

De plus, la calculatrice lit maintenant des instructions définies par les règles :

    instruction -> set Variable = expression ;
    instruction -> eval expression ;

Les deux règles correspondent respectivement à une définition de variable et une évaluation d'expression.

Écrire une fonction pour lire les instructions qui affiche ce que la calculatrice devrait faire (on évitera d'appeler la fonction Terme.calcule pour l'instant.) Pour une interactivité normale, la fonction affichera avant de consommer le point virgule (sans quoi on se retrouve bloqué dans lireLexeme ()). Par exemple :

set x = 2-3 ;
   Stockage de x = (2.0 - 3.0) = ??
set y = x*4 ;
   Stockage de y = (x * 4.0) = ??
eval 1+y ;
   Evaluation de (1.0 + y) = ??

Exercice 2.2 Calculatrice à mémoire

Il faut maintenant doter la calculatrice d'une mémoire où stocker les variables et les valeurs associées. Écrire pour cela une classe Memoire permettant de stocker des associations nom, valeur. À votre connaissance, quelle structure de donnée vous semble la plus appropriée ? Programmer cependant une structure très simple (par exemple une liste) ou utiliser une structure prédéfinie de java (voir java.util).

Une solution.

Une solution version objet.

Aller plus loin


Sujet proposé par Laurent Viennot Last modified: Thu Mar 17 23:34:28 CET 2005