Compiler Tutorial

Compiler Introduction Phase of Compiler Symbol Table Lexical Analyser Evoluation of Programming Language Regular Expression Finite Automata Syntax Analysis Derivation and Parse Tree Bottom – Up Parsing LR parser YACC in Compiler Design LALR 1 Parsing | Compiler Design

Misc

Parsing in Compiler Design Shift Reduce Parsing in Compiler Design Refractive Index and Its types 6 Phases of Compiler Compiler Construction Tools in Compiler Design

Ambiguity Elimination Compiler Design
2020-12-25 06:46:02

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.