David Madore's WebLog: Méditations sur le problème du dangling else

Un problème célèbre dans la syntaxe de langages de programmations informatiques est celui du dangling else : il concerne des langages qui admettent la syntaxe if … then … et aussi if … then … else … pour les instructions conditionnelles (ça n'a pas besoin d'être exactement les mots if, then et else, bien sûr, par exemple le C n'a pas de then du tout, et en fait la partie entre if et then n'a pas d'importance dans l'histoire) ; le problème est que comme le else est optionnel, on ne peut pas toujours décider à quel then il se rapporte. Le problème a été découvert dans Algol 60 dont la syntaxe publiée était ambiguë sans préciser la manière dont il fallait lever l'ambiguïté.

Pour illustrer de quoi il s'agit, je peux considérer la grammaire suivante (extrêmement simplifiée pour illustrer ce dont je veux parler, bien sûr) :

Instruction → foo | bar | qux | Conditional | begin InstrList end

InstrList → Instruction | Instruction InstrList

Conditional → if Expression then Instruction else Instruction
| if Expression then Instruction

Expression → true | false | happy | trippy | xyzzy

(Digression : Le terme standard est Statement là où j'ai écrit Instruction, mais je trouve que c'est une impropriété : un statement, en anglais, est une affirmation et pas une commande, donc cela ne colle pas pour un langage impératif.)

L'exemple le plus simple d'ambiguïté est : if happy then if trippy then foo else bar, qui peut se comprendre soit (1) en rapportant le else au then le plus proche, ce que je peux suggérer en indentant le programme comme

if happy
then if trippy
     then foo
     else bar

soit (2) en rapportant le else au then le plus lointain, ce qui donnerait l'indentation suivante :

if happy
then if trippy
     then foo
else bar

On peut lever l'ambiguïté au niveau du programme (i.e., sans faire d'hypothèse sur la manière dont le langage interprétera le programme ci-dessus) en ajoutant des begin … end explicites, c'est-à-dire en écrivant soit (1) if happy then begin if trippy then foo else bar end, qui s'analyse forcément comme

if happy
then begin if trippy
           then foo
           else bar
     end

soit (2) if happy then begin if trippy then foo end else bar, qui s'analyse forcément comme

if happy
then begin if trippy
           then foo
     end
else bar

