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

templatetypedef picture templatetypedef · Jun 25, 2011 · Viewed 53.8k times · Source

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?

Answer

Prashant Bhate picture Prashant Bhate · Jul 4, 2011

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