Analyse syntaxique et interprétation

<i class="fa-solid fa-compass mr-2" style="color:#9A563B"></i>21.1 Introduction et motivation

Comment une machine comprend-elle "3 + 4 * 2" et répond 11 (et non 14) ? C'est le travail d'un interpréteur, et c'est l'occasion d'un projet qui rassemble presque tout le livre. Le traitement se fait en trois étapes, une véritable chaîne de montage :

L'analyse lexicale (lexing) découpe la chaîne (chapitre 6) en lexèmes (nombres, opérateurs, parenthèses) ; l'analyse syntaxique (parsing) les organise en un arbre de syntaxe (un type somme récursif, chapitre 3) qui respecte les priorités ; l'évaluation parcourt cet arbre (comme au chapitre 3). Le parser s'écrit par descente récursive — un bel usage de la récursion mutuelle (chapitre 1).

21.2 Analyse lexicale

Un lexème est une unité de sens. Pour l'arithmétique, on en a six :

type lexeme = Nombre of int | Plus | Moins | Fois | ParenG | ParenD

L'analyseur lexical parcourt la chaîne, ignore les espaces, reconnaît les opérateurs et les parenthèses, et regroupe les chiffres consécutifs en un nombre.

let rec renverse l =          (* utilitaire (chapitre 2) *)
  let rec aux acc l = match l with [] -> acc | x :: r -> aux (x :: acc) r in
  aux [] l

let lexer s =
  let n = String.length s in
  let lex = ref [] and i = ref 0 in
  while !i < n do
    let c = s.[!i] in
    if c = ' ' then i := !i + 1
    else if c = '+' then begin lex := Plus :: !lex; i := !i + 1 end
    else if c = '-' then begin lex := Moins :: !lex; i := !i + 1 end
    else if c = '*' then begin lex := Fois :: !lex; i := !i + 1 end
    else if c = '(' then begin lex := ParenG :: !lex; i := !i + 1 end
    else if c = ')' then begin lex := ParenD :: !lex; i := !i + 1 end
    else if c >= '0' && c <= '9' then begin
      let v = ref 0 in
      while !i < n && s.[!i] >= '0' && s.[!i] <= '9' do
        v := !v * 10 + (int_of_char s.[!i] - int_of_char '0');
        i := !i + 1
      done;
      lex := Nombre !v :: !lex
    end
    else failwith "caractère inattendu"
  done;
  renverse !lex

