|Ambiguity and LR(k) firstname.lastname@example.org (Leonardo Teixeira Passos) (2006-10-03)|
|Re: Ambiguity and LR(k) email@example.com (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) firstname.lastname@example.org (Wolfram Fenske) (2006-10-06)|
|From:||Sylvain Schmitz <email@example.com>|
|Date:||4 Oct 2006 11:08:45 -0400|
|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,
Return to the
Search the comp.compilers archives again.