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

Share on Google Plus

About Data Sciences by Venu

Hi, My name is Venugopala Chary and I'm Currently working as Associate Professor in Reputed Engineerng College, Hyderabad. I have B.Tech and M.tech in regular from JNTU Hyderabad. I have 11 Years of Teaching Experience for both B.Tech and M.Tech Courses.