Re: Ambiguity and LR(k)

Sylvain Schmitz <schmitz@i3s.unice.fr>
4 Oct 2006 11:08:45 -0400

          From comp.compilers
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)
| List of all articles for this month |
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.