Re: ambiguity of grammar and LR(k)

sol!ikastan@agate-ether.berkeley.edu (Ilias Kastanas)
2 Nov 1999 00:39:30 -0500

          From comp.compilers
Related articles
[7 earlier articles]
Re: ambiguity of grammar and LR(k) Xavier.Nicollin@imag.fr (Xavier Nicollin) (1999-10-31)
Re: ambiguity of grammar and LR(k) Xavier.Nicollin@imag.fr (Xavier Nicollin) (1999-10-31)
Re: ambiguity of grammar and LR(k) henning@makholm.net (Henning Makholm) (1999-10-31)
Re: ambiguity of grammar and LR(k) henning@makholm.net (Henning Makholm) (1999-10-31)
Re: ambiguity of grammar and LR(k) uranus!ikastan@uunet.uu.net (1999-10-31)
Re: ambiguity of grammar and LR(k) linlist@fudan.edu (Linlist Leo) (1999-10-31)
Re: ambiguity of grammar and LR(k) sol!ikastan@agate-ether.berkeley.edu (1999-11-02)
| List of all articles for this month |
From: sol!ikastan@agate-ether.berkeley.edu (Ilias Kastanas)
Newsgroups: comp.theory,comp.compilers
Date: 2 Nov 1999 00:39:30 -0500
Organization: CSUnet
Distribution: inet
References: 99-10-130 99-10-158 99-10-188 99-10-195
Keywords: parse, theory

@> Yes, L = palindromes over {0,1}. The obvious grammar for L is
@> unambiguous; but L isn't LR(k) for any k, because L is not a deter-
@> ministic CFL.


Linlist Leo <linlist@fudan.edu> wrote:
@thanks a lot. that directly addressed my question. though there may
@be a little amendment -- nondeterminism doesn't imply non-lr(k). It
@just imply the language is not LR(1).


Which is the same thing. There are grammars that are LR(k+1)
but not LR(k) (k >= 1); there aren't any languages, though. If a
language has an LR(k) grammar, it also has an LR(1) grammar.


Ilias

Post a followup to this message

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