(Pour la suite, on peut complètement oublier cette histoire de begin … else, qui ne servait qu'à illustrer la possibilité ci-dessus.)

Mais on peut aussi vouloir lever l'ambiguïté en précisant la syntaxe du langage. Une approche possible consiste bien sûr à changer cette syntaxe en exigeant, par exemple, d'utiliser un mot-clé comme fi ou endif pour terminer les conditionnelles ; ou bien d'utiliser l'indentation comme le fait Python. Mais je me préoccupe ici de changements de grammaire qui ne modifient pas le langage reconnu (i.e., tout programme admis par ma syntaxe initiale doit rester valide et réciproquement).

Le C, le Java et quantité d'autres langages qui souffrent potentiellement du problème du dangling else (tous ?) utilisent la résolution (1) consistant à apparier chaque else avec le then le plus proche qui soit syntaxiquement possible. Ceci peut s'obtenir en modifiant la grammaire de la façon suivante :

Instruction → foo | bar | qux | Conditional | begin InstrList end

InstrNoSC → foo | bar | qux | CondNoSC | begin InstrList end

Conditional → if Expression then InstrNoSC else Instruction
| if Expression then Instruction

CondNoSC → if Expression then InstrNoSC else InstrNoSC

(Lire NoSC comme no short conditional ; les autres productions ne changent pas et n'ont pas d'importance ici.) L'idée est que la partie entre le then et le else d'une conditionnelle doit comporter des else à tous les niveaux (récursivement). Cette grammaire est inambiguë, même si je ne connais pas de façon simple de s'en convaincre autrement que d'en construire un analyseur (cf. aussi ici) ; par ailleurs, elle accepte les mêmes programmes que la précédente (là non plus, je ne connais pas de manière de le prouver qui ne soit pas passablement douloureuse).

Pas de mystère particulier ici. Seulement, mon obsession pour la symétrie fait que je voudrais beaucoup qu'il y eût une façon, symétriquement, de forcer la syntaxe à (2) apparier le else avec le then le plus lointain possible. Le problème, comme on va le voir, est que ce n'est pas super bien défini.

Naïvement, je me suis dit que je pouvais faire ça de manière symétrique de la précédente : au lieu de forcer la partie entre le then et le else d'une conditionnelle (complète) doit comporter des else à tous les niveaux, je vais forcer la partie qui suit le then d'une conditionnelle courte à ne comporter aucun else (i.e., que des conditionnelles courtes). Autrement dit, j'ai tenté la grammaire suivante (lire NoFC comme no full conditional) :

Instruction → foo | bar | qux | Conditional | begin InstrList end

InstrNoFC → foo | bar | qux | CondNoFC | begin InstrList end

Conditional → if Expression then Instruction else Instruction
| if Expression then InstrNoFC

CondNoFC → if Expression then InstrNoFC

Malheureusement, et de façon peut-être surprenante, cette grammaire est toujours ambiguë (je crois par ailleurs qu'elle définit le même langage que les précédentes). Voici un exemple d'ambiguïté : le programme if happy then if trippy then foo else if xyzzy then bar else qux peut s'analyser comme

if happy
then if trippy
     then foo
else if xyzzy
     then bar
     else qux

ou bien comme

if happy
then if trippy
     then foo
     else if xyzzy
          then bar
else qux

Dans les deux analyses, il est vrai que la partie qui suit le then d'une conditionnelle courte ne comporte aucun else, mais cette contrainte ne suffit manifestement pas à lever les ambiguïtés (bien sûr, le même programme avait encore plus de lectures possibles selon la grammaire initiale, donc l'ambiguïté a été réduite, et mon premier exemple de programme ambigu ne l'est plus ; mais elle n'a pas été complètement levée).

Je me pose donc la question, à laquelle je n'ai pas de réponse : y a-t-il un autre moyen systématique que (1) rapporter chaque else au then le plus proche, pour lever l'ambiguïté du dangling else ? Si possible quelque chose qui soit aussi contraire de (1) que possible ? (Mais je ne sais pas quelle lecture il faudrait donner au programme ambigu suggéré ci-dessus.)

Pour rendre les notations plus concises et formaliser le problème de façon plus condensée, je peux remplacer if Expression then par juste a, et else par juste b, et tout autre type d'Instruction par c, et éviter des règles multiples inutiles, ce qui fait que la grammaire d'origine (ambiguë) devient tout simplement

S → aSbS | aS | c

(Le mot aacbc peut s'analyser comme (a(acbc)) ou bien comme (a(ac)bc). C'est la traduction dans ces nouvelles notations de mon premier exemple.)

La désambiguïfication (1) (apparier chaque b avec le a le plus proche) est donnée par

S → aTbS | aS | c

T → aTbT | c

— elle est bien inambiguë et engendre le même langage que la précédente. La tentative de désambiguïfication (2) était

S → aSbS | aU | c

U → aU | c

— elle engendre bien le même langage (je crois), mais elle est toujours ambiguë car aacbacbc peut s'analyser comme (a(ac)b(acbc)) ou bien comme (a(acb(ac))bc) (c'est la traduction dans les nouvelles notations de l'exemple donné antérieurement).

Donc si je dois rendre ma question extrêmement formelle, ce sera : existe-t-il une grammaire hors contexte (i) inambiguë, (ii) qui engendre le même langage que les trois que je viens de citer, et (iii) qui analyse le mot aaa⋯aaacbcbc⋯bcbc (avec au moins autant de a que de b) en appariant le k-ième b compté à partir de la fin avec le k-ième a compté à partir du début (apparier voulant dire qu'ils sont produits en même temps par une règle de la grammaire). Peut-être que je peux d'ailleurs demander (iii′) que la grammaire analyse tout mot qui soit inambigu pour la dernière grammaire écrite ci-dessus de la même manière que celle-ci (c'est au moins aussi fort que (iii)), voire (iii″) qu'elle analyse tout mot du langage selon une manière possible pour la dernière grammaire écrite ci-dessus.

Il peut être opportun de rappeler à tout hasard que la grammaire de seule règle X → aXbX | c est inambiguë (elle définit exactement [rectifié] les expressions bien-parenthésées en a et cb suivies par un c terminal).

J'ai posé la question sur cs.stackexchange.com mais je n'ai pour l'instant pas eu de réponse correcte (mais au moins quelqu'un semble avoir compris la question, ce qui est déjà pas mal !, et y avoir un peu réfléchi, avec pas plus de succès que moi).

Je reconnais franchement que la difficulté est sans doute que je ne sais pas exactement ce que je veux à part une solution aussi éloignée de (1) que possible, et c'est pour ça que j'ai formalisé la question ci-dessus de manière un petit peu tarabiscotée.

(Je suis de plus en plus convaincu qu'il n'existe pas de solution à mon problème, mais du coup, j'aimerais en voir une preuve.)

Mise à jour (2017-01-18T01:00+01:00) : En fait, si ! Il semblerait que quelqu'un ait trouvé une solution. Il faut encore que je la relise et que je la comprenne, mais expérimentalement, elle fonctionne (au moins au sens où elle vérifie les conditions (i), (ii) et (iii)).

Voici en tout cas le genre de lacune scientifique qui m'agace : le problème du dangling else est archi-célèbre et évoqué à un nombre faramineux d'endroits. Ces endroits évoquent la solution adoptée par des langages comme le C et le Java pour lever l'ambiguïté, à savoir (1) rapporter chaque else au then le plus proche. Mais il faudrait quand même répondre à la question évidente : est-ce que c'était essentiellement la seule approche systématique possible ? Ou au moins la seule approche systématique possible pour une grammaire hors contexte ? Y avait-il une approche (2) diamétralement opposée, qui est ce que je cherche ? Comment la définir ? Que peut-on en dire ? Pourquoi tant de haine ? Ne serait-ce que dire que l'approche (2) n'est pas bien définie de façon évidente (ça n'a pas de sens évident de chercher à apparier chaque else au then le plus lointain qui soit syntaxiquement possible), c'est le genre de commentaires qu'on attend lorsqu'il est affirmé que le C et le Java utilisent l'approche (1).