Examples of LL(1), LR(1), LR(0), LALR(1) grammars?

Question

Is there a good resource online with a collection of grammars for some of the major parsing algorithms (LL(1), LR(1), LR(0), LALR(1))? I've found many individual grammars that fall into these families, but I know of no good resource where someone has written up a large set of example grammars.

Does anyone know of such a resource?

Solution 1

Parsing Techniques - A Practical Guide has several examples (i.e. probably half a dozen or so per type) of almost every type of grammar. You can purchase the 2nd edition book, although the 1st edition is available for free on the author's website in PDF form (near bottom of link).

The author also has some test grammars that he bundles with his code examples from the second edition, which can be found here.

Note: all of these grammars are small (less than a couple dozen rules), because of this obviously being a published book.

Solution 2

Examples from wikipedia

LL(1)

grammar

S -> F
S -> ( S + F )
F -> a

input

( a + a )

parsing steps

S -> "(" S "+" F ")"
  -> ( "F" + F ) 
  -> ( "a" + F ) 
  -> ( a + "a" )       

LR(0)

grammar

(1) E → E * B
(2) E → E + B
(3) E → B
(4) B → 0
(5) B → 1 

input

1 + 1

parsing steps

need to build a parser table and traverse through states.

LR(1)

grammar

S’ -> S S 
S  -> C C 
C  -> c C | d

input

cd

parsing steps

large table

LALR

grammar

A -> C x A | ε
B -> x C y | x C
C -> x B x | z

input

xxzxx

parsing steps

traverse large parser table

You may also want to have a look at

• Parsing Simulator tool
• antlr works - >download<
• Parser table generation from ocw mit
• From parsing to code genration ocw mit
• additional examples

Solution 3

I would not expect you to find a large collections of grammars organized that way on purpose. What would the organizer gain in return?

What you might have a chance of doing, is to find parser generators that correspond to each family (e.g., LL(1)), and go look for instances of inputs for that parser generator, all of which will be LL(1) by definition. For instance, ANTLR's grammars are all various versions of LL(k) depending on which version of ANTLR you pick (the description of the ANTLR version will tell what k it accepts); Bison grammars are all LALR(1) [ignoring the recent GLR option]. If you go to my website (see bio), you see a list of grammars that are all pretty much context-free (that is, not in any of the classes you describe).

EDIT: Note @Bart Kier's clarification that ANTLR can explicitly mark a grammar as LL(k) for specific k.

Solution 4

Most installations of yacc and its clones or replacements (like btyacc, hyacc, bison) have test suites. The grammars in those test suites together make up a list of examples. I assume the same is true for LL parser generators; but I don't know much about them. Since ANTLR was mentioned, then I might also point out that a quick search will reveal the following large example repository under ANTLR https://github.com/antlr/grammars-v4 So, I guess that counts as an answer, too.

View more solutions