In the context of abstract-syntax-tree (AST) and control-flow-graph (CFG),…
2015
In the context of abstract-syntax-tree (AST) and control-flow-graph (CFG), which one of the following is TRUE?
- A.
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\) - B.
For any input program, neither AST nor CFG will contain a cycle
- C.
The maximum number of successors of a node in an AST and a CFG depends on the input program
- D.
Each node in AST and CFG corresponds to at most one statement in the input program
Attempted by 58 students.
Show answer & explanation
Correct answer: C
Answer: The maximum number of successors of a node in an AST and a CFG depends on the input program.
Why this is true:
For the CFG: The out-degree of nodes depends on control constructs present in the program. Simple linear code yields nodes with one successor, conditionals can create two successors, switch statements can create many successors, and loops/gotos affect connectivity—so the maximum out-degree observed depends on which constructs appear.
For the AST: The number of children of a node depends on the syntactic constructs used in the program. Some node types have fixed arity (e.g., a binary operator has two children), while others (e.g., a function-call node) may have a variable number of children depending on how many arguments the program uses. Thus the maximum child count seen in a particular AST depends on the program.
Note: grammar or IR conventions can impose per-node-type bounds, but the observed maximum node degree in a specific AST or CFG varies with the input program, which is why the statement is true.