Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

CD > chapter 3 > Flashcards

chapter 3 Flashcards

1
Q

________ is the process of constructing a syntactic structure (parse tree) from a stream of tokens

A

Answer: Parsing

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

________ parsing methods include the CYK algorithm and Earley’s algorithm.

A

Answer: Universal

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

what are the three general types of parsers for grammars?

A

universal,
top-down, and
bottom-up

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Universal parsing methods are, too inefficient to use in production compilers.

A

t

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Compilers assist programmers in identifying and locating ________.

A

Answer: errors

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

In ________ , the parser discards input symbols until a designated synchronization token is found.

A

Answer: Panic Mode recovery

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

______ errors include misspellings of identifiers, keywords, or operators

A

Lexical

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

_______ errors include misplaced semicolons or extra or missing braces; that
is, “{“ or “}.”

A

Syntactic

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

_____ errors include type mismatches between operators and operands.

A

Semantic

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

________ augment grammar with productions that generate erroneous constructs.

A

Answer: Error Productions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

_____ Simplest method of recovery used by most parsing methods.

A

Panic Mode Recovery

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Panic mode recovery will lead to an infinite loop.

A

f

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

________ Replaces a prefix of remaining input by some string that allows the parser to continue.

A

Phrase Level Recovery

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Care should be taken by the replacements , not to lead to infinite loops in ______ recovery

A

Phrase Level Recovery

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

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

A

Answer: d) Global Correction

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

A context-free grammar (CFG) consists of ________, ________, ________ and ________

A

terminals,
non-terminals,
production rules, and
a start symbol.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Regular expressions can not be used for syntax analysis (specification of grammar)

A

t

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

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

A

Answer: a) Terminals aka tokens

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Non-terminals are ________ denoting _____

A

Answer: syntactic variables , sets of strings.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

CFG is aka ______

A

Backus-Naur-Form(BNF) description.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

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

A

Answer: c) Production Rules

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

______ impose a hierarchical structure on the language

A

Non-terminals

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

________ is a sequence of replacements of non-terminal symbols with strings of terminals and non-terminals.

A

Answer: Derivation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

explain production rules

A

 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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

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

A

Answer: a) Parse Tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

what are the 2 types of derivation

A

a) Leftmost Derivation
b) Rightmost Derivation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

Ambiguity in CFG occurs when a string can have more than one valid ________ or ____

A

Answer: parse tree, derivation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

Some derivations are neither leftmost nor rightmost

A

t

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

Given S ⇒ α - form of G.
If α contains non-terminals, it is called _____

A

a sentential

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
40
Q

Given S ⇒ α - form of G.
If α doesn’t contain non-terminals, it is called _____

A

a sentence of G

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
41
Q

A string of terminals and non-terminals α that can be derived from the initial symbol of the grammar is called a ________

A

sentential form

42
Q

______ provides a more compact and readable form compared to standard BNF.

A

Extended Backus-Naur Form (EBNF)

43
Q

_________ is a program, which receives valid tokens and checks them against the
grammar and produces valid parse trees otherwise generates syntactical errors.

A

a Parser

44
Q

when we want a parenthesis to appear in EBNF, we need to _______

A

surround it with quotation marks.
S -> print”(“id”)”

45
Q

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)

A

Answer: B.

46
Q

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

A

Answer: C.

47
Q

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

A

Answer: B.

48
Q

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

A

Answer: C.

49
Q

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

A

Answer: C.

50
Q

_______ Traces rightmost derivation while ______ Traces leftmost derivation

A
  • bottom-up parsing, Top-down parsing
51
Q

What are the 2 General Approach of Top-Down Parsing

A
  • recursive-descent parsing
  • Predictive Parsing.
52
Q

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.

A

Answer: C

53
Q

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

A

Answer: B

54
Q

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

A

Answer: C

55
Q

predictive parsing needs a special form of grammars called _______

A

LL(1) grammars

56
Q

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.

A

Answer: C

57
Q

Recursive descent parsers fall into a class of parsers known as ______

A

LL(k) parsers

58
Q

LL(k) stands for _______

A

Left-to-right, Leftmost-derivation, k-symbol lookahead parsers

59
Q

What data structure is primarily used by a predictive parser to simulate leftmost derivation?

A. Queue
B. Stack
C. Array
D. Tree

A

Answer: B

60
Q

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.

A

Answer: C

61
Q

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 ($)

A

Answer: D

62
Q

The parsing table is a two dimensional array M[X, a]. explain each symbol

A

X- non terminal
a - terminal or the $ SYMBOL

63
Q

The construction of a predictive parser is aided by two functions ______ and ______

A

FOLLOW , FIRST

64
Q

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.

A

Answer: B

65
Q

what is FIRST(a)

A

is the set of tokens that could appear as the first symbol in a string derived from a.

66
Q

what are the First Sets generalized rule

A
  • 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
Q

Error handling and recovery strategies ensure the ________ and usability of compilers.

a) Speed
b) Robustness
c) Compactness
d) Complexity

A

Answer: b) Robustness

68
Q

Leftmost derivation always replaces the ________ .

a) Leftmost non-terminal
b) Rightmost non-terminal
c) Leftmost terminal
d) Rightmost terminal

A

Answer: a) Leftmost non-terminal

69
Q

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

A

Answer: c) CYK Algorithm

70
Q

Ambiguity in a grammar is resolved by modifying the ________.

A

Production Rules

71
Q

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

A

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
Q

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

A

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
Q

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.

A

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
Q

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

A

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
Q

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

A

Answer: B) A substring that matches the right-hand side of a production

76
Q

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

A

Answer: B)

77
Q

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

A

Answer: C)

78
Q

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

A

Answer: C)

79
Q

What does ‘LR’ in LR parsers stand for?

A) Left-to-Right
B) Left-to-Right, Rightmost Derivation
C) Left Recursion
D) Lexical-Right

A

Answer: B)

80
Q

Which of the following is not a type of LR parser?

A) SLR Parser
B) CLR Parser
C) LALR Parser
D) TL Parser

A

Answer: D)

81
Q

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

A

Answer: B)

82
Q

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

A

Answer: C

83
Q

What does the GOTO part of an LR parse table represent?

A) Terminal symbols
B) Transition to states
C) Lookahead symbols
D) Production rules

A

Answer: B)

84
Q

_______ 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

A shift-reduce conflict

85
Q

What does SLR (Simple LR) parsing primarily rely on to resolve conflicts?

A) FIRST sets
B) FOLLOW sets
C) Parse trees
D) Grammar rules

A

Answer: B) FOLLOW sets

86
Q

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

A

Answer: C)

87
Q

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

A

Answer: A)

88
Q

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

A

Answer: C)
- lookahead = to provide more context and reduce ambiguities in parsing decisions.

89
Q

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

A

Answer: B)

90
Q

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

A

Answer: B)

91
Q

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

A

Answer: B)

92
Q

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

A

Answer: A)

93
Q

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

A

Answer: B) One lookahead symbol

94
Q

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

A

Answer: A)

95
Q

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

A

Answer: B)

96
Q

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

A

Answer: B)

97
Q

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

A

Answer: C)

98
Q

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

A

Answer: B)

99
Q

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

A

Answer: A) FIRST sets and FOLLOW sets

100
Q

When constructing an SLR parse table, what does an entry ACTION[s, a] = shift t mean?

A

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
Q

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

A

Answer: D)
- to determine the next action based on the current state and input symbol.

CD (3 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions