Re: Grammar needed

Sylvain Schmitz <>
26 Oct 2006 00:29:34 -0400

          From comp.compilers

Related articles
Grammar needed (Leonardo Teixeira Passos) (2006-10-24)
Re: Grammar needed (Sylvain Schmitz) (2006-10-26)
Re: Grammar needed (Karsten Nyblad) (2006-10-26)
Re: Grammar needed (Pete Jinks) (2006-10-26)
Re: Grammar needed (Chris F Clark) (2006-10-26)
Re: Grammar needed (Leonardo Teixeira Passos) (2006-11-01)
| List of all articles for this month |

From: Sylvain Schmitz <>
Newsgroups: comp.compilers
Date: 26 Oct 2006 00:29:34 -0400
Organization: Compilers Central
References: 06-10-101
Keywords: parse, theory
Posted-Date: 26 Oct 2006 00:29:34 EDT
X-Virus-Scanned: amavisd-new at

Leonardo Teixeira Passos wrote:
> I've been trying to obtain a grammar that meets two properties:
> (i) It represents an LR(k) language
> (ii) The grammar it self isn't LR(k) for any k, for there is at least
> one conflict. One or more of these conflicts does not indicate
> ambiguity in the grammar, but can't be solved with any k.

You can consider for instance the grammar with rules

      S -> A a | B b
      A -> A c | c (G1)
      B -> B c | c

(i) The language generated by this grammar is a deterministic language
`c+(a|b)', since it is also generated by the LR(0) grammar G2 with rules

      S -> C a | C b (G2)
      C -> C c | c

Or if you want to keep the two parts separated, by the SLR(1) grammar G3
with rules

      S -> A a | B b
      A -> c A | c (G3)
      B -> c B | c

(ii) The grammar G1 is not LR(k) for any k but unambiguous: in order to
choose between the reduction of the first `c' to `A' or `B', the parser
needs the see the ending `a' or `b', which can be arbitrarily far away
after a sequence of `c's.

Hope that helps,


Post a followup to this message

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