Solutions du TD-4, analyse lexicale, calculette

Avertissement

Ce travail pratique est le premier qui a donné lieu à l'écriture d'un vrai programme. Les difficultés n'étaient pas algorithmiques mais purement programmatoires. Il est parfaitement normal d'avoir été un peu dépassé et de ne pas avoir terminé même l'analyseur lexical.

C'est, je crois en regardant le corrigé que vous devriez comprendre comment il faut résoudre toutes ces difficultés que vous avez pu rencontrer et vous rendre compte qu'en fait, c'était facile. Par un aller-retour entre vos difficultés et les solutions, vous devriez vous familiariser avec la démarche de programmation par abstraction (je coupe en trucs simples, je réalise un truc compliqué). Il est normal, encore une fois de ne pas y arriver en deux heures.

1  Analyse lexicale

Sources SLexeme et SLexer. Il n'y a pas de difficulté réelle et le source devrait parler de lui-même. Sisi, regardez-le bien droit dans les yeux.

Je suis preneur de vos questions en cas de problème.

2  Calculette

Sources SStack et SHP. La solution propose une réalisation des piles par un tableau.

La classe HP contient une méthode exec qui utilise quelques idiomes de programmation C (et donc Java). Il s'agit d'une boucle qui lit les lexèmes par Lexer.getToken() jusqu'à plus soif. Classiquement on pourrait écrire :
  Lexeme lxm = lexer.getToken () ;

  while (lxm != null) {
    ...
    lxm = getToken () ;
  }
Mais ici, par le même souci culturel qui conduit à adopter l'accent du Sud de la France sur un terrain de rugby, j'utilise la boucle for :
 for (Lexeme lxm = lexer.getToken () ;
     lxm != null ;
     lxm = lexer.getToken ()) {
    ...
  }
De même à l'intérieur de la boucle, au lieu d'une cascade de if,
 if (lxm.nature == Lexeme.Int) {
    ...
  } else if (lxm.nature == Lexeme.OP) {
    if (lxm.as_op == '+') {
      ...
    } else if lxm.as_op == '-') {
      ...
    } 
      .
      .
      .
    } else {
        System.err.println("Opérateur inconnu : " + lxm.as_op) ;
  } else {
      System.err.println("Lexème inconnu : " + lxm) ;
  }
j'utilise l'instruction switch :
 switch (lxm.nature) {
      case Lexeme.INT:
        ...
        break ;
      case Lexeme.OP:
        switch (lxm.as_op) {
        case '+':
          ...
          break ;

        case '-':
          ...
          break ;
           .
           .
           .
        default:
          System.err.println("Opérateur inconnu : " + lxm.as_op) ;
        }
        break; // Ne pas l'oublier
      default:
          System.err.println("Lexème inconnu : " + lxm) ;
      }
Attention, chaque cas du switch doit se terminer par break si on ne veut pas tomber dans le cas suivant. Notez en particulier qu'il y a deux switch imbriqués et qu'il est facile d'oublier un switch important.

3  Opérations avancées

Nouveau lexer, Lexeme et Lexer. Nouveau source Stack des piles et HP.

On constate que les sources des classes Lexeme, Lexer et HP changent assez peu. La division du programme en lexer et machine , un peu exagérée dans les cas de la simple calculette de la section précédente, se révèle payante lorsqu'il faut étendre le code : les additions à faire se font localement à chaque classe et on arrive à un résultat complexe par une somme de petites manipulation simples.

Pour ce qui est du lexer, la reconnaissance des mots-clefs se fait dans la classe Lexeme, une fois que la classe Lexer a reconnu une suite de lettres et de chiffres commençant par une lettre. Cette technique permet ensuite d'ajouter de nouveaux mots-clefs en ne modifiant que la classe Lexeme.

Les difficultés de programmation apparaissent surtout dans la classe Stack pour programmer les rotations en temps constant. La solution (sur les tableaux) utilise deux indices sp et bot qui designent respectivement le sommet et le fond de la pile. La partie utilisée de la pile allant de bot+1 à sp-1, modulo la taille du tableau. Une fois ceci bien compris et écrites deux méthodes d'incrément et de décrément des indices de pile :
  private static int incr(int i) {
    return (i+1) % MAXSTACK ;
  }

  private static int decr(int i) {
    return (i-1+MAXSTACK) % MAXSTACK ; // Foutue norme
  }
Donc, une fois compris ces points, écrire les rotations est un jeu d'enfant.
  void rotUp () {
    // Enlever le haut
    sp = decr(sp) ;
    // Le mettre en bas
    t[bot] = t[sp] ;
    bot = decr(bot) ;
  }
On remarquera que ce code ne fait rien d'anormal dans le cas des piles vides ou ne contenant qu'un seul élément.

Une amélioration possible de la classe Stack est la réallocation dynamique du tableau en cas de débordement.

3.1  Et avec des listes ?

Essayez voir !

4  Calculette programmable

Tout est déjà là ci-dessus. On notera l'astuce qui consite à créer un StringReader pour chaque argument de la ligne de commande avant de créer un InputStreamReader pour l'entrée standard.
    // Chargement du programme
    for (int i = 0 ; i < arg.length ; i++) {
      load (new Lexer (new StringReader (arg[i]))) ;
    }
    load (new Lexer (new InputStreamReader (System.in))) ;

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