Probleme – Mesurer l'ambiguïté

1. Le calcul. Notons $N(A,i,j)$ le nombre d'arbres d'analyse du facteur $w[i..j-1]$ à partir du symbole $A$. Pour une règle $A\to X_1{X}_2\cdots X_k$, on somme sur toutes les façons de découper le facteur :

$$N(A,i,j)=\sum _{A\to X_1\cdots X_k}\sum _{i=m_0\le m_1\le \cdots \le m_k=j}\prod _{\ell =1}^{k}N(X_{\ell },m_{\ell -1},m_{\ell }),$$

avec $N(x,i,j)=1$ si $x$ est le terminal $w[i]$ et $j=i+1$, et $0$ sinon. On calcule par mémoïsation sur les triplets $(A,i,j)$ : c'est la programmation dynamique du chapitre chap:dynamique, sur les intervalles.

Un piège de programmation, qu'il faut nommer. Si l'on énumère naïvement les découpages, un facteur vide attribué au premier symbole ramène au même triplet $(A,i,j)$ et la récursion boucle. On borne donc les découpages par la longueur minimale dérivable de chaque symbole, calculée d'avance par un point fixe. Sans cette précaution, le programme ne termine pas — et l'erreur ne se voit que sur les grammaires ayant un symbole annulable.

2. Les mesures.

La grammaire à trois niveaux n'est ambiguë sur aucun mot de longueur au plus $6$, et l'on a vérifié qu'elle engendre exactement les mêmes mots sans parenthèses que la version simplifiée, jusqu'à la longueur $7$. Faiblement équivalentes, et une seule est utilisable.

3. L'ensemble des valeurs. Pour 2+3*4, les deux arbres donnent $14$ et $20$. Le nombre de valeurs distinctes croît vite : c'est le nombre d'arbres, moins les coïncidences dues à l'associativité et à la commutativité.

Et c'est là qu'est le vrai danger. Une grammaire ambiguë ne choisit pas. Deux compilateurs conformes à la même grammaire peuvent donc calculer deux résultats différents pour le même programme, sans que ni l'un ni l'autre ne soit fautif. La spécification est incomplète, et le défaut ne se voit sur aucune exécution particulière : il se voit en changeant de compilateur.

4. Non, ce procédé ne décide rien. Il trouve un témoin d'ambiguïté quand il en existe un court. Il ne prouve jamais l'absence d'ambiguïté : avoir vérifié tous les mots de longueur au plus $9$ ne dit rien du mot de longueur $10$.

Et il n'existe pas de procédé qui décide. Savoir si une grammaire non contextuelle est ambiguë est un problème indécidable — au sens exact du chapitre chap:decidabilite : aucun programme ne répond correctement pour toutes les grammaires. C'est un contraste frappant avec le chapitre chap:automates, où l'on savait décider l'équivalence de deux automates par un simple parcours.

Ce que l'on fait donc en pratique : on construit des grammaires non ambiguës par des recettes sûres — un niveau par priorité, la récursivité du côté de l'associativité voulue —, et l'on teste par le décompte ci-dessus. On ne cherche pas à décider après coup.