GATE CS 2015 Set 2 Q.24 (CS Q.14): Intermediate Code Generation, Data Flow Analysis and Code Optimization

In the context of abstract-syntax-tree (AST) and control-flow-graph (CFG), which one of the following is TRUE?

In both AST and CFG, let node $N_2$ be the successor of node $N_1$ . In the input program, the code corresponding to $N_2$ is present after the code corresponding to $N_1$

For any input program, neither AST nor CFG will contain a cycle

The maximum number of successors of a node in an AST and a CFG depends on the input program

Each node in AST and CFG corresponds to at most one statement in the input program

Official answer and solution

Official answer: C
From: Official GATE 2015 answer key

Solution

Analyze the topological properties and structural constraints of Abstract Syntax Trees and Control Flow Graphs.

Evaluate the choices:

(A) In a CFG, loops create back-edges where successor node $N_2$ can appear earlier in the program source than predecessor $N_1$ . Thus, statement A is false.
(B) A CFG for a program with loops (e.g., while, for, or goto) contains directed cycles. Thus, statement B is false.

(C) 'The maximum number of successors of a node in an AST and a CFG depends on the input program.'
- In an AST, a node representing an $n$ -ary operator or a function call with $n$ arguments has $n$ child nodes (successors), which depends arbitrarily on the input program syntax.
- In a CFG, a basic block ending in an $n$ -way switch statement has $n$ successor basic blocks, which also directly depends on the input program.
  Hence, statement C is true.

(D) In a CFG, each node is typically a basic block containing multiple statements. Thus, statement D is false.

Final answer

Common trap

Assuming CFG nodes are restricted to at most 2 successors (as in binary if-else branches), overlooking switch statements.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2015 Computer Science and Information Technology (CS) Session 2
Question: 24 of 65, printed as CS Q.14
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source