chapter 3 Flashcards
(101 cards)
1
Q
________ is the process of constructing a syntactic structure (parse tree) from a stream of tokens
A
Answer: Parsing
2
Q
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.
A
Answer: lexical
3
Q
Which phase of the compiler constructs the abstract syntax tree?
a) Lexical Analysis
b) Syntax Analysis
c) Semantic Analysis
d) Code Generation
A
Answer: b) Syntax Analysis
4
Q
what does the The parser in syntax analysis perform?
A
context free syntax analysis,
guides context-sensitive analysis,
constructs an intermediate representation, produces meaningful error messages,
and attempts error correction.
5
Q
________ parsing methods include the CYK algorithm and Earley’s algorithm.
A
Answer: Universal
6
Q
what are the three general types of parsers for grammars?
A
universal,
top-down, and
bottom-up
7
Q
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
A
Answer: b) Top-Down Parsers
8
Q
Universal parsing methods are, too inefficient to use in production compilers.
A
t
9
Q
Compilers assist programmers in identifying and locating ________.
A
Answer: errors
10
Q
The information which syntax analysis phase gets from the previous phase (lexical
analysis) is _________ and _________
A
- whether a token is valid or not and
- which class of tokens does it belong to.
11
Q
it is beyond the capabilities of the syntax analysis phase to settle issues
like:
A
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?
12
Q
what are Error handler goals
A
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
13
Q
Which of the following is not a common programming error?
a) Lexical Error
b) Syntactic Error
c) Semantic Error
d) Predictive Error
A
Answer: d) Predictive Error
14
Q
In ________ , the parser discards input symbols until a designated synchronization token is found.
A
Answer: Panic Mode recovery
15
Q
______ errors include misspellings of identifiers, keywords, or operators
A
Lexical
16
Q
_______ errors include misplaced semicolons or extra or missing braces; that
is, “{“ or “}.”
A
Syntactic
17
Q
_____ errors include type mismatches between operators and operands.
A
Semantic
18
Q
what are The four main strategies in error handling:
A
a) Panic Mode Recovery
b) Phrase Level Recovery
c) Error Productions
d) Global Correction
19
Q
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
A
Answer: b) Phrase Level Recovery
20
Q
________ augment grammar with productions that generate erroneous constructs.
A
Answer: Error Productions
21
Q
_____ Simplest method of recovery used by most parsing methods.
A
Panic Mode Recovery
22
Q
Panic mode recovery will lead to an infinite loop.
A
f
23
Q
________ Replaces a prefix of remaining input by some string that allows the parser to continue.
A
Phrase Level Recovery
24
Q
Care should be taken by the replacements , not to lead to infinite loops in ______ recovery
A
Phrase Level Recovery
25
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
26
A context-free grammar (CFG) consists of ________, ________, ________ and ________
terminals,
non-terminals,
production rules, and
a start symbol.
27
Regular expressions can not be used for syntax analysis (specification of grammar)
t
28
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
29
Non-terminals are ________ denoting _____
Answer: syntactic variables , sets of strings.
30
CFG is aka ______
Backus-Naur-Form(BNF) description.
31
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
32
______ impose a hierarchical structure on the language
Non-terminals
33
________ is a sequence of replacements of non-terminal symbols with strings of terminals and non-terminals.
Answer: Derivation
34
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
35
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
36
what are the 2 types of derivation
a) Leftmost Derivation
b) Rightmost Derivation
37
Ambiguity in CFG occurs when a string can have more than one valid ________ or ____
Answer: parse tree, derivation
38
Some derivations are neither leftmost nor rightmost
t
39
Given S ⇒ α - form of G.
If α contains non-terminals, it is called _____
a sentential
40
Given S ⇒ α - form of G.
If α doesn't contain non-terminals, it is called _____
a sentence of G
41
A string of terminals and non-terminals α that can be derived from the initial symbol of the grammar is called a ________
sentential form
42
______ provides a more compact and readable form compared to standard BNF.
Extended Backus-Naur Form (EBNF)
43
_________ is a program, which receives valid tokens and checks them against the
grammar and produces valid parse trees otherwise generates syntactical errors.
a Parser
44
when we want a parenthesis to appear in EBNF, we need to _______
surround it with quotation marks.
S -> print”(“id”)”
45
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.
46
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.
47
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.
48
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.
49
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.
50
_______ Traces rightmost derivation while ______ Traces leftmost derivation
- bottom-up parsing, Top-down parsing
51
What are the 2 General Approach of Top-Down Parsing
- recursive-descent parsing
- Predictive Parsing.
52
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
53
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
54
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
55
predictive parsing needs a special form of grammars called _______
LL(1) grammars
56
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
57
Recursive descent parsers fall into a class of parsers known as ______
LL(k) parsers
58
LL(k) stands for _______
Left-to-right, Leftmost-derivation, k-symbol lookahead parsers
59
What data structure is primarily used by a predictive parser to simulate leftmost derivation?
A. Queue
B. Stack
C. Array
D. Tree
Answer: B
60
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
61
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
62
The parsing table is a two dimensional array M[X, a]. explain each symbol
X- non terminal
a - terminal or the $ SYMBOL
63
The construction of a predictive parser is aided by two functions ______ and ______
FOLLOW , FIRST
64
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
65
what is FIRST(a)
is the set of tokens that could appear as the first symbol in a string derived from a.
66
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)
67
Error handling and recovery strategies ensure the ________ and usability of compilers.
a) Speed
b) Robustness
c) Compactness
d) Complexity
Answer: b) Robustness
68
Leftmost derivation always replaces the ________ .
a) Leftmost non-terminal
b) Rightmost non-terminal
c) Leftmost terminal
d) Rightmost terminal
Answer: a) Leftmost non-terminal
69
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
70
Ambiguity in a grammar is resolved by modifying the ________.
Production Rules
71
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.
72
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.
73
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.
74
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.
75
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
76
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)
77
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)
78
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)
79
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)
80
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)
81
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)
82
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
83
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)
84
_______ 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
85
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
86
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)
87
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)
88
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.
89
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)
90
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)
91
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)
92
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)
93
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
94
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)
95
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)
96
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)
97
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)
98
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)
99
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
100
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.
101
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.
