Ambiguity Elimination Compiler Design
Ambiguity Elimination
Ambiguity elimination makes the sentence clear and readable. A sentence is grammatically ambiguous if it can produce more than one parse tree for a particular grammar. In this article, we will learn how to remove ambiguity to make the grammar ambiguous.
Associativity
If an operand has an operator with the same precedence on both sides, the associativity of the operator will decide on which direction (side) the operand takes these operators. The operand will be taken by the left operator when the operation is left-associative and will be taken by the right operator when the operation is right-associative.
The operation such as multiplication, addition, subtraction, and division are left-associative.
Example
Suppose we have an expression as below:
id op id op id
Here, id is an operand, and op indicates the operator. This expression will be expressed as:
(id op id) op id
For example, (id + id) + id
If the operator is exponentiation, it is right-associative. It means if we evaluate the same expression, the order of evaluation will be:
id op (id op id)
For example, id ^ (id ^ id)
Precedence
If there is a situation arise when two different operators take a common operand, then the operand will assign to which operator will be decided by the precedence of operators. The 3 + 4 * 2 can have two distinct parse trees, one corresponds to (3 + 4) * 2 and another corresponds to 3 + (4 * 2). With the help of precedence among operators, this situation will be easily removed. We know that multiplication (*) has higher precedence over addition (+), so the expression 3 + 4 * 2 will be implemented as 3 + (4 * 2).
With the use of associativity of the operator and precedence of the operator, the ambiguity in grammar or its language can be eliminated.
Left Recursion
A grammar is said to be left recursive if it has any non–terminal, say A, and there is a derivation starting from that non-terminal such that A => Aa for some string a. We should know that the top-down parser cannot handle left–recursive grammar. To eliminate left–recursion from any given left-recursive string, we need to make changes in the given string.
Example
A => A? | ?
S => A? | ?
A => Sd
First is the example of immediate left recursion.
Second is the example of indirect left recursion.
Removal of left recursion
The production:
A => A? | ?
Can be transformed into the following production
A => ?A’ A’ => ?A’ | ?
without changing the strings derivable from A.
Left Factoring
The grammatical transformation is useful for the production of grammar. This transformation is suitable for predictive or top-down parser. If more than one grammar production has the same starting symbol in the string, the top-down parser cannot choose which of the production it should take to parse the string.
Example
Let us take the following grammar.
A => ?? | ?? |
In the given grammar, both the string have the same starting symbol. So we cannot immediately tell which production to choose to expand A. To eliminate this confusion, we use a technique called left factoring.
In this method, we combined the string with the same starting symbol into the single string, and the remaining derivation is added by new production.
So the above grammar can be written as:
A => ?A'
A'=> ? | ? |
Now there is only one production responsible for beginning from each starting symbol. This will be very useful for the parser to make a decision.
Limitations of Syntax Analyzers
The tokens from the lexical analyzer are the input for syntax analysis. A lexical analyzer checks the validity of the token. Syntax analyzer has the following drawback:
- The syntax analyzer cannot determine the validation of tokens.
- The syntax analyzer cannot detect that the token used in the lexical analyzer has been declared before being used or not.
- It cannot determine whether the token is initialized before using or not.
- Any operation performed on the token type is valid or not can be determined by syntax analysis.