Du texte aux lexèmes

La première phase du compilateur est aussi celle où la Théorie des langages rejoint directement la compilation. L'analyse lexicale transforme le flot de caractères du programme source en une suite d'unités lexicales — les « mots » du langage. Et cette phase n'est rien d'autre qu'un automate fini au travail : tout ce que vous avez appris sur les langages réguliers s'applique ici, tel quel.

Ce chapitre précise le vocabulaire, montre comment on spécifie puis construit un analyseur lexical, énonce les deux règles qui le rendent déterministe — le plus long lexème et la priorité entre motifs — et introduit Flex, l'outil qui l'engendre automatiquement.

Trois mots à distinguer

Le vocabulaire de la phase repose sur trois notions qu'on confond volontiers.

• Le motif (pattern) est la règle qui décrit une catégorie de lexèmes, exprimée par une expression régulière. Exemple : un identifiant, [a-zA-Z_][a-zA-Z0-9_]*.
• Le lexème est la suite de caractères concrète trouvée dans le source qui correspond au motif. Dans x1 = 42, x1 et 42 sont des lexèmes.
• L'unité lexicale (token) est la catégorie renvoyée à l'analyseur syntaxique, souvent avec une valeur associée : IDENT("x1"), NOMBRE(42), SYMBOLE("=").

Le lexeur lit des lexèmes, les reconnaît par des motifs, et produit des unités lexicales. L'analyseur syntaxique, lui, ne verra que les unités — jamais les caractères. C'est le premier maillon du filtre en cascade du chapitre 1.

Spécifier, puis construire

La beauté de cette phase est qu'on n'écrit pas l'automate à la main : on décrit chaque catégorie par une expression régulière, et l'automate s'en déduit.

1NOMBRE   →  [0-9]+2IDENT    →  [a-zA-Z_][a-zA-Z0-9_]*3ADD      →  "+"4AFFECT   →  "="5ESPACE   →  [ \t\n]+          (reconnu, mais pas transmis)

La chaîne théorique est exactement celle de la Théorie des langages : une expression régulière se convertit en automate (construction de Thompson), qu'on rend déterministe (construction des sous-ensembles) puis minimal. Le résultat est un AFD unique qui lit le source en une seule passe, de gauche à droite, sans retour arrière — d'où la rapidité de l'analyse lexicale.

Regardez-le fonctionner. L'automate ci-dessous reconnaît, depuis un même état de départ, soit un identifiant, soit un nombre — avec a pour « une lettre » et 1 pour « un chiffre ». Sur a1a, il entre dans l'état ID et y reste, parce que chaque caractère prolonge un identifiant valide : c'est déjà la règle du plus long lexème, vue de l'intérieur de l'automate.

Les deux règles qui lèvent l'ambiguïté

Un texte peut correspondre à plusieurs découpages ; deux règles universelles tranchent.

La règle du plus long lexème. On lit le lexème le plus long possible. Face à while1, le lexeur ne s'arrête pas après while : il continue tant que les caractères prolongent un identifiant, et produit un seul identifiant while1. Face à <=, il produit l'opérateur <=, pas < suivi de =. C'est le comportement naturel d'un AFD qui reste dans son état d'acceptation tant qu'une transition existe.

La priorité entre motifs. Quand plusieurs motifs reconnaissent le même lexème, un ordre départage. Le cas typique est celui des mots-clés : while, if, return correspondent aussi au motif des identifiants. Deux stratégies : soit on donne aux mots-clés une priorité supérieure dans la spécification, soit — plus simple et plus courant — on lit d'abord l'identifiant maximal, puis on consulte une table de mots réservés pour le reclasser. C'est l'approche de l'exercice.

Espaces, commentaires, littéraux

Tout ce qui est dans le source n'a pas vocation à devenir une unité lexicale.

Les espaces, tabulations et retours à la ligne sont reconnus (ils séparent les lexèmes) mais ne produisent aucune unité — sauf dans les langages où l'indentation est significative, comme Python.

