L'analyseur complet

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"

Cinq fonctions mutuellement récursives reflètent la grammaire. Les boucle_* réalisent les répétitions « $(...{)}^{\ast }$ » en associant à gauche.