Re: If_then_else and LL(1) grammars

>In the Dragon book p 175, we are given a revised grammar to resolve
>the dangling else problem. But can this set of productions be
>transformed to make them suitable for an LL(1) grammar - if so how?


No. The two productions for unmatched_stmt share an unbounded common
prefix. Even if left-factored, we end up with two productions, one
starting with stmt and the other with matched_stmt, which share FIRST
sets. No amount of left-factoring will change this. The typical
solution for LL(1) is to use the ambiguous grammar and resolve the
conflict in the generated table as shown on page 191 of the Dragon
book.


The grammar will, however, pass through a LR parser generator without
generating conflicts. But even here it is more common to use the
ambiguous grammar and eliminate conflicts afterwards. LR parser
generators typically have support for this by using operator
precedence declarations.


Torben Mogensen (torbenm@diku.dk)

Return to the comp.compilers page.
Search the comp.compilers archives again.