Conference rusure::math

1954.0. "LR(k) grammar, k=2,3,..." by STOHUB::SLBLUZ::BROCKUS (I'm the NRA! and I VoteD!) Tue Mar 21 1995 12:42

( Cross-posted in LANGUAGES and MATH )

Anybody care to help me with my homework?

I'm taking a class for my Master's degree.  The class is CSc 433, Theory of
Compiling.

After reading Knuth's 1965 paper "Parsing Languages from Left to Right",
I've started a project to automate his method of testing a grammar to see
if is LR(k), for a specified k.

My universe is:

Nonterminals are capital letters.
Terminals are lower case letters and non-white-space printables.
Start symbol is S.
Productions are provided in a file, and are of form:

<nonterm> : <string>

where <string> is simply a string of symbols, and each production fits on
one line.

My program will read the grammar file and a value for k, and do the
transformations and tests as outlined in Knuth.

I am looking for test cases for higher values of k.  k=0 and k=1 are
simple, and examples are available in my textbooks.  Grammars which are not
LR(k) for any k are also available.

Could anyone provide me with a simple, perhaps minimal, LR(2),LR(3) or
LR(4) grammar?

Thank you very much.

JPB

How about something straightforward and dumb, like (for k > 0)

          k    k-1
  S ::= Ax | Bx   y
  A ::= x
  B ::= x

which should be LR(k) but not LR(k-1)?  The point is the parser must decide
whether to reduce the initial x to an A or a B, but it can't tell which without
looking ahead k tokens to see whether the last of them is x or y.