Corrigé Centrale 2026 Informatique MPI — Partie B (Q6 à Q15) : Analyse lexicale et syntaxique d'une formule déontique (OCaml)

Tout le code de ce corrigé a été exécuté (OCaml 5.4) sur les exemples du sujet et sur des cas limites : chaîne vide, espaces seuls, caractère interdit, _ en tête, parenthèse non fermée, lexèmes restants.

Q6. On parcourt les indices de gauche à droite, en s'arrêtant au premier caractère égal à c.

let appartient chaine c =
  let n = String.length chaine in
  let rec cherche i = i < n && (chaine.[i] = c || cherche (i + 1)) in
  cherche 0

Correction. Invariant : à l'appel cherche i, c n'est à aucun indice $<i$. Si $i=n$, la réponse est donc false ; sinon c est présent si et seulement s'il est en $i$ ou à un indice $>i$. Terminaison : $n-i$ décroît strictement. L'opérateur || est paresseux et son second membre est en position terminale : la récursion est terminale, en espace constant. Coût : au plus $n$ comparaisons, $O(n)$.

Q7. La précondition est $0⩽\text{debut}$, $0⩽\text{longueur}$ et $\text{debut}+\text{longueur}⩽n$ ; une assertion la vérifie, puis String.init construit la chaîne caractère par caractère.

let sous_chaine chaine debut longueur =
  assert (debut >= 0 && longueur >= 0
          && debut + longueur <= String.length chaine);
  String.init longueur (fun k -> chaine.[debut + k])

Le caractère d'indice $k$ du résultat est chaine.[debut + k] pour $0⩽k<$ longueur : c'est la définition de la sous-chaîne, et l'assertion garantit que tous ces indices sont valides. Coût $O(\text{longueur})$. Exécuté : sous_chaine "abracadabra" 3 4 vaut "acad" (indices $3$ à $6$ : a, c, a, d) ; sous_chaine "abc" 1 3 lève Assert_failure ($1+3>3$) ; sous_chaine "abc" 3 0 vaut "". Construire le résultat par concaténations successives \^ coûterait $O({\text{longueur}}^2)$, les chaînes étant immuables. Seul String.sub est interdit ; si l'on veut aussi se passer de String.init, on remplit un tampon mutable : let b = Bytes.create longueur in for k = 0 to longueur - 1 do Bytes.set b k chaine.[debut + k] done; Bytes.to_string b (même précondition, même coût, exécuté avec les mêmes résultats).

Q8. On code l'automate par sa fonction de transition (-1 pour l'absence de transition) et ses états acceptants $1$, $2$, $3$, puis on le simule depuis l'indice debut en retenant la dernière position où l'état courant est acceptant : c'est la règle du plus long préfixe.

exception Erreur_Lexicale

let transition q c = match q with
  | 0 -> if appartient espaces c then 0
         else if appartient alphabet c then 1
         else if c = '(' || c = ')' then 3
         else -1
  | 1 -> if appartient alphabet c then 1 else if c = '_' then 2 else -1
  | 2 -> if appartient alphabet c || c = '_' then 2 else -1
  | _ -> -1                              (* l'état 3 n'a pas de transition *)

let acceptant q = q = 1 || q = 2 || q = 3

let rec premier_non_espace chaine i =
  if i < String.length chaine && appartient espaces chaine.[i]
  then premier_non_espace chaine (i + 1)
  else i

let detecte_lexeme chaine debut =
  let n = String.length chaine in
  (* q : état après lecture de chaine[debut..i-1] ;
     fin : plus grand j <= i avec chaine[debut..j-1] reconnu, -1 s'il n'y en a pas *)
  let rec lire q i fin =
    let fin = if acceptant q then i else fin in
    if i >= n then fin
    else
      let q' = transition q chaine.[i] in
      if q' = -1 then fin else lire q' (i + 1) fin
  in
  let fin = lire 0 debut (-1) in
  if fin = -1 then raise Erreur_Lexicale
  else (premier_non_espace chaine debut, fin)

Correction. L'automate est déterministe (au plus une transition par état et par caractère) ; invariant de lire : q est l'état atteint après lecture de chaine[debut..i-1] et fin est le plus grand $j⩽i$ tel que chaine[debut..j-1] soit reconnu ($-1$ sinon). La mise à jour de fin en tête de fonction maintient l'invariant. Lorsque la lecture s'arrête (fin de chaîne ou transition absente), aucun préfixe plus long ne peut être reconnu — l'automate est bloqué, et aucun état n'est atteignable ensuite — donc fin est la fin du plus long préfixe reconnu. Si fin vaut $-1$, aucun préfixe n'est reconnu (l'état $0$ n'étant pas acceptant, même le préfixe vide ne l'est pas) : on lève l'exception. Les espaces initiaux sont consommés par la boucle sur l'état $0$, et premier_non_espace calcule le début du lexème proprement dit. Terminaison : $n-i$ décroît. Coût : $O(\ell )$ appels de transition, où $\ell$ est la longueur lue, chacun en $O(52)$ à cause de appartient : linéaire.