Re: Ambiguity and LR(k)

Sylvain Schmitz <>
4 Oct 2006 11:08:45 -0400

          From comp.compilers

Related articles
Ambiguity and LR(k) (Leonardo Teixeira Passos) (2006-10-03)
Re: Ambiguity and LR(k) (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) (Wolfram Fenske) (2006-10-06)
| List of all articles for this month |

From: Sylvain Schmitz <>
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

Hope that helps,


Post a followup to this message

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