Re: If_then_else and LL(1) grammars

Torben Mogensen <torbenm@diku.dk>
27 Aug 1999 12:30:37 -0400

          From comp.compilers

Related articles
If_then_else and LL(1) grammars zzlrathb@fox.uq.net.au (Lance Rathbone) (1999-08-27)
Re: If_then_else and LL(1) grammars torbenm@diku.dk (Torben Mogensen) (1999-08-27)
| List of all articles for this month |

From: Torben Mogensen <torbenm@diku.dk>
Newsgroups: comp.compilers
Date: 27 Aug 1999 12:30:37 -0400
Organization: Compilers Central
References: 99-08-098
Keywords: parse, LL(1)

>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)


Post a followup to this message

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