Handling Ambiguous Grammars

Advantages of using Ambiguous Grammars:

• Ambiguous grammars provide a shorter and more natural specification for certain constructs when compared to the equivalent unambiguous grammars
• One can isolate a construct for optimization purposes using ambiguous grammars
• One can incorporate a special construct by adding new productions to an existing ambiguous grammar

Ambiguous grammar can be handled by bottom up parser.

Creating LR Parsers for Ambiguous Grammars:

• No ambiguous grammar can be LR. But by carefully resolving conflicts an LR parser for an ambiguous grammar can be designed
• Resolving conflicts can be done by either one of the two following methods

Method 1: By using associativity and precedence in case of expression

Method 2: By keeping in view the correct sentences in the language

Method 1:

• Consider the following ambiguous grammar for expressions

                                E → E + E | E * E | ( E ) | id

                We know that ‘+’ and ‘*’ are left associative and ‘*’ is having precedence over ‘+’

• The unambiguous version of the equivalent grammar is

                                E → E + T | T   T → T * F | F   F → ( E ) | id

Reasons to use Ambiguous version:

• We can change operator precedence
• Parser will have less number of states compared to unambiguous version
• Parser never wastes time in performing reductions like E → T or T → F

Steps for Creating LR parser

• Step 1: Construct LR(0) items.
• Step 2: Construct LR parsing table with the help of step 1
• Step 3: Parse an input string with the help of step 2

Steps for Constructing LR(0) Items

• Step 1: Add augmented grammar.
• Step 2: Apply closure and goto operations

Method 1:

E’ → E   E → E + E   E → E * E   E → ( E )  E → id

and  the LR(0) items are:

I0: E’→.E E→.E+E E→.E*E E→.id I1: E’→E. E→E.+E E→E.*E I2: E’→.E E→.E+E E→.E*E E→.(E) E→.id I3: E→.id I4: E→E+.E E→.E+E E→.E*E E→.(E) E→id

I5: E→E*.E E→.E+E E→.E*E E→.(E) E→.id I6: E→(E.) E→E.+E E→E.*E I7: E→E+E. E→E.+E E→E.*E I8: E→E*E. E→E.+E E→E.*E I9: E→(E).

 Creating LR parser for Ambiguous Grammar:

Method 1:

• While designing SLR parser table using it’s algorithm, conflicts arise as the grammar is ambiguous
• The states involved in conflicts are

                I₇: reduction by E→E+E and shift on ‘+’ and ‘*’

                I₈: reduction by E→E*E and shift on ‘+’ and ‘*’

Resolving Conflicts with I₇ on Top:

Let the input is id+id*id$. Then after consuming input upto ‘*’ the stack content will be

                                O E1 + 4 E7

Now on ‘*’ shift must happen as ‘*’ is having precedence over ‘+’

Let the input be id+id+id$. After consuming input upto second ‘+’, the stack content must be

                                0E1 + 4E7

Now ‘+’ reduction must happen as + is left associative

So, I₇ must reduce on’+’ and must shift on ‘*’.

Resolving Conflicts with I₈ on Top:

Let the input is id+id*id$. After consuming input upto ‘+’ the stack content is

                                O E1 + 5 E8

Now on ‘+’ reduction must happen as ‘*’ is having precedence over ‘+’

Let the input be id*id*id$. After consuming input upto second ‘*’, the stack content will be

                                0E1 + 5E8

Now on  ‘*’ reduction must happen as ‘*’  is left associative. 

So, I₈ must reduce on’+’ and must shift on ‘*’.

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

Issues of Interest After Merging in LALR Parser

Home

Handling Ambiguous Grammar2