This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Abstract Syntax Tree”.
1. Which tree traversal technique is used to evaluate the expression represented by syntax tree?
a) Pre-order traversal
b) In-order traversal
c) Post-order traversal
d) Breadth first traversal
View Answer
Explanation: Post-order traversal is used to navigate the syntax tree in order to evaluate the expression represented by the tree. It starts from the root node and visits the children of each node from left to right recursively. It is a special case of depth first traversal.
2. Which pattern is used to evaluate abstract syntax tree?
a) Visitor pattern
b) Singleton Pattern
c) Proxy pattern
d) Adapter pattern
View Answer
Explanation: Visitor pattern allows you to add methods to classes of different types without alteration to those classes. It also allows you to define external classes that can extend other classes. Visitor pattern is used to evaluate abstract syntax tree.
3. Abstract syntax tree is an input to which phase of compiler?
a) Lexical analysis
b) Syntax Analysis
c) Semantic Analysis
d) Intermediate code generation
View Answer
Explanation: An abstract syntax tree is the output of the parser, the second phase i.e. syntax analysis and it forms an input to semantic analysis phase of the compiler. To determine semantic correctness of declarations and statements written in program, semantic analysis is performed.
4. Which of the following expression can be represented by the given syntax tree?
a) 7 + (3 * 5)
b) 7 * (3 + 5)
c) (7 * 3) + 5
d) (7 + 3) * 5
View Answer
Explanation: Step-1: Evaluating the left sub-tree: Since, no operation is performed the value is 7.
Step-2: Evaluating the right sub-tree: (3 * 5)
Step-3: Applying the root operation: 7 + (3 * 5)
5. In an abstract syntax tree, each internal node represents an operand and each leaf node represents an operator.
a) True
b) False
View Answer
Explanation: For an expression represented by an abstract syntax tree, each internal node represents an operator. The operands of the operator are represented by the children of the node. A grammar rule can’t be represented by an internal node in syntax tree.
6. Consider the given syntax tree. Assume that division has the lowest precedence than addition, subtraction and multiplication. Addition and subtraction have the same precedence but more than multiplication. Which of the following expression can be given by the following syntax tree?
a) [5 / (p + q) * (q – r)]
b) [5 * (p + q) / (q – r)]
c) [5 + (p + q) * (q – r)]
d) [5 / (p + q) + (q – r)]
View Answer
Explanation: The root represents the operator /. The subtrees of the root represent the subexpressions 5, (p + q) and (q – r). The grouping of (p + q) and (q – r) as an operand reflects the left to right evaluation of the operators at the same precedence level. Since +, – have the same precedence and * has higher precedence p + q * q – r is equivalent to (p + q) * (q – r). The correct expression is [5 / (p + q) * (q – r)].
7. Syntax trees are comparatively denser than parse trees.
a) True
b) False
View Answer
Explanation: Syntax trees are called abstract syntax trees because they do not represent all the precise information from the real syntax of the program. Syntax trees are dense in comparison with parse tree, for constructing the same language.
8. Assume +, -, *, / are usual arithmetic operator, + has highest precedence and right associative and -, *, / have equal precedence and left associative. What is the output of the expression 23 * 3 – 6 + 11 – 2 * 8 / 4?
a) 110
b) 100
c) 130
d) 120
View Answer
Explanation: Parenthesizing the given expression we get (((((23 * 3) – (6 + 11)) – 2 ) * 8) / 4).
Equivalent postfix expression is: 23 3 * 6 11 + – 2 – 8 * 4 /
Evaluation can be done as follows-
• Start reading the expression from left to right, and perform the following steps-
1.If operand comes, push into the stack.
2.If operator comes, pop the topmost 2 elements from the stack and perform the operation between them.
3.Whatever result we get, push it again into the stack.
By following the above procedure, we get-
Hence, the output of the given expression is 100.
9. Which of the following is an application of abstract syntax tree?
a) Static code analyzing
b) Implement indexing in databases
c) Used for dynamic memory allocation
d) To represent networks of communication
View Answer
Explanation: Abstract syntax trees are used to analyze static code whereas B-trees are used to implement indexing in the database. Dynamic memory allocation is the application of linked list and graph is used to represent networks of communication.
10. Which parsing approach is followed by syntax tree?
a) Top-down parsing
b) Bottom-up parsing
c) Predictive parsing
d) Shift reduce parsing
View Answer
Explanation: Abstract Syntax Tree follows bottom-up parsing, it is the process of reducing the input string to start symbol. The syntax tree is constructed starting from the non-terminals and ends on the start symbol. To reach the start symbol, we apply production rules to find a rightmost derivation of string in reverse manner.
Sanfoundry Global Education & Learning Series – Data Structure.
To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Practice Computer Science MCQs
- Apply for Computer Science Internship
- Check Programming Books
- Practice Design & Analysis of Algorithms MCQ
- Check Data Structure Books
