Re: Grammar needed

Chris F Clark <>
26 Oct 2006 00:31:56 -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: Chris F Clark <>
Newsgroups: comp.compilers
Date: 26 Oct 2006 00:31:56 -0400
Organization: The World Public Access UNIX, Brookline, MA
References: 06-10-101
Keywords: parse, theory
Posted-Date: 26 Oct 2006 00:31:56 EDT

Leonardo Teixeira Passos <> writes:

> Hi there.
> 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.
> Condition (i) is relatively easy to achieve. However, I can't put (ii) to
> work with (i).
> Any suggestions?

Does this grammar meet your needs?

goal : nt1 | nt2;

nt1: cfl1 "b";

nt2: cfl2 "c";

cfl1 : "a" | "a" cfl1;

cfl2 : "a" | "a" cfl2;

It describes the language a+b | a+c which is LR(1), and is not
ambiguous--each string has one unique parse. However, you cannot
distinguish wether to reduce the a+ sequence as non-terminal cfl1 or
cfl2 until seeing the final b or c terminal, which can be arbitrarily
far away--thus the grammar is not LR(k) for any k.

We used grammars like this to test Yacc++'s advanced lookahead modes
when we were first trying to make it LR(infinity), back in 1989 or so.
It's easy to construct an algorithm that handles cases like this.
Think of taking a limit (or closure). However, one eventually runs
into the wall that proving a context free grammar is unambiguous is
equivalent to solving the halting problem. Thus, when you have a
closure computing parser generator, there must be some context free
grammars it doesn't resolve, or some grammars it loops on. My
suspicion is that the algorithm we use will loop, but I could never
find a small test case that was comprehensible and also showed the
algorithm looping.

Hope this helps,

Chris Clark Internet :
Compiler Resources, Inc. Web Site :
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)

Post a followup to this message

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