Conference turris::languages

388.0. "LR(k) grammars, k=2,3,..." by SLBLUZ::BROCKUS (I'm the NRA! and I VoteD!) Tue Mar 21 1995 12:27

( 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