What is a parse tree?
a) A graphical representation of the syntax of a string according to a grammar
b) A list of all terminal symbols in a grammar
c) A set of rules for generating strings
d) A sequence of terminal symbols
Answer: a) A graphical representation of the syntax of a string according to a grammar
What does a derivation in a context-free grammar represent?
a) The process of generating a string from the start symbol using production rules
b) The process of parsing a string to check if it belongs to a language
c) The process of defining terminal symbols
d) The process of identifying non-terminal symbols
Answer: a) The process of generating a string from the start symbol using production rules
Which of the following is true about parse trees?
a) They show the hierarchical structure of a string according to a CFG
b) They represent only the terminal symbols in a string
c) They are used to describe regular expressions
d) They only show the sequence of terminal symbols in a string
Answer: a) They show the hierarchical structure of a string according to a CFG
In a parse tree, what does each internal node represent?
a) A non-terminal symbol
b) A terminal symbol
c) A production rule
d) A string of terminal symbols
Answer: a) A non-terminal symbol
What does each leaf node in a parse tree represent?
a) A terminal symbol
b) A non-terminal symbol
c) A production rule
d) A grammar rule
Answer: a) A terminal symbol
Which of the following is NOT true about derivations?
a) They can be leftmost or rightmost derivations
b) They represent the process of generating a string from the start symbol
c) They show the hierarchical structure of a string
d) They can be used to generate multiple strings from the same start symbol
Answer: c) They show the hierarchical structure of a string
What is the difference between a leftmost and a rightmost derivation?
a) A leftmost derivation always replaces the leftmost non-terminal, while a rightmost derivation replaces the rightmost non-terminal
b) A leftmost derivation replaces the rightmost non-terminal, while a rightmost derivation replaces the leftmost non-terminal
c) A leftmost derivation replaces the terminal symbols first, while a rightmost derivation replaces non-terminals first
d) There is no difference between leftmost and rightmost derivations
Answer: a) A leftmost derivation always replaces the leftmost non-terminal, while a rightmost derivation replaces the rightmost non-terminal
What does the term ‘derivation sequence’ refer to?
a) The sequence of production rules applied to derive a string from the start symbol
b) The sequence of terminal symbols in the final string
c) The sequence of non-terminal symbols in a parse tree
d) The sequence of parse trees generated from a string
Answer: a) The sequence of production rules applied to derive a string from the start symbol
Which of the following statements is true about parse trees and derivations?
a) Every valid string generated by a CFG has a corresponding parse tree
b) Every parse tree generates multiple strings
c) Every derivation results in an ambiguous parse tree
d) Parse trees and derivations are unrelated concepts
Answer: a) Every valid string generated by a CFG has a corresponding parse tree
In a parse tree, what does the root node represent?
a) The start symbol of the grammar
b) A terminal symbol
c) A production rule
d) A leaf node
Answer: a) The start symbol of the grammar
What is an ambiguous grammar?
a) A grammar that can generate a string with more than one parse tree
b) A grammar that generates strings in a specific order
c) A grammar that only generates terminal symbols
d) A grammar that has no terminal symbols
Answer: a) A grammar that can generate a string with more than one parse tree
Which type of derivation is used by a top-down parser?
a) Leftmost derivation
b) Rightmost derivation
c) Both leftmost and rightmost derivations
d) None of the above
Answer: a) Leftmost derivation
Which type of derivation is used by a bottom-up parser?
a) Rightmost derivation
b) Leftmost derivation
c) Both leftmost and rightmost derivations
d) None of the above
Answer: a) Rightmost derivation
In a parse tree, what does each branch represent?
a) A production rule applied during derivation
b) A terminal symbol
c) A non-terminal symbol
d) A grammar rule
Answer: a) A production rule applied during derivation
What is the primary purpose of constructing parse trees?
a) To understand the syntactic structure of strings
b) To simplify terminal symbols
c) To define new production rules
d) To eliminate non-terminals
Answer: a) To understand the syntactic structure of strings
Which parsing technique uses parse trees to verify if a string belongs to a language?
a) Top-down parsing
b) Bottom-up parsing
c) Both top-down and bottom-up parsing
d) Regular expression parsing
Answer: c) Both top-down and bottom-up parsing
In which of the following situations is a parse tree useful?
a) When checking if a string adheres to a given grammar
b) When defining new terminal symbols
c) When calculating the length of a string
d) When sorting terminal symbols
Answer: a) When checking if a string adheres to a given grammar
Which property of a parse tree is essential for validating a string in context-free grammars?
a) The tree must represent the correct hierarchical structure according to the CFG
b) The tree must have an equal number of terminal and non-terminal symbols
c) The tree must be balanced
d) The tree must contain no duplicate symbols
Answer: a) The tree must represent the correct hierarchical structure according to the CFG
What is a ‘rightmost derivation’?
a) A derivation in which the rightmost non-terminal is replaced first
b) A derivation in which the leftmost non-terminal is replaced first
c) A derivation in which all terminal symbols are replaced first
d) A derivation in which all non-terminals are replaced at once
Answer: a) A derivation in which the rightmost non-terminal is replaced first
What is the role of non-terminal symbols in a parse tree?
a) To represent intermediate steps in the derivation process
b) To represent the final output string
c) To act as leaf nodes in the tree
d) To specify the order of terminal symbols
Answer: a) To represent intermediate steps in the derivation process
What does an ’empty string’ (ε) in a derivation signify?
a) A production rule that leads to no additional symbols
b) The end of a derivation sequence
c) The start of a derivation sequence
d) A terminal symbol
Answer: a) A production rule that leads to no additional symbols
In a context-free grammar, which of the following does NOT affect the parse tree structure?
a) The order of production rules
b) The grammar’s start symbol
c) The choice of terminals in the string
d) The choice of non-terminals in the grammar
Answer: c) The choice of terminals in the string
What is a derivation tree?
a) A tree representing the sequence of production rules applied during a derivation
b) A tree representing only the terminal symbols in a string
c) A list of all possible parse trees for a string
d) A tree representing only non-terminal symbols
Answer: a) A tree representing the sequence of production rules applied during a derivation
What does it mean if a string has multiple parse trees?
a) The grammar is ambiguous
b) The string is invalid according to the grammar
c) The string has only one valid parse tree
d) The string cannot be generated by the grammar
Answer: a) The grammar is ambiguous
Which of the following statements is true for a valid parse tree?
a) It must start with the start symbol and expand to the terminal string
b) It can start with any terminal symbol and expand to non-terminals
c) It can end with any non-terminal symbol and not require expansion
d) It can have multiple start symbols
Answer: a) It must start with the start symbol and expand to the terminal string
What does the ‘height’ of a parse tree represent?
a) The number of levels in the parse tree
b) The number of terminal symbols in the string
c) The number of non-terminal symbols in the tree
d) The depth of the leftmost branch
Answer: a) The number of levels in the parse tree
Which of the following is NOT a component of a parse tree?
a) Root node
b) Leaf nodes
c) Branches
d) Derivation steps
Answer: d) Derivation steps
Which parsing technique is associated with constructing parse trees from top to bottom?
a) Top-down parsing
b) Bottom-up parsing
c) Left-to-right parsing
d) Right-to-left parsing
Answer: a) Top-down parsing
Which parsing technique is associated with constructing parse trees from bottom to top?
a) Bottom-up parsing
b) Top-down parsing
c) Left-to-right parsing
d) Right-to-left parsing
Answer: a) Bottom-up parsing
What is the significance of the leftmost and rightmost derivations in parsing?
a) They determine the parsing strategy (top-down or bottom-up)
b) They define the terminal symbols in the grammar
c) They help in converting CFGs to regular expressions
d) They eliminate ambiguity in parse trees
Answer: a) They determine the parsing strategy (top-down or bottom-up)
In a parse tree, what is the role of a production rule?
a) To define the relationship between non-terminal symbols
b) To represent the hierarchical structure of terminal symbols
c) To show the derivation of terminal symbols
d) To link non-terminal symbols to their derivations
Answer: d) To link non-terminal symbols to their derivations
How is an ambiguous grammar typically resolved?
a) By transforming it into an unambiguous grammar
b) By adding more non-terminal symbols
c) By simplifying the production rules
d) By removing terminal symbols
Answer: a) By transforming it into an unambiguous grammar
What is the key characteristic of a derivation in a context-free grammar?
a) It must follow the production rules to generate a valid string
b) It must produce only terminal symbols
c) It must use only non-terminal symbols
d) It must be left-recursive
Answer: a) It must follow the production rules to generate a valid string
Which of the following is a common use of parse trees?
a) Syntax checking and validation of strings
b) Generating random strings
c) Optimizing grammar rules
d) Defining new terminal symbols
Answer: a) Syntax checking and validation of strings
What does ‘left-recursion’ refer to in the context of parse trees and CFGs?
a) A situation where a non-terminal symbol eventually derives itself as the leftmost symbol
b) A situation where a non-terminal symbol derives terminal symbols first
c) A situation where a parse tree is balanced
d) A situation where a parse tree has multiple branches
Answer: a) A situation where a non-terminal symbol eventually derives itself as the leftmost symbol
Which type of derivation is typically used in recursive descent parsers?
a) Leftmost derivation
b) Rightmost derivation
c) Random derivation
d) Balanced derivation
Answer: a) Leftmost derivation
Which data structure is commonly used to represent parse trees in programming?
a) Tree data structure
b) Array
c) Linked list
d) Stack
Answer: a) Tree data structure
What does ‘terminals’ refer to in a context-free grammar?
a) Symbols that appear in the final derived string
b) Symbols that are used to represent non-terminals
c) Symbols used to define production rules
d) Symbols that are not used in derivations
Answer: a) Symbols that appear in the final derived string
Which of the following is a common method for handling ambiguous grammars?
a) Refactoring the grammar to remove ambiguity
b) Adding more non-terminals
c) Ignoring the ambiguous rules
d) Expanding the grammar with additional terminals
Answer: a) Refactoring the grammar to remove ambiguity
What does a ‘derivation step’ involve?
a) Replacing a non-terminal symbol with one of its production rules
b) Replacing a terminal symbol with a non-terminal
c) Generating a new parse tree
d) Removing terminal symbols from a string
Answer: a) Replacing a non-terminal symbol with one of its production rules
Which parsing technique is most commonly associated with constructing a leftmost derivation?
a) Recursive descent parsing
b) LR parsing
c) CYK parsing
d) Earley parsing
Answer: a) Recursive descent parsing
In a context-free grammar, what is the significance of the ‘start symbol’?
a) It is the symbol from which all derivations begin
b) It represents the end of the derivation process
c) It is the symbol that defines terminal symbols
d) It indicates the end of a parse tree
Answer: a) It is the symbol from which all derivations begin
Which algorithm is used to parse context-free grammars and generate parse trees?
a) CYK algorithm
b) Dijkstra’s algorithm
c) Kruskal’s algorithm
d) A* algorithm
Answer: a) CYK algorithm
What does a ‘right-recursive’ rule involve in a CFG?
a) A non-terminal symbol eventually derives itself as the rightmost symbol
b) A non-terminal symbol derives terminal symbols first
c) A parse tree is balanced
d) A parse tree has multiple branches
Answer: a) A non-terminal symbol eventually derives itself as the rightmost symbol
What is the primary purpose of eliminating left recursion in a CFG?
a) To make the grammar suitable for top-down parsing techniques
b) To create more ambiguous grammars
c) To simplify the grammar by adding more non-terminals
d) To convert the CFG to a regular expression
Answer: a) To make the grammar suitable for top-down parsing techniques
What is a ‘derivation tree’?
a) A tree representing the sequence of production rules applied during a derivation
b) A tree showing the hierarchical structure of terminal symbols
c) A list of all parse trees for a string
d) A tree representing the final output string
Answer: a) A tree representing the sequence of production rules applied during a derivation
Which of the following is NOT a feature of parse trees?
a) They show the sequence of production rules
b) They represent the syntax of a string
c) They illustrate the derivation process
d) They list terminal symbols in order
Answer: d) They list terminal symbols in order
What is the main advantage of using parse trees in syntax analysis?
a) They provide a clear visual representation of the syntactic structure
b) They generate random strings
c) They simplify terminal symbols
d) They eliminate non-terminals
Answer: a) They provide a clear visual representation of the syntactic structure
Which of the following best describes the relationship between parse trees and derivations?
a) A parse tree is generated from a derivation sequence
b) A parse tree generates a derivation sequence
c) Derivations and parse trees are unrelated
d) Parse trees define derivation sequences
Answer: a) A parse tree is generated from a derivation sequence
Which type of derivation is useful for constructing parse trees in a top-down parsing strategy?
a) Leftmost derivation
b) Rightmost derivation
c) Random derivation
d) Balanced derivation
Answer: a) Leftmost derivation