Syntax tree representation in Compiler Design - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the purpose of a syntax tree

What is the main purpose of a syntax tree in compiler design?

A To represent the hierarchical syntactic structure of source code

B To execute the program instructions directly

C To store the compiled machine code

D To optimize the hardware performance

💡 Hint

Think about how a compiler understands the structure of code before translating it.

A syntax tree shows how the source code is structured according to the grammar rules. It helps the compiler understand the code's meaning.

📋 Factual

intermediate

Types of syntax trees

Which of the following correctly distinguishes between a parse tree and an abstract syntax tree (AST)?

A A parse tree is used only for optimization; an AST is used only for parsing

B An AST includes all grammar details; a parse tree simplifies by removing unnecessary nodes

C Both trees are identical in structure and detail

D A parse tree includes all grammar details; an AST simplifies by removing unnecessary nodes

💡 Hint

Consider which tree is more detailed and which one is more abstract.

A parse tree shows every detail from the grammar, including all tokens and rules. An AST removes extra details to focus on the essential structure.

🔍 Analysis

advanced

Analyzing syntax tree node types

Given a syntax tree for the expression 3 + 4 * 5, which node correctly represents the root of the tree?

A A node representing the number 3

B A node representing the '+' operator

C A node representing the '*' operator

D A node representing the number 5

💡 Hint

Remember operator precedence: multiplication happens before addition.

The root node represents the last operation performed, which is addition. Multiplication is a child node because it happens first.

❓ Comparison

advanced

Comparing tree representations

Which statement correctly compares the memory usage of a parse tree and an abstract syntax tree (AST) for the same source code?

A Memory usage depends only on the programming language, not the tree type

B The AST uses more memory because it stores additional semantic information

C The parse tree uses more memory because it stores all grammar details including terminals and non-terminals

D Both trees use the same amount of memory since they represent the same code

💡 Hint

Think about how much detail each tree keeps.

Parse trees keep every detail from the grammar, so they are larger. ASTs remove unnecessary nodes, making them smaller and more efficient.

❓ Reasoning

expert

Reasoning about syntax tree transformations

Why do compilers transform a parse tree into an abstract syntax tree (AST) before further processing?

A To simplify the structure by removing redundant nodes, making semantic analysis and optimization easier

B To increase the number of nodes for detailed error checking

C To store the source code as plain text for debugging

D To convert the code directly into machine language

💡 Hint

Consider what makes later compiler stages more efficient.

Transforming to an AST removes unnecessary details, focusing on the essential structure. This helps semantic analysis and optimization run more smoothly.

Practice

1. What is the main purpose of a syntax tree in compiler design?

easy

A. To manage memory allocation during runtime

B. To execute the program directly

C. To represent the structure of source code clearly

D. To store compiled machine code

Solution

1. Step 1: Understand the role of syntax trees

   Syntax trees break down source code into parts showing its structure clearly.

2. Step 2: Compare with other compiler tasks

   Execution, machine code storage, and memory management are handled by other compiler stages, not syntax trees.

3. Final Answer:

   To represent the structure of source code clearly -> Option C

4. Quick Check:

   Syntax tree = code structure [OK]

Hint: Syntax trees show code parts and structure clearly [OK]

Common Mistakes:

• Confusing syntax tree with execution or memory management
• Thinking syntax trees store machine code
• Assuming syntax trees run the program

2. Which of the following is the correct way to represent the expression a + b * c in a syntax tree?

easy

A. Root node '+' with left child 'a' and right child '*' having children 'b' and 'c'

B. Root node '*' with left child '+' and right child 'c', '+' having children 'a' and 'b'

C. Root node '+' with children 'a', 'b', and 'c' directly

D. Root node 'a' with children '+' and '*'

Solution

1. Step 1: Recall operator precedence

   Multiplication (*) has higher precedence than addition (+), so '*' is evaluated before '+'.

2. Step 2: Build the tree respecting precedence

   The root is '+', left child is 'a', right child is '*', which has 'b' and 'c' as children.

3. Final Answer:

   Root node '+' with left child 'a' and right child '*' having children 'b' and 'c' -> Option A

4. Quick Check:

   Operator precedence guides tree structure [OK]

Hint: Remember operator precedence to build syntax trees [OK]

Common Mistakes:

• Ignoring operator precedence and ordering nodes incorrectly
• Placing all operands as direct children of root
• Confusing node roles and children

3. Given the syntax tree for the expression (x - y) / z, what is the correct preorder traversal output?

medium

A. - / x y z

B. / - x y z

C. / x - y z

D. - x y / z

Solution

1. Step 1: Understand preorder traversal

   Preorder visits root first, then left subtree, then right subtree.

2. Step 2: Apply preorder to the tree

   Root is '/', left child is '-', with children 'x' and 'y', right child is 'z'. So traversal is '/ - x y z'.

3. Final Answer:

   / - x y z -> Option B

4. Quick Check:

   Preorder = root-left-right [OK]

Hint: Preorder = root, left, right traversal order [OK]

Common Mistakes:

• Mixing traversal orders (inorder, postorder)
• Visiting children before root in preorder
• Confusing node positions in tree

4. Identify the error in this syntax tree representation of the expression a + (b * c: The tree has '+' as root, 'a' as left child, and '*' as right child with children 'b' and 'c'.

medium

A. Operator '*' should be root instead of '+'

B. The tree correctly represents the expression

C. Operands 'b' and 'c' should be swapped

D. Missing closing parenthesis causes incomplete tree

Solution

1. Step 1: Check expression syntax

   The expression has an opening parenthesis '(' but no closing ')', making it incomplete.

2. Step 2: Analyze tree correctness

   The tree structure matches the intended expression but the missing ')' means the expression is invalid, so the tree is incomplete.

3. Final Answer:

   Missing closing parenthesis causes incomplete tree -> Option D

4. Quick Check:

   Unmatched parentheses cause syntax tree errors [OK]

Hint: Check parentheses balance before building syntax tree [OK]

Common Mistakes:

• Assuming tree is correct despite syntax errors
• Confusing operator precedence with syntax errors
• Ignoring unmatched parentheses

5. How would you represent the nested expression (a + b) * (c - d) as a syntax tree to correctly reflect operator precedence and grouping?

hard

A. Root '*' with left child '+' (children 'a', 'b') and right child '-' (children 'c', 'd')

B. Root '+' with children 'a', 'b', '*', 'c', 'd'

C. Root '-' with left child '*' and right child '+'

D. Root '*' with children 'a', 'b', 'c', 'd' directly

Solution

1. Step 1: Identify operator precedence and grouping

   Parentheses force addition and subtraction to happen before multiplication.

2. Step 2: Build tree respecting groups

   Root is '*', left subtree is '+' with 'a' and 'b', right subtree is '-' with 'c' and 'd'.

3. Final Answer:

   Root '*' with left child '+' (children 'a', 'b') and right child '-' (children 'c', 'd') -> Option A

4. Quick Check:

   Parentheses define subtree grouping in syntax tree [OK]

Hint: Use parentheses to group subtrees in syntax tree [OK]

Common Mistakes:

• Ignoring parentheses and operator precedence
• Placing all operands as direct children of root
• Mixing operator positions in tree