Analyse lexicale et syntaxique

Toute la théorie du cours converge ici, dans son application reine : le compilateur. Quand vous écrivez prix * 12 + (tva * 20), deux étages de la hiérarchie de Chomsky se relaient pour donner un sens à cette suite de caractères. D'abord les langages réguliers — les automates finis des chapitres 3 à 6 — découpent le texte en unités. Ensuite les langages algébriques — les grammaires du chapitre 7, reconnues par les automates à pile du chapitre 8 — en reconstruisent la structure.

Ce chapitre montre cette chaîne à l'œuvre, et referme la boucle ouverte à la toute première ligne du cours : « une suite de caractères appartient-elle à un langage décrit à l'avance ? ». La réponse, pour un langage de programmation, se donne en deux temps.

L'analyse lexicale : le régulier au travail

L'analyse lexicale est la première phase. Son rôle : transformer le flot de caractères en une suite d'unités lexicales (ou tokens) — les mots du langage. Sur prix * 12, l'analyseur lexical (le lexer) produit :

1IDENT(prix)   OP(*)   NOMBRE(12)

Chaque type d'unité est décrit par une expression régulière : un nombre est [0-9]+, un identifiant [a-z][a-z0-9]*, un opérateur l'un de + - * /. C'est exactement le monde du bloc II, et ce n'est pas un hasard : reconnaître ces motifs ne demande aucune mémoire non bornée. Un automate fini suffit.

Deux principes régissent le découpage :

• La règle du plus long. Face à 123, le lexer lit trois chiffres et produit un seul nombre, pas trois. Il reste dans son état « nombre » tant que la transition existe — le comportement exact d'un AFD qui boucle sur un état. <= est un seul opérateur, pas < suivi de =.
• La priorité entre motifs. Quand plusieurs règles pourraient s'appliquer, un ordre tranche : c'est ainsi qu'un mot-clé comme if est distingué d'un identifiant ordinaire, alors que les deux correspondent au motif des identifiants.

La conséquence pratique est directe : puisqu'un lexer est un automate fini, on l'engendre à partir d'expressions régulières plutôt que de l'écrire à la main. C'est tout l'objet des outils vus plus bas, et c'est le lien concret entre le théorème de Kleene (chapitre 5) et un compilateur réel.

L'analyse syntaxique : l'algébrique au travail

L'analyse syntaxique (le parsing) est la seconde phase. Elle prend la suite d'unités produite par le lexer et vérifie qu'elle respecte la grammaire du langage — puis en construit l'arbre de dérivation (chapitre 7), celui qui porte le sens.

C'est ici qu'intervient tout le bloc III. La grammaire d'un langage de programmation est une grammaire hors contexte ; la reconnaître demande une pile — parce qu'il faut vérifier l'imbrication des parenthèses, des blocs, des appels — donc un automate à pile (chapitre 8). Vérifier que les parenthèses de prix * (tva * 20) sont équilibrées, c'est très exactement le mécanisme « empiler/dépiler » de l'exercice du chapitre 8.

Et c'est ici que la désambiguïsation du chapitre 7 paie : la grammaire des expressions est écrite pour que 1+2*3 n'ait qu'un seul arbre, celui qui respecte la priorité du *. L'analyseur syntaxique en tire donc une structure, sans ambiguïté, et c'est cette structure que les phases suivantes du compilateur évalueront ou traduiront.

L'analyse descendante LL(1)

Parmi les méthodes d'analyse syntaxique, la plus simple à comprendre — et à programmer à la main — est l'analyse descendante LL(1). Son principe : construire l'arbre du haut vers le bas, en partant de l'axiome, et en ne regardant qu'une seule unité à l'avance.

C'est le sens du sigle : Lecture de gauche à droite, dérivation gauche (Leftmost), et 1 symbole de prévision. À chaque étape, l'analyseur doit décider quelle règle appliquer pour la variable courante — et il doit pouvoir trancher en ne voyant que la prochaine unité.

Cette décision se lit dans une table d'analyse : un tableau à double entrée (variable × unité suivante) qui indique la règle à appliquer. La construire, c'est calculer pour chaque variable ce par quoi ses dérivations peuvent commencer (les ensembles Premier) et, pour les règles pouvant s'effacer, ce qui peut suivre (les ensembles Suivant).

