This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Parse Tree”.
1. Which of the following is correct with respect to a parse tree for a given grammar?
a) n parse tree = n leftmost derivation tree = n rightmost derivation tree
b) n parse tree = n leftmost derivation tree
c) n parse tree = n rightmost derivation tree
d) n parse tree = n non-terminals
View Answer
Explanation: For a given string, if more than one parse tree exists, then their equivalent leftmost derivation tree and rightmost derivation tree also exists. A grammar that generates more than one parse tree is called an ambiguous grammar.
2. Which data structure is used in the syntax analysis phase of the compiler?
a) Tree
b) Stack
c) Linked List
d) Queue
View Answer
Explanation: Tree data structure in the form of a parse tree is used in the syntax analysis phase of the compiler. It is used to represent the source program in compiler. The given input string and pre-defined grammar are used to construct the parse tree.
3. Parse tree for the expression p & q % r % s & t & u is given below. Which of the following is correct for the given parse tree?
a) % has lower precedence than &
b) % is right associative
c) & has lower precedence than %
d) & is left associative
View Answer
Explanation: According to the given parse tree, % will be evaluated first. So % has higher precedence than & and is left-associative. In the sub-expression s & t & u, (t & u) will be evaluated first. Hence, & is right-associative and has lower precedence than %.
4. Suppose X is the starting symbol of the given grammar with the following transition rules. Compute the value of X as the root of the parse tree for the expression: 3 & 4 % 7.
X → X1 & B | B {X.value = X1.value + B.value, X.value = B.value}
B → B1 % D | D {B.value = B1.value * D.value, B.value = D.value}
D → num {D.value = num.value}
a) 31
b) 32
c) 33
d) 34
View Answer
Explanation: According to the semantic rules given in the question, & is equivalent to + and % is equivalent to *. * has higher precedence than +, because % is far from the starting symbol. Both % and & are left-associative. Hence, we can solve the expression as (3 + (4 * 7)) = 31.
5. In parse trees, every internal node represents a non-terminal and every leaf node represents a terminal.
a) True
b) False
View Answer
Explanation: For an expression represented by a parse tree, every internal node represents a grammar rule. Terminals are represented by the children of the node. The right-hand side of any production in grammar is represented by the children of a node.
6. Consider two arithmetic operators + and –. The precedence of + is higher than that of –. + is right-associative whereas – is left-associative. Which of the following parse tree represents the expression (2 – 4 + 6 + 8 -1)?
a) 
b) 
c) 
d) 
View Answer
Explanation: + has the highest precedence, the sub-expression (4 + 6 + 8) will be evaluated first. Since + is right associative, 6 + 8 will be evaluated first. Hence, the expression will be evaluated as ((2 – (4 + (6 + 8))) – 2).
7. Parse tree is constructed from the tokens produced by lexical analyzer.
a) True
b) False
View Answer
Explanation: Lexical analyzer generates token streams as output and is given to syntax analyzer as input. Here the source code is analyzed and using the input string and the production rules parse tree is constructed.
8. Assume +, -, * are usual arithmetic operators. * has the lowest precedence, + has the highest precedence and the precedence of – is medium. + and * are left-associative whereas – is right-associative. What is the value of the expression 3 – 8 + 2 – 9 * 3?
a) 4
b) 6
c) 8
d) 10
View Answer
Explanation: + has the highest precedence.
= 3 – 8 + 2 – 9 * 3
= 3 – 10 – 9 * 3
= 3 – 1 * 3
= 2 * 3
= 6
Hence, the value of the given expression is 6.
9. Which among the following best represents the computational complexity of GLR parsing?
a) O(|G| x n)
b) O(|G|2 x n)
c) O(|G| x n2)
d) O(|G|2 x n2)
View Answer
Explanation: The best computational complexity of GLR parsing is given by the Tomita parsing algorithm. Let us consider that |G| is the size of the grammar and n is the length of the string to be parsed, then the maximum time required by the algorithm is O(|G| x n). It is an adaption of Knuth’s algorithm.
10. While evaluating the parse tree, which traversal technique is used to give the original input string?
a) Pre-order traversal
b) In-order traversal
c) Post-order traversal
d) Breadth-first traversal
View Answer
Explanation: To evaluate an expression in the parse tree, in-order traversal technique is used to give the original input string. The precedence of the operators is followed by a parse tree. The operator in the sub-tree has higher precedence than the operator in the parent node. Hence, the innermost sub-tree is evaluated first.
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 Programming MCQs
- Check Computer Science Books
- Practice Computer Science MCQs
- Check Data Structure Books
- Check Programming Books