Les commentaires sont reconnus et jetés. Ils réservent quelques pièges classiques : les commentaires imbriqués, et surtout le fait qu'un /* non fermé doit produire une erreur claire plutôt que d'avaler silencieusement la fin du fichier.

Les littéraux — chaînes "...", caractères, nombres flottants — ont des motifs plus riches, avec leurs propres subtilités : séquences d'échappement (\n, \"), guillemet non fermé, format des nombres. Le lexeur les reconnaît et attache leur valeur à l'unité produite.

Flex, et les erreurs lexicales

Flex (successeur libre de Lex) engendre un analyseur lexical à partir d'une liste de motifs. On écrit des paires « expression régulière → action », et Flex produit le code de l'automate — la chaîne « expression régulière → AFD » du théorème de Kleene, automatisée :

1[0-9]+                { return NOMBRE; }2"while"               { return WHILE; }3[a-zA-Z_][a-zA-Z0-9_]* { return IDENT; }   /* après les mots-clés : priorité par l'ordre */4[ \t\n]+              { /* ignoré */ }5.                     { erreur_lexicale(); }

Flex applique par construction la règle du plus long lexème, et départage les motifs de même longueur par leur ordre d'apparition — d'où les mots-clés placés avant le motif générique des identifiants. La ligne finale . capture tout caractère non reconnu et signale une erreur lexicale : un caractère hors alphabet (@, #…), un guillemet ou un commentaire non fermé. Comme pour toute phase, un bon lexeur ne s'arrête pas à la première faute : il la signale, se resynchronise, et poursuit.

Le choix pédagogique du cours est d'écrire le lexeur à la main d'abord — c'est l'exercice ci-dessous — puis de le refaire avec Flex. On comprend alors ce que l'outil automatise, au lieu de le subir.

À vous

L'exercice construit la première couche du compilateur du TP : l'analyseur lexical du mini-langage. Vous prolongez le lexeur de la Théorie des langages avec les deux règles qui manquaient — le plus long lexème et la priorité des mots-clés — et vous produisez une suite d'unités lexicales à partir d'un véritable fragment de programme.

Sa sortie n'est pas une fin : c'est l'entrée de l'analyseur syntaxique du bloc III. Gardez ce code, il grossira tout le semestre.

// L'analyseur lexical du mini-langage. Il produit des unités (tokens) et doit
// respecter DEUX règles que tout lexeur applique :
//   1. RÈGLE DU PLUS LONG : on lit le lexème le plus long possible.
//      « while1 » est UN identifiant, pas le mot-clé « while » suivi de « 1 ».
//   2. PRIORITÉ DES MOTS-CLÉS : « while », « if », « else » ressemblent à des
//      identifiants ; on les reclasse en mots-clés APRÈS les avoir lus.

const MOTS_CLES = new Set(["if", "else", "while", "return"]);

function estLettre(c) { return /[a-zA-Z_]/.test(c); }
function estChiffre(c) { return /[0-9]/.test(c); }

// ── À VOUS : compléter le lexeur ────────────────────────────────────────────
function analyser(src) {
  const tokens = [];
  let i = 0;
  while (i < src.length) {
    const c = src[i];
    if (c === " " || c === "\n" || c === "\t") { i++; continue; }  // espaces ignorés

    if (estLettre(c)) {
      let j = i;
      while (j < src.length && (estLettre(src[j]) || estChiffre(src[j]))) j++;  // plus long
      const mot = src.slice(i, j);
      // à compléter : si 'mot' est un mot-clé -> type "MOTCLE", sinon "IDENT"
      // tokens.push({ type: ..., valeur: mot });
      i = j;
    } else if (estChiffre(c)) {
      let j = i;
      while (j < src.length && estChiffre(src[j])) j++;   // plus long
      tokens.push({ type: "NOMBRE", valeur: src.slice(i, j) });
      i = j;
    } else if ("+-*/=(){};<>".includes(c)) {
      tokens.push({ type: "SYMBOLE", valeur: c });
      i++;
    } else {
      tokens.push({ type: "ERREUR", valeur: c });   // caractère hors alphabet
      i++;
    }
  }
  return tokens;
}

// ── Vérification ────────────────────────────────────────────────────────────
const src = "while (x1 < 10) x1 = x1 + 2;";
for (const t of analyser(src)) console.log(t.type.padEnd(8) + " " + t.valeur);

function analyser(src) {
  const tokens = [];
  let i = 0;
  while (i < src.length) {
    const c = src[i];
    if (c === " " || c === "\n" || c === "\t") { i++; continue; }

    if (estLettre(c)) {
      let j = i;
      while (j < src.length && (estLettre(src[j]) || estChiffre(src[j]))) j++;
      const mot = src.slice(i, j);
      // Priorité des mots-clés : on a lu le plus long lexème « identifiant »,
      // puis on le RECLASSE en mot-clé s'il figure dans la liste réservée.
      tokens.push({ type: MOTS_CLES.has(mot) ? "MOTCLE" : "IDENT", valeur: mot });
      i = j;
    } else if (estChiffre(c)) {
      let j = i;
      while (j < src.length && estChiffre(src[j])) j++;
      tokens.push({ type: "NOMBRE", valeur: src.slice(i, j) });
      i = j;
    } else if ("+-*/=(){};<>".includes(c)) {
      tokens.push({ type: "SYMBOLE", valeur: c });
      i++;
    } else {
      tokens.push({ type: "ERREUR", valeur: c });
      i++;
    }
  }
  return tokens;
}
// Sortie sur « while (x1 < 10) x1 = x1 + 2; » :
//   MOTCLE while | SYMBOLE ( | IDENT x1 | SYMBOLE < | NOMBRE 10 | SYMBOLE ) |
//   IDENT x1 | SYMBOLE = | IDENT x1 | SYMBOLE + | NOMBRE 2 | SYMBOLE ;

// ── Ce que l'exercice enseigne ──────────────────────────────────────────────
//
// 1. Un lexeur EST un automate fini (cf. Théorie des langages) : chaque
//    branche du while est un état, la boucle interne « tant que c'est une
//    lettre ou un chiffre » est la boucle de l'AFD sur son état « identifiant ».
//
// 2. La RÈGLE DU PLUS LONG évite « while1 » découpé en « while » + « 1 » :
//    on lit tant que le lexème peut grandir, puis on tranche. Sans elle, le
//    langage serait ambigu à lire.
//
// 3. La PRIORITÉ DES MOTS-CLÉS ne se gère PAS dans l'automate : « while »
//    suit le même motif qu'un identifiant. On lit d'abord l'identifiant
//    maximal, PUIS on consulte une table de mots réservés. C'est plus simple
//    et plus rapide qu'un automate qui distinguerait chaque mot-clé.
//
// 4. Espaces et commentaires sont RECONNUS mais ne produisent pas de token :
//    ils séparent les lexèmes sans en être. Un « @ » hors alphabet produit
//    une erreur LEXICALE — la première du filtre en cascade du chapitre 1.
//
// C'est la première couche du compilateur du TP : sa sortie, la suite de
// tokens, alimentera l'analyseur syntaxique du bloc III.

Ce que la suite en fait

Le lexeur produit une suite plate d'unités lexicales — mais un programme n'est pas une liste, c'est une structure : des expressions imbriquées, des blocs, des conditions. Reconstruire cette structure est le travail de l'analyse syntaxique, le cœur du cours.

Le bloc III commence par préparer la grammaire (chapitre 3), puis construit l'arbre de deux façons complémentaires : par le haut (analyse descendante, chapitre 4) et par le bas (analyse ascendante, chapitre 5). La suite de tokens que vous venez de produire en sera l'entrée directe.

À retenir