Une grammaire est LL(1) quand cette table n'a jamais deux règles dans une même case — sinon, l'analyseur ne saurait pas choisir avec un seul symbole d'avance. Toutes les grammaires ne sont pas LL(1) : certaines demandent de regarder plus loin, ou une méthode ascendante (LR, qui construit l'arbre du bas vers le haut et sous-tend l'outil Yacc/Bison). En L2, retenez le principe LL(1) et la notion de table de décision — les détails des ensembles Premier/Suivant relèvent du cours de compilation.

Les outils : Lex/Flex et Yacc/Bison

On n'écrit plus un lexer ni un analyseur syntaxique entièrement à la main : on les engendre à partir de leur description, ce qui est l'aboutissement pratique de toute la théorie du cours.

• Lex (et sa version libre Flex) prend une liste d'expressions régulières et engendre le code d'un analyseur lexical — un AFD compilé, exactement la chaîne « expression régulière → automate » du théorème de Kleene, automatisée.
• Yacc (et sa version libre Bison) prend une grammaire et engendre le code d'un analyseur syntaxique — un automate à pile, cette fois, conforme au bloc III.

Les deux se complètent : Flex produit le flot d'unités, Bison le consomme pour construire l'arbre. Le point à saisir n'est pas la syntaxe de ces outils, mais ce qu'ils prouvent : les objets abstraits de l'année — automates, expressions régulières, grammaires — sont effectifs au point d'être compilés en programmes par d'autres programmes. La théorie des langages n'est pas une curiosité formelle ; c'est l'ingénierie qui fait tenir chaque compilateur, chaque interpréteur, chaque validateur de format.

À vous

Le TP qui clôt le cours : écrire un analyseur lexical pour un mini-langage d'expressions. Vous découpez prix * 12 + (tva * 20) en unités — identifiants, nombres, opérateurs, parenthèses — selon la règle du plus long.

En le codant, deux choses deviennent évidentes. D'abord, le lexer est un automate fini : chaque branche est un état, la boucle « lire tant que c'est un chiffre » est la boucle d'un AFD. Ensuite, où s'arrête le régulier : le lexer produit des unités mais ne vérifie pas que les parenthèses sont équilibrées — cela demande une pile, donc l'analyse syntaxique du bloc III. Le TP fait ainsi se toucher les deux étages de la hiérarchie, et donne à toute l'année sa raison d'être.

// Un analyseur lexical (lexer) transforme un TEXTE en une suite d'UNITÉS
// lexicales (tokens) : nombres, identifiants, opérateurs, parenthèses. C'est
// la première étape de tout compilateur, et c'est un AUTOMATE FINI — donc du
// langage régulier (chapitres 3 à 6).
//
// Chaque type d'unité est décrit par une expression régulière :
//   NOMBRE      : [0-9]+
//   IDENT       : [a-z]+
//   OP          : + - * /
//   PAR_G PAR_D : ( )
//   (les espaces séparent mais ne produisent pas d'unité)

// ── À VOUS : le lexer ───────────────────────────────────────────────────────
// Parcourir 'texte' de gauche à droite et produire la liste des unités.
// Règle du PLUS LONG : "123" est UN nombre, pas trois. On lit donc autant de
// chiffres consécutifs que possible avant de conclure (comme un AFD qui reste
// dans son état "nombre" tant qu'il lit des chiffres).
function estChiffre(c) { return c >= "0" && c <= "9"; }
function estLettre(c)  { return c >= "a" && c <= "z"; }

function analyser(texte) {
  const unites = [];
  let i = 0;
  while (i < texte.length) {
    const c = texte[i];
    if (c === " ") { i++; continue; }              // espace : on saute
    if (estChiffre(c)) {
      // à compléter : lire TOUS les chiffres consécutifs -> une unité NOMBRE
      // puis avancer i
    } else if (estLettre(c)) {
      // à compléter : lire toutes les lettres consécutives -> une unité IDENT
    } else if ("+-*/".includes(c)) {
      // à compléter : une unité OP d'un seul caractère
    } else if (c === "(" || c === ")") {
      // à compléter : une unité PAR
    } else {
      unites.push({ type: "ERREUR", valeur: c }); i++;  // symbole inconnu
    }
  }
  return unites;
}

