4 Oct 2006 11:08:45 -0400

Related articles |
---|

Ambiguity and LR(k) leonardo@dcc.ufmg.br (Leonardo Teixeira Passos) (2006-10-03) |

Re: Ambiguity and LR(k) schmitz@i3s.unice.fr (Sylvain Schmitz) (2006-10-04) |

Re: Ambiguity and LR(k) debray@CS.Arizona.EDU (Saumya K. Debray) (2006-10-04) |

Re: Ambiguity and LR(k) int2k@gmx.net (Wolfram Fenske) (2006-10-06) |

From: | Sylvain Schmitz <schmitz@i3s.unice.fr> |

Newsgroups: | comp.compilers |

Date: | 4 Oct 2006 11:08:45 -0400 |

Organization: | Compilers Central |

References: | 06-10-013 |

Keywords: | LR(1), parse, theory |

Posted-Date: | 04 Oct 2006 11:08:45 EDT |

Leonardo Teixeira Passos wrote:

*> I would like to know if a grammar is ambiguous then there isn't a*

*> LR(k) syntax analyser that can be generated from it.*

Yes, this is true. You can find proofs of this for instance in Geller

and Harrison, _On LR(k) Grammars and Languages_, TCS 4:245--276, 1977,

or in most theory-oriented textbooks on parsing.

Intuitively, you cannot generate a deterministic parser for an ambiguous

grammar: if each parsing action done by the parser is chosen

deterministically, then there is a unique way to recognize the entire

input string, and the grammar is not ambiguous.

*> Is the other way of thinking also true, i.e., if there isn't a k*

*> such that a LR(k) syntax analyser can be automatically generated*

*> from a grammar G, then G is definitely ambiguous?*

*> [As I recall, there are plenty of grammars that are unambiguous but cannot*

*> be parsed by any technique that uses fixed lookahead. -John]*

There are. Counter examples in programming languages include for

instance the "modifiers conflict" of Java

<http://java.sun.com/docs/books/jls/first_edition/html/19.doc.html#44488>.

--

Hope that helps,

Sylvain

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.