compiler-constructiondangling-else

LL(1) grammar for dangling else


In compiler construction, one of the main ambiguity problems is dangling else. As mentioned in Compilers: Principles, Techniques, and Tools book by Aho, Lam, Sethi and Ullman, the grammar for the dangling else can't be used with LL(1) parsers.

Is it true that it can't be handled to be LL(1)?


Solution

  • Its true, it can't be parsed by LL(k) or by LALR(k) in their pure forms. The problem is that there are two possible interpretations of the dangling else; its an ambiguity problem ("else" belongs to nearest "if", or does not belong).

    It is usually cured by insisting on just one of the two interpretations, e.g., "else belongs to nearest if".

    Many parser generators can get this "right by accident"; the solution with LL is to accept the first parse that works and try "else attaches to closest" first. The solution with LR is "shift on else" which is easily caused, by simply checking for "shift" actions before "reduce" actions.

    It only gets to be a problem with a parser that will really pick up ambiguous parses, such as GLR. Here one can provide extra-grammatical hints, e.g, "shift on else".