Compiler Design-Derivations and Parse Tree

Derivations and Parse Tree

What is a Parse Tree?

Parse tree is a hierarchical representation of terminals or non-terminals.

• The terminals or Non-terminals (Symbols) represent the derivation of the grammar to yield input strings.
• The root of the parse tree must be the starting symbol of the grammar.
• The terminals are the roots of the parse tree.
• The inner nodes are the grammar productions.

The rules for drawing a Parse Tree

1. All leaf nodes need to be terminals
2. All inner nodes need to be non-terminals.
3. In-order traversal gives the original input string.

Reference Link

Derivations and Parse Tree