GATE CSE 2015 Set 2 | Question: 14

Question

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

Comments

https://eli.thegreenplace.net/2009/02/16/abstract-vs-concrete-syntax-trees

---

What does the line  the maximum number of nodes in ana AST and a CFG depend on input program  SAY in what sense do they mean

---

vishalshrm539 i dont think so ...cause for example for the code “a+b” for AST of this a will be a succesor of + but it’s appearing before + in the code {this is assuming that by "successor" we mean child of a node cause i dont think we can use "successor" defination used in context of BST here}

Answer 1

Option (C) is Correct

• A. is false , In CFG , code of $N_2$ may be present before $N_1$ when there is a loop or Goto.
• B. is false , CFG contains cycle when input program has loop.
• C. is true ,successors in AST and CFG depend on Input program. 
• D. is false, In CFG a single node may belong to a block of statements.

Comments

Can u plz explain what is the meaning of successor in AST and CFG , couldn't get this meaning .

---

Successors are Descendents.   

When there is an edge from  A to B then :

          B is a successor of A.

---

So in case of CFG we have a descendant only when the node is next instruction to it , How can u prove stmt A to be false ,plz give one instance .

---

https://gateoverflow.in/8139/gate2015-2_29

Here 2 is a successor of 10,11 and vice-versa

---

Ya thankss got that point ,just one confusion that when we talk about AST then in that case we draw a syntax tree for deriving the expression so then what about successor for that ,actually I am seriously confused a bit in this terminology .

---

When there is an edge from  A to B then :

          B is a successor of A.

 So, for AST also it is valid ,take any AST example.

---

Ya that is true but it is in terms of the production rules that we use while building the syntax tree not related to occurence of instructions in any order

---

Option A , is false even if it is False for cfg.

---

Is CFG  also called Program control graph...?

---

Are they in syllabus now ?

 

Anyone give an example of option d.... In CFG a single node may belong to a block of statements.

---

nice explanation Himanshu

---

I don't think these topics are in syllabus now.

---

they are in syllabus.

---

AST was always in syllabus. CFG is also in syllabus due to newly added code optimization section.