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.

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.