Handling Ambiguous Grammars 2

Method 2:

Consider the following ambiguous grammar for if statement.

                                Stmt → if expr then stmt else stmt

                                                | if expr then stmt

                                                | other

Rewritten (after renaming) as,

                                S → iSeS | iS | a

The augmented grammar is S’ → S   S → iSeS   S → iS   S → a and LR(0) items are,

I0: S’ → .S S → .iSeS S → .iS S → .a I1: S’ → S. I2: S → i.SeS S → i.S S →.iSeS S → .iS S → .a

I3: S → a. I4: S → iS.eS S → .iS I5: S → iSe.S S → .iSeS S → .iS S → .a I6: S → iSeS.

While designing SLR parser table using it’s algorithm, we get conflicts as the grammar is ambiguous

The only state involved in conflict is

                I₄: Reduction by S → iS. on e and also on e due to S →iS.eS

Resolving conflict with I4 on top

                When I₄is on top, the stack contains, If expr then stmt

                Then, else on the input must cause a shift as it is associated with the if

After resolving conflicts the SLR parsing table is as shown in the table.

State	Action				Goto
	i	e	a	$	S
0	s2		s3		1
1				Acc
2	s2		s3		4
3		r3		r3
4		s5		r2
5	s2		s3		6
6		r1		r1

Exercise:

Create an SLR parser for the following ambiguous grammar

E → E sub E

E → E sup E

E → { E }

E → C

Note: Treat sub and sup as equal precedence operators and right associative.

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.