Probleme – Analyser une expression arithmétique

1. Le point de départ, et l'obstacle.

$$E\to E+T\mid E-T\mid T,T\to T\times F\mid F,F\to (E)\mid \text{entier}.$$

Les trois niveaux encodent la priorité ; la récursivité à gauche encode l'associativité à gauche. Mais traduite littéralement, la règle $E\to E-T$ donne une fonction qui s'appelle elle-même sans avoir rien consommé : pas de variant, pas de terminaison.

On la remplace par une boucle : $E\to T\{(+|-)T\}$. Et l'on accumule à gauche dans la boucle, ce qui rend l'associativité que la réécriture avait perdue.

2. L'analyseur.

exception Echec of string

type expr =
  | Ent of int
  | Plus of expr * expr
  | Moins of expr * expr
  | Fois of expr * expr

(* Analyse texte et rend son arbre de syntaxe abstraite.
   Leve Echec avec la position fautive si le texte est malforme.
   Complexite : Theta(|texte|) -- chaque caractere est lu une seule fois. *)
let analyser texte =
  let n = String.length texte in
  let pos = ref 0 in
  let regarde () = if !pos < n then Some texte.[!pos] else None in
  let lire c =
    if !pos < n && texte.[!pos] = c then incr pos
    else raise (Echec (Printf.sprintf "attendu %c en position %d" c !pos))
  in
  let entier () =
    let debut = !pos in
    while !pos < n && texte.[!pos] >= '0' && texte.[!pos] <= '9' do incr pos done;
    if !pos = debut then raise (Echec (Printf.sprintf "chiffre attendu en %d" !pos));
    Ent (int_of_string (String.sub texte debut (!pos - debut)))
  in
  (* E -> T { (+|-) T }  : la BOUCLE remplace la recursion a gauche.
     VARIANT : n - !pos decroit strictement a chaque tour, car lire consomme.
     INVARIANT : acc contient l'arbre de tout ce qui a ete lu depuis le debut
                 de l'expression courante -- d'ou l'ASSOCIATIVITE A GAUCHE. *)
  let rec e () =
    let acc = ref (t ()) in
    let continuer = ref true in
    while !continuer do
      match regarde () with
      | Some '+' -> lire '+'; acc := Plus (!acc, t ())
      | Some '-' -> lire '-'; acc := Moins (!acc, t ())
      | _ -> continuer := false
    done;
    !acc
  and t () =
    let acc = ref (f ()) in
    let continuer = ref true in
    while !continuer do
      match regarde () with
      | Some '*' -> lire '*'; acc := Fois (!acc, f ())
      | _ -> continuer := false
    done;
    !acc
  and f () =
    match regarde () with
    | Some '(' -> lire '('; let x = e () in lire ')'; x
    | _ -> entier ()
  in
  let x = e () in
  if !pos <> n then raise (Echec (Printf.sprintf "reste a lire en %d" !pos));
  x

let rec evalue = function
  | Ent k -> k
  | Plus (a, b) -> evalue a + evalue b
  | Moins (a, b) -> evalue a - evalue b
  | Fois (a, b) -> evalue a * evalue b

Trois fonctions, trois niveaux de la grammaire — et l'ordre des appels, $e$ appelant $t$ appelant $f$, est la priorité des opérateurs. Rien d'autre ne l'encode.

3. Les vérifications. On affiche l'arbre entièrement parenthésé, ce qui rend sa forme visible, et l'on compare avec la variante fautive qui associerait à droite.

Une seule ligne diffère, et c'est celle où l'opérateur n'est pas associatif : $3$ contre $7$. Sur les cinq autres, le défaut d'associativité est invisible bien que l'arbre soit différent — voir la colonne 1+2+3+4, où les deux arbres sont franchement distincts et les deux valeurs égales.

Un test d'aller-retour clôt l'affaire : réanalyser le texte entièrement parenthésé rend le même arbre, sur les huit expressions essayées.

4. Les entrées malformées. L'analyseur doit refuser, et dire où. Chaque refus est mesuré :

Les deux dernières familles sont distinctes, et c'est ce qui compte : « reste à lire » vient du contrôle final, les autres viennent d'un échec interne. Un analyseur qui oublierait le contrôle final accepterait 1) et 1 2 — c'est la faute de l'exercice sur le contrôle de fin.