Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Ambiguity in Grammar
2.1.
Example 1
2.2.
Example 2
2.3.
Example 3
2.4.
Inherently ambiguous for context-free grammar
3.
Frequently Asked Questions
3.1.
What do you mean by unambiguous grammar?
3.2.
What do you mean by Context-Free Grammar?
4.
Conclusion
Last Updated: Mar 27, 2024

Ambiguous Grammar

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @
TOC

Introduction

Before heading towards ambiguous grammar, let's see about Context-Free Grammar. A context-free grammar is a formal grammar used to generate all the possible patterns of strings.

A context-free grammar is classified based on:

  • Number of Derivation trees
  • Number of Strings


The number of Derivation trees is further classified into


Let's have a detailed look at when grammar is ambiguous.

You can also read about - Moore Machine

Ambiguity in Grammar

A grammar or a Context-Free Grammar(CFG) is said to be ambiguous if there exists more than one leftmost derivation(LMDT) or more than one rightmost derivation(RMDT), or more than one parse tree for a given input string.

Technically, we can say that context-free grammar(CFG) represented by G = (N, T, P, S) is said to be ambiguous grammar if there exists more than one string in L(G). Otherwise, the grammar will be unambiguous.

One thing that should be transparent is that ambiguity is a property of grammar and not a language. 

Since Ambiguous Grammar can produce two Parse trees for the same expression, it's often confusing for a compiler to find out which one among all available Parse Trees is the correct one according to the context of the work. This is the reason ambiguity is not suitable for compiler construction.

Example 1

Let production rule is given as:

S -> AB|aaB 

A -> a|Aa 

B -> b 

Let us generate string aab from the given grammar. Parse trees for generating string aab are as follows : 

Parse Tree

Here for the same string, we are getting more than one parse tree. Hence, grammar is ambiguous grammar. 

Example 2

Let production rule is given as: 

E -> EE+

E -> E(E)

E -> id 

Parse tree for id(id)id + is:

Parse Tree

Only one parse tree is possible for id(id)id+, so the given grammar is unambiguous.

Also read - Arden's theorem

Example 3

Check the given production is ambiguous or not

S → aSb | SS  

S → ε  

For the string "aabb" the above grammar can generate two parse trees.

Parse Tree

Since there are two parse trees for a single string, "aabb", the grammar G is ambiguous.

Note:

We can disambiguate a grammar such that only one derivation is possible for the string.

Inherently ambiguous for context-free grammar

If every grammar that generates L is ambiguous, then language is inherently ambiguous. eg for inherent grammar is L= {a^nb^nc^m}∪{a^nb^mc^m}.

Also see, Turing Machine in TOC.

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

Frequently Asked Questions

What do you mean by unambiguous grammar?

In ambiguous grammar, both rightmost and leftmost derivations are the same. Unambiguous grammar generates only one parse tree and does not contain any ambiguity.

What do you mean by Context-Free Grammar?

Context-free grammar is a formal grammar used to generate all possible strings in a given formal language.

Conclusion

This blog has covered the following things:

What do you mean by context-free grammar?

When will grammar be ambiguous?

Examples show ambiguous and unambiguous grammar.

What is the difference between ambiguous and unambiguous context-free 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.

Happy learning!

Previous article
Derivation Tree
Next article
Unambiguous Grammar
Live masterclass