chapter 3 Flashcards
________ is the process of constructing a syntactic structure (parse tree) from a stream of tokens
Answer: Parsing
The parser receives a string of tokens from the ________ analyzer and verifies if the string of token names can be generated by the grammar for the source language.
Answer: lexical
Which phase of the compiler constructs the abstract syntax tree?
a) Lexical Analysis
b) Syntax Analysis
c) Semantic Analysis
d) Code Generation
Answer: b) Syntax Analysis
what does the The parser in syntax analysis perform?
context free syntax analysis,
guides context-sensitive analysis,
constructs an intermediate representation, produces meaningful error messages,
and attempts error correction.
________ parsing methods include the CYK algorithm and Earley’s algorithm.
Answer: Universal
what are the three general types of parsers for grammars?
universal,
top-down, and
bottom-up
Which of the following parsers build parse trees from the top (root) to the bottom (leaves)?
a) Bottom-Up Parsers
b) Top-Down Parsers
c) CYK Parsers
d) Earley Parsers
Answer: b) Top-Down Parsers
Universal parsing methods are, too inefficient to use in production compilers.
t
Compilers assist programmers in identifying and locating ________.
Answer: errors
The information which syntax analysis phase gets from the previous phase (lexical
analysis) is _________ and _________
- whether a token is valid or not and
- which class of tokens does it belong to.
it is beyond the capabilities of the syntax analysis phase to settle issues
like:
Whether or not a variable has already been declared?
Whether or not a variable has been initialized before use?
Whether or not a variable is of the type on which the operation is allowed?
what are Error handler goals
Report the presence of errors clearly and accurately
Recover from each error quickly enough to detect subsequent errors
Add minimal overhead to the processing of correct programs
Which of the following is not a common programming error?
a) Lexical Error
b) Syntactic Error
c) Semantic Error
d) Predictive Error
Answer: d) Predictive Error
In ________ , the parser discards input symbols until a designated synchronization token is found.
Answer: Panic Mode recovery
______ errors include misspellings of identifiers, keywords, or operators
Lexical
_______ errors include misplaced semicolons or extra or missing braces; that
is, “{“ or “}.”
Syntactic
_____ errors include type mismatches between operators and operands.
Semantic
what are The four main strategies in error handling:
a) Panic Mode Recovery
b) Phrase Level Recovery
c) Error Productions
d) Global Correction
Which error recovery strategy involves making local corrections to allow the parser to continue?
a) Panic Mode Recovery
b) Phrase Level Recovery
c) Error Productions
d) Global Correction
Answer: b) Phrase Level Recovery
________ augment grammar with productions that generate erroneous constructs.
Answer: Error Productions
_____ Simplest method of recovery used by most parsing methods.
Panic Mode Recovery
Panic mode recovery will lead to an infinite loop.
f
________ Replaces a prefix of remaining input by some string that allows the parser to continue.
Phrase Level Recovery
Care should be taken by the replacements , not to lead to infinite loops in ______ recovery
Phrase Level Recovery
Which error recovery strategy identifies and corrects errors to obtain a globally least-cost correction?
a) Panic Mode Recovery
b) Phrase Level Recovery
c) Error Productions
d) Global Correction
Answer: d) Global Correction
A context-free grammar (CFG) consists of ________, ________, ________ and ________
terminals,
non-terminals,
production rules, and
a start symbol.
Regular expressions can not be used for syntax analysis (specification of grammar)
t
Which component of a CFG are the basic symbols from which strings are formed?
a) Terminals
b) Non-terminals
c) Production Rules
d) Start Symbol
Answer: a) Terminals aka tokens
Non-terminals are ________ denoting _____
Answer: syntactic variables , sets of strings.
CFG is aka ______
Backus-Naur-Form(BNF) description.
Which part of a CFG defines how syntactical constructs may be built from terminals?
a) Terminals
b) Non-terminals
c) Production Rules
d) Start Symbol
Answer: c) Production Rules
______ impose a hierarchical structure on the language
Non-terminals
________ is a sequence of replacements of non-terminal symbols with strings of terminals and non-terminals.
Answer: Derivation
explain production rules
The left-hand side (head) of each rewriting rule is a single non- terminal.
The right-hand side (body) of each rewriting rule is a string of terminals and/or non-terminals
Example: E—-> E+T
- Terminal: T
- Non-Terminal: E,T
A hierarchical structure representing the syntactic structure of the input based on a CFG is known as a ________.
a) Parse Tree
b) Derivation
c) Syntax Graph
d) Semantic Tree
Answer: a) Parse Tree
what are the 2 types of derivation
a) Leftmost Derivation
b) Rightmost Derivation
Ambiguity in CFG occurs when a string can have more than one valid ________ or ____
Answer: parse tree, derivation
Some derivations are neither leftmost nor rightmost
t
Given S ⇒ α - form of G.
If α contains non-terminals, it is called _____
a sentential
Given S ⇒ α - form of G.
If α doesn’t contain non-terminals, it is called _____
a sentence of G
A string of terminals and non-terminals α that can be derived from the initial symbol of the grammar is called a ________
sentential form
______ provides a more compact and readable form compared to standard BNF.
Extended Backus-Naur Form (EBNF)
_________ is a program, which receives valid tokens and checks them against the
grammar and produces valid parse trees otherwise generates syntactical errors.
a Parser
when we want a parenthesis to appear in EBNF, we need to _______
surround it with quotation marks.
S -> print”(“id”)”
Which of the following is a valid EBNF notation for a series of one or more statements S terminated by semicolons?
A) S → { B }
B) B → (S;)+
C) C → S ; C
D) S → print(id)
Answer: B.
What is the main goal of a parser in the context of a compiler?
A) Tokenize the input program
B) Optimize the code
C) Check the syntax of a sequence of tokens
D) Generate machine code
Answer: C.
Which type of parser constructs the parse tree from the root to the leaves?
A) Bottom-up parser
B) Top-down parser
C) Recursive descent parser
D) Shift-reduce parser
Answer: B.
What is a key advantage of top-down parsing?
A) Handles ambiguous grammars easily
B) Always finds the most optimized parse tree
C) Can be constructed easily by hand
D) Always avoids backtracking
Answer: C.
In bottom-up parsing, what does the action ‘reduce’ involve?
A) Adding a new token to the parse tree
B) Removing a substring from the input
C) Replacing a substring with a nonterminal
D) Shifting the input pointer
Answer: C.
_______ Traces rightmost derivation while ______ Traces leftmost derivation
- bottom-up parsing, Top-down parsing
What are the 2 General Approach of Top-Down Parsing
- recursive-descent parsing
- Predictive Parsing.
Which of the following is true about recursive-descent parsing?
A. It is a bottom-up parsing technique.
B. It does not require backtracking.
C. It uses recursive procedures to process the input.
D. It is the most efficient parsing technique.
Answer: C
Why is backtracking needed in some top-down parsing techniques?
A. To handle ambiguous grammars
B. To handle non-deterministic choices
C. To improve parsing efficiency
D. To manage memory usage
Answer: B
Which parsing method is known to be efficient and does not require backtracking?
A. Recursive-descent parsing
B. Bottom-up parsing
C. Predictive parsing
D. Backtracking parser
Answer: C
predictive parsing needs a special form of grammars called _______
LL(1) grammars
What is a key characteristic of LL(1) grammars?
A. They allow multiple lookahead symbols.
B. They are used in bottom-up parsing.
C. They allow only one symbol of lookahead.
D. They require backtracking.
Answer: C
Recursive descent parsers fall into a class of parsers known as ______
LL(k) parsers
LL(k) stands for _______
Left-to-right, Leftmost-derivation, k-symbol lookahead parsers
What data structure is primarily used by a predictive parser to simulate leftmost derivation?
A. Queue
B. Stack
C. Array
D. Tree
Answer: B
In predictive parsing, what is the significance of the parsing table?
A. It stores the input string to be parsed.
B. It stores the grammar rules.
C. It directs the parser on which production to apply.
D. It keeps track of the parsing history.
Answer: C
Which component of a predictive parser indicates the end of the input string?
A. Stack
B. Parsing table
C. Lookahead symbol
D. End-of-file marker ($)
Answer: D
The parsing table is a two dimensional array M[X, a]. explain each symbol
X- non terminal
a - terminal or the $ SYMBOL
The construction of a predictive parser is aided by two functions ______ and ______
FOLLOW , FIRST
What does the FOLLOW set of a non-terminal represent in a grammar?
A. The set of terminals that can appear at the beginning of any string derived from that non-terminal.
B. The set of terminals that can appear immediately after that non-terminal in a valid sentence.
C. The set of all possible strings that can be derived from that non-terminal.
D. The set of all non-terminals that can appear after that non-terminal in a valid sentence.
Answer: B
what is FIRST(a)
is the set of tokens that could appear as the first symbol in a string derived from a.
what are the First Sets generalized rule
- If X is a terminal , then FIRST(X) is X itself. Example: First(id)={id}.
- If X is a non-terminal ,then FIRST(X) is set of terminals derived from X.
X—>Y - FIRST(X) = FIRST(Y)
Error handling and recovery strategies ensure the ________ and usability of compilers.
a) Speed
b) Robustness
c) Compactness
d) Complexity
Answer: b) Robustness
Leftmost derivation always replaces the ________ .
a) Leftmost non-terminal
b) Rightmost non-terminal
c) Leftmost terminal
d) Rightmost terminal
Answer: a) Leftmost non-terminal
Which of the following methods can parse any grammar but is inefficient for production compilers?
a) Top-Down Parsing
b) Bottom-Up Parsing
c) CYK Algorithm
d) Recursive Descent Parsing
Answer: c) CYK Algorithm
Ambiguity in a grammar is resolved by modifying the ________.
Production Rules
What is the purpose of constructing a predictive parse table?
A) To generate tokens
B) To automate the parsing process
C) To check for syntax errors
D) To optimize the code
Answer: B) To automate the parsing process
Explanation: Predictive parse tables help in automating the parsing process by providing guidance on which production rules to apply based on the current input symbol and top of the stack.
What is the initial step in constructing a predictive parse table?
A) Calculating FIRST sets
B) Calculating FOLLOW sets
C) Identifying terminals and non-terminals
D) Defining production rules
Answer: A) Calculating FIRST sets
Explanation: The construction of a predictive parse table begins with calculating the FIRST sets for all non-terminals in the grammar.
Which of the following is true about the FOLLOW set of a non-terminal?
A) It contains terminals that can appear immediately to the left of the non-terminal.
B) It contains terminals that can appear immediately to the right of the non-terminal.
C) It includes all terminals in the grammar.
D) It contains non-terminals that can follow the non-terminal in some derivation.
Answer: B) It contains terminals that can appear immediately to the right of the non-terminal.
Explanation: The FOLLOW set of a non-terminal contains all terminals that can appear immediately to the right of the non-terminal in some derivation.
In shift-reduce parsing, what does the ‘shift’ operation do?
A) Removes a symbol from the stack
B) Adds a symbol to the stack
C) Replaces a symbol on the stack
D) Moves the input pointer to the next symbol
Answer: B) Adds a symbol to the stack
Explanation: The ‘shift’ operation in shift-reduce parsing moves the current input symbol to the stack and advances the input pointer.
What is a ‘handle’ in bottom-up parsing?
A) The leftmost non-terminal in a production
B) A substring that matches the right-hand side of a production
C) The top symbol on the stack
D) The current input symbol
Answer: B) A substring that matches the right-hand side of a production
In a shift-reduce parser, what does the ‘reduce’ operation involve?
A) Shifting a terminal onto the stack
B) Removing a handle from the stack and replacing it with a non-terminal
C) Advancing the input pointer without modifying the stack
D) Discarding symbols from the input
Answer: B)
What does the stack contain during the shift-reduce parsing process?
A) Only terminals
B) Only non-terminals
C) Both terminals and non-terminals
D) Intermediate code representations
Answer: C)
In the stack implementation of a shift-reduce parser, what triggers a ‘reduce’ operation?
A) The top of the stack contains a terminal
B) The input symbol matches a terminal in the grammar
C) The stack contains a handle that matches the right-hand side of a production
D) The stack is empty
Answer: C)
What does ‘LR’ in LR parsers stand for?
A) Left-to-Right
B) Left-to-Right, Rightmost Derivation
C) Left Recursion
D) Lexical-Right
Answer: B)
Which of the following is not a type of LR parser?
A) SLR Parser
B) CLR Parser
C) LALR Parser
D) TL Parser
Answer: D)
What is the main advantage of LALR parsers over SLR parsers?
A) Simpler to implement
B) Can handle more grammars
C) Faster parsing speed
D) Generates smaller parse tables
Answer: B)
What is included in the ACTION part of an LR parse table?
A) Shift and reduce operations
B) Only shift operations
C) Shift, reduce, accept, and error operations.
D) Production rules
Answer: C
What does the GOTO part of an LR parse table represent?
A) Terminal symbols
B) Transition to states
C) Lookahead symbols
D) Production rules
Answer: B)
_______ conflict occurs when the parser can either shift the next input symbol or reduce the handle on the stack, but it is unclear which action to take.
A shift-reduce conflict
What does SLR (Simple LR) parsing primarily rely on to resolve conflicts?
A) FIRST sets
B) FOLLOW sets
C) Parse trees
D) Grammar rules
Answer: B) FOLLOW sets
In SLR parsing, what triggers a shift operation?
A) The input symbol is in the FOLLOW set of a non-terminal
B) The input symbol is in the FIRST set of a non-terminal
C) The next input symbol matches an entry in the ACTION table
D) The stack is empty
Answer: C)
What distinguishes CLR (Canonical LR) parsing from SLR parsing?
A) CLR uses more lookahead symbols
B) CLR uses fewer states
C) CLR does not use FOLLOW sets
D) CLR has simpler parse tables
Answer: A)
What is the main purpose of constructing LR(1) items in CLR parsing?
A) To reduce the number of states
B) To simplify the grammar
C) To include lookahead information
D) To eliminate shift-reduce conflicts
Answer: C)
- lookahead = to provide more context and reduce ambiguities in parsing decisions.
What is the key feature of LALR (Look-Ahead LR) Parsing compared to CLR parsing?
A) Larger parse tables
B) Fewer states
C) More states
D) Simpler grammar
Answer: B)
What is the key feature of LALR parsing compared to CLR parsing?
A) Larger parse tables
B) Fewer states
C) More states
D) Simpler grammar
Answer: B)
LALR parsers are particularly known for which of the following advantages?
A) Ability to parse all context-free grammars
B) Simplified implementation compared to CLR
C) Smallest possible parse tables
D) Fastest parsing speed
Answer: B)
What does an LR(1) item consist of?
A) A production and a lookahead symbol
B) A production and a FOLLOW set
C) A terminal and a non-terminal
D) A state and a terminal
Answer: A)
In the context of LR parsing, what does the ‘1’ in LR(1) signify?
A) One production rule
B) One lookahead symbol
C) One state
D) One terminal symbol
Answer: B) One lookahead symbol
How are shift-reduce conflicts generally resolved in LR parsers?
A) By using precedence and associativity rules
B) By increasing the number of lookahead symbols
C) By reducing the grammar complexity
D) By implementing recursive descent parsing
Answer: A)
Which type of conflict occurs less frequently in LR parsers but is still significant?
A) Shift-Reduce conflict
B) Reduce-Reduce conflict
C) Shift-Shift conflict
D) Parse conflict
Answer: B)
What is a common strategy for error recovery in LR parsers?
A) Ignoring the error and continuing parsing
B) Performing local corrections
C) Backtracking to previous states
D) Terminating the parsing process
Answer: B)
Why might an LR parser be preferred over a recursive descent parser for complex languages?
A) LR parsers are easier to implement
B) LR parsers are more efficient in terms of memory usage
C) LR parsers can handle left recursion directly
D) LR parsers have simpler error handling
Answer: C)
How do LALR parsers achieve a balance between SLR and CLR parsers?
A) By using a single lookahead symbol
B) By combining states with similar contexts
C) By reducing the number of production rules
D) By simplifying FOLLOW sets
Answer: B)
What information is needed to fill in the ACTION table in SLR parsing?
A) FIRST sets and FOLLOW sets
B) Parse trees and derivations
C) Terminals and non-terminals
D) Production rules and states
Answer: A) FIRST sets and FOLLOW sets
When constructing an SLR parse table, what does an entry ACTION[s, a] = shift t mean?
if the parser is in state ‘s’ and the next input symbol is ‘a’, it should shift ‘a’ onto the stack, move to state ‘t’, and advance the input pointer.
What is the first step in the LR parsing algorithm after initializing the stack?
A) Shift the first input symbol
B) Check for errors
C) Apply a reduction
D) Consult the ACTION table
Answer: D)
- to determine the next action based on the current state and input symbol.