// ── Vérification ────────────────────────────────────────────────────────────
const src = "prix * 12 + (tva * 20)";
for (const u of analyser(src)) {
  console.log(u.type.padEnd(8) + " " + u.valeur);
}

function analyser(texte) {
  const unites = [];
  let i = 0;
  while (i < texte.length) {
    const c = texte[i];
    if (c === " ") { i++; continue; }
    if (estChiffre(c)) {
      let j = i;
      while (j < texte.length && estChiffre(texte[j])) j++;   // plus long
      unites.push({ type: "NOMBRE", valeur: texte.slice(i, j) });
      i = j;
    } else if (estLettre(c)) {
      let j = i;
      while (j < texte.length && estLettre(texte[j])) j++;     // plus long
      unites.push({ type: "IDENT", valeur: texte.slice(i, j) });
      i = j;
    } else if ("+-*/".includes(c)) {
      unites.push({ type: "OP", valeur: c }); i++;
    } else if (c === "(" || c === ")") {
      unites.push({ type: "PAR", valeur: c }); i++;
    } else {
      unites.push({ type: "ERREUR", valeur: c }); i++;
    }
  }
  return unites;
}
// Sortie sur "prix * 12 + (tva * 20)" :
//   IDENT prix | OP * | NOMBRE 12 | OP + | PAR ( | IDENT tva | OP * |
//   NOMBRE 20 | PAR )

// ── Ce que ce TP noue, et pourquoi il clôt le cours ─────────────────────────
//
// 1. Le lexer EST un automate fini. Chaque branche du while correspond à un
//    état ; la boucle interne « lire tant que c'est un chiffre » est la
//    boucle d'un AFD sur son état « nombre ». La règle du PLUS LONG est le
//    comportement standard : on reste dans l'état tant que la transition
//    existe. C'est pourquoi les outils réels COMPILENT des expressions
//    régulières en AFD (chapitres 5 et 4) : concis à écrire, rapide à exécuter.
//
// 2. Le lexer produit des UNITÉS ; il ne vérifie PAS la structure. Que
//    « 12 + » soit incomplet, que les parenthèses soient déséquilibrées, ce
//    n'est pas son travail. Vérifier « prix * ( ... ) » bien formé demande de
//    compter les parenthèses — donc une PILE, donc l'analyse SYNTAXIQUE
//    (grammaires et automates à pile, chapitres 7-8).
//
// 3. La chaîne complète d'un compilateur, en une phrase : le texte passe par
//    l'analyse LEXICALE (régulier, ce lexer) qui le découpe en unités, puis
//    par l'analyse SYNTAXIQUE (algébrique) qui en construit l'arbre — celui
//    dont le chapitre 7 disait qu'il porte le sens. Les deux étages de la
//    hiérarchie de Chomsky travaillent l'un après l'autre. Tout le cours
//    converge ici.

Ce que ce cours vous laisse

Vous avez remonté la hiérarchie de Chomsky par le bas, en construisant à chaque étage le même triptyque : une manière de décrire les langages, une machine pour les reconnaître, et un lemme de pompage pour marquer la frontière.

• Les langages réguliers : automates finis, expressions régulières, unifiés par le théorème de Kleene ; frontière tracée par le lemme de pompage ($a^n b^n$ leur échappe).
• Les langages algébriques : grammaires hors contexte et automates à pile, équivalents ; frontière tracée par le lemme de pompage algébrique ($a^n b^n c^n$ leur échappe).
• L'application qui noue le tout : le compilateur, où le régulier découpe et l'algébrique structure.

Deux idées survivront à l'oubli des constructions. La première : à chaque classe de langages correspond une quantité précise de mémoire — aucune pour le régulier, une pile pour l'algébrique, un ruban illimité pour la machine de Turing au-dessus. La seconde : ces objets sont effectifs. Ce que vous avez prouvé au tableau, un outil comme Flex le compile en programme — et c'est ce qui fait de la théorie des langages l'un des ponts les plus directs entre les mathématiques et le logiciel qui tourne.

À retenir

Exercices d'entraînement