Parse tree

• Parse tree is the graphical representation of symbol. The symbol can be terminal or non-terminal.
• In parsing, the string is derived using the start symbol. The root of the parse tree is that start symbol.
• It is the graphical representation of symbol that can be terminals or non-terminals.
• Parse tree follows the precedence of operators. The deepest sub-tree traversed first. So, the operator in the parent node has less precedence over the operator in the sub-tree.

The parse tree follows these points:

• All leaf nodes have to be terminals.
• All interior nodes have to be non-terminals.
• In-order traversal gives original input string.

Example:

Production rules:

1. T= T + T | T * T  
2. T = a|b|c  

Input:

a * b + c

Step 1:

Step 2:

Step 3:

Step 4:

Step 5: