Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Mar 27, 2024

Difference between Ambiguous and Unambiguous Grammar

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

Introduction

Grammar can be defined as a finite set of rules that determines how to generate sentences with correct syntax. OR, It is a set of rules that can be used to generate strings of a particular language. 

Grammar is classified into two types based on derivation trees. And the two types are ambiguous and unambiguous grammar. 

In this blog, we will learn about these two types of grammar and understand the difference between them.

What is Ambiguous Grammar

If it is possible to get one of the following:

  • More than one parse tree for a given string  
  • More than one leftmost derivation or rightmost derivation for context-free grammar

Then grammar is considered ambiguous grammar. 

Example

Consider the grammar rule given below:

 A-> A+A | id 

We need to generate id+id+id, which is a string.

 

        

                                                         illustrationillustration

                                        Possible Leftmost derivations for input string according to given grammar rule

According to the given grammar rule, these two leftmost derivations are generated for the input string. Since, more than one left most derivation is possible for the given string for the given grammar rule, so the grammar is ambiguous.

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

What is Unambiguous Grammar

If it is not possible to get even one of the following:

  • More than one parse tree for a given string 
  • More than one leftmost derivation or rightmost derivation for context-free grammar

Then grammar is considered unambiguous grammar. Grammar is unambiguous when it is not ambiguous.

Example

Consider the grammar rule given below:

A - A+id | id 

We need to generate id+id+id, which is a string. 

                                           

 

                                                                                      illustration

                                                      Possible Leftmost derivation for input string according to given grammar rule

According to the given grammar rule, this leftmost derivation is generated for the input string. Since, only one Leftmost derivation is possible for the given string for the given grammar rule, so the grammar is unambiguous. 

Difference between Ambiguous and Unambiguous Grammar

The following are differences between Ambiguous  and Unambiguous Grammar:

            Ambiguous Grammar

      Unambiguous Grammar

 

It contains ambiguity. It does not contain ambiguity.
We get more than one parse tree. We get only one parse tree.
The leftmost and the rightmost derivation of this grammar represents different parse trees. This grammar's leftmost and rightmost derivation represent the same parse trees.
We get a smaller size of the parse tree. 

We get a bigger size of the parse tree.

 

The number of non-terminals is lesser in this grammar. More number of non-terminals are there in this c
The generation of a parsing tree for this is faster. The generation of parsing trees for this is slower.

Example of Ambiguous Grammar−

A → A + A / A x A / id

 

Example of Unambiguous Grammar−

A→ A + E / E

A → A x F / F

A → id

 

 

 

 

 

Also read, Arden's theorem

Frequently Asked Questions

What type of grammar is not good for compiler construction?

Ambiguous grammar is not good for compiler construction. Since it will generate multiple parse trees for the same program(the program will be considered a string by the compiler), it will result in two meanings.

Is it possible to remove ambiguity from the grammar? How?

Yes, it is possible to remove ambiguity from the grammar. It can be removed only by re-writing the complete grammar without ambiguity. But it cannot be removed by any method or can be automatically detected.

Which grammar among ambiguous and unambiguous grammar is considered powerful?

Ambiguous grammar is powerful since it generates a parsing tree faster than unambiguous grammar.

How are ambiguous and unambiguous grammar different with respect to size of parse tree?

Ambiguous grammar generates a parsing tree of smaller size while unambiguous grammar generates a parsing tree of larger size.

What is ambiguous grammar code?

Ambiguous grammar in programming refers to a string in a language that can be derived in more than one way from the grammar, leading to multiple parse trees. This ambiguity can confuse interpreting the code.

Conclusion

This blog covered the concepts of ambiguous and unambiguous grammar along with their differences, examples, and frequently asked questions.

After brushing up on your concepts about the topic difference between Ambiguous and Unambiguous Grammar, do not stop here to learn about the Derivation tree.

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.

Happy Learning!!!

Topics covered
1.
Introduction
2.
What is Ambiguous Grammar
2.1.
Example
3.
What is Unambiguous Grammar
3.1.
Example
4.
Difference between Ambiguous and Unambiguous Grammar
5.
 
6.
 
7.
 
8.
 
9.
Frequently Asked Questions
9.1.
What type of grammar is not good for compiler construction?
9.2.
Is it possible to remove ambiguity from the grammar? How?
9.3.
Which grammar among ambiguous and unambiguous grammar is considered powerful?
9.4.
How are ambiguous and unambiguous grammar different with respect to size of parse tree?
9.5.
What is ambiguous grammar code?
10.
Conclusion