Dangling autre - Dangling else

Le else pendant est un problème de programmation informatique dans lequel une clause else facultative dans une instruction if–then(–else) rend les conditions imbriquées ambiguës. Formellement, la grammaire sans contexte de référence du langage est ambiguë , ce qui signifie qu'il y a plus d'un arbre d'analyse correct .

Dans de nombreux langages de programmation, on peut écrire du code exécuté de manière conditionnelle sous deux formes : la forme if-then et la forme if-then-else – la clause else est facultative :

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, en particulier chaque fois qu'une forme if-then apparaît comme s1dans une forme if-then-else :

if a then if b then s else s2

Dans cet exemple, sest exécuté sans ambiguïté quand aest vrai et best vrai, mais on peut interpréter s2comme étant exécuté quand aest faux (en attachant ainsi le else au premier if) ou quand aest vrai et best faux (en attachant ainsi le else au second si ). En d'autres termes, on peut voir l'énoncé précédent comme l'une des expressions suivantes :

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

Le problème d'autre qui traîne remonte à ALGOL 60 et a été résolu de diverses manières dans les langues suivantes. Dans les analyseurs syntaxiques LR , l'autre pendant est l'exemple archétypal d'un conflit décalage-réduction .

Eviter l'ambiguïté tout en gardant la syntaxe

C'est un problème qui revient souvent dans la construction d'un compilateur , en particulier l' analyse sans analyseur . La convention lorsqu'il s'agit de l'autre pendant en suspens est d'attacher l'autre à l'instruction if voisine, permettant des grammaires sans contexte sans ambiguïté, en particulier. Les langages de programmation comme Pascal, C et Java suivent cette convention, il n'y a donc aucune ambiguïté dans la sémantique du langage , bien que l'utilisation d'un générateur d'analyseur puisse conduire à des grammaires ambiguës . Dans ces cas, le regroupement alternatif est accompli par des blocs explicites, comme begin...enden Pascal et {...}en C.

Selon l'approche de construction du compilateur, on peut prendre différentes mesures correctives pour éviter toute ambiguïté :

Si l'analyseur est produit par un générateur d' analyseur SLR, LR(1) ou LALR LR , le programmeur s'appuiera souvent sur la fonctionnalité d'analyseur généré en préférant Shift à Reduce en cas de conflit. Alternativement, la grammaire peut être réécrite pour supprimer le conflit, au prix d'une augmentation de la taille de la grammaire (voir ci - dessous ).
Si l'analyseur est écrit à la main, le programmeur peut utiliser une grammaire sans contexte non ambiguë . Alternativement, on peut s'appuyer sur une grammaire non contextuelle ou une grammaire d'expression d'analyse .

Éviter l'ambiguïté en changeant la syntaxe

Le problème peut également être résolu en rendant explicite le lien entre un else et son if, dans la syntaxe. Cela permet généralement d'éviter les erreurs humaines.

Les solutions possibles sont :

Avoir une déclaration "end if". Des exemples de tels langages sont ALGOL 68 , Ada , Eiffel , PL/SQL , Visual Basic et AppleScript .
Interdire à l'instruction qui suit un « alors » d'être elle-même un « si » (cela peut cependant être une paire de crochets d'instruction contenant uniquement une clause si-alors). Cette approche est suivie par ALGOL 60 .
Exiger des accolades (parenthèses) lorsqu'un "else" suit un "if".
Exiger que chaque « if » soit associé à un « else ». Pour éviter un problème similaire concernant la sémantique plutôt que la syntaxe, Racket s'écarte de Scheme en considérant une ifclause sans clause de secours comme une erreur, distinguant efficacement les expressions conditionnelles (ie if) des instructions conditionnelles (ie whenet unless, qui n'ont pas de clauses de secours).
Utilisation de mots-clés différents pour les instructions "if" à une alternative et à deux alternatives. S-algol utilise if e do spour le cas à une alternative et if e1 then e2 else e3pour le cas général.
Exiger des accolades inconditionnellement, comme Swift et Modula-2 . C'est effectivement vrai en Python car ses règles d'indentation délimitent chaque bloc, pas seulement ceux des instructions "if". Pour réduire l'encombrement résultant, Modula-2 supprime l'ouvre-bloc sur les niveaux non fonctionnels.

Exemples

Des exemples concrets suivent.

C

En C , la grammaire lit, en partie :

 statement = ...
    | selection-statement

 selection-statement = ...
    | IF ( expression ) statement
    | IF ( expression ) statement ELSE statement

Ainsi, sans autre règle, l'énoncé

if (a) if (b) s; else s2;

pourrait être analysé de manière ambiguë comme s'il s'agissait de :

if (a)
{
  if (b)
    s;
  else
    s2;
}

ou alors:

if (a)
{
  if (b)
    s;
}
else
  s2;

En pratique en C le premier arbre est choisi, en associant le elseau plus proche if.

Éviter le conflit dans les parseurs LR

L'exemple ci-dessus pourrait être réécrit de la manière suivante pour lever l'ambiguïté :

statement: open_statement
         | closed_statement
         ;

open_statement: IF '(' expression ')' statement
              | IF '(' expression ')' closed_statement ELSE open_statement
              ;

closed_statement: non_if_statement
                | IF '(' expression ')' closed_statement ELSE closed_statement
                ;

non_if_statement: ...
                ;

Toute autre règle de grammaire liée à l'instruction peut également devoir être dupliquée de cette manière si elle peut se terminer directement ou indirectement par un statementou un selection-statementnon-terminal.

Cependant, nous donnons une grammaire qui inclut à la fois les instructions if et while.

statement: open_statement
         | closed_statement
         ;

open_statement: IF '(' expression ')' statement
              | IF '(' expression ')' closed_statement ELSE open_statement
              | WHILE '(' expression ')' open_statement
              ;

closed_statement: simple_statement
                | IF '(' expression ')' closed_statement ELSE closed_statement
                | WHILE '(' expression ')' closed_statement
                ;

simple_statement: ...
                ;

Enfin, nous donnons la grammaire qui interdit les instructions IF ambiguës.

statement: open_statement
         | closed_statement
         ;

open_statement: IF '(' expression ')' simple_statement
              | IF '(' expression ')' open_statement
              | IF '(' expression ')' closed_statement ELSE open_statement
              | WHILE '(' expression ')' open_statement
              ;

closed_statement: simple_statement
                | IF '(' expression ')' closed_statement ELSE closed_statement
                | WHILE '(' expression ')' closed_statement
                ;

simple_statement: ...
                ;

Avec cette grammaire, l'analyse de "if (a) if (b) c else d" échoue :

statement
open_statement
IF '(' expression ')' closed_statement ELSE open_statement
'if' '(' 'a' ')' closed_statement 'else' 'd'

puis l'analyse échoue en essayant de correspondre closed_statementà "if (b) c". Une tentative avec closed_statementéchoue de la même manière.

Voir également

Le piratage lexer

Languages

In other projects