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