Analyse lexicale

Un compilateur comporte toujours une première phase qui détermine les unités lexicales à l'aide d'un automate fini.

Considérons le texte suivant :

int f(int arg) {
  return 2*arg+1;
}

Ce texte est d'abord découpé en lexèmes : dans l'exemple ci-dessus, int, (, return et 1 sont des lexèmes, tandis que in ou int f n'en sont pas. Chaque lexème appartient à une unité lexicale, qui comporte un ou plusieurs lexèmes. Voici les unités lexicales correspondant aux exemples précédents : ident (qui contient tous les identificateurs), par-gauche (qui contient seulement la parenthèse ouvrante), return (qui contient seulement le mot-clé return), nombre (qui contient tous les lexèmes numériques).

L'analyse lexicale d'un texte, c'est-à-dire d'un mot sur l'alphabet Unicode, consiste à le transformer en une suite d'unités lexicales, c'est-à-dire en un mot sur un autre alphabet. Par exemple, le texte précédent int f ... est transformé en ident ident par-gauche ident ident par-droite acc-gauche return nombre mult ident plus nombre point-virgule acc-droite. Certaines unités lexicales sont affectées d'une valeur (par exemple, la valeur numérique d'un nombre, ou la valeur textuelle d'un ident).

L'API de Java dispose d'une classe StreamTokenizer, dans le paquet java.io qui aide à effectuer l'analyse lexicale d'un flot d'entrée. Selon le type de langage qui doit être analysé, il peut être utile de spécialiser cette classe ; voici par exemple une classe adaptée à l'analyse lexicale de programmes Java :

class JavaTokenizer extends StreamTokenizer {
   JavaTokenizer(InputStreamReader in) {
     super(in);
     slashSlashComments(true);
     slashStarComments(true);
     ordinaryChar('/');
     ordinaryChar('.');
     wordChars('_', '_');
   }
}

La méthode nextToken() retourne l'unité lexicale suivante sous forme d'un entier ou bien la constante TT_EOF si la fin du flot est atteinte ; le champ ttype contient soit la valeur de l'unité lexicale (la constante de classe TT_WORD ou TT_NUMBER) si c'est un identificateur ou un nombre, ou quand le lexème est un caractère ordinaire, le code de ce caractère, ou, quand le lexème est une chaîne littérale, le caractère de citation (" ou ').

class Lexer {
  public static void main(String[] args) throws IOException {

    JavaTokenizer jt =
      new JavaTokenizer(
         new FileReader(args[0]));

    while (jt.nextToken() != StreamTokenizer.TT_EOF) {
      switch(jt.ttype) {
      case StreamTokenizer.TT_WORD:
        System.out.print("ident "); break;
      case StreamTokenizer.TT_NUMBER:
        System.out.print("nombre "); break;
      default: System.out.print((char)jt.ttype + " ");
      }
    }
    System.out.println();
  }
}

L'exécution de ce programme, sur le texte int f ... ci-dessus produit la suite d'unités lexicales suivantes :

          ident ident ( ident ident ) 
          { ident nombre * ident + nombre ; }

Le lexème correspondant à une unité lexicale ident est obtenu à l'aide de la variable jt.sval, de type String ; le lexème correspondant à une unité lexicale nombre est converti en un nombre, obtenu dans la variable jt.nval, de type double.

Pour vérifier que le texte int f ... est un programme Java correct, on doit vérifier que le mot ident ident ... vérifie les règles de grammaire de Java, ce qu'on appelle l'analyse syntaxique . Cette vérification ne peut pas se faire avec un automate fini, car elle nécessite de garder en mémoire les états passés. On doit donc combiner un automate fini avec une pile , mais la description de cet algorithme dépasse le cadre de ce cours.