27 Aug 1999 12:30:37 -0400

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

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.