Probleme – La grammaire de balisage du programme, de bout en bout

1. La non-ambiguïté. Introduisons la hauteur $h(u)=|u{|}_a-|u{|}_b$.

Lemme. Tout $w\in L(S)$ vérifie $h(w)=0$ et tout préfixe $p$ de $w$ vérifie $h(p)\ge 0$. Tout $t\in L(T)$ vérifie $h(t)=0$, et tout préfixe propre et non vide $p$ de $t$ vérifie $h(p)\ge 1$.

Preuve du lemme, par induction mutuelle. Pour $S\to c$ : hauteur nulle partout. Pour $S\to TS$ : la concaténation de deux mots de hauteur nulle, dont les préfixes restent positifs. Pour $T\to aSb$ : le a initial monte à $1$, les préfixes de $u$ y ajoutent une quantité positive, et seul le b final redescend à $0$.

La non-ambiguïté suit. Soit $w\in L(S)$, non vide. Sa première lettre décide la règle : si c'est c, la seule règle possible est $S\to c$ et $w=c$ ; si c'est a, la seule règle possible est $S\to TS$. Il reste à montrer que la coupure entre $T$ et $S$ est unique : d'après le lemme, la partie $T$ est le préfixe de $w$ qui ramène $h$ à zéro pour la première fois, et cette position est déterminée par $w$ seul. Chaque nœud de l'arbre étant ainsi forcé, l'arbre est unique.

Le décompte machine confirme : les $9$ mots de longueur au plus $10$ ont chacun exactement un arbre d'analyse.

2. L'analyseur qui construit l'arbre. Le type inductif est la grammaire :

type arbre =
  | Feuille                        (* S -> c     *)
  | Bloc of arbre * arbre          (* S -> T S, avec T -> a S b *)

exception Echec

(* Analyse mot et rend son arbre. Leve Echec si mot n'est pas dans L(S).
   INVARIANT : a l'appel de s (), pos designe le debut d'un mot de L(S) ;
               au retour, pos designe la position juste apres ce mot.
   VARIANT : n - !pos decroit strictement a chaque appel de lire. *)
let arbre_de mot =
  let n = String.length mot in
  let pos = ref 0 in
  let lire c = if !pos < n && mot.[!pos] = c then incr pos else raise Echec in
  let rec s () =
    if !pos < n && mot.[!pos] = 'a' then
      let dedans = t () in Bloc (dedans, s ())
    else (lire 'c'; Feuille)
  and t () =
    lire 'a'; let a = s () in lire 'b'; a
  in
  let a = s () in
  if !pos <> n then raise Echec;
  a

(* Le mot se relit depuis l'arbre : c'est le test d'ALLER-RETOUR. *)
let rec vers_mot = function
  | Feuille -> "c"
  | Bloc (d, suite) -> "a" ^ vers_mot d ^ "b" ^ vers_mot suite

Terminaison. Chaque appel de t consomme au moins un caractère avant de rappeler s : le variant $n-\mathtt{pos}$ décroît strictement. Il n'y a pas de récursivité à gauche, et c'est ce qui rend l'analyseur possible.

Correction. L'invariant écrit au-dessus du code : le choix de règle est déterminé par le caractère courant — a force $S\to TS$, tout le reste force $S\to c$ —, ce qui est exactement le contenu de la démonstration de non-ambiguïté.

L'aller-retour. vers_mot (arbre_de w) = w doit être vrai pour tout $w$ du langage. Exécuté sur les $9$ mots reconnus de longueur au plus $10$ : aucun échec. C'est le test qui vaut le plus cher pour son prix : il éprouve d'un coup l'analyseur et la structure de l'arbre.

Les arbres obtenus :

  c          arbre c                      profondeur 1
  acbc       arbre T(c).c                 profondeur 3
  aacbcbc    arbre T(T(c).c).c            profondeur 5
  acbacbc    arbre T(c).T(c).c            profondeur 4
  aaacbcbcbc arbre T(T(T(c).c).c).c       profondeur 7

Noter les deux mots de longueur $7$ : même longueur, arbres de profondeurs $5$ et $4$. L'un imbrique, l'autre juxtapose.

3. Le dénombrement. Notons $s_n$ le nombre de mots de $L(S)$ de longueur $n$, et $t_n$ celui de $L(T)$. Les deux règles donnent

$$s_1=1,s_n=\sum _k{t}_k{s}_{n-k},t_n=s_{n-2}.$$

On sait déjà que les longueurs sont congrues à $1$ modulo $3$. Posons $u_m=s_{3m+1}$. Alors $t_{3j+3}=s_{3j+1}=u_j$, et la première relation devient

$$u_m=\sum _{j=0}^{m-1}{u}_j{u}_{m-1-j},$$

qui est exactement la récurrence de Catalan. Donc $u_m=C_m=\frac{1}{m+1}\left(\genfrac{}{}{0ex}{}{2m}{m}\right)$.

Vérifié de deux façons : par énumération exhaustive de tous les mots sur trois lettres jusqu'à la longueur $10$, qui donne $1,1,2,5$ mots pour $m=0,1,2,3$ ; et par la récurrence poussée jusqu'à $m=7$, qui donne $429$.

Pourquoi Catalan, encore. Parce qu'un mot du langage est un arbre : les blocs $a\dots b$ sont les nœuds, le c final est la fin d'une liste de fils. Le langage de balisage et les arbres binaires sont deux écritures du même objet — c'est ce que la remarque du chapitre appelle « une grammaire non contextuelle est une définition inductive ».