Roikkuva else

(Alun perin kurssin TIEA241 Automaatit ja kieliopit syksy 2017 materiaaleista.)

Klassinen ongelma ohjelmointikielten kääntäjien tekniikassa on ns. roikkuva else (engl. dangling else). Tarkastellaan seuraavaa BNF-fragmenttia:

<statement> ::=
  print <expression> ;
| { <statement-list> }
| if ( <expression> ) <statement>
| if ( <expression> ) <statement> else <statement>

<statement-list> ::=
  <empty>
| <statement-list> <statement>

<empty> ::=

Tästä on mahdollista johtaa kaksi eri jäsennyspuuta merkkijonolle if (a) if (b) print 1; else print 2;, ja nämä kaksi eri jäsennyspuuta johtavat ohjelman erilaiseen käyttäytymiseen, kun a on epätosi (toinen tulostaa 2 ja toinen ei mitään). Tapana on tulkita, että else paritetaan aina lähimpään vapaaseen if-lauseeseen, jolloin oikea tulostus on tyhjä; tämä saadaan aikaiseksi esimerkiksi seuraavalla kielioppifragmentilla:

<statement> ::=
  <matched-statement>
| <open-statement>

<matched-statement> ::=
  print <expression> ;
| { <statement-list> }
| if ( <expression> ) <matched-statement> else <matched-statement>

<open-statement> ::=
  if ( <expression> ) <statement>
| if ( <expression> ) <matched-statement> else <open-statement>