Parse trees and derivations MCQs

By: Prof. Dr. Fazal Rehman Shamil | Last updated: September 23, 2024

A parse tree is:

A) A tree representation of a regular expression.
B) A tree that shows how a string is derived from a context-free grammar.
C) A tree used in the minimization of DFAs.
D) A tree that represents the transitions of a Turing machine.
Answer: B

In a parse tree, each internal node represents:

A) An input symbol.
B) A non-terminal symbol.
C) A terminal symbol.
D) A state in a DFA.
Answer: B

In a parse tree, each leaf node represents:

A) An input symbol.
B) A non-terminal symbol.
C) A terminal symbol.
D) A production rule.
Answer: C

The root of a parse tree represents:

A) The start symbol of the grammar.
B) A terminal symbol.
C) The first production rule used.
D) The last production rule used.
Answer: A

Which of the following is true about leftmost derivation?

A) It replaces the rightmost non-terminal at each step.
B) It replaces the leftmost non-terminal at each step.
C) It replaces all non-terminals simultaneously.
D) It always leads to a right parse tree.
Answer: B

Which of the following is true about rightmost derivation?

A) It replaces the rightmost non-terminal at each step.
B) It replaces the leftmost non-terminal at each step.
C) It replaces all non-terminals simultaneously.
D) It always leads to a left parse tree.
Answer: A

In a parse tree, what does a node with children represent?

A) A terminal symbol.
B) A production rule application.
C) A start symbol.
D) An input string.
Answer: B

Which of the following statements is true about derivations in context-free grammars?

A) Leftmost and rightmost derivations always yield different parse trees.
B) Leftmost and rightmost derivations may yield the same parse tree.
C) Leftmost derivations are used only in ambiguous grammars.
D) Rightmost derivations are used only in unambiguous grammars.
Answer: B

Which of the following is a necessary condition for a grammar to be ambiguous?

A) It generates more than one parse tree for some string.
B) It generates no parse tree for some string.
C) It has left recursion.
D) It has right recursion.
Answer: A

Which of the following grammars is ambiguous?

A) S → aS | ε
B) S → aSb | ε
C) S → SS | a
D) S → aSbS | ε
Answer: C

In a context-free grammar, if a string has more than one parse tree, the grammar is:

A) Ambiguous
B) Unambiguous
C) Regular
D) Context-sensitive
Answer: A

Which type of derivation is typically used to construct a parse tree?

A) Leftmost derivation
B) Rightmost derivation
C) Both leftmost and rightmost derivations
D) Parallel derivation
Answer: A

In a parse tree, if a node has a non-terminal symbol, its children can be:

A) Only terminal symbols.
B) Only non-terminal symbols.
C) Both terminal and non-terminal symbols.
D) Only the start symbol.
Answer: C

The yield of a parse tree is:

A) The sequence of terminal symbols from the root to the leaves.
B) The sequence of non-terminal symbols from the root to the leaves.
C) The sequence of terminal symbols from the leftmost leaf to the rightmost leaf.
D) The sequence of non-terminal symbols from the leftmost leaf to the rightmost leaf.
Answer: C

If a context-free grammar is unambiguous, then:

A) Every string in the language has a unique parse tree.
B) No string in the language has a parse tree.
C) Every string in the language has more than one parse tree.
D) The grammar must be left-recursive.
Answer: A

In a derivation tree (parse tree), an interior node labeled with a non-terminal A and having children labeled with B1, B2, …, Bn represents:

A) The production A → B1B2…Bn
B) The production B1B2…Bn → A
C) The production A → ε
D) The production A → BnB(n-1)…B1
Answer: A

Which of the following statements is false about a parse tree?

A) It uniquely represents a derivation of a string.
B) It provides a hierarchical structure of the derivation.
C) It can have multiple root nodes.
D) It can be used to determine if a grammar is ambiguous.
Answer: C

Which of the following can be used to check the syntax of a programming language?

A) Deterministic Finite Automata
B) Pushdown Automata
C) Parse Tree
D) Regular Expressions
Answer: C

In the context of context-free grammars, which of the following is true?

A) Every regular language has a context-free grammar.
B) Every context-free language has a regular grammar.
C) Every context-free language is unambiguous.
D) Every context-free grammar generates a regular language.
Answer: A

A derivation in a context-free grammar is called leftmost if:

A) At each step, the leftmost non-terminal is replaced.
B) At each step, the rightmost non-terminal is replaced.
C) All non-terminals are replaced simultaneously.
D) Only terminal symbols are replaced.
Answer: A

What is the primary purpose of using a parse tree in syntax analysis?

A) To minimize the number of states in a DFA.
B) To visually represent the syntactic structure of a string.
C) To convert a regular expression to a DFA.
D) To eliminate left recursion in a grammar.
Answer: B

Which type of derivation corresponds to the depth-first traversal of a parse tree?

A) Leftmost derivation
B) Rightmost derivation
C) Breadth-first derivation
D) In-order traversal
Answer: A

In a parse tree, the leaves represent:

A) Production rules
B) Non-terminal symbols
C) Terminal symbols
D) Start symbols
Answer: C

If a context-free grammar has both left and right recursion, it is likely to be:

A) Unambiguous
B) Ambiguous
C) Regular
D) Context-sensitive
Answer: B

In context-free grammar, epsilon (ε) represents:

A) A terminal symbol
B) A non-terminal symbol
C) An empty string
D) A production rule
Answer: C

Which of the following derivation methods is used in bottom-up parsing?

A) Leftmost derivation
B) Rightmost derivation
C) Both leftmost and rightmost derivations
D) None of the above
Answer: B

 

Related Posts: