Dangling else

En informatique, et notamment dans la conception et l'analyse des langages de programmation, le problème du dangling else (anglais que l'on pourrait traduire par le problème du « sinon pendant ») est un problème de programmation informatique qui résulte de l'ambiguïté de l'interprétation de la clause sinon dans l'imbrication de deux instructions conditionnelles de la forme si-alors-sinon. Formellement, la grammaire non contextuelle du langage est ambiguë, ce qui signifie qu'il peut y avoir plusieurs arbres d'analyse corrects pour une même instruction.

Le « dangling else »

Dans de nombreux langages de programmation, on peut écrire une instruction conditionnelle sous deux formes : la forme si-alors  et la forme si-alors-sinon. En d'autres termes, la clause sinon est facultative, et les deux constructions suivantes sont valides :

if a then s
if b then s1 else s2

Cela donne lieu à une ambiguïté d'interprétation lorsqu'il y a des instructions imbriquées, plus précisément à chaque fois qu'un si-alors apparaît à la place du s1 dans une autre instruction si-alors-sinon, soit dans la situation que voici :

if a then if b then s else s2

Dans cet exemple, l'instruction exécutée est sans ambiguïté s lorsque a et b sont vrai ; mais on peut considérer que s2 doit être exécutée lorsque a est faux (et donc rattacher le else au premier if), ou lorsque a est vrai et b est faux (et donc rattacher le else au deuxième if). En d'autres termes, on peut voir l'instruction précédente comme l'une des expressions suivantes :

if a then (if b then s) else s2
      ou
if a then (if b then s else s2)

Un compilateur doit analyser correctement l'instruction, et choisir entre les deux interprétations selon le concepteur du langage de programmation. Le problème du dangling else date d'ALGOL 60[1], et a été résolu de diverses manières dans les langages qui ont suivi. Dans les analyseurs LR, le dangling else est l'exemple typique d'un conflit shift-reduce[2].

Exemples

En langage C

  if (a == 1)
    if (b == 1)
      a = 42;
  else
    b = 42;

Dans cet exemple, un programmeur pourrait s'attendre à ce que la variable b prenne la valeur 42 quand a ≠ 1. Le compilateur Compiler rattache le else au deuxième if et ne fait pas l'affection. Si l'on veut que b prenne la valeur 42 quand a≠ 1, l'instruction if interne doit être mise entre accolades :

  if (a == 1)
  {
    if(b == 1)
      a = 42;
  }
  else
    b = 42;

Autres langages

Dans certains langages, le problème est résolu en associant obligatoirement une parenthèse fermante à chaque if. Par exemple, dans le langage de script Shell de Bourne, c'est un fi qui représente la parenthèse fermante ; le morceau de programme s'écrit alors :

if [ $a -eq 1 ] ; then
  if [ $b -eq 1 ] ; then
    a=42
  fi
else
  b=42
fi

D'autres langages de programmation, comme par exemple Python, résolvent le problème par indentation :

if a == 1:
    if b == 1:
        a = 42
else:
    b = 42

En Ada le problème n'apparaît pas à cause d'un parenthésage syntaxique inambigu, où chaque IF est fermé par un ENDIF :

IF a = 1 THEN
    IF b = 1 THEN
        a := 42;
    END IF;
ELSE
     b := 42;
END IF;

D'autres langages, comme Pascal, adoptent comme C le rattachement du else au dernier if.

Notes et références

1. P. W. Abrahams, « A final solution to the Dangling else of ALGOL 60 and related languages », Communications of the ACM, vol. 9, n^o 9,‎ 1966, p. 679 (DOI 10.1145/365813.365821)
2. Section 5.2 Shift/Reduce Conflicts sur le site du système GNU.