Logo

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 rules. In each rewriting step, a non-terminal is replaced by the body of its production. At each step of the derivation, we have to make two decisions. First, we have to choose which non-terminal should be replaced, and the second is which production rule should choose to replace that non-terminal.

Each non-terminal can be replaced by more than one derivations in the same production rule, but the order of replacement will be different.

Left-most Derivation

If the input is scanned and replaced with the production rule from left to right, it is known as left-most derivation. In other words, we can say that we read the input string from left to right.

Example

Consider the following grammar-

S ? aB / bA

S ? aS / bAA / a

B ? bS / aBB / b

Let us consider a string w = aaabbabbba

Now, derive the string w using left-most derivation as follows

S? aB

? aaBB                    (Using B? aBB)

? aaaBBB                (Using B? aBB)

? aaabBB                 (Using B? b)

? aaabbB                  (Using B? b)

? aaabbaBB              (Using B? aBB)

? aaabbabB               (Using B? b)

? aaabbabbS               (Using B? bS)

? aaabbabbbA        (Using S ? bA)

? aaabbabbba         (Using A ? a)

Right-most Derivation

In the right-most derivation, the right-most non-terminal is always selected. If the input is scanned and replaced with the production rule from right to left, it is known as right-most derivation.

Example

Consider the following example:

S ? aB / bA

S ? aS / bAA / a

B ? bS / aBB / b

Let us consider a string w = aaabbabbba

Now, derive the string using right-most derivation as follows:

S   ? aB

?  aaBB                    (Using B ? aBB)

? aaBaBB                 (Using B ? aBB)

? aaBaBbS               (Using B ? bS)

? aaBaBbbA             (Using S ? bA)

? aaBaBbba              (Using A ? a)

? aaBabbba              (Using B ? b)

? aaaBBabbba          (Using B ? aBB)

? aaaBbabbba          (Using B ? b)

? aaabbabbba           (Using B ? b)

Parse Tree

The hierarchical structure of a symbol (terminal or non-terminal) is known as a parse tree. The symbol represents the derivation of grammar to get the input string. It depicts how productions are put to replace non-terminal. Start symbol of the production rule will be the root of a parse tree. The role of the parse tree is to see how the string is formed using the start symbol. An interior node of the parse tree is non-terminal, and all the leaf node of the parse tree is terminal. An in-order traversal of the parse tree will give an original input string.

Example 1

Production rules

S = S + S | S * S

S = a|b|c

Step 1:

Step 2:

Step 3:

Step 4:

Step 5:

Example 2

Consider the following production rule

S -> sAB

A -> a

B -> b

If the input string is “sab”, then the parse tree is:

Another production rule

S -> AB

A -> c/aA

B -> d/bB

If the input string for the following production is "acbd", then the parse tree will be:

Ambiguity

For a given input string, if there exists more than one parse tree, then grammar A is said to be ambiguous. In another way, we can say that ambiguous grammar is one that produces more than one left-most derivation or right-most derivation for a given input string. Inherent language is generated by this kind of grammar.

For the design of the compiler, the grammar should be unambiguous. A grammar with ambiguity is not good for compiler design. There are no methods that can automatically detect ambiguity. To remove the ambiguity, we have to rewrite the full grammar that doesn’t contain ambiguity. It can also be removed by setting and following the associativity and precedence limitations.

Example

S = aSb | SS

S = C

For the string aabb, the above production rule will produce two parse trees:

Related Topics

LALR 1 Parsing | Compiler Design

LALR (1) Parsing The LALR parsing refers to the "lookahead LR" that has many lesser steps than typical parsers based on LR(1) items. For constructing the LALR(1) parsing table, the canonical...

6 minutes read.

Machine-Independent Optimizations in Compiler Design

Machine-Independent Optimizations The main aim of machine-independent optimization is to improve the generated intermediate code so that compiler can get better target code. Eliminating unwanted code from the object code or replacing...

8 minutes read.

Basic Blocks and Flow Graphs in Compiler Design

Basic Blocks and Flow Graphs In this section, we are going to learn how to work with basic block and flow graphs in compiler design. Basic Block The basic block is a set...

3 minutes read.

Run-Time Environments

Run-Time Environments Storage Organization Every target program has its own logical address, and an executable program runs in it. The logical address space has the location for each program value. The...

2 minutes read.

Syntax-Directed Translation

Syntax-Directed Translation A context-free-grammar with some additional rules is known as a syntax-directed definition. In SDT, attributes are associated with grammar symbols and rules are associated with productions. The attributes can...

3 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.

S-attributed and L-attributed SDTs

S-attributed and L-attributed SDTs STD stands for Syntax Directed Translation. When we associate some informal notations called semantic rules and the grammar, they are known as STD. So we can say...

2 minutes read.

SLR 1 Parsing Compiler Design

SLR(1) Parsing It is a simple LR parsing. Most of the function of this parsing is the same as LR(0) parsing. The parsing table for both the parser vary. The SLR(1)...

5 minutes read.

Shift Reduce Parsing in Compiler Design

Like the bottom-up parsing, the shift reduce parser also builds the parse tree from the leaves (bottom) to the root (up). The LR parser is a more versatile variation of...

4 minutes read.

Three-Address Code

Three-Address Code If there is at most one operator on the right side of the instruction, then the instruction will be the three-address code so that no arithmetic expressions are permitted....

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.

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.

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.

Parsing in Compiler Design

Parsing is the term used to describe the process of converting data between different formats. The parser can carry out this operation. The parser is a part of the translator...

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.

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.

Run-Time Storage Management

Run-Time Storage Management Every executing program has its own logical address space. Logical address space is partitioned into: Code: It is responsible for storing the executable target code. Static: It is used to...

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.

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.

Stack Allocation of Space

Stack Allocation of Space Almost all compilers for languages that use procedure, functions, or methods manage their run-time memory as a stack. Whenever a procedure is called, the local variable's space...

2 minutes read.