Compter les arbres d'analyse

1. Deux arbres pour n+n+n — selon que le $+$ de la racine est le premier ou le second. Cinq pour n+n+n+n.

2. On compte, par programmation dynamique sur les intervalles du mot :

Ce sont les nombres de Catalan $C_k=\frac{1}{k+1}\left(\genfrac{}{}{0ex}{}{2k}{k}\right)$, où $k$ est le nombre de $+$. Ce n'est pas un hasard : un arbre d'analyse est ici un arbre binaire à $k$ nœuds internes — l'objet du chapitre chap:arbres —, et compter ces arbres, c'est compter les parenthésages de $k+1$ termes, exactement comme au chapitre chap:dynamique pour le produit de matrices. L'accord a été vérifié jusqu'à $k=6$ : $132$ arbres pour six $+$.

3. Parce que l'addition est associative : $(1+2)+3$ et $1+(2+3)$ valent tous deux $6$. La grammaire est ambiguë, mais l'ambiguïté n'a pas de conséquence observable sur la valeur.

C'est précisément ce qui rend le défaut dangereux. Remplaçons $+$ par $-$ : la même grammaire $E\to E-E\mid \text{n}$ donne encore deux arbres pour 8-3-2, mais ils valent $3$ et $7$. Une grammaire ambiguë ne devient un bogue que le jour où l'opérateur cesse d'être associatif — et ce jour-là, le bogue est déjà en production. On ne teste pas une grammaire sur l'addition.