Parse Tree in Automata

The process of deriving a string from a given grammar is called derivation. The geometrical representation of a derivation is known as a derivation tree or parse tree.

In Parse Tree, the deepest sub-tree from leftmost is traversed first by following the rule of In-order traversal. In this way, the original input string is obtained, but

  • All leaf nodes must be terminals.
  • All interior nodes must be Non-terminals.

Example of Parse Tree

Suppose the following Production rules of a Grammar (G)

S → S + S | S * S  

S → x|y|z  

and Input is (x * y + Z)

Step 1

Parse Tree step 01

Step 2

Parse Tree step 02

Step 3

Parse Tree step 03

Step 4

Parse Tree step 04

 

Step 5

Parse Tree step 05