Do you think IIT Guwahati certified course can help you in your career?
No
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.
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.
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.
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.
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.