Top-down parsing (Recursive Descent, LL parsers)(MCQs)

What is the primary goal of top-down parsing? a) To construct a parse tree from the start symbol to the terminal symbols b) To convert a grammar to Chomsky Normal Form c) To check if a string is regular d) To minimize the number of states in a finite automaton Answer: a) To construct a parse tree from the start symbol to the terminal symbols Which of the following is a characteristic of Recursive Descent Parsing? a) It uses a set of mutually recursive procedures to parse a string b) It constructs parse trees from bottom to top c) It uses a stack to handle parsing d) It requires the grammar to be in Chomsky Normal Form Answer: a) It uses a set of mutually recursive procedures to parse a string Which type of grammar is suitable for LL parsing? a) LL(1) grammar b) LR(1) grammar c) SLR(1) grammar d) LALR(1) grammar Answer: a) LL(1) grammar What does the ‘1’ in LL(1) parsing signify? a) One lookahead token is used for parsing b) One recursion depth in the parsing process c) One level of parse tree d) One production rule per non-terminal Answer: a) One lookahead token is used for parsing In Recursive Descent Parsing, what does each non-terminal in the grammar correspond to? a) A procedure or function b) A terminal symbol c) A production rule d) A lookahead token Answer: a) A procedure or function Which of the following is NOT a requirement for a grammar to be LL(1)? a) The grammar must be unambiguous b) The grammar must be left-recursive c) The grammar must be in a suitable form for top-down parsing d) The grammar must have no left recursion Answer: b) The grammar must be left-recursive What is the purpose of left-factoring in LL(1) parsing? a) To eliminate common prefixes in production rules b) To add more non-terminals to the grammar c) To simplify the grammar by removing terminals d) To convert the grammar to regular expressions Answer: a) To eliminate common prefixes in production rules Which parsing strategy uses a stack to store states and handles ambiguities by backtracking? a) Recursive Descent Parsing b) LL(1) Parsing c) LR Parsing d) SLR Parsing Answer: a) Recursive Descent Parsing In LL(1) parsing, what does the ‘left’ signify? a) The parser processes input from left to right b) The grammar is processed in a left-recursive manner c) The grammar can be parsed using left recursion d) The parsing is done from right to left Answer: a) The parser processes input from left to right Which of the following is a limitation of Recursive Descent Parsing? a) It cannot handle left-recursive grammars b) It requires the grammar to be in Chomsky Normal Form c) It cannot handle ambiguous grammars d) It cannot parse strings from left to right Answer: a) It cannot handle left-recursive grammars What does ‘lookahead’ mean in the context of LL(1) parsing? a) The parser inspects the next token in the input to decide which production rule to apply b) The parser looks for all possible tokens in the input c) The parser processes tokens in reverse order d) The parser ignores the next token in the input Answer: a) The parser inspects the next token in the input to decide which production rule to apply Which of the following is a characteristic of LL(1) grammars? a) They have no ambiguity and no left recursion b) They can handle multiple lookahead tokens c) They can be parsed using bottom-up techniques d) They require multiple passes to parse Answer: a) They have no ambiguity and no left recursion In which scenario would you use left recursion elimination? a) When converting a grammar to be compatible with LL(1) parsing b) When simplifying a grammar for regular expressions c) When constructing a parse tree for an ambiguous grammar d) When converting a grammar to Chomsky Normal Form Answer: a) When converting a grammar to be compatible with LL(1) parsing What does an LL(1) parser use to make parsing decisions? a) A parsing table and one lookahead token b) A stack and multiple lookahead tokens c) A list of production rules and multiple recursive calls d) A set of parsing trees and backtracking Answer: a) A parsing table and one lookahead token Which technique is commonly used to handle ambiguities in Recursive Descent Parsing? a) Backtracking b) Left recursion elimination c) Left-factoring d) Error recovery Answer: a) Backtracking Which of the following statements is true about LL(1) parsing tables? a) They are used to decide which production rule to apply based on the current non-terminal and lookahead token b) They are used to handle left recursion in the grammar c) They are used to convert a grammar to regular expressions d) They are used to represent the hierarchy of parse trees Answer: a) They are used to decide which production rule to apply based on the current non-terminal and lookahead token What does ‘right recursion’ refer to in the context of parsing? a) A non-terminal symbol eventually derives itself as the rightmost symbol in the production rules 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 in the production rules Which type of parser is specifically designed to handle left-recursive grammars? a) LR parser b) LL(1) parser c) Recursive Descent parser d) SLR parser Answer: a) LR parser What is the primary advantage of LL(1) parsing over other parsing techniques? a) Simplicity and efficiency in parsing b) Ability to handle complex grammars c) Flexibility in handling ambiguous grammars d) Capability to parse from right to left Answer: a) Simplicity and efficiency in parsing Which of the following is NOT a feature of LL(1) parsing? a) Uses a single lookahead token b) Can handle left-recursive grammars c) Constructs parse trees from top to bottom d) Requires grammar to be free from ambiguity Answer: b) Can handle left-recursive grammars What does ‘backtracking’ involve in the context of Recursive Descent Parsing? a) Trying different parsing paths when a rule fails and returning to try other alternatives b) Applying all production rules simultaneously c) Ignoring the parsing path and starting over d) Converting left-recursive rules to right-recursive rules Answer: a) Trying different parsing paths when a rule fails and returning to try other alternatives What is the primary purpose of a parsing table in LL(1) parsing? a) To guide the selection of production rules based on the current non-terminal and lookahead token b) To track recursive calls and handle ambiguities c) To store terminal symbols d) To convert the grammar to regular expressions Answer: a) To guide the selection of production rules based on the current non-terminal and lookahead token What type of grammar is needed for Recursive Descent Parsing? a) Non-left-recursive and unambiguous grammar b) Left-recursive and ambiguous grammar c) Regular grammar d) Chomsky Normal Form grammar Answer: a) Non-left-recursive and unambiguous grammar Which of the following actions is typically performed in LL(1) parsing? a) Consult the parsing table to determine which production to use b) Use a stack to handle recursion c) Apply backtracking to resolve parsing conflicts d) Convert the input string to a series of non-terminals Answer: a) Consult the parsing table to determine which production to use Which type of parsing strategy is best suited for parsing a language with a complex syntax? a) LR parsing b) LL(1) parsing c) Recursive Descent parsing d) SLR parsing Answer: a) LR parsing In Recursive Descent Parsing, how is left recursion typically handled? a) By transforming the grammar to eliminate left recursion b) By adding more recursive functions c) By using multiple lookahead tokens d) By converting the grammar to regular expressions Answer: a) By transforming the grammar to eliminate left recursion What does the ‘top-down’ approach in top-down parsing refer to? a) Constructing the parse tree starting from the start symbol and expanding towards the terminals b) Parsing the string from the end to the beginning c) Using multiple lookahead tokens for parsing d) Handling ambiguities by backtracking Answer: a) Constructing the parse tree starting from the start symbol and expanding towards the terminals Which parsing technique is considered a subset of LL(1) parsing? a) Recursive Descent Parsing b) LR Parsing c) SLR Parsing d) LALR Parsing Answer: a) Recursive Descent Parsing What is the primary purpose of eliminating left recursion in a grammar? a) To make the grammar compatible with top-down parsing techniques like LL(1) b) To convert the grammar to Chomsky Normal Form c) To simplify the production rules for regular expressions d) To add more non-terminals to the grammar Answer: a) To make the grammar compatible with top-down parsing techniques like LL(1) Which of the following is an advantage of Recursive Descent Parsing? a) Easy to implement and understand b) Handles left recursion automatically c) Requires complex parsing tables d) Handles multiple lookahead tokens efficiently Answer: a) Easy to implement and understand What is a common issue with using Recursive Descent Parsing? a) It cannot handle left-recursive grammars b) It requires extensive parsing tables c) It cannot parse from left to right d) It is not suitable for unambiguous grammars Answer: a) It cannot handle left-recursive grammars Which of the following is true about LL(1) parsing tables? a) They are used to parse strings based on the current non-terminal and lookahead token b) They handle left recursion by backtracking c) They require multiple passes through the input string d) They are used to construct parse trees from bottom to top Answer: a) They are used to parse strings based on the current non-terminal and lookahead token Which type of grammar does LL(1) parsing handle efficiently? a) Non-left-recursive and unambiguous grammar b) Left-recursive and ambiguous grammar c) Context-sensitive grammar d) Regular expressions Answer: a) Non-left-recursive and unambiguous grammar What is the role of left-factoring in LL(1) parsing? a) To eliminate common prefixes in production rules to ensure that the grammar can be parsed using a single lookahead token b) To add more terminals to the grammar c) To simplify the grammar by removing recursion d) To convert the grammar to regular expressions Answer: a) To eliminate common prefixes in production rules to ensure that the grammar can be parsed using a single lookahead token Which parsing technique is best suited for grammars with ambiguous productions? a) LR Parsing b) LL(1) Parsing c) Recursive Descent Parsing d) SLR Parsing Answer: a) LR Parsing What does a parsing table in LL(1) parsing use to determine which production rule to apply? a) The current non-terminal and the lookahead token b) The entire input string c) A stack of non-terminals d) A list of all possible production rules Answer: a) The current non-terminal and the lookahead token What is a key advantage of using LL(1) parsing over Recursive Descent Parsing? a) It avoids backtracking by using a parsing table b) It handles left-recursion automatically c) It can parse from right to left d) It is suitable for ambiguous grammars Answer: a) It avoids backtracking by using a parsing table Which of the following statements is true about Recursive Descent Parsing? a) It requires a separate function for each non-terminal in the grammar b) It uses a single lookahead token to make parsing decisions c) It builds a parse tree from bottom to top d) It handles multiple lookahead tokens efficiently Answer: a) It requires a separate function for each non-terminal in the grammar What does ‘eliminating left recursion’ involve? a) Transforming production rules where a non-terminal derives itself as the leftmost symbol b) Adding more non-terminals to the grammar c) Removing terminal symbols from production rules d) Rewriting grammar rules in reverse order Answer: a) Transforming production rules where a non-terminal derives itself as the leftmost symbol Which type of parsing strategy uses a stack to manage parsing states and handle grammar rules? a) LL(1) Parsing b) Recursive Descent Parsing c) LR Parsing d) SLR Parsing Answer: c) LR Parsing What is the purpose of using a lookahead token in LL(1) parsing? a) To make decisions about which production rule to apply based on the next token in the input b) To backtrack and try different parsing paths c) To handle left recursion in the grammar d) To convert the grammar to a different format Answer: a) To make decisions about which production rule to apply based on the next token in the input Which parsing technique is NOT typically used for top-down parsing? a) LL(1) Parsing b) Recursive Descent Parsing c) LR Parsing d) SLR Parsing Answer: c) LR Parsing Which of the following is true about the relationship between LL(1) parsing and left recursion? a) LL(1) parsing cannot handle left-recursive grammars b) LL(1) parsing can handle left-recursive grammars with modifications c) LL(1) parsing eliminates left recursion automatically d) LL(1) parsing uses left recursion to simplify parsing Answer: a) LL(1) parsing cannot handle left-recursive grammars What is the main advantage of using LL(1) parsing for programming languages? a) It provides a straightforward and efficient parsing method with predictable behavior b) It handles complex and ambiguous grammars without additional modifications c) It can parse languages with multiple lookahead tokens d) It automatically generates parsing tables from grammar rules Answer: a) It provides a straightforward and efficient parsing method with predictable behavior Which of the following best describes the ‘top-down’ nature of LL(1) parsing? a) The parse tree is constructed starting from the start symbol and expanding towards the leaves b) The parse tree is constructed starting from the leaves and expanding towards the root c) Parsing is done from right to left d) Parsing is done using a stack to handle recursion Answer: a) The parse tree is constructed starting from the start symbol and expanding towards the leaves What is the key limitation of LL(1) parsing compared to other parsing strategies? a) It cannot handle left-recursive grammars b) It requires multiple passes through the input string c) It cannot handle non-context-free grammars d) It is less efficient than other parsing strategies Answer: a) It cannot handle left-recursive grammars Which parsing technique is commonly used in the implementation of compilers for programming languages? a) LL(1) Parsing b) LR Parsing c) SLR Parsing d) Recursive Descent Parsing Answer: b) LR Parsing In LL(1) parsing, how is a parse decision made when encountering a non-terminal symbol? a) By consulting the parsing table based on the current non-terminal and lookahead token b) By backtracking and trying different production rules c) By applying all production rules simultaneously d) By using a stack to manage parsing states Answer: a) By consulting the parsing table based on the current non-terminal and lookahead token What does a parser do when it encounters a terminal symbol in LL(1) parsing? a) It matches the terminal symbol with the current input token b) It consults the parsing table for possible production rules c) It backtracks to try different parsing paths d) It adds more non-terminals to the grammar Answer: a) It matches the terminal symbol with the current input token Which of the following is a key characteristic of LL(1) parsing compared to Recursive Descent Parsing? a) LL(1) parsing uses a parsing table and avoids backtracking b) Recursive Descent Parsing uses a parsing table and handles left recursion c) LL(1) parsing handles left recursion automatically d) Recursive Descent Parsing avoids backtracking and uses a parsing table Answer: a) LL(1) parsing uses a parsing table and avoids backtracking