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?

Wye

These are parsing algorithms not grammars. Do you mean examples of syntax that requires one type of parser or another? – Transilient

I think that technically speaking, LL(1) etc. are actually families of grammars. The parsing algorithms named after them are algorithms that can parse any grammar that happens to be in the family of languages. – Wye

I suggest you taking a look at the ANTLR website. It has some good language grammars ;) – Tenno

If you had such a list, what on earth would you do with it? The list of names in each category doesn't seem very interesting by itself; surely you don't want to actually process the content of all those grammars? – Latonialatoniah

@Ira Baxter- I'm currently teaching a compilers course and keep having to steal example grammars from other sources when I want to show off various parsing algorithms. It's tricky (but doable) to create nontrivial grammars in these categories, and extremely difficult to make grammars that are LR(1) but not LALR(1) or LALR(1) but not SLR(1). I was hoping to find examples of real-world grammars that match these descriptions so that I could focus on presenting he material rather than tweaking grammars. – Wye

@Prashant Bhate, perhaps it has disappeared because you wanted it too much. – Appoggiatura

The book in my answer below seems to have good examples that would be a good fit for a compiler class. – Dialectic

The following link to my personal GitHub repository contains 4 LL(1) grammars, one LR(0) grammar which is NOT LL(1), one SLR(1) which is NOT LR(0) and one LR(1) which is NOT SLR(1). ALL the examples can be compiled and run by simply writing "make" in the terminal of any *.nix like OS. – Guarino

Answer 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.

Dialectic

Answer 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

Ade

can you please tell me how to prove a grammar to be LR(0) or SLR(1)? – Snooze

@katia- You may want to check out cs143.stanford.edu, Stanford's compilers course, which has a whole bunch of lecture slides and handouts detailing how you'd do this. The second problem set and midterm (and their solutions) go into some detail about this. – Wye

I do not believe the given grammar is LR(0). In the state: [S -> E .], [E -> E . + B] we have a shift/reduce conflict. We need to use a token of lookahead to determine whether to reduce, S -> E . on $ lookahead, or to continue shifting. The conflict is resolved using the generic FOLLOW set for S, making the grammar SLR not LR(0). – Nikaniki

I agree with @ChrisSmowton – Veasey

@ChrisSmowton, , the grammar is indeed LR(0). to create the Items DFA, one usually add the rule S -> E# (where # is the end of the input) hence the mentionned state contains [S -> E . #], [E -> E . + B] and there is no conflict, but 2 different shifts (one being the accept action). – Dresser

Your LR(1) example is LR(0) with the following table. States 0-8. Start state: 0. Gotos S': 0→8; S: 0→1, 1→7; C: {0,1}→2, 2→4, 3→5. Shifts c: {0,1,2,3}→3, d: {0,1,2,3}→6. Reduces {S⇐CC} on 4, {C⇐cC} on 5, {C⇐d} on 6, {S'⇐SS} on 7. Accept {⇐S'} on 8. Also: "cd" is not accepted by the grammar, though "cdddd" is. – Garzon

Answer 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.

Latonialatoniah

Good suggestion to try parser generators. Using ANTLR, you can set the look ahead manually like this: options { k=1; } for LL(1), or, the default options { k=*; } for LL(k). – Appoggiatura

@Bart Kiers: I was under the impression that older versions of ANTLR couldn't do k>1 and k=* variously. Do all versions accept an explicit declaration? Still, interesting to know. I thought the most recent ANTLR used grammmar-rule specific lookaheads to figure out what the lookahead was automatically. But I am not an ANTLR expert. – Latonialatoniah

I believe the unbound lookahead, k=*, was added in the ANTLR v3. ANTLR v2.x always had a fixed k. This is off the top of my head, I'll have a look at my copy of the ANTLR reference later on and if I'm mistaken, I'll rectify. But I'm pretty sure it's correct. – Appoggiatura

Answer 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.

Decommission