Automata Theory Questions and Answers – Construction and Yield of a Parse Tree

«
»

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Construction and Yield of a Parse Tree”.

1. The most suitable data structure used to represent the derivations in compiler:
a) Queue
b) Linked List
c) Tree
d) Hash Tables
View Answer

Answer: c
Explanation: The tree, known as “Parse tree” when used in a compiler, is the data structure of choice to represent the source program.
advertisement

2. Which of the following statement is false in context of tree terminology?
a) Root with no children is called a leaf
b) A node can have three children
c) Root has no parent
d) Trees are collection of nodes, with a parent child relationship
View Answer

Answer: a
Explanation: A node has atmost one parent, drawn above the node, and zero or more children drawn below. Lines connect parents to children. There is one node, one root, that has no parent; this node appears to be at the top of the tree. Nodes with no children are called leaves. Nodes that are not leaves are called interior nodes.

3. In which order are the children of any node ordered?
a) From the left
b) From the right
c) Arbitrarily
d) None of the mentioned
View Answer

Answer: a
Explanation: The children of a node are ordered from the left and drawn so. If N is to the left of node M, then all the descendents of N are considered to be to the left of all the descendents of M.
advertisement
advertisement

4. Which among the following is the root of the parse tree?
a) Production P
b) Terminal T
c) Variable V
d) Starting Variable S
View Answer

Answer: d
Explanation: The root is labelled by the start symbol. All the leaves are either labelled by a a terminal or with e.

5. For the expression E*(E) where * and brackets are the operation, number of nodes in the respective parse tree are:
a) 6
b) 7
c) 5
d) 2
View Answer

Answer: b
Explanation:The number of nodes in the respective parse tree is 7
advertisement

6. The number of leaves in a parse tree with expression E*(E) where * and () are operators
a) 5
b) 2
c) 4
d) 3
View Answer

Answer: a
Explanation: The number of leaves in parse tree with expression E*(E) where * & () are operators is 5

7. Which of the following does the given parse tree correspond to?
The following is a parse tree for the production 0110 over {0,1}*
a) P->1100
b) P->0110
c) P->1100ε
d) P->0101
View Answer

Answer: b
Explanation: The following is a parse tree for the production 0110 over {0,1}*.
advertisement

8. A grammar with more than one parse tree is called:
a) Unambiguous
b) Ambiguous
c) Regular
d) None of the mentioned
View Answer

Answer: b
Explanation: A context free grammar G is ambiguous if there is at least one string in L(G) having two or more distinct derivation trees or equivalently, two or more distinct leftmost derivations.

9. __________ is the acyclic graphical representation of a grammar.
a) Binary tree
b) Oct tree
c) Parse tree
d) None of the mentioned
View Answer

Answer: c
Explanation: In order to graphically represent a derivation of a grammar we need to use parse trees.
advertisement

10. Grammar is checked by which component of compiler?
a) Scanner
b) Parser
c) Semantic Analyzer
d) None of the mentioned
View Answer

Answer: b
Explanation: Parser or syntax analyzer is the one responsible for checking the grammar and reporting errors. In this phase, parse tree is generated and syntax is analyzed.

Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, 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 & technical discussions at Telegram SanfoundryClasses.