Le sinon pendant, et sa réparation

1. Le plus court mot ambigu est ssaea, soit si si a sinon a. Il a exactement deux arbres :

• le sinon se rattache au second si : $I\to \text{s}I$ avec $I\to \text{s}I\text{e}I$ à l'intérieur ;
• le sinon se rattache au premier : $I\to \text{s}I\text{e}I$ avec $I\to \text{s}I$ à l'intérieur.

Les deux lectures ne diffèrent pas seulement sur le papier : dans le premier cas, l'instruction du sinon s'exécute quand la première condition est vraie et la seconde fausse ; dans le second, quand la première est fausse. Un décompte par programmation dynamique donne $2$ arbres pour ssaea, $3$ pour sssaeaea — le nombre croît avec l'imbrication.

2. La réparation. On distingue les instructions appariées — dont tout si a son sinon — des autres :

$$\begin{array}{lcl}I& \to & F\mid O\\ F& \to & \text{s}F\text{e}F\mid \text{a}\text{(apparieˊe : toujours un sinon)}\\ O& \to & \text{s}I\mid \text{s}F\text{e}O\text{(ouverte : un si sans sinon quelque part)}\end{array}$$

La clé est la règle $O\to \text{s}F\text{e}O$ : entre un si et son sinon, on n'autorise qu'une instruction appariée. Un sinon ne peut donc jamais « sauter » par-dessus un si ouvert : il se rattache forcément au plus proche.

Vérifications. Les deux grammaires engendrent le même langage : les $30$ mots de longueur au plus $8$ coïncident. La seconde n'est ambiguë sur aucun mot de longueur au plus $9$, et ssaea n'y a plus qu'un arbre.

Ce que font les vrais langages. Trois attitudes, et toutes se rencontrent :

• garder la grammaire ambiguë et ajouter une règle hors grammaire — « le sinon se rattache au si le plus proche » : c'est le choix de C et de Java ;
• remanier la grammaire comme ci-dessus ;
• rendre le marqueur de fin obligatoire (fi, end, accolades) : l'ambiguïté disparaît alors par construction, sans qu'aucune règle extérieure ne soit nécessaire. C'est le choix d'Algol 68 et de Python.

Le troisième est le seul où l'on n'a rien à retenir.