Parse Tree Multiple Choice Questions and Answers (MCQs)

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

Answer: a
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

Answer: a
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?
Parse tree of expression p & q % r % s & t & u
a) % has lower precedence than &
b) % is right associative
c) & has lower precedence than %
d) & is left associative
View Answer

Answer: c
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 %.
advertisement
advertisement

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

Answer: a
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

Answer: a
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.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

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) Parse tree having + as the highest precedence
b) Parse tree having - as the highest precedence
c) Parse tree
d) Parse tree with expression
View Answer

Answer: a
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

Answer: a
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.
advertisement

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

Answer: b
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

Answer: a
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.
advertisement

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

Answer: b
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.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.