Parse Tree

What is parse trees

A parse tree is an entity which represents the structure of the derivation of a terminal string from some non-terminal (not necessarily the start symbol). The definition is as in the book. Key features to define are the root ∈ V and yield ∈ Σ^* of each tree.

• For each σ ∈ Σ , there is a tree with root σ and no children; its yield is σ
• For each rule A → ε , there is a tree with root A and one child ε ; its yield is ε
• If t₁ , t₂ , ..., t_n are parse trees with roots r₁ , r₂ , ..., r_n and respective yields y₁ , y₂ , ..., y_n , and A → r₁ r₂ ...r_n is a production, then there is a parse tree with root A whose children are t₁ , t₂ , ..., t_n . Its root is A and its yield is the concatenation of yields: y₁ y₂ ...y_n

Observe that parse trees are constructed from bottom up , not top down. The actual construction of "adding children" should be made more precise, but we intuitively know what's going on.

As an example, here are all the parse (sub) trees used to build the parse tree for the arithmetic expression

4 + 2 * 3
E → E + T | E - T | T 
T → T * F | F  
F → a| ( E )

                                

represents an operand of some type, be it a number or variable. The trees are grouped by height.

Parse Tree Content

Content	Description
Leaves	Labeled By Terminal or ε
Interior Nodes	Labeled By a Variable
Children	Labeled BY the right side of a Production for the Parent
Root	Labeled by the Start symbol

Parse Tree Visualization

Check to Parse Tree Test