---
title: "Role of parse tree in CFG"
subject: "Theory of Computation"
chapter: 3
key: "semester_3/theory_of_computation:parse-tree-role"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/parse-tree-role
site: BCT Engineering
---

# Role of parse tree in CFG

Theory of Computation · Chapter 3: Context Free Grammar

- Asked in: 2074 Asoj
- Video: [Lec-48: Derivation Tree 🌲Parse Tree 🌲 with example in TOC & Compiler design](https://www.youtube.com/watch?v=nUVmsW68K0Y) — Gate Smashers
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/parse-tree-role
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-3

## Question

Mention the role of a parse tree in a context free grammar.

## Short answer

A parse tree shows the derivation structure of a string, proves membership in the language, hides derivation order, detects ambiguity (two trees for same string means ambiguous grammar), and is used in compilers for syntax analysis and code generation.

## Answer

A **parse tree** (derivation tree) of a CFG G = (V, T, P, S) is an ordered tree in which the root is labelled S, each interior node is a variable A with children X1 … Xk whenever A → X1…Xk is a production, and the leaves are terminals or ε. The **yield** (the leaves read left to right) is the derived string.

#### Roles of the parse tree
1. **Shows the structure of a string.** It displays how the string is derived from the start symbol, grouping the symbols into phrases. Example: for E → E+E | E*E | id the tree shows which operator is applied first.
2. **Proves membership.** A string is in L(G) if and only if it has a parse tree with root S and that yield. Derivations, recursive inference and parse trees are equivalent.
3. **Hides the order of derivation.** Many derivations (leftmost, rightmost, mixed) can correspond to one parse tree. The tree fixes the structure and ignores the order in which variables are replaced.
4. **Detects ambiguity.** A grammar is ambiguous if a string has two different parse trees. Comparing trees is the standard test.
5. **Basis of compilers.** In the syntax analysis phase of a compiler, the parser builds a parse tree for the source program. Meaning (semantics) and code generation follow the tree. Operator precedence and associativity are encoded by the tree shape.
6. **Used in proofs.** The pumping lemma for CFLs is proved by considering long paths in a parse tree: a variable repeats on the path, giving the pumpable substrings v and y.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. How does a parse tree help detect ambiguity in a grammar?
   A. A grammar is ambiguous if some string has two different parse trees
   B. A grammar is ambiguous if a string has two different derivations of any kind
   C. A grammar is ambiguous if the tree has more than one leaf
   D. A grammar is ambiguous if the yield is empty
   Answer: A. Different derivation orders can give the same tree, so ambiguity means two distinct parse trees for one string. (Key point: Ambiguity test)

2. What does a parse tree ignore about a derivation?
   A. Which production is used at each node
   B. The order in which variables are replaced
   C. The root label
   D. The terminals at the leaves
   Answer: B. Many leftmost, rightmost or mixed derivations correspond to one tree; the tree fixes structure, not replacement order. (Key point: Derivation order)

3. When is a string w in L(G) according to parse trees?
   A. When it labels some interior node
   B. When it has a parse tree whose root is any variable
   C. When it has a parse tree with root S and yield w
   D. When it has a unique derivation
   Answer: C. w is in L(G) iff there is a parse tree with root S whose leaves read left to right give w. (Key point: Yield and membership)

4. How does the pumping lemma for CFLs use parse trees?
   A. A variable must repeat on a long path, giving pumpable substrings v and y
   B. The tree must be a complete binary tree
   C. All leaves must be the same terminal
   D. The root must repeat on every path
   Answer: A. Long paths in the tree force a repeated variable, whose two occurrences give the pumpable parts v and y. (Key point: Use in pumping lemma)

## Related in Theory of Computation

- [CFG for aⁿb^(2n); parse tree](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acfg-an-b2n-parse-tree) — Theory of Computation, chapter 3, asked 2×
- [CFG for palindromes with parse trees](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acfg-palindrome-parse-trees) — Theory of Computation, chapter 3
- [Unrestricted grammar; superset of CFG](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Aunrestricted-grammar-explain) — Theory of Computation, chapter 4, asked 2×
- [CFG versus unrestricted grammar](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acfg-vs-unrestricted-grammar) — Theory of Computation, chapter 4
- [CFG for aᵐbⁿ with m ≥ n](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acfg-am-bn-m-ge-n) — Theory of Computation, chapter 3, asked 2×
- [Define CFG with example](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acfg-define-example) — Theory of Computation, chapter 3, asked 2×

## Related in other subjects

- [Context-sensitive, context-free, regular grammars](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Agrammar-types-context-sensitive-free-regular) — Discrete Structure, chapter 2