Parse trees and derivations(MCQs)

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