Par exemple, si on tape 123 2 + 1232*5/, on attend l'affichage de :
Entier(123) Entier(2) Plus Entier(1232) Mult Entier(5) Div
Autrement dit, il s'agit de faire une sorte de Scanner en mieux (Scanner ne sait pas couper 1232*5 en trois morceaux par exemple).
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). System.in est de type InputStream qui permet de représenter tout type de flot de caractères. Écrire une classe Lexeur dont le constructeur prend en argument un InputStream et le stocke dans un champ entree de la classe. On pourra ainsi créer un analyseur lexical qui lit l'entrée standard par :
Lexeur lex = new Lexeur (System.in) ;
La lecture se fait caractère par caractère, la classe Lexeur contiendra donc un champ carCourant pour stocker le caractère courant lu en entrée. Pour passer au caractère suivant, on appelera :
final static char FIN_ENTREE = (char)-1 ;
void avancerCar () {
try {
carCourant = (char) entree.read () ;
} catch (java.io.IOException e) {
carCourant = FIN_ENTREE ;
/* En cas d'exception, on consid`ere
* la fin de l'entrée atteinte. */
}
}
Explication : Étant donné un flot de caractères InputStream entree, l'appel entree.read () permet de lire un caractère du flot. Cette fonction renvoie un entier qui vaut le code du caractère lu. Elle 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 Lexeur < fichier.txt). Pour plus d'informations, consulter la documentation de InputStream.
Ajouter un champ carCourant dans la classe et modifier le constructeur pour l'initialiser au premier caractère du flot d'entrée par un appel à avancerCar.
Testez votre classe par un appel à la méthode suivante :
void testEcho () {
while (carCourant != FIN_ENTREE) {
System.out.println ("lu: ("+carCourant+")") ;
avancerCar () ;
}
}
Expérimentez un peu la lecture de caractères :
Nous utilisons ici un style objet avec une classe différente pour chaque sorte de lexème plutôt qu'une seule classe avec un champ nature comme les transparents d'amphi. Cela est possible si toutes ces classes héritent d'une même classe permettant de représenter n'importe quelle sorte de lexème.
Écrire ainsi une classe abstraite Lexeme permettant de représenter un lexème. Cette classe est vide pour l'instant. Elle est abstraite pour être sûr qu'on ne puisse pas l'instancier.
Chaque sorte de lexème sera donc représentée par une classe héritant de Lexeme. Écrire ainsi dans le même fichier des classes Entier, Plus, Moins, Mult, et Div qui étendent la classe Lexeme. La classe Entier aura un champ valeur pour stocker la valeur de l'entier lu. Munir la classe d'un constructeur lorsque le constructeur par défaut ne convient pas. Munir chaque classe d'une méthode toString pour permettre un affichage similaire à l'exemple ci-dessous.
Avec la fonction main suivante :
public static void main (String[] args) {
System.out.println (new Entier (123)) ;
System.out.println (new Plus ()) ;
}
java Lexeme devrait donner :
Entier(123) Plus
Nous allons de plus introduire une sorte de lexème permettant de représenter la fin de fichier. Écrire une classe Fin étendant la classe Lexeme pour cela. Munir Lexeme d'une méthode estFin pour tester si un lexème est la fin de fichier. Cette méthode par défaut retournera false. Redéfinir estFin dans la classe Fin de sorte qu'elle renvoie true pour un lexème de type Fin.
Pour tester votre classe Lexeur, sa fonction main lira une suite de lexèmes et les affichera au fur et à mesure, soit :
public static void main (String[] args) {
Lexeur lex = new Lexeur (System.in) ;
Lexeme l ;
do {
l = lex.lireLexeme () ;
System.out.println (l) ;
} while (! l.estFin ()) ;
}
La méthode lireLexeme doit lire des caractères jusqu'à obtention d'un lexème qu'elle retourne. Par lire, on entend qu'à la sortie de la fonction, le caractère courant est le premier caractère suivant le lexème dans le flot. Par exemple, après avoir lu 1232 dans 1232*5, le caractère courant sera *. Pour cela, on utilisera les méthodes auxiliaires suivantes.
lireLexeme fera tout d'abord appel à :
Selon le caractère courant, lireLexeme fera ensuite appel à :
Méthode : la principale difficulté réside dans le placement des appels à avancerCar. La méthode lireLexeme sert plutôt d'aiguillage et ne consomme pas directement de caractère : en fonction du caractère courant, une des fonctions auxiliaires 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é.
Testez votre programme sur l'exemple du début du TD.
Donner (en commentaire dans le programme) une expression régulière caractérisant l'ensemble des mots que votre méthode lireLexeme peut lire sans produire d'erreur. On utilisera Blanc, Digit, '+', '-', '*' et '/' pour désigner respectivement un caractère blanc, un chiffre, le caractère plus, le caractère moins, le caractère multiplié, et le caractère divisé.
Il s'agit maintenant de réaliser une calculatrice.
Dans la tradition HP, nous allons utiliser la notation polonaise inverse, ce qui évite d'avoir à taper des parenthèses. Ainsi (1-2)*3 ce calcule en tapant 1 2 - 3 *. Pour cela, on utilise une pile de réels pour stocker les résultats intermédiaires des calculs. Ainsi en tapant 1 2 - 3 *, l'évolution de la pile est la suivante (le sommet de la pile est à droite) :
Entier(1)
pile : [1.0]
Entier(2)
pile : [1.0, 2.0]
Moins
pile : [-1.0]
Entier(3)
pile : [-1.0, 3.0]
Mult
pile : [-3.0]
Méthode : on dotera la classe Lexeme d'une méthode operer qui permet d'appliquer 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é. Attention à l'ordre des opérandes, quand on tape 1 2 -, le résultat est -1.
Pour la pile, utiliser par exemple Stack<Double>. Modifier ensuite la fonction main de l'exercice précédent pour obtenir le programme voulu. On affichera la pile après la lecture de chaque lexème (on se contentera de la méthode toString de Stack<Double>).
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 :
Toutes ces instructions seront regroupées sous une même classe MotCle étendant Lexeme. Le nom de l'instruction représentée par le lexème sera stocké dans un champ de type String (on fait plus simple que les transparents d'amphi). 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. Rajouter une méthode lireMotCle dans Lexeur. (Pour faire plus efficace on pourrait associer des constantes aux indices de ce tableau et identifier l'instruction représentée par le lexème par un int plutôt qu'une String comme indiqué dans les transparents d'amphi.)
Au prochain TD nous programmerons l'analyse d'expressions infixes comme (1 - 2) * 3 ; 1+2. Le point virgule ; servira à séparer des calculs. Nous aurons donc besoin de trois classes ParG, ParD et PtVirg pour représenter trois nouvelles sortes de lexèmes : parenthèse gauche, parenthèse droite et point virgule respectivement.
Ces lexèmes n'auront aucun effet sur la pile de votre calculatrice. En tapant (1 2 -) ;, on obtiendra par exemple :
ParG
pile : []
Entier(1)
pile : [1.0]
Entier(2)
pile : [1.0, 2.0]
Moins
pile : [-1.0]
ParD
pile : [-1.0]
PtVirg
pile : [-1.0]
Corriger votre programme pour autoriser de plus la saisie de nombres en virgule flottante (appelés flottants). Votre programme distinguera les flottants des entiers (nombres qu'il lisait selon l'exercice 3). Les flottants sont définis par l'expression rationnelle suivante (les espaces servent à rendre l'expression lisible, il ne peut y avoir aucun caractère espace dans un flottant) :
flottant = mantisse | mantisse exposant mantisse = chiffre+ | chiffre*frac chiffre = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 frac = .chiffre* exposant = (e | E) expVal expVal = expValPos | + expValPos | - expValPos expValPos = chiffre+
(Rappel : exp+ équivaut à exp exp*.)
Indication : ne pas hésiter à écrire des fonctions pour la lecture des sous-expressions définies ci-dessus. Il ne serait pas étonnant de voir trois nouvelles fonctions venir accompagner la fonction lireEntier () (il ne faut donc pas sous-estimer la difficulté de cette question).
On pourra utiliser la fonction double Math.pow(double a, double b) qui calcule a à la puissance b.
En plus des nombres, la pile doit maintenant stocker leurs types (une solution simple consiste à empiler des lexèmes). Attention, les opérations ne donnent pas le même résultat selon le type des arguments (par exemple, 1 2 / ne donnera pas le même résultat que 1.0 2.0 /). Rajouter maintenant des instructions pour manipuler la pile en prenant des arguments entiers sur la pile :
Entier(3)
pile : [..., 4.0, 3.0, 2.0, 1.0, 3]
ROLLU
pile : [..., 4.0, 2.0, 1.0, 3.0]
Entier(3)
pile : [..., 4.0, 3.0, 2.0, 1.0, 3]
ROLLD
pile : [..., 4.0, 1.0, 3.0, 2.0]
Cet exercice est repris d'un TD de Luc Maranget.
Pour pouvoir exécuter un programme, la calculatrice devra lire tout le programme et le stocker avant de l'exécuter. Il nous manque principalement deux types d'instructions pour pouvoir faire des programmes : les branchements et les tests. On rajoutera donc les instruction suivantes :
Comme exemple d'exécution, si pgm.hp est « LBL0 SWAP - RTN » (sous-routine qui calcule y-x), alors on aura :
radius$ java Calculette 1 3 GSB0 < pgm.hp ======== Programme charge ========== 000 Entier(1) 001 Entier(3) 002 Instruction(GSB0) 003 Instruction(RTN) 004 Instruction(SWAP) 005 - 006 Instruction(RTN) 007 FinDeFichier ======= Table des etiquettes ======= LBL0 = 004 LBL1 = 000 LBL2 = 000 LBL3 = 000 LBL4 = 000 LBL5 = 000 LBL6 = 000 LBL7 = 000 LBL8 = 000 LBL9 = 000 ============= Execution ============ 000 Entier(1) : 1 001 Entier(3) : 1, 3 002 Instruction(GSB0) : 1, 3 004 Instruction(SWAP) : 3, 1 005 - : 2 006 Instruction(RTN) : 2 003 Instruction(RTN) : 2
Pour changer plus facilement les arguments du calcul, une partie du programme est donnée en argument.
Voici deux exemples de programme (remarquer l'ajout de commentaires) :
Calcul de la factorielle du sommet de la pile :
%% Factorielle LBL0 2 XLTY GTO1 DROP % jeter le 2 DUP 1 - GSB0 % fact de n-1 * % fois n RTN %% Cas terminal LBL1 DROP DROP 1 RTN
Nombres de Fibonacci (Un = Un-1 + Un-2, U0=U1=1) :
%% Fonction fib recursive LBL1 2 XLTY GTO2 - DUP 1 + %Optim d'enfer « 2 » est de'ja sur la pile GSB1 SWAP GSB1 + RTN %%% Cas terminal LBL2 DROP DROP 1 RTN
Ecrire le programme hp pour calculer le nombre d'or sours la forme 1 + 1/(1 + 1/(1+ 1/(...))).