# 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
c) Tree
d) Hash Tables

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

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

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

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.

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

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

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

7. Which of the following does the given parse tree correspond to? a) P->1100
b) P->0110
c) P->1100ε
d) P->0101

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

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

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

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

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

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. 