Do you think IIT Guwahati certified course can help you in your career?
No
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.
The leftmost and rightmost derivations are the same in Unambiguous Grammar.
The Unambiguous Grammar generates a single parse tree.
In Unambiguous Grammar, the length of the parse tree is relatively long.
The speed of tree derivation in Unambiguous Grammar is slower than in Ambiguous Grammar.
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.
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.)
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:
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.
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:
Check whether the Grammar is Ambiguous or Unambiguous.
Convert an Ambiguous Grammar into an Unambiguous Grammar.