lexer "3 + 42" renvoie [Nombre 3; Plus; Nombre 42]. On accumule en tête (donc à l'envers), puis on renverse. La boucle interne lit un nombre à plusieurs chiffres comme au chapitre 6.

21.3 L'arbre de syntaxe

On représente l'expression par un arbre (chapitre 3), où la structure encode les priorités : dans l'arbre de 3 + 4 2, le Fois est plus bas* que le Add, donc évalué d'abord.

type expr =
  | Const of int
  | Add of expr * expr
  | Sub of expr * expr
  | Mul of expr * expr

21.4 Analyse syntaxique par descente récursive

On décrit la syntaxe par une grammaire à trois niveaux, du moins prioritaire au plus prioritaire :

À chaque niveau correspond une fonction, qui consomme des lexèmes et renvoie un couple (arbre construit, lexèmes restants). Les fonctions s'appellent mutuellement (let rec … and …, chapitre 1).

let rec parse_expr lex =
  let (g, reste) = parse_terme lex in
  boucle_add g reste
and boucle_add g lex =
  match lex with
  | Plus :: reste  -> let (d, r) = parse_terme reste in boucle_add (Add (g, d)) r
  | Moins :: reste -> let (d, r) = parse_terme reste in boucle_add (Sub (g, d)) r
  | _ -> (g, lex)
and parse_terme lex =
  let (g, reste) = parse_facteur lex in
  boucle_mul g reste
and boucle_mul g lex =
  match lex with
  | Fois :: reste -> let (d, r) = parse_facteur reste in boucle_mul (Mul (g, d)) r
  | _ -> (g, lex)
and parse_facteur lex =
  match lex with
  | Nombre v :: reste -> (Const v, reste)
  | ParenG :: reste ->
      let (e, r) = parse_expr reste in
      (match r with
       | ParenD :: r2 -> (e, r2)
       | _ -> failwith "parenthese fermante attendue")
  | _ -> failwith "facteur attendu"

Les fonctions boucle_add et boucle_mul enchaînent les opérations à gauche : en construisant Add (g, d) puis en continuant avec ce résultat comme nouveau membre gauche, on obtient l'associativité à gauche. La descente expr → terme → facteur encode les priorités : un + ne se forme qu'après avoir entièrement analysé les *.

21.5 Interprétation

On assemble la chaîne complète : lexer, parser, évaluer (l'évaluation est celle du chapitre 3, étendue à Sub).

let rec evalue e =
  match e with
  | Const n -> n
  | Add (a, b) -> evalue a + evalue b
  | Sub (a, b) -> evalue a - evalue b
  | Mul (a, b) -> evalue a * evalue b

let interprete s =
  let (e, reste) = parse_expr (lexer s) in
  if reste <> [] then failwith "expression mal formee"
  else evalue e

interprete "3 + 4 2" vaut 11 ; interprete "(3 + 4) 2" vaut 14. Le test reste <> [] rejette les entrées mal formées (lexèmes en trop, comme "3 4").

<i class="fa-solid fa-dumbbell mr-2" style="color:#2E7559"></i>21.6 Exercices résolus

Niveau $\star$ (application directe du cours)

type lexeme = Nombre of int | Plus | Moins | Fois | ParenG | ParenD
(* lexer "(1+2)" = [ParenG; Nombre 1; Plus; Nombre 2; ParenD] *)

let rec evalue e =
  match e with
  | Const n -> n
  | Add (a, b) -> evalue a + evalue b
  | Sub (a, b) -> evalue a - evalue b
  | Mul (a, b) -> evalue a * evalue b

let lexer_simple s =
  let lex = ref [] in
  for i = String.length s - 1 downto 0 do      (* à l'envers : pas de renverse *)
    let c = s.[i] in
    let l =
      if c = '+' then Plus else if c = '-' then Moins
      else if c = '*' then Fois else if c = '(' then ParenG
      else if c = ')' then ParenD
      else Nombre (int_of_char c - int_of_char '0')
    in
    lex := l :: !lex
  done;
  !lex

Niveau $\star \star$ (raisonnement intermédiaire)

let lexer s =
  let n = String.length s in
  let lex = ref [] and i = ref 0 in
  while !i < n do
    let c = s.[!i] in
    if c = ' ' then i := !i + 1
    else if c = '+' then begin lex := Plus :: !lex; i := !i + 1 end
    else if c = '-' then begin lex := Moins :: !lex; i := !i + 1 end
    else if c = '*' then begin lex := Fois :: !lex; i := !i + 1 end
    else if c = '(' then begin lex := ParenG :: !lex; i := !i + 1 end
    else if c = ')' then begin lex := ParenD :: !lex; i := !i + 1 end
    else if c >= '0' && c <= '9' then begin
      let v = ref 0 in
      while !i < n && s.[!i] >= '0' && s.[!i] <= '9' do
        v := !v * 10 + (int_of_char s.[!i] - int_of_char '0');
        i := !i + 1
      done;
      lex := Nombre !v :: !lex
    end
    else failwith "caractere inattendu"
  done;
  renverse !lex

let rec parse_facteur lex =
  match lex with
  | Nombre v :: reste -> (Const v, reste)
  | ParenG :: reste ->
      let (e, r) = parse_expr reste in
      (match r with
       | ParenD :: r2 -> (e, r2)
       | _ -> failwith "parenthese fermante attendue")
  | _ -> failwith "facteur attendu"
and parse_expr lex = ...   (* mutuellement récursif *)

Niveau $\star \star \star$ (approfondissement)

let rec parse_expr lex =
  let (g, reste) = parse_terme lex in
  boucle_add g reste
and boucle_add g lex =
  match lex with
  | Plus :: reste  -> let (d, r) = parse_terme reste in boucle_add (Add (g, d)) r
  | Moins :: reste -> let (d, r) = parse_terme reste in boucle_add (Sub (g, d)) r
  | _ -> (g, lex)
and parse_terme lex =
  let (g, reste) = parse_facteur lex in
  boucle_mul g reste
and boucle_mul g lex =
  match lex with
  | Fois :: reste -> let (d, r) = parse_facteur reste in boucle_mul (Mul (g, d)) r
  | _ -> (g, lex)
and parse_facteur lex =
  match lex with
  | Nombre v :: reste -> (Const v, reste)
  | ParenG :: reste ->
      let (e, r) = parse_expr reste in
      (match r with ParenD :: r2 -> (e, r2) | _ -> failwith "parenthese attendue")
  | _ -> failwith "facteur attendu"

let interprete s =
  let (e, reste) = parse_expr (lexer s) in
  if reste <> [] then failwith "expression mal formee" else evalue e

| Div :: reste -> let (d, r) = parse_facteur reste in boucle_mul (Divi (g, d)) r
(* ... *)
| Divi (a, b) -> evalue a / evalue b

21.7 Exercices d'entraînement

Légende : $\star$ application directe, $\star \star$ raisonnement intermédiaire, $\star \star \star$ approfondissement ; $⧫$ signale un classique incontournable. La numérotation prolonge celle des dix exercices résolus.

Thème A — Lexique.

• [11.] $\star$ Étendre lexer pour accepter le caractère de tabulation comme séparateur.
• [12.] $\star \star$ Compter, dans une chaîne, le nombre de nombres (lexèmes Nombre).
• [13.] $\star \star \star$ $⧫$ Reconnaître des identifiants (suites de lettres) comme nouveau lexème Ident of string ? Discuter (chapitre 6 : construire une chaîne).

Thème B — Arbre et évaluation.

• [14.] $\star \star$ Écrire taille_expr et profondeur_expr (chapitre 3) sur l'arbre de syntaxe.
• [15.] $\star \star \star$ Réafficher l'arbre en notation infixe entièrement parenthésée (string).
• [16.] $\star \star \star$ Réafficher l'arbre en notation postfixe et l'évaluer avec une pile (chapitre 8).

Thème C — Extensions du parser.

• [17.] $\star \star$ Ajouter la division (cf. exercice 9) et tester sur "12 / 3 / 2".
• [18.] $\star \star \star$ Ajouter l'opérateur unaire - (moins préfixe : "-3 + 5").
• [19.] $\star \star \star$ $⧫$ Ajouter la puissance ^, associative à droite (2 ^ 3 ^ 2 $=2^9$) ; pourquoi la boucle à gauche ne convient-elle plus ?

Thème D — Vers un vrai langage.

• [20.] $\star \star \star$ Ajouter des variables : un environnement (table de hachage du chapitre 8) associant un nom à une valeur.
• [21.] $\star \star \star$ Évaluer une expression booléenne (chapitre 17) par le même procédé lexer/parser/eval.
• [22.] $\star \star$ $⧫$ Discuter : quelles étapes ajouter pour passer de cet interpréteur d'expressions à celui d'un mini-langage avec affectations et boucles ?