TD 5    Calculatrice à pile

Le TD est consacré à l'analyse lexicale et consistera à réaliser une calculatrice à pile de type HP dont il faut traiter l'entrée.

Le minimum à faire est l'exercice 1.

A la fin du TD, vous devrez déposer vos programmes en tapant dans une fenêtre xterm une commande :

/users/profs/info/Depot/INF_431/deposer [pgm] TD_5 [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 les entrées

L'idée ici est de lire ce qui est tapé au clavier et de l'interpréter comme une suite de lexèmes.

Par exemple, si on tape 123 2 + 1232*5/, on attend l'affichage de :

Entier(123)
Entier(2)
+
Entier(1232)
*
Entier(5)
/

1.1 Les lexèmes

Écrire une classe Lexeme permettant de représenter un entier comme 123 ou une opération comme +. Pour cela, on identifie les différents types de lexèmes par un entier, et pour rendre le programme lisible, on utilisera les constantes suivantes :

    final static int ENTIER=0, PLUS=1, MOINS=2, MULT=3, DIV=4, FIN_FICHIER = -1 ;

Un champ int nature permettra d'identifier la nature du lexème. Dans le cas d'un entier, un champs supplémentaire int valeurEntier stockera la valeur de l'entier. Contrairement aux transparents d'amphi, la nature d'une opération ne sera pas égale au code du caractère de l'opération.

Écrire un ou plusieurs constructeurs et une méthode static void afficher (Lexeme l) permettant d'afficher un lexème.

1.2 Lire ce qui est tapé

La lecture se fait caractère par caractère. On stockera dans une variable globale static char carCourant la valeur du caractère courant. Pour lire les caractères tapés au clavier, il faut lire l'entrée « standard » System.in (qui est l'analogue de la sortie « standard » System.out pour lire au lieu d'écrire). La méthode System.in.read () permet de lire un caractère de l'entrée standard. Cette fonction renvoie un entier qui vaut le code du caractère lu. Pour passer au caractère suivant, on utilisera donc la procédure avancerCar () suivante :

    final static char EOF = (char)-1 ; // caract`ere << End Of File >>

    static char carCourant ;

    static void avancerCar () {
	try {
	    carCourant = (char) System.in.read () ;
	} catch (java.io.IOException e) {
	    carCourant = EOF ; /* En cas d'exception, on consid`ere 
                                  la fin de fichier atteinte. */
	}
    }

Remarquons que System.in.read () renvoie -1 lorsque la fin de fichier est atteinte, c'est à dire qu'il n'y a plus de caractère à lire. Cela se produit si on tape Ctrl-D au clavier durant l'exécution. Cela se produira aussi si l'on a redirigé l'entrée standard pour que la lecture se fasse depuis un fichier au lieu du clavier (par exemple : java Prog < fichier.txt). On pourra donc tester si la fin de fichier est atteinte par le test suivant :

    if (carCourant == EOF) 
        ...

System.in est un objet de la classe InputStream du package java.io dont on pourra consulter la description dans la documentation de java pour plus d'informations.

La procédure main de votre programme devra initialiser carCourant par un appel à avancerCar () puis lire une suite de lexèmes et les afficher au fur et à mesure, soit :

    public static void main (String[] args) {
	avancerCar () ;
	Lexeme l ;
	do {
	    l = lireLexeme () ;
	    Lexeme.afficher (l) ;
	} while (l.nature != Lexeme.FIN_FICHIER) ;
    }

On écrira une fonction static Lexeme lireLexeme () qui lit les caractères tapés et renvoie le premier lexème rencontré.

lireLexeme fera tout d'abord appel à :

Selon le caractère courant, lireLexeme fera ensuite appel à :

Conseil : la principale difficulté réside dans le placement des appels à avancerCar (). Un caractère est consommé lorsque l'on passe au suivant par avancerCar(). En corollaire, lorsqu'un lexème est reconnu (i.e. au retour de lireLexeme ()) le caractère courant est le premier qui suit (éventuellement EOF). De plus la fonction lireLexeme () sert plutôt d'aiguillage et ne consomme pas directement de caractère : en fonction du caractère courant, une des fonctions auxiliaire est appelée. Un appel à lireOperation (), par exemple, présuppose que le caractère courant correspond à une opération et fera un appel à avancerCar () avant de retourner le lexème aproprié. De même, lireLesBlancs () fera des appels à avancerCar () tant que le caractère courant est un blanc...

Vous pouvez mettre toutes les fonctions ci-dessus dans la classe Lexeme, cependant il peut-être plus élégant de regrouper toute la partie lecture (avancerCar (), les lire... (), etc...) dans une même classe AnalyseLex.

Une solution.

Une solution dans un style plus objet. (Voir la solution de l'exercice 2.2 pour une solution dans un style objet de Lexeme.)

Exercice 2. La calculatrice

Il s'agit maintenant de réaliser une calculatrice.

2.1 La pile

Dans la tradition HP, utiliser une pile de réels pour stocker les résultats intermédiaires des calculs. Utiliser Pile.java pour gagner du temps (new Pile () permet de créer une pile vide, Pile.empiler() et Pile.depiler() permettent d'empiler ou de dépiler un nombre). On affichera la pile après la lecture de chaque lexème (Pile.java contient pour cela une procédure afficher ()). Ainsi en tapant 1 2 + 3 4 + 5 6 +** 231 -, on obtiendra (le sommet de la pile est à droite et les calculs se font avec des double) :

Entier(1)             
             pile :       1.0
Entier(2)             
             pile :       1.0, 2.0
+                       
             pile :       3.0
Entier(3)             
             pile :       3.0, 3.0
Entier(4)             
             pile :       3.0, 3.0, 4.0
+                       
             pile :       3.0, 7.0
Entier(5)             
             pile :       3.0, 7.0, 5.0
Entier(6)             
             pile :       3.0, 7.0, 5.0, 6.0
+                       
             pile :       3.0, 7.0, 11.0
*                       
             pile :       3.0, 77.0
*                       
             pile :       231.0
Entier(231)
             pile :       231.0, 231.0
-
             pile :       0.0

Indication : on pourra utiliser une procédure qui applique le résultat de la lecture d'un lexème sur une pile : un nombre est empilé, pour une opération les deux éléments au sommet de la pile sont dépilés et le résultat de l'opération est empilé. Modifier ensuite la fonction main de l'exercice précédent pour obtenir le programme voulu.

Calculer une approximation du nombre d'or Phi en évaluant :

1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
/ + / + / + / + / +
/ + / + / + / + / +
/ + / + / + / + / +
/ + / + / + / + / +

Vérifier que Phi - 1/Phi = 1.

Une solution.

2.2 Plus d'instructions

Rajouter des instructions pour manipuler la pile :

Toutes ces instructions seront regroupées sous un même type de lexème MOT_CLE et un nouveau champ mot (de type String) permettra de stocker le mot en question. Toute suite de lettres sera considérée comme un lexème correspondant à un mot clé. Pour rendre l'ajout de nouvelles instructions plus facile, les mots clés connus (ici, les noms des instructions) seront stockés dans un tableau. Quand un lexème correspondant à un mot clé est lu, il faudra vérifier que le nom associé est bien présent dans le tableau. On utilisera une fonction lireMotCle () qui lit un mot clé.

Une solution.

Une solution dans un style plus objet.

Une solution encore plus objet (avec héritage pour Lexeme).

Aller plus loin


Laurent Viennot
Last modified: Tue Mar 8 16:14:51 CET 2005