Nepovinné else

Nepovinné else (anglicky dangling else) v podmíněném příkazu způsobuje, že mnoho programovacích jazyků je nejednoznačných. Formální příčinou je, že bezkontextová gramatika příslušného jazyka je nejednoznačná, což znamená, že pro některé programy existuje více než jeden správný derivační strom.

Příčina nejednoznačnosti

Mnoho programovacích jazyků dovoluje psát podmíněný příkaz dvěma způsoby: ve tvaru if-then a ve tvaru if-then-else:

if a then s
if a then s1 else s2

To znamená, že else část není povinná. Pokud je povoleno vnořovat příkazy, nepovinné else způsobuje nejednoznačnost interpretace následující konstrukce:

if a then if b then s else s2

V tomto případě je jednoznačné, že příkaz s se provede, pokud je pravdivé a i b, ale není jednoznačné, zda se má příkaz s2 provést, pokud je a nepravdivé (tedy else patří k prvnímu if), nebo pokud je a pravdivé a b nepravdivé (tedy else patří ke druhému if). Jinými slovy je otázkou, zda se má předchozí příkaz chápat jako

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

Problém nepovinného else se objevil v jazyce ALGOL 60,[1] a v následujících jazycích byl řešen různými způsoby. V LR analyzátorech je nepovinné else typickým příkladem konfliktu přesun-redukce (anglicky shift-reduce conflict).

Odstranění nejednoznačnosti beze změny syntaxe

Při konstrukci překladačů mnoha jazyků je nutné problém nejednoznačnosti nepovinného else vyřešit, zvláště při současném provádění lexikální a syntaktické analýzy. Obvykle se nepovinné else přiřazuje k nejbližšímu předchozímu if příkazu,[2], díky čemuž bude bezkontextová gramatika jazyka jednoznačná. Tento přístup používají programovací jazyky jako Pascal[3], C[4] a Java[5], takže jejich sémantika je v tomto bodě jednoznačná, přestože použití generátoru syntaktických analyzátorů může vést k nejednoznačné gramatice. Pokud je třeba dosáhnout jiného seskupení, lze explicitně použít bloky (složené příkazy), např. begin...end v jazyce Pascal[6] nebo {...} v jazyce C.

V závislosti na přístupu ke konstrukci překladače lze provést různé korekce, které zabraňují nejednoznačnosti:

  • Pokud je analyzátor vytvořený generátorem SLR, LR(1) nebo LALR syntaktických analyzátorů, programátor se často spoléhá na to, že generovaný analyzátor dává v případě konfliktu přednost přesunu před redukcí[2]. Jinou možností je přepsat gramatiku tak, aby se konflikt odstranil, na úkor zvětšení velikosti gramatiky (viz níže).
  • Pokud je analyzátor vytvořený prořezávacím generátorem (anglicky Pruning and Deep Pruning LR generator), je možné použít direktivy, které nejednoznačnosti zcela vyříznou.[7]
  • Pokud je analyzátor napsaný ručně, programátor může použít jednoznačnou bezkontextovou gramatiku, případně může použít jinou než bezkontextovou gramatiku nebo gramatiku pro analýzu výrazů.

Odstranění nejednoznačnosti změnou syntaxe

Problém nepovinného else lze řešit explicitním spojením else a if na syntaktické úrovni. Tím zpravidla zabraňuje lidským chybám.[8] Možná řešení jsou:

  • Zakázat, aby za „then“, mohl být příkaz „if“ (tento příkaz však může být uzavřen v příkazových závorkách). Tento přístup používá ALGOL 60[9] a Python[10].
  • Požadovat použití bloku, pokud „else“ následuje "if".[11]
  • Požadovat, aby každý "if" byl párován s „else“.

Příklady

Následují konkrétní příklady.

Jazyk C

Gramatika jazyka C obsahuje:

příkaz = ...
   | podmíněný-příkaz

podmíněný-příkaz = ...
   | IF ( výraz ) příkaz
   | IF ( výraz ) příkaz ELSE příkaz

Bez dalších pravidel je analýza příkazu

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

nejednoznačná; mohla by být chápána jako

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

nebo jako

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

V praxi se v jazyce C používá první interpratace, která přiřazuje else k nejbližšímu předcházejícímu if.

Odstranění konfliktu v LR analyzátorech

Výše uvedený příklad lze přepsat následujícím způsobem, aby se odstranila nejednoznačnost:

příkaz = ...
   | podmíněný-příkaz

příkaz-s-else = ...
   | podmíněný-příkaz-s-else

podmíněný-příkaz = ...
   | IF ( výraz ) příkaz
   | IF ( výraz ) příkaz-s-else ELSE příkaz

podmíněný-příkaz-s-else = ...
   | IF ( výraz ) příkaz-s-else ELSE příkaz-s-else

Podobně je třeba zdvojit všechna ostatní pravidla gramatiky týkající se příkazu, která přímo nebo nepřímo končí neterminálem příkaz nebo podmíněný-příkaz.

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Dangling else na anglické Wikipedii.

  1. A final solution to the Dangling else of ALGOL 60 and related languages [online]. Dostupné online. 
  2. a b 5.2 Shift/Reduce Conflicts z WWW serveru GNU Operating System
  3. ISO 7185:1990 (Pascal) 6.8.3.4: Za podmíněným příkazem if bez else části nesmí bezprostředně následovat slovo else.
  4. ISO 9899:1999 (C): 6.8.4.1(3): "Else patří k lexikálně nejbližšímu předchozímu if, které syntaxe povoluje.", dostupné na WG14 N1256, p. 134
  5. The Java Language Specification, Java SE 9 Edition, 14.5. Statements [online]. Dostupné online. 
  6. Pascal, Nell Dale a Chip Weems, "Dangling Else", p. 160–161
  7. http://www.mightyheave.com/blog/?p=17#more-17[nedostupný zdroj]
  8. Ambiguity of dangling else: non-context-free grammars are semantically opaque
  9. 4.5.1 Conditional Statements — Syntax v P. Nauer (ed.), Revised Report on the Algorithmic Language ALGOL 60, CACM 6,1, 1963 stránky 1-17
  10. Python Language Reference, 9. Full Grammar Specification
  11. Nejednoznačnost nepovinného else: vyžaduje složené závorky, když za if následuje else

Zdroj