Re: Examples of LR(k) grammars (k > 1) sought

Ziemowit Laski wrote:
> I was wondering if anyone could point me to actual examples of
> grammars that are LR(k) but _not_ LALR(k), for k > 1, and/or to an
> algorithm for generating such grammars.


The usual example of an LR(1) grammar which is not LALR is:


S -> aAa | bAb | aBb | bBa
A -> c
B -> c


The LR(0) state reached when reading "ac" or "bc" allows both the
reductions of "c" to "A" and to "B". The lookahead possible for each
reduction contains "a" and "b", for the LR(0) state merge has lost the
information of which token---"a" or "b"---has been read first.
Increasing the value of k will not change anything.


If you also need your grammar to be non-LR(1), just put the end context
further as in:
S -> aADa | bADb | aBDb | bBDa
A -> c
B -> c
D -> d^{k-1}


If you were looking for more real life examples, I remember there is one
in the bison manual [http://www.gnu.org/software/bison/manual], which
you can probably adapt in order to have k > 1.


--
Hope that helps,


      Sylvain

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