LR(1) Items Constructions

Example: Show that S →AS | b  A →SA | a is not LR(1)

The augmented grammar is S’ → S  S → AS  A → SA  A → a and the sets of LR(1) items are,

I0: S’ → .S, $ S →.AS, $/a/b S → ..b, $/a/b A →.SA, a/b A →.a, a/b I1: S’ →S., $ A →S.A, a/b A →.SA, a/b A →.a, a/b S →.AS, a/b S →.b, a/b I2: S’ →A.S, $/a/b S →.AS, $/a/b S →.b, $/a/b A →.SA, a/b A →.a, a/b I3: S →b., $ I4: A →a., a/b I5: A → SA., a/b S → A.S, a/b S → .AS, a/b S → .b, a/b A →.SA, a/b

I6: A →S.A, a/b A → .SA, a/b A → .a, a/b S →.AS, a/b S →.b, a/b I7: S →b., a/b I8: S →AS., $/a/b A →S.A, a/b A →.SA, a/b A →.a, a/b A →.a, a/b S → .AS, $/a/b S →.b, a/b I9: S → AS., a/b A →S.A, a/b A →.SA, a/b A →.a, a/b S →.AS, a/b S →.b, a/b I10: S →A.S, a/b S →.AS, a/b S →.b, a/b A →.SA, a/b A →.a, a/b

Parsing Table: 

State	Action			Goto
	a	b	s	S	A
0	s4	s3		1	2
1	s4	s7	acc	6	5
2	s4	s3		8	2
3	r2	r2	r2
4	r2	r4
5	s4,r3	s7,r3		9	10
6	s4	s7		6	5
7	r2	r2
8	s4,r1	s7,r1	r1	6	5
9	s4,r1	s7,r1		6	5
10	s4	s7		9	10

 Note: As the table has multiple entries, the grammar is not LR(1). (Given Grammar is ambiguous)

• Note: If the CLR parsing table constructed has no multiply defined entries in the action field, then the grammar is known as LR(1) grammar. This happens only when the given grammar is ambiguous
• Every SLR(1) grammar is also LR(1)
• For an SLR(1) grammar the CLR parser may have more number of states than the SLR parser for the same grammar

How to Construct CLR Parsing Table

Home

LALR Parser