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]
où [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.
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) /
É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 permettant d'afficher un lexème.
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 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)
...
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 écriera une fonction
static Lexeme lireLexeme () qui lit les caractères
tapés et renvoie le premier lexème rencontré.
lireLexeme fera elle même appel à :
static Lexeme lireOperation ()
qui lit une opération quand le caractère courant est +,
-, *, ou /,
static void lireLesBlancs ()
qui lit les blancs qui suivent quand le caractère courant en est un
(on pourra utiliser Character.isWhitespace (carCourant)),
static Lexeme lireEntier ()
qui lit un entier (pour simplifier, on pourra supposer que
seuls des entiers positifs sont tapés). (On pourra de même utiliser
Character.isDigit (carCourant).)
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 corrolaire, 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.
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. 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 +**,
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
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.
Rajouter des instructions pour manipuler la pile :
dup qui duplique le sommet de la pile,
drop qui efface le sommet de la pile,
swap qui échange les deux nombres au sommet de la pile,
chs qui change le signe du nombre au sommet de 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é.