Ambiguity and LR(k)

Leonardo Teixeira Passos <leonardo@dcc.ufmg.br>
3 Oct 2006 18:20:26 -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: Leonardo Teixeira Passos <leonardo@dcc.ufmg.br>
Newsgroups: comp.compilers
Date: 3 Oct 2006 18:20:26 -0400
Organization: POP-MG/RNP
Keywords: LR(1), parse, theory
Posted-Date: 03 Oct 2006 18:20:26 EDT

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. 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 definitly ambiguous?


Are there any hints or proofs for the given staments?


It seems to me that if a grammar is ambiguous, then there isn't a
LR(k) syntax analyser that can be generated for it. However, I cannot
prove or disprove this.
[As I recall, there are plenty of grammars that are unambiguous but cannot
be parsed by any technique that uses fixed lookahead. -John]


Post a followup to this message

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