What is a Parse Tree or Derivation Tree?

Let's understand about parse tree which is also known as the derivation tree.

Parsing is a way to derive string from given grammar by parse tree or better to say derivation tree.

Parse tree or derivation tree is the tree representation having root nodes with its corresponding child node. With the help of that tree, we derive context-free language from a given grammar. A parse tree is an ordered tree in which the left-hand side of production represents a parent node and the right-hand side of production () represents a children node.

There are certain conditions for constructing a parse tree from a given CFG. Those are as follows.

·        Each vertex of the tree must have a label. The label is non-terminal or terminal or null (Λ).

·        The root of the tree is the start symbol, i.e., S.

·        The label of the internal vertices is a non-terminal symbol ∈ VN.

·        If there is a production A → X₁X₂ . . .  X_K, then for a vertex label A, the children of that node will be X ₁X₂ . . .  X_K.

 A vertex n is called a leaf of the parse tree if its label is a terminal symbol ∈ Σ or null (Λ)

The parse tree construction is possible only for CFG. This is because of the properties of a tree match with the properties of CFG.
Here, we are describing the similar properties of a tree and a CFG.

·    For a tree, there must be some root. For every CFG, there is a single start symbol.

·      Each node of a tree has a single label. For every CFG at the LHS, there is a single non-terminal.

·       A child node is derived from a single parent. For constructing a CFL from a given CFG, a non-terminal is replaced by a suitable string at the RHS (if for a non-terminal, there are multiple productions). Each of the characters of the string is generating a node. That is, for each single node there is a single parent.

The parse tree construction is possible only for CFG. This is because of the properties of a tree match with the properties of CFG.

Properties of trees that are similar to CFG were described here:

·        Tree and CFG both have a single initial state. Root in tree & start symbol in CFG.

·     Single label in each node of the tree, similarly there is single non-terminal for every CFG at its LHS.

·     Each node of a tree has a single label. For every CFG at the LHS, there is a single non-terminal.

·        A child node is derived from a single parent. For constructing a CFL from a given CFG, a non-terminal is replaced by a suitable string at the RHS (if for a non-terminal, there are multiple productions). Each of the characters of the string is generating a node. That is, for every single node there is a single parent.

Because of the above-mentioned similarities, we can construct a parse tree or derivation tree of CFG only.

Note: If we talk about context-sensitive grammar as bB → aa or AA → B then since more than two elements are on the left side of the production it will not be possible to generate a parse tree as a parse tree has only a single parent node.

Consider the following examples.

 Also, Study about: 

• Mealy Machine
• Moore Machine
• Rice Theorem
• Brief about Turing Machine
• Multi Dimension Turing Machine
• Multiple Turing Machine
• Parikh Theorem in TOC
• Parse Tree or Derivation Tree
• What do you Understand by Derivation
• MyHill Nerode Theorem
• Minimize Myhill Nerode Theorem
• Push Down Automata
• Know Where we use Automata
• What do you understand by Derivation of Grammar
• What is Context-free Grammar
• Example based on CFG
• Regular Expression in TOC
• What is Two-way infinite Turing machine?
• Example to generate Parse tree from the given grammar

Also Read, some interview tips

• Why Should I Hire You?
• What are your weaknesses?
• What are your greatest strengths?
• Tell me about yourself.
• What's the reason behind leaving your current position at your company?
• Do You Know how the power of Keywords impacts on Resume?
• Top 8 Proofreading Tips and Techniques in 2022.
• Top Ten Technical Resume Writing Tips in 2022.
• Tips for your resume before you get entry to Job Market
• What Questions you can ask HR during the Interview.
• How to make an impressive resume?
• Best Resume writing Technique.
• What Questions you can ask HR during the Interview.