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.

Related Topics

Translation of Array References in Compiler Design

Translation of Array References We can access the elements of an array stored in consecutive blocks very easily and quickly. In a programming language like C and Java, the size of...

2 minutes read.

Syntax Analysis Compiler Design

Syntax Analysis This article will describe the parsing method used in the compiler. The grammatical rule of programming language can be constructed with the help of context-free grammars or BNF (Backus–Naur...

3 minutes read.

Symbol Table Compiler Design

Symbol Table It is an important data structure used by the compiler. It stores information about various entities such as object, class, variable names, functions name, interfaces, procedure, literals, string etc.  The...

3 minutes read.

Compiler Design Tutorial

Our compiler design tutorial will provide all the information about compiler from basic to advanced level. This compiler tutorial will help the student for their semester as well as for...

3 minutes read.

Data Flow Analysis in Compiler Design

Data Flow Analysis All the optimization techniques we have learned earlier depend on data flow analysis. DFA is a technique used to know about how the data is flowing in any...

3 minutes read.

Code Generation

Code Generation The last phase of the compiler is code generation. It is the compiler's back-end that makes multiple passes over the IR before generating the target program. The code generator's...

4 minutes read.

Evolution of Programming Languages in Compiler Design

The Evolution of Programming Languages The first computer came in the 1940s and was programmed in a binary language that told the computer what operations are to be performed and in...

4 minutes read.

Regular Expression | Compiler Design

Regular Expression A regular expression is a set of patterns that can match a character or string. It can also match alternative characters or strings. The grammar defined by the regular...

3 minutes read.

Errors in Compiler Design

Introduction Errors in compiler design refer to mistakes or issues that arise during the process of execution of the program. A compiler is a program that translates source code written in...

4 minutes read.

YACC in Compiler Design

YACC  YACC is known as Yet Another Compiler Compiler. It is used to produce the source code of the syntactic analyzer of the language produced by LALR (1) grammar. The input...

5 minutes read.

Optimization of Basic Blocks in Compiler Design

Optimization of Basic Blocks We can apply the optimization process on a basic block. While optimization, there is no need to change the set of expressions computed by the block. The basic...

3 minutes read.

Finite State Machine

Finite State Machine A finite state machine is a simple machine to recognize patterns. It takes a string of symbols as the input and changes its state to another state, but...

3 minutes read.

Boolean Expression in Compiler Design

Boolean Expression The translation of conditional statements such as if-else statements and while-do statements is associated with Boolean expression's translation. The main use of the Boolean expression is the following: Boolean expressions...

3 minutes read.

Lexical Analysis in Compiler Design

Lexical Analysis It is the first phase of the compiler. As we know, it is also known as a scanner. The input for lexical analysis is source code. After taking source...

2 minutes read.

Target Machine

Target Machine A target machine is a byte-addressable machine. This machine has n general-purpose registers, R0, R1,.....Rn-1. A Simple Target Machine Model has three-address instruction. A full-edged assembly language would have...

3 minutes read.

Switch Case Statement Compiler Design

Case Statement The “case” or “switch” statement is available in various languages. The following is the syntax for the case statement: switch (E)  {             case V1: S1             case V2: S2 ...

1 minute read.

Phases of Compiler

Phases of Compiler The compilation process of a compiler goes through various phases. Each phase of the compiler takes the output from the previous as an input. Here we will see all...

2 minutes read.

Derivation and Parse Tree in Compiler Design

Derivation and Parse Tree In this article, we will learn Derivation and Parse Tree. Derivations The parse tree can be constructed by taking a derivational view in which production is treated as rewriting...

4 minutes read.

CLR Parsing Compiler Design

CLR Parsing CLR parsing refers to the canonical lookahead. We will use the canonical collection of LR(1) items for the construction of the CLR(1) parsing table. Generally, CLR(1) parsing has more...

6 minutes read.

Bottom-Up Parsing in Compiler Design

Bottom-Up Parsing A bottom-up parsing constructs the parse tree for an input string beginning from the bottom (the leaves) and moves to work towards the top (the root). Bottom-up parsing is...

6 minutes read.