Re: Grammar needed

On Thu, 26 Oct 2006, Chris F Clark wrote:


> 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;
>


I've tried your grammar, but it happens that it is a genuine LALR(1)
grammar, and thus LR(1).


This can be seen when the closure operation is executed in the
generation of the 1st LR(0) state:


goal ::= (*)nt1
goal ::= (*)nt2
nt1 ::= (*) cfl1 "b"
nt2 ::= (*) cfl2 "c"
cfl1 ::= (*) "a"
cfl1 ::= (*) cfl1 "a"
cfl2 ::= (*) "a"
cfl2 ::= (*) cfl2 "a"


As can be infered from that, in the LALR(1) machine cfl1 and cfl2 will be
reduced in the presence of "b" and "c" respectively, causing no conflicts.


However, based on your example, I've wrote a non LALR(k) grammar that
meets conditions (i) and (ii):


s ::= a | b ;
a ::= b1 A ;
b ::= b2 B ;
b1 ::= B b1 | B ;
b2 ::= B b2 | B ;


That suits my needs, although I haven't checked if it is a non LR(k)
grammar - a non LALR(k) was ok for me :)


Thanks for your help and patience.


> 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.

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