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.

Handling Ambiguous Grammar1

Home

Error Recovery in Parsing