TD-4, analyse lexicale, calculette




Ce document est disponible à l'URL http://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/TC/TD-4/

Envoyez vos programmes à Luc.Maranget@inria.fr. Les solutions sont ici.

Le but de cet exercice est la construction d'une petite calculette (entière) dans le style des calculettes Helwet-Packard. Ces calculettes sont intéressantes informatiquement parlant car elles exposent leur fonctionnement interne qui utilise une pile.

1 Analyse Lexicale
Contrairement à une calculette ordinaire, qui a des touches, la nôtre va lire son programme sur l'entrée standard (System.in).

1.1 Cette entrée que l'on dit standard
System.in est un objet de la classe InputStream. Cette classe n'est pas la plus pratique à utiliser directement, car on ne peut y lire que des octets. Or, les caractères de Java sont sur seize bits, et convertir les octets en caractères dépend du choix d'un encodage.

Pour s'en tirer, on va ``emballer'' (to wrap) System.in dans un objet de la classe InputStreamReader, qui permet de lire des caractères directement. On construit un tel objet par :
Reader in2 = new InputStreamReader (System.in) ;
(On pourrait spécifier en plus une chaîne qui donnerait le nom de l'encodage, ici on se contente de l'encodage par défaut).

On remarquera que le type de in2 est simplement Reader. Cette classe est une sur-classe de InputStreamReader (des méthodes en moins). En voyant notre InputStreamReader comme un Reader on oublie qu'il s'agit d'un fichier, ne s'intéressant plus qu'aux méthodes utiles pour nous (les méthodes read et close). L'usage de ces méthodes est décrit par un exemple de filtre trivial qui renvoie son entrée sur sa sortie :
import java.io.*; // La classe Reader est dans le package java.io

class Cat {

  public static void main(String [] args) {
    Reader entree =  new InputStreamReader(System.in) ;

    try {
      for (;;) {// Boucle infinie, on sort par break
        int c = entree.read (); // Lire un caractère
        if (c == -1)            // Fin de l'entrée
          break;
        else                    // Cas normal
          System.out.print ((char)c);
      }
      entree.close();
    } catch (IOException e) { // En cas de malaise
      System.err.print("Malaise : ") ;  
      System.err.println(e.getMessage()) ;
      System.exit(-1) ; // Terminer le programme sur erreur
    }      
  }
}
Si besoin est, cet exemple est analysé en détail dans les morceaux de Java.

1.2 Analyse lexicale
Cette exercice est en deux classes.

D'abord concevez une classe Lexeme des lexèmes (des mots quoi). Les mots de la calculette sont les entiers positifs (ou nuls !) et les opérateurs (+, -, etc.), définis comme étant un caractère non-alphabétique. On s'inspirera des transparents du cours. La classe Lexeme devra impérativement définir une méthode toString conforme aux habitudes.

En même temps, concevez une classe Lexer, qui devra impérativement se conformer au modèle suivant :
class Lexer {
  Lexer (Reader in)  // Constructeur qui prend un Reader en entrée
  Lexeme getToken () // Renvoie le prochain lexème, ou null à la fin
  void close ()      // Ferme l'entrée du lexer
}
Vous remarquerez (pas de ``throws IOException''), que les méthodes ci-dessus ne lèvent jamais d'exception que l'on doit déclarer.

