Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Properties of Unambiguous Grammar
3.
Rules to Remove Ambiguity
4.
Frequently Asked Questions
4.1.
What is unambiguous Grammar?
4.2.
What is the leftmost and rightmost derivation?
4.3.
What are ambiguous and unambiguous sentences?
5.
Conclusion
Last Updated: Mar 27, 2024

Unambiguous Grammar

Author GAZAL ARORA
1 upvote
Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM
TOC

Introduction

Google's meaning of unambiguous is not open to more than one interpretation.

It means no ambiguity. A grammar is unambiguous if there is no ambiguity in it. This means it should contain only one leftmost derivation (LMD), one rightmost derivation (RMD), and one parse tree for the given input string.

Any parsers do not parse this Grammar.

Example of Unambiguous Grammar:

X -> AB
A -> Aa / a
B -> b

 

Also see, Turing Machine in TOC.

Properties of Unambiguous Grammar

  1. The leftmost and rightmost derivations are the same in Unambiguous Grammar.
  2. The Unambiguous Grammar generates a single parse tree.
  3. In Unambiguous Grammar, the length of the parse tree is relatively long.
  4. The speed of tree derivation in Unambiguous Grammar is slower than in Ambiguous Grammar.
  5. There is no ambiguity in Unambiguous Grammar.


Note: To check if a Grammar is ambiguous or not, draw a parse tree of some string that belongs to the language produced by that Grammar. If the number of parse trees is greater than one, the Grammar is ambiguous. 

The string must be carefully chosen because some strings may be available in the language produced by the unambiguous Grammar, which has just one parse tree.

Read About - Simplification of CFG

For example,

Q1: Consider the following grammar G:

S → AB | aaB  
A → a | Aa  
B → b  

 

Determine whether or not the grammar G is ambiguous. 

Solution: Let's create the string "aab."

Parse Tree

The given grammar G is ambiguous because there are two different parse trees for deriving the same string.

Also read - Arden's theorem

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Rules to Remove Ambiguity

Use the following rules to convert the ambiguous grammar to unambiguous grammar:

Rule 1: If the left-associative operators (-, +, *, /) are used in the production rule, use left Recursion. In the left recursion, the leftmost symbol on the right side is the same as the non-terminal on the left side.

Rule 2: If the right-associative operates(^) is used in the production rule, then apply right recursion. Right recursion means that the rightmost symbol on the left side corresponds to the non-terminal on the right side.

Let's understand with an example,

Q: Consider the ambiguous grammar G:

E -> E-E | id

 

Suppose we want to get the string id-id-id. Consider id = 4  As a result, you should get: 4 - 4 - 4 = -4. (Since the priority operators are the same, we should consider associativity from left to right.)

Parse Tree

To make the Grammar unambiguous, the parse tree that grows on the left side of the root will be correct.

To convert G into Unambiguous Grammar, make it Left Recursive by replacing the leftmost non-terminal E in the right side of the production with another variable, P. The grammar is as follows:

E -> E - P | P
P -> id

 

As seen below, the above grammar is now unambiguous and will include only one Parse Tree:

Parse Tree

 

Note: While converting Ambiguous Grammar to Unambiguous Grammar, we should not change the Ambiguous Grammar's original language. As a result, the non-terminals in the Ambiguous Grammar must be substituted with other variables to get the same language as previously while also maintaining the precedence and associativity rules.

You can also read about - Moore Machine

Frequently Asked Questions

What is unambiguous Grammar?

If there is no ambiguity in the Grammar, it is unambiguous. This means that it is an unambiguous grammar if it does not contain more than one leftmost derivation (LMD), more than one rightmost derivation (RMD), or more than one parse tree for the given input string.

What is the leftmost and rightmost derivation?

A leftmost derivation is obtained by applying production on the leftmost variable in each step. A rightmost derivation is obtained by using production on the rightmost variable in each step.

What are ambiguous and unambiguous sentences?

All sentences with ambiguous words are ambiguous, while every sentence with no ambiguous words is unambiguous.

Conclusion

In this article, we learned about Unambiguous Grammar. We learned that Grammar is unambiguous if it contains only one leftmost derivation (LMD), one rightmost derivation (RMD), and one parse tree for the given input string.

With the help of some examples, we also learned about the rules we must follow to convert Ambiguous Grammar to Unambiguous Grammar.

Now you are ready to solve questions like:

  1. Check whether the Grammar is Ambiguous or Unambiguous.
  2. Convert an Ambiguous Grammar into an Unambiguous Grammar.


Recommended Readings:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Live masterclass