Re: Grammar needed

Leonardo Teixeira Passos <leonardo@dcc.ufmg.br> 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


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)
------------------------------------------------------------------------------

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