Les principales difficultés prévisibles de cet exercice sont : Vous pourrez tester votre classe Lexer par la classe TestLexer. Et vous devriez obtenir :
maranget@manche ~/TD/TD-4 >  java TestLexer 
123
Lexème : 123
1 2 3
Lexème : 1
Lexème : 2
Lexème : 3
1+2+3
Lexème : 1
Lexème : +
Lexème : 2
Lexème : +
Lexème : 3
^d
(Les entrées et sorties sont mélangées, ^d est Control-d, pour finir l'entrée standard.) Solution.

2 Calculette HP

2.1 Les objets piles
On convient d'utiliser des objets piles. C'est à dire que l'on crée une nouvelle pile stack en invoquant le constructeur de la classe Stack des piles d'entiers stack = new Stack (). Ensuite on dépilera par stack.pop() et on empilera par stack.push(i). Par rapport à une solution sans objets, un avantage est une notation plus compacte et la possibilité de faire cohabiter plusieurs piles.

Le squelette d'une telle classe est le suivant :
class Stack {
  ... // Champs de l'objet pile (cf. plus loin)

  Stack () { // Constructeur des piles
    /* Initialisation des champs */
  }

  int pop () { }

  void push (int i) { }

  public String toString () { // Renvoie une chaîne qui représente la pile
   
  }
}
Les piles peuvent s'implémenter avec des listes ou des tableaux, le principal champ privé des objets piles sera donc une liste (comme dans le cas des grands entiers) ou un tableau. Souvenez-vous aussi que normalement les piles ont déjà étés vues au TD-2 et les listes au TD-3. N'hésitez pas à récupérer du code.

2.2 Calculette
Écrire une classe HP, qui interprète le contenu de l'entrée standard. Soit +, -, * et / sont les quatre opérations, réalisées sur la pile. Un entier sera empilé (pas de touche ``enter'', pour ceux qui connaissent les calculettes HP). On remarque donc qu'une instruction de la calculette est simplement un lexème.

Réaliser une opération en pile consiste à dépiler deux arguments, à effectuer l'opération, puis finalement à empiler le résultat.

Soit en considérant le petit programme petit.hp, vous devriez obtenir :
maranget@manche ~/TD/TD-4 > java HP < petit.hp 
 321 : 321
 123 : 123, 321
   - : 198
 111 : 111, 198
   + : 309
(La pile est affichée après chaque opération, le haut de la pile étant à gauche.)

N'oubliez pas de réfléchir trente secondes au sens de la soustraction et de la division. Solution.

3 Ajouter des instructions
Les véritables calculettes HP ont des instructions de manipulation de la pile. Nous allons nous en inspirer et définir cinq instructions. Pour chaque instruction, la démarche suivante est suggérée.
  1. Créer un nouveau lexème, on se rendra vite compte que le plus simple est de d'abord considérer une nouvelle sorte de lexèmes, genre les identificateurs (suite de lettres en majuscule), puis de vérifier les instructions possibles, une par une, idéalement dans la classe Lexeme, à l'aide d'une méthode statique :
    static Lexeme instruction (String s)
    
  2. Réaliser la fonctionnalité de la nouvelle instruction, en modifiant la classe HP et éventuellement la classe Stack.
On testera la calculette sur les exemples ci-dessus et on vérifiera bien que les instructions ROTU et ROTD sont inverses l'une de l'autre.

On pensera aux cas limites (pile vide...).

Enfin et plus difficile, on s'imposera ou pas des rotations de pile réalisées en temps indépendant de la taille de la pile. Solution.

4 Calculette ``programmable''
Cet exercice combine de nombreux savoir-faire, il est plus à voir comme un prolongement. Pendant le TD, on s'attachera à l'essentiel en évitant par exemple les affichages excessivement travaillés.

Il nous manque, pour exécuter de véritables programmes avec notre calculette, deux types d'instructions, les branchements et les tests. On s'inspire encore du fonctionnement des calculettes dites programmables. En outre, les programmes de la calculette, qui deviennent un peu complexes, contiendront des commentaires à jeter au moment de l'analyse lexicale. Un commentaire commence par ``%'' et s'étend jusqu'à la fin de la ligne. Voici un exemple de programme :
%% Fonction fib recursive
LBL1
2 SWAP
XLTY GTO2
DUP ROTU SWAP - %Optim d'enfer ``2'' est de'ja sur la pile
GSB1
ROTD 1 -
GSB1
+
RTN
%%% Cas terminal
LBL2 POP POP 1 RTN
La présence des étiquettes LBLn et des branchement change significativement le comportement de la calculette : il n'est plus possible de lire et d'exécuter le programme en même temps. Il faudra :
  1. Lire complètement le programme et le charger en mémoire en résolvant les références (ici, une étiquette correspond à une position d'instruction).
  2. Exécuter le programme en mémoire.
En outre, on impose que la nouvelle calculette compose son programme à partir de deux sources : d'abord la ligne de commande, ensuite l'entrée standard. Cela permet par exemple d'appeler le programme ci-dessus pour divers entiers. (Dans un premier temps, on pourra supposer que les arguments de la ligne de commandes sont des entiers et simplement les empiler).

Par exemple, si pgm.hp est ``LBL0 SWAP - RTN'' (sous-routine qui calcule x-y), alors on aura :
maranget@manche ~/TD/TD-4 > java HP 1 3 GSB0 RTN < pgm.hp
======= Programme chargé =========
000    1
001    3
002 GSB0
003  RTN
004 SWAP
005    -
006  RTN
======= Table des étiquettes =======
LBL0 = 004
LBL1 = 000
LBL2 = 000
LBL3 = 000
LBL4 = 000
LBL5 = 000
LBL6 = 000
LBL7 = 000
LBL8 = 000
LBL9 = 000

======= Exécution ========
000    1 : 1
001    3 : 3, 1
002 GSB0 : 3, 1
004   SWAP : 1, 3
005      - : 2
006    RTN : 2
003  RTN : 2
(Les finauds remarqueront que ``GSB0 RTN'' ne sert à rien.)

Quelques programmes à tester, le pgcd simple (pas de sous-routine), le pgcd compliqué et fibonacci récursif. Solution..


Dernière modification : 2002-11-27

Ce document a été traduit de LATEX par HEVEA.