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

Ziemowit Laski wrote:
> Hello,
>
> 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.
>
> Thanks in advance,
>
> --Zem


S -> a A c a
S -> b A c b
S -> a B c b
S -> b B c a


A -> a


B -> a


Upper and lower case letters are non terminals and terminals,
respectively. The egrammar is LR(2) but not LALR(2). You can
substitute k-1 c's for c in the grammar above to get a gammar that is
LR(k) but not LALR(k).


The attached grammar is a bit more fun. It can be handled by a parser
generator, that can handle LR(6) grammars when splitting states, but
calculates 7 tokens of look ahead. (I am writng a parser generator,
that can handle LR(K) grammars through state splitting.) Please note
that "PRECEDENCE x" is not a part of the productions. It is a
specification that the parser generator should use LR(6) state splitting
and 7 tokens of lookahead.


Karsten Nyblad
148f3wg02 at sneakemail.com


TERMINALS a, b, c, d, e, f ;


NONTERMINALS A, B, C, D, E, F, V, W, X, Y, Z ;


PRECEDENCE
                  LR(6) a, x;


PRECEDENCE
                  LALR(7) a, x;


STARTSYMBOL V ;


PRODUCTIONS
                  V -> W a;
                  V -> a W b;
                  V -> a a W c;
                  V -> a a a W d;
                  V -> a a a a W e;
                  V -> a a a a a W f;


                  W -> X a;
                  W -> a X b;
                  W -> a a X c;
                  W -> a a a X d;
                  W -> a a a a X e;
                  W -> a a a a a X f;


                  X -> Y a;
                  X -> a Y b;
                  X -> a a Y c;
                  X -> a a a Y d;
                  X -> a a a a Y e;
                  X -> a a a a a Y f;


                  Y -> Z a;
                  Y -> a Z b;
                  Y -> a a Z c;
                  Y -> a a a Z d;
                  Y -> a a a a Z e;
                  Y -> a a a a a Z f;


                  Z -> A a;
                  Z -> a A b;
                  Z -> a a A c;
                  Z -> a a a A d;
                  Z -> a a a a A e;
                  Z -> a a a a a A f;


                  A -> B a b PRECEDENCE x;
                  A -> C a c PRECEDENCE x;
                  A -> D a d PRECEDENCE x;
                  A -> E a e PRECEDENCE x;
                  A -> F a f PRECEDENCE x;


                  A -> a B a f PRECEDENCE x;
                  A -> a C a b PRECEDENCE x;
                  A -> a D a c PRECEDENCE x;
                  A -> a E a d PRECEDENCE x;
                  A -> a F a e PRECEDENCE x;


                  A -> a a B a e PRECEDENCE x;
                  A -> a a C a f PRECEDENCE x;
                  A -> a a D a b PRECEDENCE x;
                  A -> a a E a c PRECEDENCE x;
                  A -> a a F a d PRECEDENCE x;


                  A -> a a a B a d PRECEDENCE x;
                  A -> a a a C a e PRECEDENCE x;
                  A -> a a a D a f PRECEDENCE x;
                  A -> a a a E a b PRECEDENCE x;
                  A -> a a a F a c PRECEDENCE x;


                  A -> a a a a B a c PRECEDENCE x;
                  A -> a a a a C a d PRECEDENCE x;
                  A -> a a a a D a e PRECEDENCE x;
                  A -> a a a a E a f PRECEDENCE x;
                  A -> a a a a F a b PRECEDENCE x;


                  B -> a a a a a C PRECEDENCE x;
                  B -> a a a a a PRECEDENCE x;


                  C -> a a a a a D PRECEDENCE x;
                  C -> a a a a a PRECEDENCE x;


                  D -> a a a a a E PRECEDENCE x;
                  D -> a a a a a PRECEDENCE x;


                  E -> a a a a a F PRECEDENCE x;
                  E -> a a a a a PRECEDENCE x;


                  F -> a a a a a B PRECEDENCE x;
                  F -> a a a a a PRECEDENCE x;

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