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

Question

Is there a good resource on the Internet with a set of grammars for some basic parsing algorithms (LL (1), LR (1), LR (0), LALR (1))? I have found many separate grammars that fall into these families, but I don’t know of a good resource where someone wrote a large set of grammar examples.

Does anyone know about such a resource?

Answer 1

Analysis Methods - The practice guide contains several examples (that is, probably half a dozen or so) for each type of grammar. You can purchase a book of the 2nd edition, although the 1st edition is available free of charge for the author of the website in PDF format (near the bottom of the link).

The author also has some test grammars, which he associates with code samples from the second edition, which can be found here .

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

Answer 2

Examples from wikipedia

LL (1)

Grammar

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

entrance

 ( 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 

entrance

 1 + 1 

parsing steps

 need to build a parser table and traverse through states. 

LR (1)

Grammar

 S' -> SSS -> CCC -> c C | d 

entrance

 cd 

parsing steps

 large table 

Lalr

Grammar

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

entrance

 xxzxx 

parsing steps

 traverse large parser table 

You can also watch

• Parsing Tool
• antlr works - > download <
• Parser table generation from ocw mit
• From parsing to coding of ocw mit code
• additional examples

Answer 3

I would not expect you to find whole collections of grammars organized in this way. What will the organizer get in return?

What could you do is find parser generators that correspond to each family (for example, LL (1)), and look for examples of inputs for this parser generator, all of which will be LL (1) by definition. For example, ANTLR grammars are different versions of LL (k) depending on the version of ANTLR you choose (a description of the ANTLR version will tell you that k accepts); Bison grammars are LALR (1) [ignoring the last GLR option]. If you go to my website (see Biography), you will see a list of grammars that are pretty much context free (that is, not in any of the classes that you describe).

EDIT: Pay attention to @Bart Kier, explaining that ANTLR can explicitly mark the grammar as LL (k) for a specific k.