Computer Science Exit Exam Study Guide · 200 questions
Read the question first. Select the eye beside the reading hint, study the cited module section, then reveal the answer. Each eye controls only its own block. All hints and answers start closed whenever this page opens.
Read the linked study-guide sections before revealing the answer. PDF page references count from the first page of the document.
200 of 200 questions
Question 1
Which grammar gives multiple parse trees for the same string?
A. Unambiguous
B. Regular
C. Ambiguous
D. All of the above
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
COMP10 defines ambiguity by the existence of one terminal string with two different parse trees. This is exactly the property asked for. An unambiguous grammar excludes it. Being regular describes a grammar class rather than guaranteeing multiple trees, so it does not make all the listed descriptions correct.
Evidence in the complete study note
A grammar is ambiguous if at least one terminal string has two different parse trees, equivalently two leftmost derivations. Merely changing derivation order on the same tree does not establish ambiguity. E→E+E|E*E|id allows different trees for id+id*id.COMP10
Use E→E+T|T, T→T*F|F, F→(E)|id to give * higher precedence and both operators left associativity. For subtraction, a−b−c then groups (a−b)−c. The dangling-else grammar permits else to attach to either nested if; a nearest-unmatched-if rule or grammar rewrite resolves it. Taking a leftmost derivation by itself does not resolve ambiguous interpretation.COMP10
Choice by choice
A · incorrect — Unambiguous means each generated string has a unique parse tree, directly contradicting the property.
B · incorrect — Regularity restricts grammar form; it does not require multiple parse trees for a string.
C · correct — Ambiguity is precisely the existence of multiple parse trees for the same terminal string.
D · incorrect — Unambiguous grammars do not have the stated property, so all cannot be correct.
Question 2
Leaf nodes in a parse tree indicate?
A. sub-terminals
B. half-terminals
C. non-terminals
D. terminals
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
PDF p. 9 explicitly states that internal nodes are non-terminals and leaves are terminals. Thus the leaf labels in this module’s derivation trees are terminals, not the grammar variables expanded at internal nodes.
Evidence in the complete study note
A context-free grammar G=(N,T,P,S) has nonterminals N, terminals T, productions P and start S. A production A→α rewrites one nonterminal. A sentential form is any string of terminals/nonterminals derivable from S; a sentence contains only terminals. A leftmost derivation rewrites the leftmost remaining nonterminal; a rightmost one rewrites the rightmost.COMP09
A parse tree shows grammar productions: root S, internal nonterminals, and terminal leaves, with ε sometimes shown for empty productions. Its left-to-right yield is the input. An AST omits grammar scaffolding and punctuation; expression operands are leaves and operators internal nodes. The parser can build either representation, depending on implementation.COMP09
Choice by choice
A · incorrect — Sub-terminals is not a category in the module’s CFG or tree definitions (p. 9).
B · incorrect — Half-terminals is not a category in those definitions (p. 9).
C · incorrect — Non-terminals label internal nodes, not leaves (p. 9).
D · correct — The module expressly assigns terminals to leaves (p. 9).
Question 3
Which one of the following is not the task of lexical analyzer?
A. Group characters into lexemes
B. Output a sequence of tokens
C. Read the input characters
D. Build syntax tree
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
Scanning reads characters and represents matched lexemes as tokens (PDF pp. 5, 8). Syntax analysis then groups those tokens and produces a parse tree. Building that tree is therefore the non-lexical task.
Evidence in the complete study note
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
A parse tree shows grammar productions: root S, internal nonterminals, and terminal leaves, with ε sometimes shown for empty productions. Its left-to-right yield is the input.COMP09
Choice by choice
A · incorrect — Grouping characters into matched lexemes belongs to scanning (pp. 5, 8).
B · incorrect — A sequence of tokens is the scanner’s stated output (p. 8).
C · incorrect — Reading the stream of source characters is explicitly lexical analysis.
D · correct — Constructing the syntactic tree belongs to syntax analysis.
Question 4
Which statement is false about a compiler parser that constructs a parse tree and supports syntax-error diagnosis and recovery?
A. Parser builds the parse tree
B. Parser attempts to correct or recover few errors
C. Parser cannot perform context free syntax analysis
D. Parser produces appropriate error messages
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
A parser analyzes the token stream against the context-free syntax and builds its structural representation. In a compiler with syntax diagnostics and recovery, it can report an unexpected token and try to resume at a useful boundary. Therefore the claim that it cannot perform context-free syntax analysis reverses its defining role. Building a parse tree, reporting syntax errors and attempting the specified recovery behavior are compatible responsibilities.
Evidence in the complete study note
A context-free grammar G=(N,T,P,S) has nonterminals N, terminals T, productions P and start S. A production A→α rewrites one nonterminal.COMP09
A parse tree shows grammar productions: root S, internal nonterminals, and terminal leaves, with ε sometimes shown for empty productions. Its left-to-right yield is the input.COMP09
Panic-mode recovery skips input until a synchronizing token such as ; or } permits parsing to resume. Phrase-level recovery makes a local insertion/deletion. Report the location and cause while avoiding cascades of misleading diagnostics. Lexical, syntax and semantic phases each detect their own errors; error handling is a shared service.COMP39
Choice by choice
A · incorrect — Building a parse tree represents the grammar structure recognized by syntax analysis.
B · incorrect — Error recovery may skip to a synchronization token or make a limited local repair.
C · correct — Context-free syntax analysis is the parser’s defining task, so denying it is false.
D · incorrect — Syntax diagnostics identify unexpected or missing tokens with useful source locations.
Question 5
For an infix source expression targeting a postfix stack evaluator, which notation conversion prepares it for evaluation?
A. Convert infix notation to postfix notation
B. Convert postfix notation to prefix notation
C. Evaluate infix notation to prefix notation
D. Convert postfix to infix notation
Hint / Module Reference (Where to Read)
Track where each computed value comes from and when each production action runs. Distinguish the representation from its attached information.
Correct answer: A — Convert infix notation to postfix notation
A postfix evaluator reads operands before the operator that combines them. Converting an infix expression to postfix therefore supplies the required input order for the specified stack target. For example, the tree for a−4+c yields a 4 − c + in postorder. This is a choice of representation for this evaluator, rather than a mandatory strategy for every compiler.
Evidence in the complete study note
A syntax-directed translation scheme embeds executable actions in productions; the actions run while translating a source program, not while generating the compiler. Attributes may compute types, values, AST pointers or generated code. The scheme defines an input-to-output translation, not merely an input language.COMP25
Create an identifier leaf with mkleaf(id,entry), a number with mkleaf(num,value), and an operator node with mknode(op,left,right). For a−4+c, construct +(−(a,4),c). Postorder traversal prints postfix: a 4 − c +. A stack evaluator pushes operands and pops right then left operands for an operator. Infix-to-postfix is useful for stack machines but not mandatory for all compilers.COMP25
Choice by choice
A · correct — Infix-to-postfix supplies the required target order.
B · incorrect — Neither source nor target matches this direction.
C · incorrect — Prefix is not the specified target.
D · incorrect — This reverses the specified translation direction.
Question 6
Which named transformation directly replaces an expression whose operands are compile-time constants with its computed value?
A. Pee hole optimization
B. Constant folding
C. Invariant computation
D. Code hoisting
Hint / Module Reference (Where to Read)
Trace whether computation is evaluated, moved, shared or removed. Preserve observable effects and use the stated arithmetic and target assumptions.
Constant folding evaluates an expression from operands known at compilation and substitutes its value, such as replacing 3*4 with 12. This removes that expression’s run-time arithmetic. A peephole pass describes a small inspection region and may perform several transformations; it is not the particular evaluation rule. Loop-invariant computation can remain unknown until execution, and hoisting moves safe invariant work rather than necessarily computing a compile-time value.
Evidence in the complete study note
Constant folding evaluates constant expressions during compilation: 3*4→12.COMP30
A loop-invariant expression has unchanged inputs during a loop. Hoist it to a preheader only when evaluation is safe on the paths where it will newly run.COMP32
Peephole optimization examines short instruction windows.COMP31
Choice by choice
A · incorrect — Peephole identifies a short-window optimization method, not specifically constant-expression evaluation.
B · correct — Constant folding computes a known constant expression during compilation.
C · incorrect — An invariant may depend on a run-time input even though it stays unchanged across a loop.
D · incorrect — Hoisting moves a computation to a preheader; it need not evaluate it at compilation.
Question 7
Which listed deterministic parser families can evaluate synthesized attributes for suitable grammars and semantic actions? Select all that apply.
A. Ambiguous grammar
B. LR grammar
C. LL grammar
D. None
Hint / Module Reference (Where to Read)
Track where each computed value comes from and when each production action runs. Distinguish the representation from its attached information.
Correct answers (select all): B, C — LR grammar; LL grammar
Synthesized attributes flow from child nodes to their parent. LR parsers naturally compute these during reduction, after the right-hand-side children have been recognized. Suitable LL implementations can also compute them after their recursive child calls return. Ambiguity is a property of grammar interpretation, not a deterministic parser family or attribute-evaluation method. Thus both LR and LL are valid families for this task.
Evidence in the complete study note
A syntax-directed definition is a CFG with attributes on grammar symbols and semantic rules on productions. An annotated parse tree displays computed attribute values; it is not itself an inherited or synthesized attribute. Synthesized attributes flow from children to a parent; inherited attributes carry context from parent or siblings.COMP24
For E→E1+T, E.val=E1.val+T.val synthesizes an expression value. A declaration’s type environment passed into its body is inherited. S-attributed definitions use only synthesized attributes and fit LR reduction-time evaluation naturally; suitable LL parsers can also compute them. L-attributed definitions restrict dependencies so a left-to-right traversal can evaluate inherited context. Attribute dependency cycles can prevent evaluation.COMP24
Choice by choice
A · incorrect — Ambiguity is not a deterministic parser family or evaluation mechanism.
B · correct — LR reduction actions can compute parent values from children.
C · correct — Suitable LL actions can compute values after child processing.
D · incorrect — Both LR and LL provide supported implementations.
Question 8
Identifiers consist of one Letter followed by zero or more Letters or Digits. Which expressions denote exactly that language? Select all that apply. Here + means one-or-more, | alternation, and _ a literal underscore.
A. Letter(Letter+|Digit*)*
B. Letter(Letter|Digit)+
C. Letter(Letter|Digit)*
D. Letter(_Digit)*
Hint / Module Reference (Where to Read)
Follow the representation at each construction step and apply the pattern or state-set rules consistently, including empty cases.
Correct answers (select all): A, C — Letter(Letter+|Digit*)*; Letter(Letter|Digit)*
C directly expresses a leading letter followed by any sequence of letters and digits. A is equivalent: its outer star may take zero blocks, and repeated letter or digit blocks can generate every such suffix. B excludes a one-letter identifier because its suffix uses plus. D permits literal underscores and restricted digit blocks, so it does not denote the specified identifier language.
Evidence in the complete study note
Regular expressions use concatenation, alternation r|s, Kleene star r* for zero or more, and r+ for one or more. In a simplified alphabet, identifier = Letter(Letter|Digit)*; it permits a single letter and forbids a leading digit.COMP05
Letter(Letter+|Digit*)* denotes the same language as Letter(Letter|Digit)* under ordinary regular-expression semantics: repeated blocks can contain any trailing letter/digit sequence. These two regular expressions are equivalent. Regular patterns handle ordinary tokens; arbitrary balanced nesting generally needs grammar/stack structure.COMP05
Choice by choice
A · correct — Its repeated blocks generate every allowed suffix, including the empty suffix.
B · incorrect — The trailing plus excludes a one-letter identifier.
C · correct — This directly states the required pattern.
D · incorrect — Its literal underscores violate the specified alphabet and its restricted suffix misses identifiers.
Question 9
What is the process of finding a parse tree for a string of tokens called?
A. Recognizing
B. Parsing
C. Tokenizing
D. Analyzing
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
Parsing is explicitly the process of constructing a parse tree for a sentence generated by a grammar (PDF p. 10). That is the operation named in the question; token production precedes it (p. 8).
Evidence in the complete study note
A context-free grammar G=(N,T,P,S) has nonterminals N, terminals T, productions P and start S. A production A→α rewrites one nonterminal. A sentential form is any string of terminals/nonterminals derivable from S; a sentence contains only terminals. A leftmost derivation rewrites the leftmost remaining nonterminal; a rightmost one rewrites the rightmost.COMP09
A parse tree shows grammar productions: root S, internal nonterminals, and terminal leaves, with ε sometimes shown for empty productions. Its left-to-right yield is the input. An AST omits grammar scaffolding and punctuation; expression operands are leaves and operators internal nodes. The parser can build either representation, depending on implementation.COMP09
Choice by choice
A · incorrect — The module does not use Recognizing as the name of this construction (p. 10).
B · correct — Parsing matches the express definition (p. 10).
C · incorrect — Tokenizing produces the token stream, rather than its parse tree (p. 8).
D · incorrect — Analyzing is a broad description; the defined specific process is Parsing (p. 10).
Question 10
Which compiler phase groups source characters into lexemes and classifies them as identifier, keyword, literal or operator tokens?
A. Interpretation analysis
B. Lexical analysis
C. Syntax analysis
D. General syntax analysis
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
Lexical analysis groups the source character sequence into lexemes and emits token categories with attributes. Syntax analysis instead combines already recognized tokens into larger grammatical structures such as expressions and statements. Specifying characters and token categories resolves the original mixture of lexical classification and parsing terminology. The generic interpretation and syntax labels do not describe the requested character-to-token phase.
Evidence in the complete study note
Grouping characters into token classes is lexical analysis; grouping tokens into expressions and statements is syntax analysis.COMP41
Trees store hierarchical constructs, while a symbol table stores declaration metadata.COMP41
Choice by choice
A · incorrect — Interpretation executes a representation rather than classifying lexemes.
B · correct — Lexical analysis turns character sequences into tokens.
C · incorrect — Syntax analysis groups tokens into grammatical structures.
D · incorrect — This syntax label concerns parsing rather than lexical classification.
Question 11
For a register-based target compiler, which choice most completely lists general code-generator tasks?
A. Instruction selection
B. Register allocation and assignment
C. Instruction ordering
D. All
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
COMP34 separates selecting target operations, deciding storage in registers, assigning physical registers, and scheduling instructions. The three concrete choices name these standard code-generation tasks. Since the question offers an aggregate covering them, that aggregate is the complete answer; each individual choice supplies only part of the requested task list.
Evidence in the complete study note
Code generation lowers checked IR to a target form. Instruction selection chooses target operations; register allocation chooses where values reside; scheduling orders instructions while respecting dependencies; storage layout assigns offsets and follows ABI requirements. Register assignment names actual physical registers after allocation decisions.COMP34
For t=a+b, a simple target could emit LOAD R1,a; LOAD R2,b; ADD R3,R1,R2; STORE t,R3. Other targets may combine loads with arithmetic or keep t in a register. Machine idioms, register availability and instruction order affect execution time.COMP34
Choice by choice
A · incorrect — True as one component, but incomplete as the requested full selection. Instruction selection chooses which target instructions implement the intermediate operations.
B · incorrect — True as one component, but incomplete as the requested full selection. Register allocation and physical assignment decide where values reside and which registers hold them.
C · incorrect — True as one component, but incomplete as the requested full selection. Instruction ordering schedules computations while preserving data and control dependencies.
D · correct — All three listed activities belong to the code-generator task set described in COMP34.
Question 12
What is the term for an actual occurrence of a character sequence in source text that matches a token pattern, such as total or 42?
A. Pattern
B. Lexemes
C. Tokens
D. All
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
A lexeme is the actual character sequence occurring in source text. A token is the category and optional attribute emitted for that occurrence, while a pattern defines which spellings are members of the category. For example, total is a lexeme classified as an identifier token. These are related but distinct objects, so the aggregate choice cannot name the concrete occurrence.
Evidence in the complete study note
A token is a category with optional attribute, such as (ID, symbol-entry) or (INT_LITERAL,42). A lexeme is the actual character sequence, such as total or 42. A pattern specifies which lexemes belong to a token class. The scanner emits an ordered token stream, not an unordered mathematical set.COMP04
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
Grouping characters into token classes is lexical analysis; grouping tokens into expressions and statements is syntax analysis.COMP41
Trees store hierarchical constructs, while a symbol table stores declaration metadata.COMP41
Choice by choice
A · incorrect — A pattern describes possible spellings.
B · correct — Lexeme names the actual matched source sequence.
C · incorrect — Token names the category and optional attribute.
D · incorrect — The three concepts are distinct, not synonymous.
Question 13
Which one of the following are the specific character strings that make up a token?
A. Token
B. Lexemes
C. Lexical units
D. Pattern
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
A lexeme is the sequence of characters matched by a pattern to form a token (PDF p. 8). A token instead denotes a class of similar lexemes, and a pattern specifies the rule. “Specific character strings” therefore identifies lexemes.
Evidence in the complete study note
A token is a category with optional attribute, such as (ID, symbol-entry) or (INT_LITERAL,42). A lexeme is the actual character sequence, such as total or 42. A pattern specifies which lexemes belong to a token class. The scanner emits an ordered token stream, not an unordered mathematical set.COMP04
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
Choice by choice
A · incorrect — Token names the class in the module’s token/lexeme distinction (p. 8).
B · correct — Lexemes are the actual matched sequences (p. 8).
C · incorrect — Lexical units is not the defined name for specific strings in this passage (p. 8).
D · incorrect — A pattern is the matching rule, not its particular match (p. 8).
Question 14
Which one of the following are the program properties that can be checked at run time?
A. Static checking
B. Dynamic semantics
C. Other Static Checks
D. None
Hint / Module Reference (Where to Read)
Ask whether the required information is a declaration’s identity and attributes, program structure or the ordered source tokens.
Semantic checks are static when done during compilation and dynamic when done during run-time (PDF p. 14). Interpreting “Dynamic semantics” as the option’s name for run-time semantic checking, B fits; static checking and other static checks occur during compilation.
Evidence in the complete study note
Static checks occur before execution: type compatibility, duplicate declarations within a restricted scope, valid names, argument counts, return compatibility and control-flow placement. A break is valid only in constructs allowed by the language; in C/C++ it can exit a loop or switch. A compiler may annotate an AST or create typed IR; there is no mandatory uniquely named output tree.COMP21
Dynamic checks depend on runtime values, such as some bounds and null checks. Static analysis can prove some accesses safe or faulty; “all memory errors cannot be statically checked” is too strong. Unreachable code is not universally a semantic error: some languages reject it in specified cases, others merely warn or optimize it away.COMP21
Choice by choice
A · incorrect — Static checking is done at compilation, not run-time (p. 14).
B · correct — B corresponds to the module’s run-time dynamic semantic checks (p. 14).
C · incorrect — Other static checks retain the compile-time timing (p. 14).
D · incorrect — None does not fit because the dynamic check category is present (p. 14).
Question 15
For a language with insignificant whitespace and comments, which choice most completely lists the scanner’s secondary tasks?
A. Stripping out blanks, tabs, new lines
B. Stripping out comments
C. Error reporting
D. All
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
COMP04 says scanners usually skip whitespace and comments while retaining source positions. COMP39 adds that lexical analysis detects its own errors and that error handling is shared. These establish all three listed secondary scanner duties under the ordinary language convention. Layout-sensitive languages are an explicit exception in COMP04, not evidence that scanners never perform these tasks.
Evidence in the complete study note
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
Report the location and cause while avoiding cascades of misleading diagnostics. Lexical, syntax and semantic phases each detect their own errors; error handling is a shared service.COMP39
Choice by choice
A · incorrect — True as one component, but incomplete as the requested full selection. Ordinary scanners skip blanks, tabs and newlines while retaining positions; layout-sensitive languages need special handling.
B · incorrect — True as one component, but incomplete as the requested full selection. Comments are normally discarded instead of being delivered as ordinary parser tokens.
C · incorrect — True as one component, but incomplete as the requested full selection. Lexical errors require reporting, with positions retained to locate the offending source text.
D · correct — Together the choices cover normal whitespace removal, comment removal and lexical error reporting.
Question 16
Which one of the following is the parse tree showing the values of attributes at each node?
A. Inherited attribute
B. Synthesized attribute
C. Annotated parse tree
D. A&B
Hint / Module Reference (Where to Read)
Track where each computed value comes from and when each production action runs. Distinguish the representation from its attached information.
COMP24 directly calls a parse tree displaying computed attribute values an annotated parse tree. Inherited and synthesized classify how attribute information flows; neither is the name of the entire displayed tree. Combining those attribute categories still does not name the representation described in the question.
Evidence in the complete study note
A syntax-directed definition is a CFG with attributes on grammar symbols and semantic rules on productions. An annotated parse tree displays computed attribute values; it is not itself an inherited or synthesized attribute. Synthesized attributes flow from children to a parent; inherited attributes carry context from parent or siblings.COMP24
For E→E1+T, E.val=E1.val+T.val synthesizes an expression value. A declaration’s type environment passed into its body is inherited. S-attributed definitions use only synthesized attributes and fit LR reduction-time evaluation naturally; suitable LL parsers can also compute them. L-attributed definitions restrict dependencies so a left-to-right traversal can evaluate inherited context. Attribute dependency cycles can prevent evaluation.COMP24
Choice by choice
A · incorrect — An inherited attribute carries contextual information; it is not a parse tree displaying values.
B · incorrect — A synthesized attribute carries a value upward, rather than naming the annotated tree.
C · correct — This is the note’s precise name for a parse tree showing attribute values at nodes.
D · incorrect — Combining two attribute categories does not give the name of the displayed tree.
Question 17
Which one of the following can be applied directly after intermediate code generation to
improve the intermediate representation?
A. Peephole optimization
B. Constant Propagation
C. Dead code elimination
D. All
Hint / Module Reference (Where to Read)
Trace whether computation is evaluated, moved, shared or removed. Preserve observable effects and use the stated arithmetic and target assumptions.
Optimization changes intermediate code to remove inefficiencies (PDF p. 7). The module lists peephole transformations and constant propagation (p. 18), and elimination of never-executed or unreachable statements (p. 18). Each can improve an intermediate representation before target code is emitted; no exclusive ordering among those transformations is specified.
Evidence in the complete study note
Constant folding evaluates constant expressions during compilation: 3*4→12. Constant propagation substitutes known values: x=3; y=x+2 becomes y=3+2 before folding. Copy propagation substitutes a copied name while its source remains unchanged. Dead-code elimination removes unreachable code or computations whose values are unused and whose evaluation has no necessary side effects.COMP30
Common-subexpression elimination reuses an earlier value only if operand values and relevant memory remain unchanged. A DAG can represent sharing. Algebraic simplification removes identities when valid: integer x+0→x. Strength reduction replaces an operation with an equivalent cheaper form, such as unsigned x*8→x<<3 for a valid width and shift count. Target costs determine whether it is actually cheaper.COMP31
Peephole optimization examines short instruction windows. It can remove redundant loads/stores, replace machine idioms and shorten jump chains: jump L1 where L1 immediately jumps L2 can become jump L2. Local optimization is a wider category; peephole optimization is a concrete method within the relevant scope.COMP31
B · incorrect — Constant propagation is a listed optimization technique (p. 18).
C · incorrect — Removing unreachable intermediate statements is dead code elimination (p. 18).
D · correct — All three fit the optimization of intermediate code described on p. 7.
Question 18
Which compiler structure associates declared identifier names or identities with attributes such as type, scope and storage location, irrespective of its container implementation?
A. Literal Table
B. Symbol table
C. Hash table
D. All
Hint / Module Reference (Where to Read)
Ask whether the required information is a declaration’s identity and attributes, program structure or the ordered source tokens.
A symbol table maps identifier names or declaration identities to attributes such as type, scope and storage location. A hash table is one possible implementation of that mapping, not its semantic role. Literal tables concern literal values, and punctuation need not have symbol records at all. Restricting the question to identifier metadata avoids claiming that every token kind uses the same table.
Evidence in the complete study note
A symbol table maps names or symbol identities to attributes: type, scope, width, storage offset, parameter signature, constant information or linkage. A hash table gives expected O(1) insertion/lookup with suitable hashing; a stack of scope tables supports lexical nesting. Search the nearest scope first, insert declarations in the current scope, and remove visibility when leaving it.COMP19
Scanning may intern a spelling first; semantic analysis determines the declaration and type. Implementations differ, so first interaction is conventional rather than universal. Not every punctuation token needs a symbol-table entry; literals may use a separate literal table. A hash table is an implementation, not the information’s semantic role.COMP19
Grouping characters into token classes is lexical analysis; grouping tokens into expressions and statements is syntax analysis.COMP41
Trees store hierarchical constructs, while a symbol table stores declaration metadata.COMP41
Choice by choice
A · incorrect — A literal table concerns literal values.
B · correct — The symbol table provides this mapping.
C · incorrect — Hashing is an implementation technique rather than the semantic role.
D · incorrect — The structures have different roles.
Question 19
The output of lexical analyzer is*
A. Syntax tree
B. Strings of characters
C. A set of tokens
D. set of regular expressions
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
The output of lexical analysis is expressly a sequence of tokens (PDF p. 8). C is the only option naming that output, although “set” should be read informally: order matters, so the module’s precise word is sequence.
Evidence in the complete study note
A token is a category with optional attribute, such as (ID, symbol-entry) or (INT_LITERAL,42). A lexeme is the actual character sequence, such as total or 42. A pattern specifies which lexemes belong to a token class. The scanner emits an ordered token stream, not an unordered mathematical set.COMP04
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
Choice by choice
A · incorrect — The parse tree is produced by syntax analysis.
B · incorrect — Characters are the scanner input, not its classified output.
C · correct — Tokens are the output elements (p. 8).
D · incorrect — Patterns describe tokens; they are not the source-specific output sequence (p. 8).
Question 20
Which of the following is NOT the primary role of code generator in compiler design? *
A. instruction selection
B. Declaration of variables
C. instruction ordering
D. A Register allocation
Hint / Module Reference (Where to Read)
Identify what the representation stores, what it omits and which later transformations it must support; separate a representation property from an algorithmic task.
Code generation lowers checked intermediate code into target operations. It selects instructions, allocates registers and orders instructions subject to dependencies. Declarations instead establish source names, types and storage information during analysis; generating code may use that information without declaring the variables again. Thus the declaration activity is outside the primary code-generator task set, while the other three choices describe target implementation decisions.
Evidence in the complete study note
IR separates source analysis from target implementation, allowing optimizers and backends to be reused. It should be easy to generate, analyze, transform and lower.COMP26
Ordinary TAC arithmetic has at most one operation, two sources and one destination: t1=c*d; t2=b+t1; a=t2. Quadruples store (op,arg1,arg2,result); triples omit an explicit result field and refer to instruction positions. Indirect triples reference a separate ordering list, easing rearrangement. Trees describe expressions; DAGs share common subexpressions, while quadruples/triples are instruction-record structures.COMP26
Code generation lowers checked IR to a target form. Instruction selection chooses target operations; register allocation chooses where values reside; scheduling orders instructions while respecting dependencies; storage layout assigns offsets and follows ABI requirements. Register assignment names actual physical registers after allocation decisions.COMP34
For t=a+b, a simple target could emit LOAD R1,a; LOAD R2,b; ADD R3,R1,R2; STORE t,R3. Other targets may combine loads with arithmetic or keep t in a register. Machine idioms, register availability and instruction order affect execution time.COMP34
Choice by choice
A · incorrect — Instruction selection chooses target operations implementing the IR.
B · correct — Processing source declarations belongs to analysis and symbol-table/type handling.
C · incorrect — Instruction ordering schedules target computations while preserving dependencies.
D · incorrect — Register allocation decides where intermediate values reside.
Question 21
Which one of the following is different from the others?
A. quadruples
B. triples
C. tree
D. indirect triples
Hint / Module Reference (Where to Read)
Identify what the representation stores, what it omits and which later transformations it must support; separate a representation property from an algorithmic task.
Quadruples, triples, indirect triples, trees and DAGs all implement three-address code (PDF p. 16). Quadruples and triples have numbered record fields, and indirect triples use pointers; tree is the hierarchical representation. C is the natural odd one out under that structural distinction.
Evidence in the complete study note
IR separates source analysis from target implementation, allowing optimizers and backends to be reused. It should be easy to generate, analyze, transform and lower.COMP26
Ordinary TAC arithmetic has at most one operation, two sources and one destination: t1=c*d; t2=b+t1; a=t2. Quadruples store (op,arg1,arg2,result); triples omit an explicit result field and refer to instruction positions. Indirect triples reference a separate ordering list, easing rearrangement. Trees describe expressions; DAGs share common subexpressions, while quadruples/triples are instruction-record structures.COMP26
Choice by choice
A · incorrect — Quadruples are instruction records with four fields (p. 16).
B · incorrect — Triples are instruction records with three fields (p. 16).
C · correct — Tree is the hierarchical structure among the options (p. 16).
D · incorrect — Indirect triples retain a pointer-based triple representation (p. 16).
Question 22
A compiler computes expression-type attributes and checks compatibility as grammar productions are processed. Which offered description most specifically identifies this mechanism?
A. During lexical analysis
B. During syntax analysis
C. During syntax directed translation
D. During code optimization
Hint / Module Reference (Where to Read)
Check operand compatibility and permitted conversions under the stated language rules; distinguish grammatical structure from semantic meaning.
Correct answer: C — During syntax directed translation
The compiler in the scenario evaluates type attributes and applies compatibility checks as grammar productions are processed. This is syntax-directed translation: semantic rules or actions are attached to grammatical structure. Pure lexical analysis only recognizes tokens, and pure syntax recognition alone does not establish operand-type compatibility. Optimization transforms an already analyzed representation. Parsing can invoke these semantic actions, so the mechanism is more precise than naming syntax analysis alone.
Evidence in the complete study note
A syntax-directed definition is a CFG with attributes on grammar symbols and semantic rules on productions.COMP24
A syntax-directed translation scheme embeds executable actions in productions; the actions run while translating a source program, not while generating the compiler. Attributes may compute types, values, AST pointers or generated code.COMP25
A type checker verifies that operations are defined for their operands. In a simple strict language, integer mod requires two integers; array indexing requires an array and integer index; an if condition requires Boolean; assignment requires equal or convertible types. Function calls check parameter count and compatibility, and returns match result types.COMP22
Choice by choice
A · incorrect — Token recognition alone does not compute full expression-type compatibility.
B · incorrect — Pure syntax recognition checks grammar; the scenario additionally attaches semantic computations.
C · correct — Syntax-directed semantic actions compute and check attributes associated with productions.
D · incorrect — Optimization transforms analyzed code rather than naming the stated checking mechanism.
Question 23
In a conventional pipeline that lowers TAC further to native code or VM instructions, which representation is intermediate rather than the final emitted target?
A. Three address code
B. Assembly language
C. Absolute machine code
D. Byte Code
Hint / Module Reference (Where to Read)
Identify what the representation stores, what it omits and which later transformations it must support; separate a representation property from an algorithmic task.
Three-address code is intermediate in the specified pipeline: analysis and optimization transform it before code generation lowers it further. Assembly, absolute machine code and VM bytecode can each be final target forms for an appropriate compiler. This pipeline-specific distinction does not assert that TAC could never be another translator’s target; it identifies the expressly stated intermediate role here.
Evidence in the complete study note
Code generation lowers checked IR to a target form. Instruction selection chooses target operations; register allocation chooses where values reside; scheduling orders instructions while respecting dependencies; storage layout assigns offsets and follows ABI requirements. Register assignment names actual physical registers after allocation decisions.COMP34
For t=a+b, a simple target could emit LOAD R1,a; LOAD R2,b; ADD R3,R1,R2; STORE t,R3. Other targets may combine loads with arithmetic or keep t in a register. Machine idioms, register availability and instruction order affect execution time.COMP34
IR separates source analysis from target implementation, allowing optimizers and backends to be reused. It should be easy to generate, analyze, transform and lower.COMP26
Ordinary TAC arithmetic has at most one operation, two sources and one destination: t1=c*d; t2=b+t1; a=t2. Quadruples store (op,arg1,arg2,result); triples omit an explicit result field and refer to instruction positions. Indirect triples reference a separate ordering list, easing rearrangement. Trees describe expressions; DAGs share common subexpressions, while quadruples/triples are instruction-record structures.COMP26
Choice by choice
A · correct — TAC is lowered further in this pipeline.
B · incorrect — Assembly can be a final emitted target.
C · incorrect — Absolute machine code can be a final target.
D · incorrect — VM bytecode can be a final target.
Question 24
Which of the following is NOT important property of intermediate code
representation?
A. Ease of generation
B. Ease of manipulation
C. Register allocation
D. Level of abstraction
Hint / Module Reference (Where to Read)
Identify what the representation stores, what it omits and which later transformations it must support; separate a representation property from an algorithmic task.
An intermediate representation should be convenient to generate, analyze and transform, and its abstraction should suit optimization and target lowering. Those are design properties of the representation. Register allocation is an algorithmic backend task that chooses locations for values; it is not itself a property such as ease of generation or abstraction level. An IR can carry information useful to that task without making allocation a representation property.
Evidence in the complete study note
IR separates source analysis from target implementation, allowing optimizers and backends to be reused. It should be easy to generate, analyze, transform and lower.COMP26
Ordinary TAC arithmetic has at most one operation, two sources and one destination: t1=c*d; t2=b+t1; a=t2. Quadruples store (op,arg1,arg2,result); triples omit an explicit result field and refer to instruction positions. Indirect triples reference a separate ordering list, easing rearrangement. Trees describe expressions; DAGs share common subexpressions, while quadruples/triples are instruction-record structures.COMP26
Code generation lowers checked IR to a target form. Instruction selection chooses target operations; register allocation chooses where values reside; scheduling orders instructions while respecting dependencies; storage layout assigns offsets and follows ABI requirements. Register assignment names actual physical registers after allocation decisions.COMP34
For t=a+b, a simple target could emit LOAD R1,a; LOAD R2,b; ADD R3,R1,R2; STORE t,R3. Other targets may combine loads with arithmetic or keep t in a register. Machine idioms, register availability and instruction order affect execution time.COMP34
Choice by choice
A · incorrect — Ease of generation is a useful IR design property.
B · incorrect — Ease of manipulation supports analysis and transformation passes.
C · correct — Register allocation is a backend decision over values rather than an IR property.
D · incorrect — Abstraction level determines which source and target details the representation exposes.
Question 25
What is the main purpose of syntax-directed translation in a compiler?
A. To interleave semantic analysis with syntax analysis using attributes attached to
grammar symbols
B. To generate optimized machine code directly
C. .
To tokenize the source code
D. To replace the parser with a finite automaton
Hint / Module Reference (Where to Read)
Track where each computed value comes from and when each production action runs. Distinguish the representation from its attached information.
Correct answer: A — To interleave semantic analysis with syntax analysis using attributes attached to
grammar symbols
A syntax-directed definition is a CFG with attributes and rules; attributes attach to symbols and rules to productions (PDF p. 12). Actions execute according to the parsing mechanism. This is the grammar-based integration of semantic processing described in A, rather than a direct optimized-machine-code replacement for the remaining phases.
Evidence in the complete study note
A syntax-directed definition is a CFG with attributes on grammar symbols and semantic rules on productions. An annotated parse tree displays computed attribute values; it is not itself an inherited or synthesized attribute. Synthesized attributes flow from children to a parent; inherited attributes carry context from parent or siblings.COMP24
For E→E1+T, E.val=E1.val+T.val synthesizes an expression value. A declaration’s type environment passed into its body is inherited. S-attributed definitions use only synthesized attributes and fit LR reduction-time evaluation naturally; suitable LL parsers can also compute them. L-attributed definitions restrict dependencies so a left-to-right traversal can evaluate inherited context. Attribute dependency cycles can prevent evaluation.COMP24
Choice by choice
A · correct — A matches the attribute/rule and parsing-action definitions (p. 12).
B · incorrect — Machine-code conversion is a later code-generation task (p. 7), not the definition of SDT.
C · incorrect — Tokenization is lexical analysis (p. 8).
D · incorrect — The module retains the grammar/parsing mechanism; it does not replace it with an automaton (p. 12).
Question 26
Straight directed translation uses:
A. Purely lexical rules
B. Backtracking algorithms
C. ¢.
Grammar without attributes
D. Grammar with sematic rule
Hint / Module Reference (Where to Read)
Track where each computed value comes from and when each production action runs. Distinguish the representation from its attached information.
Interpreting the apparent typo “Straight directed translation” as syntax-directed translation, the module defines it through actions on productions and a CFG with attributes and semantic rules (PDF p. 12). D is the only option that retains this grammar-plus-rule structure.
Evidence in the complete study note
A syntax-directed definition is a CFG with attributes on grammar symbols and semantic rules on productions. An annotated parse tree displays computed attribute values; it is not itself an inherited or synthesized attribute. Synthesized attributes flow from children to a parent; inherited attributes carry context from parent or siblings.COMP24
For E→E1+T, E.val=E1.val+T.val synthesizes an expression value. A declaration’s type environment passed into its body is inherited. S-attributed definitions use only synthesized attributes and fit LR reduction-time evaluation naturally; suitable LL parsers can also compute them. L-attributed definitions restrict dependencies so a left-to-right traversal can evaluate inherited context. Attribute dependency cycles can prevent evaluation.COMP24
Choice by choice
A · incorrect — Pure lexical rules omit the production-associated semantic actions (p. 12).
B · incorrect — Backtracking is not the defining mechanism; actions follow the chosen parser (p. 12).
C · incorrect — A grammar without attributes omits the defining additions in a syntax-directed definition (p. 12).
D · correct — A grammar with semantic rules matches the definition (p. 12).
Question 27
Which one of the following is a top-down parser without backtracking?
A. LR parser
B. Brute force parser
C. Operator precedence parser
D. Predictive parser
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
COMP11 defines predictive parsing by choosing productions with lookahead without backtracking. This supplies both requirements in the stem: top-down direction and absence of backtracking. LR and operator-precedence parsing belong to bottom-up approaches; brute-force top-down trial does not provide the no-backtracking guarantee.
Evidence in the complete study note
Top-down parsing starts with S and expands productions toward the input, usually constructing a leftmost derivation. Recursive descent typically has one procedure per nonterminal. A general recursive-descent implementation can backtrack; a predictive parser chooses a production using lookahead without backtracking. LL(1) scans Left to right, produces a Leftmost derivation and uses one lookahead token.COMP11
Bottom-up parsing starts from input and reduces toward S, constructing a rightmost derivation in reverse.COMP15
Operator-precedence parsing is a restricted bottom-up expression-parsing method using a stack and precedence relations. With a suitable expression grammar, the stack retains unfinished surrounding expressions while nested parentheses are processed.COMP-S01
Choice by choice
A · incorrect — LR parsing reduces input bottom-up rather than expanding the start symbol top-down.
B · incorrect — Brute-force production trials can require backtracking and do not meet the defining predictive constraint.
C · incorrect — Operator-precedence parsing is a bottom-up technique rather than predictive top-down expansion.
D · correct — Predictive parsing uses lookahead to choose productions without backtracking, exactly as COMP11 states.
Question 28
If input is "a" is for syntax tree, which function is used to create tree?
A. mknode(num, value)
B. mkleaf(num, value)
C. mkleaf(id, entry)
D. mknode(op, left, right)
Hint / Module Reference (Where to Read)
Track where each computed value comes from and when each production action runs. Distinguish the representation from its attached information.
For the expression a-4+c the first construction is P1=mkleaf(id,entrya) (PDF p. 13). Since a is an identifier, its node stores a pointer to the identifier’s symbol-table entry. Numeric leaf construction is instead used for 4; operator nodes connect child nodes.
Evidence in the complete study note
A syntax-directed translation scheme embeds executable actions in productions; the actions run while translating a source program, not while generating the compiler. Attributes may compute types, values, AST pointers or generated code. The scheme defines an input-to-output translation, not merely an input language.COMP25
Create an identifier leaf with mkleaf(id,entry), a number with mkleaf(num,value), and an operator node with mknode(op,left,right). For a−4+c, construct +(−(a,4),c). Postorder traversal prints postfix: a 4 − c +. A stack evaluator pushes operands and pops right then left operands for an operator. Infix-to-postfix is useful for stack machines but not mandatory for all compilers.COMP25
Choice by choice
A · incorrect — The module uses mkleaf, not mknode, for a numeric constant, and a is not a number (p. 13).
B · incorrect — This creates a numeric leaf, suitable for 4 rather than identifier a (p. 13).
C · correct — This is exactly the identifier-leaf constructor used for a (p. 13).
D · incorrect — This makes an operator node with two children, not an identifier leaf (pp. 12–13).
Question 29
Which statement is WRONGLY described about code generation?
A. Code generation can be considered as the start phase of compilation
B. The target program is the output of the code generator
C. Checked intermediate code is supplied as input to the code generator.
D. It used to produce the target code for three-address statements.
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
Correct answer: A — Code generation can be considered as the start phase of compilation
Lexical analysis begins the standard pipeline by recognizing tokens. Code generation occurs after analysis and IR construction, lowering checked IR to a target form. Its output is target code, which may be assembly or an object form, and it can translate three-address statements. Therefore calling code generation the start phase is the wrong description. The input option is read as checked IR suitable for lowering, without claiming a compiler can prove the absence of every program defect.
Evidence in the complete study note
The conventional sequence is lexical analysis → syntax analysis → semantic analysis → intermediate-code generation → optimization → target-code generation. Scanning turns characters into tokens; parsing builds structure; semantics checks declarations and types; synthesis produces implementation code. A phase is a logical activity; a pass is a traversal that can combine activities.COMP03
Code generation lowers checked IR to a target form.COMP34
Choice by choice
A · correct — Code generation follows the frontend and IR; it is not the initial scanning phase.
B · incorrect — The generator produces code in a target representation.
C · incorrect — Checked intermediate code supplies the operations and metadata to lower.
D · incorrect — Three-address statements can be lowered into target instructions.
Question 30
Which of the following is NOT a task of the lexical analyzer?
A. Generating parse trees
B. Correlating errors with line numbers
C. Entering identifiers into the symbol table
D. Stripping whitespace and comments
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
Scanning turns characters into tokens, usually skips insignificant whitespace and comments, and retains source positions for diagnostics. A scanner may also intern identifier spellings in a symbol table; later semantic processing adds scope and declaration information. Parse-tree construction belongs to syntax analysis because it arranges the token stream according to grammar productions. It is consequently the activity outside the scanner’s listed responsibilities.
Evidence in the complete study note
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
A parse tree shows grammar productions: root S, internal nonterminals, and terminal leaves, with ε sometimes shown for empty productions. Its left-to-right yield is the input.COMP09
Choice by choice
A · correct — Parse trees represent grammar structure built by parsing.
B · incorrect — Tracking token positions and line numbers supports scanner diagnostics.
C · incorrect — Scanner-side interning can enter identifier spellings, distinct from later declaration analysis.
D · incorrect — Ordinary scanners discard insignificant whitespace and comments.
Question 31
Which analysis used to read the sequence of the characters from the
source program?
A. a | Lexical Analysis A
B. i? Syntax Analysis ><
C. /@| Semantic Analysis x
D. | All of the above x
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
PDF p. 5 explicitly says lexical analysis scans source code as a stream of characters; syntax groups tokens, and semantics checks meaningful compatibility (p. 6).
Evidence in the complete study note
A token is a category with optional attribute, such as (ID, symbol-entry) or (INT_LITERAL,42). A lexeme is the actual character sequence, such as total or 42. A pattern specifies which lexemes belong to a token class. The scanner emits an ordered token stream, not an unordered mathematical set.COMP04
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
Choice by choice
A · correct — Lexical analysis explicitly reads the character stream.
B · incorrect — Syntax analysis works on tokens grouped hierarchically.
Bottom-up parsing starts with input symbols and reduces recognized right-hand sides until it reaches the start symbol. A shift-reduce parser implements this by shifting input onto a stack and reducing handles. Recursive descent expands from a start-symbol procedure and is top-down; predictive parsing is a top-down approach that uses lookahead to choose productions. Therefore the aggregate alternative cannot apply to methods with these different construction directions.
Evidence in the complete study note
Top-down parsing starts with S and expands productions toward the input, usually constructing a leftmost derivation. Recursive descent typically has one procedure per nonterminal. A general recursive-descent implementation can backtrack; a predictive parser chooses a production using lookahead without backtracking. LL(1) scans Left to right, produces a Leftmost derivation and uses one lookahead token.COMP11
Bottom-up parsing starts from input and reduces toward S, constructing a rightmost derivation in reverse.COMP15
Choice by choice
A · incorrect — Recursive descent expands productions from nonterminals and is top-down.
B · incorrect — Predictive parsing chooses top-down productions using lookahead.
C · correct — Shifting input and reducing handles is the bottom-up shift-reduce method.
D · incorrect — The list includes top-down methods, so not all are bottom-up.
Question 33
How many tokens are in the C++ loop header for (int i = 0; i <= 10; i++)? Ignore whitespace and count <= and ++ as single operator tokens.
A. 4
B. 5
C. 9
D. 14
Hint / Module Reference (Where to Read)
Follow the representation at each construction step and apply the pattern or state-set rules consistently, including empty cases.
The tokens are for, (, int, i, =, 0, ;, i, <=, 10, ;, i, ++, ). There are fourteen occurrences. Whitespace contributes nothing, but both semicolons and both parentheses count. Longest match makes <= and ++ one token each; it does not merge neighboring identifiers or discard repeated tokens. The numerical option therefore gives the unique count.
Evidence in the complete study note
At each input position, choose the longest matching lexeme; if equal lengths match multiple flex rules, choose the earliest rule. Thus ifx is an identifier rather than if followed by x; <= and ++ are each one operator token.COMP07
There are 14 tokens, irrespective of spacing. The increment operator is one token.COMP07
Choice by choice
A · incorrect — Four omits most token occurrences.
B · incorrect — Five misses operators, punctuation and operands.
C · incorrect — Nine is below the fourteen-token count.
D · correct — The complete sequence contains fourteen tokens.
Question 34
Identify the correct definition of lexical analysis.
A. Breaking a sequence of characters into packets.
B. Breaking a sequence of characters into groups.
C. Breaking a sequence of characters into tokens.
D. Breaking a sequence of characters into lines.
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
Correct answer: C — Breaking a sequence of characters into tokens.
Lexical analysis takes a source program and outputs a sequence of tokens (PDF p. 8). Thus its relevant grouping units are tokens, rather than network packets, arbitrary groups, or source lines.
Evidence in the complete study note
A token is a category with optional attribute, such as (ID, symbol-entry) or (INT_LITERAL,42). A lexeme is the actual character sequence, such as total or 42. A pattern specifies which lexemes belong to a token class. The scanner emits an ordered token stream, not an unordered mathematical set.COMP04
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
Choice by choice
A · incorrect — Packets are not the compiler units described on p. 8.
B · incorrect — Groups is too unspecific; the defined output units are tokens (p. 8).
C · correct — Breaking the character sequence into tokens matches scanning (pp. 5, 8).
D · incorrect — Lines are tracked and whitespace stripped; they are not the primary output units (p. 8).
Question 35
What does a top-down parser generate?
A. Rightmost derivation in reverse.
B. Rightmost derivation.
C. Leftmost derivation in reverse.
D. Leftmost derivation.
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
The module says top-down parsing builds from the start symbol (PDF p. 10), and the LL/LR comparison pairs top-down LL with leftmost derivation and bottom-up LR with rightmost derivation in reverse (p. 11). D matches the top-down direction.
Evidence in the complete study note
Top-down parsing starts with S and expands productions toward the input, usually constructing a leftmost derivation. Recursive descent typically has one procedure per nonterminal. A general recursive-descent implementation can backtrack; a predictive parser chooses a production using lookahead without backtracking. LL(1) scans Left to right, produces a Leftmost derivation and uses one lookahead token.COMP11
A nonrecursive predictive parser stores grammar symbols on an explicit stack and consults a table. It is another implementation of predictive parsing, not a wholly different language class. Table-driven and recursive predictive implementations can both be linear for a fixed suitable grammar. Efficiency cannot be ranked from their names alone.COMP11
Choice by choice
A · incorrect — Rightmost derivation in reverse is the LR/bottom-up entry (p. 11).
B · incorrect — Rightmost derivation alone is not the listed top-down entry (p. 11).
C · incorrect — The top-down derivation is leftmost in the forward direction, not reversed (p. 11).
D · correct — Leftmost derivation is explicitly the LL/top-down entry (p. 11).
Question 36
For line 3, fro ((I = o, I;, in the displayed C program, classify only lexical and syntactic well-formedness. Treat fro and o as legal identifier spellings and leave declaration/type diagnostics outside this question.
A. Syntax error, with no lexical error established.
B. No compilation error.
C. Only lexical error.
D. Both lexical and syntax error.
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
Correct answer: A — Syntax error, with no lexical error established.
The characters fro and o form valid identifier lexemes, so their spellings do not establish a lexical error. The displayed line nevertheless has mismatched parentheses and an invalid token arrangement, establishing a syntax error. Under this restricted lexical/syntactic classification, A is correct. Declaration or type diagnostics may arise in a real compiler, but are outside the expressly stated classification scope.
Evidence in the complete study note
A lexical error prevents forming a legal token, such as an invalid character or unterminated literal. A syntax error is an illegal token arrangement, such as a missing delimiter. A semantic error violates name, scope or type rules after grammatical recognition.COMP08
In the malformed C line fro ((I = o, I;, fro and lowercase o are legal identifier lexemes. Misspelling for does not turn fro into a lexical error; mismatched syntax is definite, and undeclared o can also produce a semantic diagnostic.COMP08
Choice by choice
A · correct — The arrangement is syntactically invalid without an established lexical fault.
B · incorrect — Mismatched delimiters prevent syntactic validity.
C · incorrect — Legal identifier spellings do not establish a lexical error.
D · incorrect — A syntax error exists but no lexical error is established.
Question 37
Which tool is used for grouping of characters in tokens in the compiler?
A. Parser
B. Code optimizer
C. Code generator
D. Scanner
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
Lexical analysis is called scanning on PDF p. 5 and outputs tokens on p. 8. Hence the scanner is the component that groups source characters into tokens, before the parser handles token structure.
Evidence in the complete study note
A token is a category with optional attribute, such as (ID, symbol-entry) or (INT_LITERAL,42). A lexeme is the actual character sequence, such as total or 42. A pattern specifies which lexemes belong to a token class. The scanner emits an ordered token stream, not an unordered mathematical set.COMP04
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
Choice by choice
A · incorrect — The parser groups tokens into syntactic constructs.
B · incorrect — The optimizer improves intermediate code (p. 7).
C · incorrect — The generator converts intermediate code to machine code (p. 7).
D · correct — Scanner is the component associated with lexical analysis (pp. 5, 8).
Question 38
When parsing techniques are classified by the direction in which they construct the parse tree, how many broad categories are there?
A. three types
B. four types
C. two types
D. five types
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
Construction direction gives two broad categories. Top-down parsing expands from the start symbol toward the input, while bottom-up parsing reduces input toward the start symbol. Recursive descent, predictive parsing and LR are algorithms or families within that classification rather than additional directions. Counting named algorithms would give a different and open-ended taxonomy, so the revised question explicitly counts only the broad construction directions.
Evidence in the complete study note
The common two-way classification of parsing is by construction direction: top-down parsing expands from the start symbol, while bottom-up parsing reduces the input toward that symbol. This counts broad directions, not the number of parser algorithms or implementations.COMP-S01
Choice by choice
A · incorrect — Three is not the number of construction directions in this two-way taxonomy.
B · incorrect — Four may count selected algorithms, but it does not count the two broad directions.
C · correct — The directions are top-down and bottom-up.
D · incorrect — Five is not the number of construction directions.
Question 39
In which parsing, the parser constructs the parse tree from the start symbol and transforms it into the input symbol.
A. Bottom-up parsing
B. Top-down parsing
C. None of the above
D. Both a and b
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
Top-down parsing starts from the start symbol and transforms it into the input (PDF p. 10). Bottom-up parsing starts with input symbols and constructs toward the start symbol. The stem is an almost verbatim description of the first direction.
Evidence in the complete study note
Top-down parsing starts with S and expands productions toward the input, usually constructing a leftmost derivation. Recursive descent typically has one procedure per nonterminal. A general recursive-descent implementation can backtrack; a predictive parser chooses a production using lookahead without backtracking. LL(1) scans Left to right, produces a Leftmost derivation and uses one lookahead token.COMP11
A nonrecursive predictive parser stores grammar symbols on an explicit stack and consults a table. It is another implementation of predictive parsing, not a wholly different language class. Table-driven and recursive predictive implementations can both be linear for a fixed suitable grammar. Efficiency cannot be ranked from their names alone.COMP11
Choice by choice
A · incorrect — Bottom-up starts from input symbols, the opposite endpoint (p. 10).
B · correct — Top-down starts from the start symbol as requested (p. 10).
C · incorrect — The described category is explicitly present, so none is false (p. 10).
D · incorrect — Both is false because the two categories have opposite starting points (p. 10).
Question 40
Which derivation is generated by the top-down parser?
A. Right-most derivation in reverse
B. Left-most derivation in reverse
C. Right-most derivation
D. Left-most derivation
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
The LL/top-down column uses leftmost derivation, while the LR/bottom-up column uses rightmost derivation in reverse (PDF p. 11). Consequently a top-down parser generates a forward leftmost derivation.
Evidence in the complete study note
Top-down parsing starts with S and expands productions toward the input, usually constructing a leftmost derivation. Recursive descent typically has one procedure per nonterminal. A general recursive-descent implementation can backtrack; a predictive parser chooses a production using lookahead without backtracking. LL(1) scans Left to right, produces a Leftmost derivation and uses one lookahead token.COMP11
A nonrecursive predictive parser stores grammar symbols on an explicit stack and consults a table. It is another implementation of predictive parsing, not a wholly different language class. Table-driven and recursive predictive implementations can both be linear for a fixed suitable grammar. Efficiency cannot be ranked from their names alone.COMP11
Choice by choice
A · incorrect — This is the bottom-up LR direction (p. 11).
B · incorrect — The LL entry is leftmost without reversal (p. 11).
C · incorrect — Rightmost is not the listed top-down derivation (p. 11).
D · correct — Leftmost is explicitly the top-down/LL entry (p. 11).
Question 41
Which derivation is generated by the bottom-up parser?
A. Right-most derivation in reverse
B. Left-most derivation in reverse
C. Right-most derivation
D. Left-most derivation
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
Correct answer: A — Right-most derivation in reverse
PDF p. 10 describes bottom-up parsing as reducing input symbols toward the start symbol, following a rightmost derivation in reverse. PDF p. 11 repeats this as the definition of LR parsing. Thus A gives both the correct derivation kind and direction.
Evidence in the complete study note
Bottom-up parsing starts from input and reduces toward S, constructing a rightmost derivation in reverse. A handle is a production RHS occurrence whose reduction is the next step of that reverse derivation. Not every substring matching a RHS is a handle in the current context.COMP15
Shift pushes the next input token and a state; reduce replaces a recognized RHS by its LHS and consults GOTO; accept recognizes completion; error reports an invalid situation. For A→XYZ, pop three grammar symbols and their states, expose state q, then push A and GOTO[q,A]. “Go” is not a separate standard shift-reduce ACTION, although GOTO is essential table machinery.COMP15
Choice by choice
A · correct — Rightmost derivation in reverse is explicitly stated (pp. 10–11).
B · incorrect — Leftmost in reverse is not the module’s bottom-up rule (p. 11).
C · incorrect — Rightmost without reversal would expand rather than describe the stated reductions (pp. 10–11).
D · incorrect — Leftmost is paired with LL/top-down parsing (p. 11).
Question 42
Among these named deterministic parser methods, which has the broadest grammar coverage under the standard SLR(1), LALR(1) and canonical LR(1) comparison?
A. Operator Precedence
B. SLR
C. Canonical LR
D. LALR
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
Canonical LR(1) keeps context-specific lookahead and covers at least the grammars handled by SLR(1) and LALR(1), with strictly greater coverage in the standard comparison. Operator-precedence parsing is a more restricted expression-parsing method. This is a comparison of grammar coverage, not speed, implementation simplicity or table size. Canonical LR may require larger tables and still does not parse every unambiguous context-free grammar.
Evidence in the complete study note
In the standard comparison by grammar coverage, canonical LR(1) is more general than the restricted operator-precedence method. Together with SLR(1)⊆LALR(1)⊆LR(1), this makes canonical LR(1) the broadest of those named deterministic parsing methods. Broader coverage does not mean faster execution or smaller tables.COMP-S01
The standard grammar-class hierarchy is LR(0)⊆SLR(1)⊆LALR(1)⊆LR(1), with increasing capability and often table size.COMP17
Choice by choice
A · incorrect — Operator-precedence parsing applies to a more restricted grammar family.
B · incorrect — SLR(1) uses less context-specific reduction information and has narrower grammar coverage.
C · correct — Canonical LR(1) has the broadest coverage among the named methods.
D · incorrect — Merging LR(1) cores for LALR(1) can lose distinctions needed by some LR(1) grammars.
Question 43
The output of the lexical analyzer is _______
A. string character
B. a syntax tree
C. a set of RE
D. a set of tokens
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
The lexical analyzer’s output is a sequence of tokens (PDF p. 8). Among the options only D identifies these elements; “set” is informal wording for the ordered stream.
Evidence in the complete study note
A token is a category with optional attribute, such as (ID, symbol-entry) or (INT_LITERAL,42). A lexeme is the actual character sequence, such as total or 42. A pattern specifies which lexemes belong to a token class. The scanner emits an ordered token stream, not an unordered mathematical set.COMP04
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
Choice by choice
A · incorrect — Source characters are scanned as input.
B · incorrect — The syntax tree belongs to parsing.
C · incorrect — Regular expressions are not the listed scanner output; patterns are rules (p. 8).
D · correct — Tokens are explicitly the scanner output (p. 8).
Question 44
Which is the least sufficient Chomsky grammar family for ordinary token patterns specified by classical regular expressions, rather than a purpose-based grammar name?
A. Lexical Grammar
B. Context-free Grammar
C. Syntactic Grammar
D. Regular Grammar
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
Ordinary regular-expression token patterns describe regular languages, whose least sufficient Chomsky family is regular grammar. A lexical grammar names a specification by purpose, whereas this question asks for its formal family. Context-free grammars are more expressive than required and typically model nested syntax. Syntactic grammar is another purpose label rather than the specific formal family matching the regular token patterns.
Evidence in the complete study note
Classical regular expressions, consistently right-linear regular grammars and finite automata describe the same regular-language family. Thus an ordinary token pattern specified by a regular expression also has a regular grammar and an equivalent finite-state recognizer.COMP-S03
This equivalence concerns expressive power, not spelling of the specification or implementation size. Context-free grammars can also describe regular languages, but their larger family is needed for syntax with unbounded nested structure rather than ordinary regular token patterns.COMP-S03
Lexical analysis scans source characters into tokens and removes blanks/newlines/comments (PDF pp. 5, 8). Thus comment removal, whitespace removal, and tokenization all belong to the scanner in this module, making D the inclusive choice.
Evidence in the complete study note
A token is a category with optional attribute, such as (ID, symbol-entry) or (INT_LITERAL,42). A lexeme is the actual character sequence, such as total or 42. A pattern specifies which lexemes belong to a token class. The scanner emits an ordered token stream, not an unordered mathematical set.COMP04
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
Choice by choice
A · incorrect — Comment removal is expressly stated (p. 8).
B · incorrect — Whitespace stripping is expressly stated (p. 8).
C · incorrect — Interpreting “syntaxes” as source text, tokenization is the lexical role.
D · correct — All combines the three documented responsibilities (pp. 5, 8).
Question 46
Which is considered as the sequence of characters in a token?
A. Mexeme
B. Lexeme
C. Texeme
D. Pattern
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
PDF p. 8 calls the matched character sequence a Lexeme. A pattern is the rule that matches that sequence, rather than the concrete spelling itself.
Evidence in the complete study note
A token is a category with optional attribute, such as (ID, symbol-entry) or (INT_LITERAL,42). A lexeme is the actual character sequence, such as total or 42. A pattern specifies which lexemes belong to a token class. The scanner emits an ordered token stream, not an unordered mathematical set.COMP04
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
Choice by choice
A · incorrect — Mexeme is not a defined tokenization term (p. 8).
B · correct — Lexeme is the exact defined term (p. 8).
C · incorrect — Texeme is not a defined tokenization term (p. 8).
D · incorrect — Pattern is a rule describing a token, not the matched sequence (p. 8).
Question 47
Which part of the compiler highly used the grammar concept?
A. Code optimization
B. Code generation
C. Parser
D. Lexical Analysis
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
PDF p. 9 explicitly states that parsers/syntax analyzers are generated for a particular grammar and CFGs specify programming-language syntax. This directly connects the parser to the grammar concept asked about.
Evidence in the complete study note
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
A parse tree shows grammar productions: root S, internal nonterminals, and terminal leaves, with ε sometimes shown for empty productions. Its left-to-right yield is the input.COMP09
Choice by choice
A · incorrect — Optimization is defined through removal of inefficiencies, not grammar-based recognition (p. 7).
B · incorrect — Generation converts intermediate code to machine code (p. 7).
C · correct — Parser generation and syntax specification are explicitly grammar-based (p. 9).
D · incorrect — Lexical patterns classify tokens (p. 8); the cited grammar emphasis is the parser (p. 9).
Question 48
Which phase of the compiler checks the grammar of the programming?
A. Code Optimization
B. Semantic Analysis
C. Code Generation
D. Syntax Analysis
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
Syntax analysis groups tokens into nested constructs, catches syntactic errors, and uses source-language grammar rules (PDF p. 5). Therefore it checks grammatical program structure; semantic checks, optimization and target-code generation perform different work.
Evidence in the complete study note
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
A parse tree shows grammar productions: root S, internal nonterminals, and terminal leaves, with ε sometimes shown for empty productions. Its left-to-right yield is the input.COMP09
Choice by choice
A · incorrect — Optimization removes intermediate-code inefficiencies (p. 7).
B · incorrect — Semantic analysis checks meaningful compatibility and types (p. 6).
C · incorrect — Code generation emits machine code from intermediate code (p. 7).
D · correct — Syntax analysis is explicitly governed by grammar rules.
Question 49
Which listed data structure supplies declaration names, scopes and types to semantic analysis?
A. Yacc
B. Lex
C. Symbol Table
D. Type Checking
Hint / Module Reference (Where to Read)
Check operand compatibility and permitted conversions under the stated language rules; distinguish grammatical structure from semantic meaning.
A symbol table supplies the identities and attributes needed to resolve names and check types during semantic analysis. Type checking is an important activity using that information, but is not itself the requested data structure. Yacc and Lex generate parsers and scanners respectively. This narrower role makes the symbol table unique without denying that several components contribute to semantic processing.
Evidence in the complete study note
A symbol table maps names or symbol identities to attributes: type, scope, width, storage offset, parameter signature, constant information or linkage.COMP19
Lex/flex generates scanners from patterns and actions. Yacc means Yet Another Compiler Compiler; Yacc/Bison generates parsers from grammar rules and semantic actions.COMP39
A type checker verifies that operations are defined for their operands.COMP22
Choice by choice
A · incorrect — Yacc is a parser generator.
B · incorrect — Lex is a scanner generator.
C · correct — The symbol table stores declaration and type metadata.
D · incorrect — Type checking is an activity, not the information structure.
Question 50
Which phase of the compiler is also known as Scanner?
A. Syntax Analysis
B. Lexical Analysis
C. Semantic Analysis
D. Code generation
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
The module labels lexical/linear analysis “scanning” (PDF p. 5). Its scanner reads characters into tokens (p. 8), so B names the phase associated with Scanner.
Evidence in the complete study note
A token is a category with optional attribute, such as (ID, symbol-entry) or (INT_LITERAL,42). A lexeme is the actual character sequence, such as total or 42. A pattern specifies which lexemes belong to a token class. The scanner emits an ordered token stream, not an unordered mathematical set.COMP04
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
Choice by choice
A · incorrect — Syntax analysis is called parsing.
B · correct — Lexical analysis is explicitly scanning.
C · incorrect — Semantic analysis checks types/meaning (p. 6).
D · incorrect — Code generation converts intermediate code to machine code (p. 7).
Question 51
Which phase of the compiler is also known as Parser?
A. Code Optimization
B. Semantic Analysis
C. Syntax Analysis
D. Lexical Analysis
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
Syntax/hierarchical analysis is explicitly labeled Parsing (PDF p. 5); p. 9 equates parsers with syntax analyzers. Thus the phase known as Parser is syntax analysis.
Evidence in the complete study note
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
A parse tree shows grammar productions: root S, internal nonterminals, and terminal leaves, with ε sometimes shown for empty productions. Its left-to-right yield is the input.COMP09
Choice by choice
A · incorrect — Optimization improves intermediate code (p. 7).
COMP11 introduces recursive descent as a top-down implementation, normally with one procedure per nonterminal. It expands the start symbol toward the input. LR and LALR instead use bottom-up reductions, and operator-precedence parsing is also bottom-up. Therefore only recursive descent names the top-down family among these options.
Evidence in the complete study note
Top-down parsing starts with S and expands productions toward the input, usually constructing a leftmost derivation. Recursive descent typically has one procedure per nonterminal. A general recursive-descent implementation can backtrack; a predictive parser chooses a production using lookahead without backtracking. LL(1) scans Left to right, produces a Leftmost derivation and uses one lookahead token.COMP11
Bottom-up parsing starts from input and reduces toward S, constructing a rightmost derivation in reverse.COMP15
Operator-precedence parsing is a restricted bottom-up expression-parsing method using a stack and precedence relations. With a suitable expression grammar, the stack retains unfinished surrounding expressions while nested parentheses are processed.COMP-S01
Choice by choice
A · incorrect — LALR is an LR bottom-up family, using merged LR item states.
B · incorrect — LR recognizes input through bottom-up shifts and reductions.
C · incorrect — Operator-precedence parsing reduces expressions bottom-up rather than expanding productions top-down.
D · correct — Recursive descent implements top-down parsing through procedures corresponding to nonterminals.
Question 53
Keywords are recognized in a compiler during -
A. the code generation
B. the data flow analysis
C. the lexical analysis of the program
D. the program parsing
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
Correct answer: C — the lexical analysis of the program
Keywords are listed among the token categories identified during lexical analysis (PDF pp. 5, 8). Recognizing a reserved spelling therefore occurs in the lexical classification of the program rather than later target generation or parsing.
Evidence in the complete study note
A token is a category with optional attribute, such as (ID, symbol-entry) or (INT_LITERAL,42). A lexeme is the actual character sequence, such as total or 42. A pattern specifies which lexemes belong to a token class. The scanner emits an ordered token stream, not an unordered mathematical set.COMP04
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
Choice by choice
A · incorrect — Generation acts on intermediate code, not raw keyword spellings (p. 7).
B · incorrect — Data-flow analysis is not identified as keyword recognition.
C · correct — Keywords are explicitly lexical token classes (pp. 5, 8).
D · incorrect — Parsing groups the already-produced tokens.
Question 54
Which names denote the graph whose vertices are basic blocks and edges are possible next-block control transfers? Select all that apply. In A, control graph abbreviates control-flow graph.
A. Control graph
B. DAG
C. Flow graph
D. Hamilton graph
Hint / Module Reference (Where to Read)
Identify what the representation stores, what it omits and which later transformations it must support; separate a representation property from an algorithmic task.
Correct answers (select all): A, C — Control graph; Flow graph
A control-flow graph represents basic blocks as vertices and possible execution transfers, including fall-through, as edges. With the stated abbreviation, both control graph and flow graph name that representation. An expression DAG instead represents shared computations and value dependencies. A Hamiltonian-path label concerns a graph property rather than the compiler representation of block successors. Thus A and C are both valid names.
Evidence in the complete study note
A basic block is a maximal straight-line instruction sequence entered at its beginning and exited at its end. Leaders are the first instruction, every jump target, and each instruction after a branch. Start a block at each leader and continue until the next leader.COMP28
A control-flow graph has blocks as vertices and possible next-block transfers as edges, including fall-through. A node D dominates N when every entry-to-N path passes through D. For an edge N→H where H dominates N, H is a loop header of a natural loop. This structure supports loop analysis. An expression DAG records value dependencies, not arbitrary control flow.COMP28
Choice by choice
A · correct — The declared abbreviation denotes the specified graph.
B · incorrect — An expression DAG records value dependencies, not block successors.
C · correct — Flow graph conventionally names this representation.
D · incorrect — Hamiltonian paths do not define the block-successor representation.
Question 55
In the compiler, the function of using intermediate code is:
A. to improve the register allocation
B. to increase the error reporting & recovery.
C. to make semantic analysis easier.
D. to increase the chances of re-using the machine-independent code optimizer in other compilers.
Hint / Module Reference (Where to Read)
Identify what the representation stores, what it omits and which later transformations it must support; separate a representation property from an algorithmic task.
Correct answer: D — Reuse the machine-independent optimizer across compilers.
COMP26 explains that IR separates source analysis from target implementation, making optimizers and backends reusable. This directly supports reusing a machine-independent optimizer in different compilers. An IR can support allocation and analysis, but none of the other proposed improvements is its defining architectural function, nor does merely introducing IR guarantee them.
Evidence in the complete study note
IR separates source analysis from target implementation, allowing optimizers and backends to be reused. It should be easy to generate, analyze, transform and lower.COMP26
Ordinary TAC arithmetic has at most one operation, two sources and one destination: t1=c*d; t2=b+t1; a=t2. Quadruples store (op,arg1,arg2,result); triples omit an explicit result field and refer to instruction positions. Indirect triples reference a separate ordering list, easing rearrangement. Trees describe expressions; DAGs share common subexpressions, while quadruples/triples are instruction-record structures.COMP26
Choice by choice
A · incorrect — Allocation may analyze IR, but improved allocation is not the portability function identified here.
B · incorrect — Error reporting and recovery are shared compiler services, not the defining purpose of introducing IR.
C · incorrect — Semantic analysis normally establishes source correctness before lowering; IR is not introduced chiefly to simplify it.
D · correct — Separating source and target through IR enables reuse of machine-independent optimization passes.
Question 56
How many categories result when optimizations are divided solely by whether they depend on the target machine?
A. two types
B. three types
C. four types
D. five types
Hint / Module Reference (Where to Read)
Trace whether computation is evaluated, moved, shared or removed. Preserve observable effects and use the stated arithmetic and target assumptions.
The stated criterion divides optimizations into machine-dependent and machine-independent categories, giving two categories. Other taxonomies use different criteria, such as local, global and loop scope, and need not have the same count. Individual transformations are not additional categories under this binary division. Naming the criterion fixes the count without claiming a universal number of optimization types across all classifications.
Evidence in the complete study note
A loop-invariant expression has unchanged inputs during a loop. Hoist it to a preheader only when evaluation is safe on the paths where it will newly run. Induction variables change by a loop-invariant increment, such as i=i+1. For repeated t=4*i, maintain a running t increased by 4 when equivalent, reducing repeated multiplication.COMP32
Loop fusion or jamming combines loops with compatible bounds and safe dependence order. Unrolling replicates a body to reduce branch overhead and expose parallelism; handle remaining iterations and increased code size. Loop-invariant code motion, fusion, unrolling and strength reduction are different transformations. A finite taxonomy needs a criterion: machine dependent/independent versus local/global/loop are different classifications.COMP32
Choice by choice
A · correct — The two categories are machine-dependent and machine-independent.
B · incorrect — Three fits another possible scope taxonomy.
C · incorrect — This binary division does not yield four categories.
D · incorrect — This binary division does not yield five categories.
Question 57
The value of which variable is updated inside the loop by a loop-invariant value?
A. loop
B. strength
C. induction
D. invariable
Hint / Module Reference (Where to Read)
Trace whether computation is evaluated, moved, shared or removed. Preserve observable effects and use the stated arithmetic and target assumptions.
COMP32 defines induction variables as values changed by a loop-invariant increment, such as i=i+1. This matches an update inside a loop by an invariant amount. A loop-invariant value itself stays unchanged; strength is part of the term strength reduction, and loop alone names a construct rather than this variable class.
Evidence in the complete study note
A loop-invariant expression has unchanged inputs during a loop. Hoist it to a preheader only when evaluation is safe on the paths where it will newly run. Induction variables change by a loop-invariant increment, such as i=i+1. For repeated t=4*i, maintain a running t increased by 4 when equivalent, reducing repeated multiplication.COMP32
Loop fusion or jamming combines loops with compatible bounds and safe dependence order. Unrolling replicates a body to reduce branch overhead and expose parallelism; handle remaining iterations and increased code size. Loop-invariant code motion, fusion, unrolling and strength reduction are different transformations. A finite taxonomy needs a criterion: machine dependent/independent versus local/global/loop are different classifications.COMP32
Choice by choice
A · incorrect — Loop names the repeated control construct rather than the variable category defined by invariant increments.
B · incorrect — Strength refers to replacing costly operations, not to this variable classification.
C · correct — An induction variable is updated by a loop-invariant increment during loop iterations.
D · incorrect — An invariant value remains unchanged, unlike the updated variable described in the stem.
Question 58
Which compiler runs on one machine and generates code for multiple machines?
A. Multipass compiler
B. Cross compiler
C. Optimizing compiler
D. Onepass compiler
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
A cross-compiler runs on platform A and generates executable code for another platform B (PDF p. 3). B matches the host/target distinction. The module’s definition concerns a different target platform; it does not require one executable to support several targets simultaneously.
Evidence in the complete study note
A preprocessor handles directives such as file inclusion and macros. An assembler translates assembly to object code. A linker combines object files and libraries, resolves external symbols and performs relocation. A loader maps an executable into memory and starts it. Compilation alone does not necessarily produce a ready executable.COMP02
A cross-compiler runs on a host platform and generates code for a different target. Multiple targets require appropriate backends, not a special definition of cross-compilation. A retargetable compiler supports changing target descriptions. Incremental compilation recompiles affected fragments or dependent units after edits; it is more than literally replacing changed lines. One-pass versus multipass counts traversals, not supported targets.COMP02
Choice by choice
A · incorrect — Multipass is not the host/target distinction described on p. 3.
B · correct — Cross compiler is explicitly the platform-A to platform-B translator (p. 3).
C · incorrect — Optimizing refers to improving code (p. 7), not the host/target relationship.
D · incorrect — Onepass is not the documented host/target category.
Question 59
Which phenomenon happens when the non-terminal on the left side is repeated as the first symbol on the right side?
A. Left-most derivation
B. Left recursion
C. Left factoring
D. Left parsing
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
COMP12 writes immediate left recursion as A→Aα: the production’s left-hand nonterminal occurs first on its right-hand side. This is precisely the pattern in the question. Leftmost derivation chooses which nonterminal to expand; left factoring extracts a shared prefix. Neither is the repeated-leftmost-self-reference property.
Evidence in the complete study note
Immediate left recursion has A→Aα. For A→Aα|β, where β does not start with A, introduce a new nonterminal A′ and use:
A→βA′
A′→αA′|ε
This preserves the generated language; tree shape changes, so semantic actions must preserve intended associativity. Indirect left recursion follows a cycle through other nonterminals and also needs removal for ordinary predictive descent.COMP12
Left factoring rewrites A→αβ|αγ using:
A→αA′
A′→β|γ
It postpones a choice until after the common prefix. It does not by itself remove ambiguity or guarantee LL(1). LR parsers can handle suitable left-recursive grammars; ordinary unmodified recursive descent can recurse forever before consuming input.COMP12
Choice by choice
A · incorrect — Leftmost derivation chooses the leftmost remaining nonterminal to rewrite, regardless of self-reference.
B · correct — A production beginning with its own left-hand nonterminal is immediate left recursion.
C · incorrect — Left factoring extracts common prefixes from alternatives and does not define recursive self-reference.
D · incorrect — Left parsing is not the note’s name for the production pattern described.
Question 60
The compiler can detect what type of errors?
A. neither logical nor grammatical error
B. logical errors only
C. grammatical errors only
D. both grammatical and logical errors
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
PDF p. 5 says syntax analysis catches syntactic errors, so grammar violations are detectable. PDF p. 6 adds semantic type mismatches; it does not claim detection of arbitrary mistakes in the intended algorithm. Among the offered grammatical-versus-logical choices, C fits if “logical” means wrong intended algorithm rather than all semantic errors.
Evidence in the complete study note
A lexical error prevents forming a legal token, such as an invalid character or unterminated literal. A syntax error is an illegal token arrangement, such as a missing delimiter. A semantic error violates name, scope or type rules after grammatical recognition. A wrong algorithm can compile successfully; compilers do not detect all logical mistakes.COMP08
Choice by choice
A · incorrect — Neither conflicts with the documented detection of syntactic errors.
B · incorrect — Logical-only omits the explicitly detected grammatical errors.
C · correct — Grammatical errors are expressly detected; the intended-algorithm interpretation of logical makes this the matching choice.
D · incorrect — The module does not claim that general intended-algorithm errors are detected.
Question 61
Which method merges the multiple loops into the single one?
A. Constant Folding
B. Loop rolling
C. Loop fusion or jamming
D. None of the above
Hint / Module Reference (Where to Read)
Trace whether computation is evaluated, moved, shared or removed. Preserve observable effects and use the stated arithmetic and target assumptions.
Correct answer: C — Loop fusion, also called jamming.
COMP32 explicitly defines loop fusion or jamming as combining loops with compatible bounds and safe dependence order. That is the requested merging transformation. Constant folding evaluates constant expressions, while loop rolling does not name this fusion of separate loops. Fusion must preserve dependence order; it is not automatically legal for arbitrary loops.
Evidence in the complete study note
A loop-invariant expression has unchanged inputs during a loop. Hoist it to a preheader only when evaluation is safe on the paths where it will newly run. Induction variables change by a loop-invariant increment, such as i=i+1. For repeated t=4*i, maintain a running t increased by 4 when equivalent, reducing repeated multiplication.COMP32
Loop fusion or jamming combines loops with compatible bounds and safe dependence order. Unrolling replicates a body to reduce branch overhead and expose parallelism; handle remaining iterations and increased code size. Loop-invariant code motion, fusion, unrolling and strength reduction are different transformations. A finite taxonomy needs a criterion: machine dependent/independent versus local/global/loop are different classifications.COMP32
Choice by choice
A · incorrect — Constant folding evaluates constant expressions at compile time; it does not combine loop bodies.
B · incorrect — Loop rolling is not the note’s named transformation for merging separate compatible loops.
C · correct — Fusion or jamming combines compatible loops into one while preserving required dependence order.
D · incorrect — The explicit fusion/jamming option already names the requested transformation.
Question 62
Which parser is known as the shift-reduce parser?
A. Bottom-up parser
B. Top-down parser
C. Both Top-down and bottom-up
D. None of the Above
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
PDF p. 10 names bottom-up parsing as SR parsing and describes reductions from the input to the start symbol. Interpreting SR as shift-reduce, A is the matching category; top-down is instead predictive.
Evidence in the complete study note
Bottom-up parsing starts from input and reduces toward S, constructing a rightmost derivation in reverse. A handle is a production RHS occurrence whose reduction is the next step of that reverse derivation. Not every substring matching a RHS is a handle in the current context.COMP15
Shift pushes the next input token and a state; reduce replaces a recognized RHS by its LHS and consults GOTO; accept recognizes completion; error reports an invalid situation. For A→XYZ, pop three grammar symbols and their states, expose state q, then push A and GOTO[q,A]. “Go” is not a separate standard shift-reduce ACTION, although GOTO is essential table machinery.COMP15
Choice by choice
A · correct — Bottom-up is explicitly the SR category (p. 10).
B · incorrect — Top-down is labeled predictive, not SR (p. 10).
C · incorrect — Both collapses two categories the module distinguishes (p. 10).
D · incorrect — The bottom-up category is present (p. 10), so none is false.
Question 63
The full form of YACC is:
A. Yet Another Computer Computer
B. Yet Another Computer Compiler
C. Yet Another Compiler Computer
D. Yet Another Compiler Compiler
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
Correct answer: D — Yet Another Compiler Compiler.
COMP39 expands Yacc as Yet Another Compiler Compiler and describes Yacc/Bison as generating parsers from grammar rules and semantic actions. The other expansions interchange computer and compiler and do not match the note. The name refers to a parser generator, distinct from Lex/flex scanner generation.
Evidence in the complete study note
Panic-mode recovery skips input until a synchronizing token such as ; or } permits parsing to resume. Phrase-level recovery makes a local insertion/deletion. Report the location and cause while avoiding cascades of misleading diagnostics. Lexical, syntax and semantic phases each detect their own errors; error handling is a shared service.COMP39
Lex/flex generates scanners from patterns and actions. Yacc means Yet Another Compiler Compiler; Yacc/Bison generates parsers from grammar rules and semantic actions. Typical specification files have definitions, %% rules, and %% user code. Classic Yacc uses LALR; Bison supports additional LR and generalized modes. Scanner generation does not replace the CFG parser.COMP39
Choice by choice
A · incorrect — Computer Computer replaces both required occurrences of Compiler and is not the stated expansion.
B · incorrect — The first noun must be Compiler, not Computer.
C · incorrect — The final noun must also be Compiler, not Computer.
D · correct — This matches the exact Yacc expansion given in COMP39.
Question 64
What type of conflicts can occur in the shift-reduce parsing? Select the most complete choice.
A. reduce/reduce
B. shift/reduce
C. Both shift/reduce and reduce/reduce
D. None of the above
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
Correct answer: C — Both shift/reduce and reduce/reduce
COMP17 distinguishes a shift/reduce conflict, where shifting competes with reduction, from reduce/reduce, where two reductions compete. Both can arise in shift-reduce table construction. The combined option therefore answers the question completely; either individual conflict is a valid example but omits the other named kind.
Evidence in the complete study note
SLR(1) uses LR(0) states and FOLLOW(A) for reduction by a completed A production. Canonical LR(1) attaches context-specific lookahead to items. LALR(1) merges canonical states with the same LR(0) core, combining lookaheads; merging can introduce reduce/reduce conflicts. The standard grammar-class hierarchy is LR(0)⊆SLR(1)⊆LALR(1)⊆LR(1), with increasing capability and often table size.COMP17
A shift/reduce conflict offers both consuming a token and reducing; reduce/reduce offers two reductions. An SLR or LALR conflict does not by itself prove the grammar ambiguous. Canonical LR(1) handles LR(1) grammars, not every unambiguous CFG. Precedence and associativity can resolve suitable expression conflicts; changing parser names alone does not repair all ambiguity.COMP17
Choice by choice
A · incorrect — True as one component, but incomplete as the requested full selection. Two competing reductions form a reduce/reduce conflict, one of the listed possible types.
B · incorrect — True as one component, but incomplete as the requested full selection. A shift competing with a reduction forms the other standard conflict type.
C · correct — This aggregate includes both conflict types explicitly defined in COMP17.
D · incorrect — Both listed kinds can occur, so denying every listed type is false.
Question 65
Which algorithm invokes a function GETREG()?
A. Code motion algorithm
B. Code optimization algorithm
C. Intermediate Code
D. Code generation algorithm
Hint / Module Reference (Where to Read)
Match stored information to its lifetime, access path and calling-convention role; distinguish compile-time organization from run-time storage.
COMP35 directly associates getReg with a simple code-generation algorithm. It selects operand/result registers for a TAC instruction before loads and the target operation are emitted and descriptors are updated. Code motion and general optimization serve other transformation purposes; intermediate code is the input representation here rather than the algorithm making the register choice.
Evidence in the complete study note
A register descriptor records which current values are held in a register. An address descriptor for a name records all current locations containing its value, possibly memory and multiple registers. A memory copy can become stale after a register-only assignment. These are code-generator bookkeeping structures, not source-language types.COMP35
A simple code-generation algorithm calls getReg for a TAC instruction to select operand/result registers, emits necessary loads, emits the operation, then updates descriptors. Prefer an already suitable register or a reusable dead operand; otherwise choose a spill victim and store any live value lacking another current copy. At a block exit, preserve values needed by successors.COMP35
Choice by choice
A · incorrect — Code motion relocates computations; it is not the described getReg-driven emission algorithm.
B · incorrect — Optimization is broader, but COMP35 specifically locates getReg in the target code-generation algorithm.
C · incorrect — Intermediate code supplies instructions to the generator; it is not the algorithm invoking the register selector.
D · correct — The note explicitly describes getReg as part of simple target code generation.
Question 66
The execution time of the code depends on? Select the most complete choice.
A. the usage of machine idioms
B. the way the registers are used
C. the orders in which the computations are performed
D. All of the mentioned
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
COMP34 states that machine idioms, register availability and instruction order affect execution time. These correspond to all three concrete choices. Better register use can reduce loads/spills; target idioms affect instruction cost, and legal scheduling changes execution efficiency. The aggregate is therefore the complete response rather than any one factor in isolation.
Evidence in the complete study note
Code generation lowers checked IR to a target form. Instruction selection chooses target operations; register allocation chooses where values reside; scheduling orders instructions while respecting dependencies; storage layout assigns offsets and follows ABI requirements. Register assignment names actual physical registers after allocation decisions.COMP34
For t=a+b, a simple target could emit LOAD R1,a; LOAD R2,b; ADD R3,R1,R2; STORE t,R3. Other targets may combine loads with arithmetic or keep t in a register. Machine idioms, register availability and instruction order affect execution time.COMP34
Choice by choice
A · incorrect — True as one component, but incomplete as the requested full selection. Choosing target machine idioms changes the operations emitted and their target costs.
B · incorrect — True as one component, but incomplete as the requested full selection. Register use affects memory traffic and spills, which can change execution time.
C · incorrect — True as one component, but incomplete as the requested full selection. The scheduling of computations affects execution efficiency while dependencies constrain legal orders.
D · correct — COMP34 explicitly includes all three factors, so the aggregate is the complete answer.
Question 67
Which is the most specific named method for examining a short instruction window and replacing jump L1 with jump L2 when L1 immediately jumps to L2?
A. Latter optimization technique
B. Peephole optimization technique
C. Local optimization technique
D. Code optimization technique
Hint / Module Reference (Where to Read)
Trace whether computation is evaluated, moved, shared or removed. Preserve observable effects and use the stated arithmetic and target assumptions.
Correct answer: B — Peephole optimization technique
Peephole optimization examines a short instruction window and replaces it with an equivalent, preferable sequence. The described jump-chain rewrite is a direct example. Local optimization and code optimization are broader classifications that may include the transformation, but do not name the specific short-window method requested. Latter optimization is not a method defined in the supplied note.
Evidence in the complete study note
Peephole optimization examines short instruction windows. It can remove redundant loads/stores, replace machine idioms and shorten jump chains: jump L1 where L1 immediately jumps L2 can become jump L2.COMP31
Choice by choice
A · incorrect — Latter optimization does not name the specified method.
B · correct — Peephole explicitly performs short-window jump-chain rewrites.
C · incorrect — Local optimization is broader than the requested method.
D · incorrect — Code optimization is broader than the requested method.
Question 68
Which of the following term is used to keep track of the location where the current values of the name are stored?
A. Register descriptor
B. Address descriptor
C. Allocation descriptor
D. Flag register
Hint / Module Reference (Where to Read)
Match stored information to its lifetime, access path and calling-convention role; distinguish compile-time organization from run-time storage.
COMP35 defines an address descriptor for a name as recording all current locations that contain its value, including memory and registers. That matches tracking where a name’s current value is stored. A register descriptor instead records values held in a particular register, reversing the direction of the association.
Evidence in the complete study note
A register descriptor records which current values are held in a register. An address descriptor for a name records all current locations containing its value, possibly memory and multiple registers. A memory copy can become stale after a register-only assignment.COMP35
Choice by choice
A · incorrect — A register descriptor maps a register to its current values rather than a name to all locations.
B · correct — An address descriptor records the current memory and register locations holding a name’s value.
C · incorrect — Allocation descriptor is not the note’s defined bookkeeping structure for name-to-location tracking.
D · incorrect — A flag register stores machine status flags rather than all locations of a named value.
Question 69
In a nontrivial expression AST whose leaves are operands, which complete category of nodes carries operator symbols, including operators in nested subexpressions?
A. Root
B. Interior nodes
C. Leaves
D. Nodes
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
In an expression AST, leaves carry operands such as identifiers and constants, while nonleaf nodes carry the operators that combine child expressions. A nontrivial tree’s root can also be an operator, but naming only the root omits nested operators. Naming all nodes includes operand leaves. The complete category requested is therefore the interior nodes, which includes an operator root and any other nonleaf operator nodes.
Evidence in the complete study note
A context-free grammar G=(N,T,P,S) has nonterminals N, terminals T, productions P and start S. A production A→α rewrites one nonterminal. A sentential form is any string of terminals/nonterminals derivable from S; a sentence contains only terminals. A leftmost derivation rewrites the leftmost remaining nonterminal; a rightmost one rewrites the rightmost.COMP09
A parse tree shows grammar productions: root S, internal nonterminals, and terminal leaves, with ε sometimes shown for empty productions. Its left-to-right yield is the input. An AST omits grammar scaffolding and punctuation; expression operands are leaves and operators internal nodes. The parser can build either representation, depending on implementation.COMP09
Choice by choice
A · incorrect — The root alone omits operators in nested subexpressions.
B · correct — Interior nodes are the complete nonleaf category carrying operators in this expression AST.
C · incorrect — Leaves carry operands rather than combining operators.
D · incorrect — All nodes includes operand leaves and is too broad.
Question 70
Which of the following is used in various stages or phases of the compiler?
A. Records
B. Program
C. Symbol Table
D. Table
Hint / Module Reference (Where to Read)
Ask whether the required information is a declaration’s identity and attributes, program structure or the ordered source tokens.
The module stores semantic type information in the symbol table (PDF p. 6), puts identifier-entry pointers in syntax-tree leaves (p. 13), and enters names/types during declarations (p. 17). These uses support the symbol table as a shared structure across compiler work.
Evidence in the complete study note
A symbol table maps names or symbol identities to attributes: type, scope, width, storage offset, parameter signature, constant information or linkage.COMP19
Symbol-table management and error reporting support multiple phases rather than forming one mandatory seventh final phase.COMP03
Scanning may intern a spelling first; semantic analysis determines the declaration and type.COMP19
Choice by choice
A · incorrect — Records is only a generic storage term, not the shared named structure in these passages.
B · incorrect — Program is the object being compiled, not the metadata table.
C · correct — Symbol Table is explicitly used in several contexts (pp. 6, 13, 17).
D · incorrect — Table is nonspecific; Symbol Table is the documented structure.
Question 71
Which of the following structure has four fields?
A. Parse tree
B. Triples
C. Indirect Triples
D. Quadruples
Hint / Module Reference (Where to Read)
Identify what the representation stores, what it omits and which later transformations it must support; separate a representation property from an algorithmic task.
PDF p16 explicitly divides a quadruple into operator, arg1, arg2, and result: four fields. It contrasts triples with three fields.
Evidence in the complete study note
IR separates source analysis from target implementation, allowing optimizers and backends to be reused. It should be easy to generate, analyze, transform and lower.COMP26
Ordinary TAC arithmetic has at most one operation, two sources and one destination: t1=c*d; t2=b+t1; a=t2. Quadruples store (op,arg1,arg2,result); triples omit an explicit result field and refer to instruction positions. Indirect triples reference a separate ordering list, easing rearrangement. Trees describe expressions; DAGs share common subexpressions, while quadruples/triples are instruction-record structures.COMP26
Choice by choice
A · incorrect — A parse tree is a hierarchical representation, not the four-field instruction defined on p16.
B · incorrect — P16 explicitly gives triples three fields.
C · incorrect — P16 describes indirect triples through pointers, not a fourth result field.
D · correct — P16 explicitly lists the four quadruple fields.
Question 72
What is the conventional name for the compact expression representation with operand leaves and operator interior nodes?
A. Syntax tree
B. Parser tree
C. Structured tree
D. Sematic tree
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
The conventional expression AST places operands at leaves and operators at interior nodes, removing grammar scaffolding and punctuation. A parse tree instead records grammar productions: its internal nodes are nonterminals, and its yield includes the terminals of the source phrase. The other two names do not identify the conventional expression representation in this comparison. The syntax-tree choice supplies the specific structure described by the question.
Evidence in the complete study note
A context-free grammar G=(N,T,P,S) has nonterminals N, terminals T, productions P and start S. A production A→α rewrites one nonterminal. A sentential form is any string of terminals/nonterminals derivable from S; a sentence contains only terminals. A leftmost derivation rewrites the leftmost remaining nonterminal; a rightmost one rewrites the rightmost.COMP09
A parse tree shows grammar productions: root S, internal nonterminals, and terminal leaves, with ε sometimes shown for empty productions. Its left-to-right yield is the input. An AST omits grammar scaffolding and punctuation; expression operands are leaves and operators internal nodes. The parser can build either representation, depending on implementation.COMP09
Choice by choice
A · correct — An expression syntax tree places operands at leaves and operators at nonleaf nodes.
B · incorrect — A parse tree’s internal labels are grammar nonterminals, not generally expression operators.
C · incorrect — This generic phrase does not specify the conventional expression AST representation requested.
D · incorrect — Semantic annotation can be attached to representations, but this is not the conventional name for the described AST.
Question 73
Which statement is an abstract form of intermediate code?
A. 3- address
B. 2-address
C. address
D. Intermediate code
Hint / Module Reference (Where to Read)
Identify what the representation stores, what it omits and which later transformations it must support; separate a representation property from an algorithmic task.
PDF pp15–16 defines three-address code as a generic intermediate representation, X = Y op Z. Thus A names the supplied abstract statement form; D only repeats the general category.
Evidence in the complete study note
IR separates source analysis from target implementation, allowing optimizers and backends to be reused. It should be easy to generate, analyze, transform and lower.COMP26
Ordinary TAC arithmetic has at most one operation, two sources and one destination: t1=c*d; t2=b+t1; a=t2. Quadruples store (op,arg1,arg2,result); triples omit an explicit result field and refer to instruction positions. Indirect triples reference a separate ordering list, easing rearrangement. Trees describe expressions; DAGs share common subexpressions, while quadruples/triples are instruction-record structures.COMP26
Choice by choice
A · correct — P15 gives precisely this statement form.
B · incorrect — No two-address intermediate statement form is supplied; it is not the form defined on p15.
C · incorrect — A bare address is not the statement X = Y op Z.
D · incorrect — This names the category rather than the particular statement form requested.
Question 74
Which mapping is described by the implementation of the syntax-directed translator?
A. Parse table
B. Input
C. Output
D. Input-Output
Hint / Module Reference (Where to Read)
Track where each computed value comes from and when each production action runs. Distinguish the representation from its attached information.
COMP25 distinguishes translation from recognition: semantic actions compute an output, such as values, ASTs or code, from an input program. Accordingly the implemented translator defines an input-to-output mapping. A parse table may drive an implementation, but neither the table nor either endpoint alone names that mapping.
Evidence in the complete study note
A syntax-directed translation scheme embeds executable actions in productions; the actions run while translating a source program, not while generating the compiler. Attributes may compute types, values, AST pointers or generated code. The scheme defines an input-to-output translation, not merely an input language.COMP25
Create an identifier leaf with mkleaf(id,entry), a number with mkleaf(num,value), and an operator node with mknode(op,left,right). For a−4+c, construct +(−(a,4),c). Postorder traversal prints postfix: a 4 − c +. A stack evaluator pushes operands and pops right then left operands for an operator. Infix-to-postfix is useful for stack machines but not mandatory for all compilers.COMP25
Choice by choice
A · incorrect — A parse table can guide recognition; it is not the translation mapping itself.
B · incorrect — Input is only the domain side and omits the translated result.
C · incorrect — Output is only the result side and omits the mapping from source inputs.
D · correct — Syntax-directed translation relates each processed input to its computed translation output.
Question 75
Which transition function moves the dot over a grammar symbol and takes closure to build successor states in the canonical LR(0) item collection?
A. FIRST
B. GOTO
C. COMPUTE
D. FOLLOW
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
GOTO(I,X) advances the dot over X in eligible items and then takes closure, producing a successor item state. Repeating this over grammar symbols builds the canonical collection. The collection is the resulting set of item sets, not the function itself. FIRST and FOLLOW compute terminal sets for different parsing purposes; COMPUTE does not name the defined LR successor operation.
Evidence in the complete study note
Augment the grammar with S′→S. An LR(0) item A→α·β records progress through a production. CLOSURE(I) repeatedly adds B→·γ whenever an item has its dot before nonterminal B and B→γ is a production.COMP16
GOTO(I,X) moves the dot past X in every eligible item and takes closure. Start with CLOSURE({S′→·S}); repeatedly compute nonempty GOTO sets for all grammar symbols until no new state appears. The resulting set of item sets is the canonical collection, not GOTO itself.COMP16
Choice by choice
A · incorrect — FIRST finds possible beginning terminals.
B · correct — GOTO produces the successor item state.
C · incorrect — COMPUTE is not the defined successor-state function.
D · incorrect — FOLLOW finds possible following terminals.
Question 76
Which of the following option is not a function of the shift-reduce parser?
A. Reduce
B. Accept
C. Go
D. Shift
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
Correct answer: C — “Go” is not a standard shift-reduce ACTION.
COMP15 lists shift, reduce, accept and error as standard shift-reduce actions. GOTO is essential after a reduction but is separate table machinery, not a distinct action called Go. Reading function as the standard action category yields the offered Go choice; the three other choices are explicitly standard actions.
Evidence in the complete study note
Bottom-up parsing starts from input and reduces toward S, constructing a rightmost derivation in reverse. A handle is a production RHS occurrence whose reduction is the next step of that reverse derivation. Not every substring matching a RHS is a handle in the current context.COMP15
Shift pushes the next input token and a state; reduce replaces a recognized RHS by its LHS and consults GOTO; accept recognizes completion; error reports an invalid situation. For A→XYZ, pop three grammar symbols and their states, expose state q, then push A and GOTO[q,A]. “Go” is not a separate standard shift-reduce ACTION, although GOTO is essential table machinery.COMP15
Choice by choice
A · incorrect — Reduce is a standard action that replaces a recognized right-hand side by its left-hand nonterminal.
B · incorrect — Accept is a standard action indicating successful completion of recognition.
C · correct — Go is not one of the standard ACTION names; GOTO is separate transition-table machinery.
D · incorrect — Shift is a standard action that consumes input and pushes a token with its state.
Question 77
Which listed grammar classes guarantee no adjacent nonterminals on a production right-hand side? Select all that apply. Regular means consistently right-linear; irregular means arbitrary unrestricted.
A. Arbitrary unrestricted grammar
B. Right-linear regular grammar
C. Operator grammar
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
An operator grammar explicitly forbids adjacent nonterminals on a right-hand side. A consistently right-linear regular grammar has at most one nonterminal in such a rule, so it also guarantees the restriction. Arbitrary unrestricted grammars have no comparable adjacency guarantee. The property is therefore shared by the two specified classes and cannot be used to identify only operator grammar.
Evidence in the complete study note
LL, LR and recursive-descent parsers can all handle nested parentheses for suitable grammars. An explicit or implicit stack, not the LR label alone, supports unbounded nesting. Both LL and LR can use parsing tables. Deterministic LL/LR grammars must be unambiguous; a general ambiguous grammar requires rewriting, disambiguation policy or a generalized method such as GLR.COMP18
An operator grammar conventionally forbids adjacent nonterminals on a RHS and usually ε productions. Operator-precedence parsing additionally requires conflict-free precedence relations. Ordinary right-linear regular grammars also lack adjacent nonterminals, so that property alone does not uniquely identify the operator-grammar category. Regular patterns are chiefly lexical specifications; CFGs chiefly describe nested syntax.COMP18
Choice by choice
A · incorrect — An unrestricted grammar can contain adjacent nonterminals.
B · correct — A right-linear regular rule has at most one nonterminal.
C · correct — Operator grammars forbid adjacent nonterminals by definition.
Question 78
In an implementation where the scanner interns identifier spellings in a symbol table before returning their tokens, which phase first interacts with that table?
A. Syntax analysis
B. Parsing
C. Scanning
D. Semantic analysis
Hint / Module Reference (Where to Read)
Ask whether the required information is a declaration’s identity and attributes, program structure or the ordered source tokens.
Interning associates an identifier spelling with a table entry while scanning its characters and returning the identifier token. Under this explicit implementation convention, scanning is the first phase to interact with the table. Parsing and semantic analysis use or enrich this information later; semantic analysis resolves declaration identity and type. This establishes an ordering for the stated implementation rather than a universal compiler requirement.
Evidence in the complete study note
Scanning may intern a spelling first; semantic analysis determines the declaration and type. Implementations differ, so first interaction is conventional rather than universal.COMP19
A token is a category with optional attribute, such as (ID, symbol-entry) or (INT_LITERAL,42). A lexeme is the actual character sequence, such as total or 42. A pattern specifies which lexemes belong to a token class. The scanner emits an ordered token stream, not an unordered mathematical set.COMP04
Choice by choice
A · incorrect — Syntax analysis receives tokens after this scanner has interned identifiers.
B · incorrect — Parsing is syntax analysis and occurs after the stated interning.
C · correct — Scanning performs the stipulated initial interning.
D · incorrect — Semantic analysis enriches name/type information after that initial interaction.
Question 79
What is the name given to the sequence of alphabets that are identified as a token?
A. Lexeme
B. Prefix
C. Pattern
D. Grammar
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
PDF p8 calls the sequence of characters matched by a pattern to form a token a lexeme. Interpreting alphabets as characters makes A exact.
Evidence in the complete study note
A token is a category with optional attribute, such as (ID, symbol-entry) or (INT_LITERAL,42). A lexeme is the actual character sequence, such as total or 42. A pattern specifies which lexemes belong to a token class. The scanner emits an ordered token stream, not an unordered mathematical set.COMP04
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
Choice by choice
A · correct — Matches the p8 definition.
B · incorrect — Prefix is not the defined name for the matched sequence.
C · incorrect — P8 defines a pattern as a rule, not the matched sequence.
D · incorrect — P9 uses grammar for syntactic production rules, not a token occurrence.
Question 80
In a compiler where semantic analysis annotates an existing AST with resolved declarations and checked types, what is its resulting program representation?
A. Language constructs
B. Unannotated concrete syntax tree
C. AST annotated with resolved declarations and checked types
D. Token
Hint / Module Reference (Where to Read)
Ask whether the required information is a declaration’s identity and attributes, program structure or the ordered source tokens.
Correct answer: C — AST annotated with resolved declarations and checked types
The stated implementation resolves names and checks types on an existing abstract syntax tree, so its result is that AST with semantic annotations. An unannotated syntax tree omits the newly checked information; language constructs is too generic to identify the representation. Tokens are the scanner’s earlier output. Other compilers may produce typed IR, but the question specifies the retained-tree implementation.
Evidence in the complete study note
Static checks occur before execution: type compatibility, duplicate declarations within a restricted scope, valid names, argument counts, return compatibility and control-flow placement. A break is valid only in constructs allowed by the language; in C/C++ it can exit a loop or switch. A compiler may annotate an AST or create typed IR; there is no mandatory uniquely named output tree.COMP21
Dynamic checks depend on runtime values, such as some bounds and null checks. Static analysis can prove some accesses safe or faulty; “all memory errors cannot be statically checked” is too strong. Unreachable code is not universally a semantic error: some languages reject it in specified cases, others merely warn or optimize it away.COMP21
Choice by choice
A · incorrect — Language constructs does not identify the specified annotated representation.
B · incorrect — An unannotated concrete syntax tree is not the specified result.
C · correct — The result is the AST enriched with checked semantic information.
D · incorrect — Tokens precede syntax and semantic analysis.
Question 81
For const int x=8; const int y=16; if(x>y){int z=x+y;}, which techniques directly apply to evaluating the condition from known constants and removing its unreachable branch? Select all that apply. Distinguish constant evaluation from algebraic identity simplification.
A. Arithmetic simplification
B. Dead code elimination
C. Code motion
D. Compile time evaluation
Hint / Module Reference (Where to Read)
Trace whether computation is evaluated, moved, shared or removed. Preserve observable effects and use the stated arithmetic and target assumptions.
Correct answers (select all): B, D — Dead code elimination; Compile time evaluation
With x=8 and y=16, the condition x>y evaluates to false during compilation. The branch body is consequently unreachable and can be removed. These are compile-time evaluation and dead-code elimination, respectively. No computation needs to move to another program location, and the decisive evaluation is not an algebraic identity such as x+0→x. Both direct transformations belong in the answer.
Evidence in the complete study note
For const int x=8,y=16; if(x>y){int z=x+y;}, propagate the constants, fold 8>16 to false, then remove the unreachable branch. Both compile-time evaluation and dead-code elimination apply.COMP30
Algebraic simplification removes identities when valid: integer x+0→x.COMP31
Choice by choice
A · incorrect — No algebraic identity rewrite is the decisive step.
B · correct — The constant-false branch is unreachable and removable.
C · incorrect — Code motion does not describe evaluating or deleting the branch.
D · correct — Known constants permit compile-time evaluation of the condition.
Question 82
Which one of the following phases is done BEFORE the semantic analysis phase of the
compiling process?
A. Syntax analysis
B. Intermediate code generation
C. Code generation
D. Code optimization
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
PDF pp5–7 orders syntax analysis before semantic analysis, followed by intermediate generation, optimization, and code generation.
Evidence in the complete study note
The conventional sequence is lexical analysis → syntax analysis → semantic analysis → intermediate-code generation → optimization → target-code generation. Scanning turns characters into tokens; parsing builds structure; semantics checks declarations and types; synthesis produces implementation code. A phase is a logical activity; a pass is a traversal that can combine activities.COMP03
The front end handles source-language rules; a middle end analyzes and transforms IR; the backend handles target details. Symbol-table management and error reporting support multiple phases rather than forming one mandatory seventh final phase. Optimization can occur at several levels, including after instruction selection. “Final phase” means code generation in the standard six-phase teaching pipeline.COMP03
Choice by choice
A · correct — Syntax analysis appears on p5 before semantics on p6.
B · incorrect — Intermediate generation follows semantic analysis on p6.
C · incorrect — Code generation is phase 6 on p7.
D · incorrect — Optimization is phase 5 on p7, after semantics.
Question 83
Which phase of the compiling process is considered the FINAL phase?
A. Intermediate code generation
B. Semantic analysis
C. Code optimization
D. Code generation
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
Correct answer: D — Code generation in the conventional pipeline.
COMP03 calls code generation the final phase of the standard six-phase teaching pipeline. Intermediate generation, semantic analysis and optimization precede it there. Some implementations perform later target optimization, but that does not change the conventional phase answer requested here; the note explicitly records that distinction.
Evidence in the complete study note
The conventional sequence is lexical analysis → syntax analysis → semantic analysis → intermediate-code generation → optimization → target-code generation. Scanning turns characters into tokens; parsing builds structure; semantics checks declarations and types; synthesis produces implementation code. A phase is a logical activity; a pass is a traversal that can combine activities.COMP03
The front end handles source-language rules; a middle end analyzes and transforms IR; the backend handles target details. Symbol-table management and error reporting support multiple phases rather than forming one mandatory seventh final phase. Optimization can occur at several levels, including after instruction selection. “Final phase” means code generation in the standard six-phase teaching pipeline.COMP03
Choice by choice
A · incorrect — Intermediate-code generation precedes optimization and target-code generation in the conventional sequence.
B · incorrect — Semantic analysis checks names and types before intermediate and target synthesis.
C · incorrect — Optimization precedes final code generation in the simplified six-phase teaching pipeline.
D · correct — COMP03 explicitly names code generation as final under this standard pipeline convention.
Question 84
Which one of the following is used for the purpose of syntax analysis?
A. Loader
B. Linker
C. Parser
D. Scanner
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
PDF p10 defines parsing as constructing a parse tree, and p5 labels syntax analysis Parsing. P3 assigns distinct object-code roles to loader and linker.
Evidence in the complete study note
A preprocessor handles directives such as file inclusion and macros. An assembler translates assembly to object code. A linker combines object files and libraries, resolves external symbols and performs relocation. A loader maps an executable into memory and starts it.COMP02
Scanning turns characters into tokens; parsing builds structure; semantics checks declarations and types; synthesis produces implementation code.COMP03
Choice by choice
A · incorrect — P3 loads an executable into memory.
B · incorrect — P3 merges object files.
C · correct — Parsing is syntax analysis (p5).
D · incorrect — Scanning produces tokens (p8), prior to parsing.
Question 85
Which output does syntax analysis produce when it retains every grammar production and terminal occurrence, including punctuation, without semantic attribute annotation?
A. Concrete syntax tree (parse tree)
B. Annotated parse tree
C. Abstract syntax tree
D. Pattern
Hint / Module Reference (Where to Read)
Track where each computed value comes from and when each production action runs. Distinguish the representation from its attached information.
Correct answer: A — Concrete syntax tree (parse tree)
A concrete syntax or parse tree records the grammar productions used, with nonterminal interiors and terminal leaves. Because the specified representation retains grammar scaffolding and punctuation, it is not the abstract syntax tree that omits those details. Semantic attribute values would make an annotated tree, which this question excludes. A lexical pattern is a specification for tokens rather than the parsed program representation.
Evidence in the complete study note
A syntax-directed definition is a CFG with attributes on grammar symbols and semantic rules on productions. An annotated parse tree displays computed attribute values; it is not itself an inherited or synthesized attribute.COMP24
A parse tree shows grammar productions: root S, internal nonterminals, and terminal leaves, with ε sometimes shown for empty productions. Its left-to-right yield is the input. An AST omits grammar scaffolding and punctuation; expression operands are leaves and operators internal nodes. The parser can build either representation, depending on implementation.COMP09
Choice by choice
A · correct — A full syntax/parse tree records the retained grammar detail.
B · incorrect — Semantic attribute annotation is expressly excluded.
C · incorrect — An AST omits the scaffolding and punctuation retained here.
D · incorrect — A pattern specifies lexical membership rather than parsed program structure.
Question 86
For a fixed suitable grammar, which listed approaches can be efficient top-down parsers using prediction without backtracking? Select all that apply.
A. Recursive-descent parser
B. Shift-reduce parser
C. Non-recursive predictive parser
D. LR parser
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
Correct answers (select all): A, C — Recursive-descent parser; Non-recursive predictive parser
Recursive descent can use lookahead to predict productions without backtracking. Nonrecursive predictive parsing implements the same top-down strategy with an explicit stack and table. Both can run linearly for a fixed suitable grammar. Shift-reduce and LR instead work bottom-up, reducing input toward the start symbol, so they do not meet the specified parsing direction even if they are efficient.
Evidence in the complete study note
Top-down parsing starts with S and expands productions toward the input, usually constructing a leftmost derivation. Recursive descent typically has one procedure per nonterminal. A general recursive-descent implementation can backtrack; a predictive parser chooses a production using lookahead without backtracking. LL(1) scans Left to right, produces a Leftmost derivation and uses one lookahead token.COMP11
A nonrecursive predictive parser stores grammar symbols on an explicit stack and consults a table. It is another implementation of predictive parsing, not a wholly different language class. Table-driven and recursive predictive implementations can both be linear for a fixed suitable grammar. Efficiency cannot be ranked from their names alone.COMP11
Bottom-up parsing starts from input and reduces toward S, constructing a rightmost derivation in reverse.COMP15
Choice by choice
A · correct — Predictive recursive descent is a supported efficient top-down implementation.
B · incorrect — Shift-reduce is bottom-up.
C · correct — Nonrecursive prediction is a supported efficient top-down implementation.
D · incorrect — LR is bottom-up.
Question 87
Which abstract data structure naturally represents hierarchical source-program constructs with parent/child relationships, as in a parse tree or AST?
A. 2D-array
B. Stack
C. Tree
D. Queue
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
A tree represents the hierarchy of program constructs through parent/child relationships. Parse trees preserve grammar detail, while ASTs retain the essential expression and statement structure. Arrays may implement node storage, and stacks or queues may support traversal, but those container roles do not make them the requested hierarchical model. The structure being represented, rather than the storage allocation technique, determines this answer.
Evidence in the complete study note
Grouping characters into token classes is lexical analysis; grouping tokens into expressions and statements is syntax analysis.COMP41
Trees store hierarchical constructs, while a symbol table stores declaration metadata.COMP41
A context-free grammar G=(N,T,P,S) has nonterminals N, terminals T, productions P and start S. A production A→α rewrites one nonterminal. A sentential form is any string of terminals/nonterminals derivable from S; a sentence contains only terminals. A leftmost derivation rewrites the leftmost remaining nonterminal; a rightmost one rewrites the rightmost.COMP09
A parse tree shows grammar productions: root S, internal nonterminals, and terminal leaves, with ε sometimes shown for empty productions. Its left-to-right yield is the input. An AST omits grammar scaffolding and punctuation; expression operands are leaves and operators internal nodes. The parser can build either representation, depending on implementation.COMP09
Choice by choice
A · incorrect — A 2D array is not the requested abstract hierarchical model.
B · incorrect — A stack supports processing order rather than the full parent/child model.
C · correct — A tree directly models hierarchical constructs.
D · incorrect — A queue supports work ordering rather than the hierarchy itself.
Question 88
In which phase of the compilation process does the source program get broken into its
constituent parts?
A. Semantic Analysis
B. Syntax Analysis
C. Synthesis
D. Lexical Analysis
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
PDF p5 scans characters into lexemes represented as tokens. These constituent lexical units precede hierarchical grouping during parsing.
Evidence in the complete study note
A token is a category with optional attribute, such as (ID, symbol-entry) or (INT_LITERAL,42). A lexeme is the actual character sequence, such as total or 42. A pattern specifies which lexemes belong to a token class. The scanner emits an ordered token stream, not an unordered mathematical set.COMP04
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
Choice by choice
A · incorrect — P6 checks meaningful compatibility after lexical decomposition.
B · incorrect — Parsing groups already recognized tokens (p5).
C · incorrect — P3 calls synthesis machine dependent; it is not the scanning stage.
D · correct — P5 decomposes the character stream into tokens.
Question 89
Which described check requires runtime values rather than being solely a static check? In D, the index depends on input and no static proof of its bounds is available.
A. Type checking for compatibility
B. Uniqueness checks like redefined variables
C. Checking that break is inside an allowed loop or switch
D. Checking an input-dependent array index against runtime bounds, with no static proof available
Hint / Module Reference (Where to Read)
Ask whether the required information is a declaration’s identity and attributes, program structure or the ordered source tokens.
Correct answer: D — Checking an input-dependent array index against runtime bounds, with no static proof available
Type compatibility, duplicate declarations and valid placement of break can be checked from the source program and its declarations. The specified array index depends on runtime input, and no static bounds proof is available, so its validity requires a runtime check. This does not claim that every memory access fault is inherently undetectable statically; the explicit value-dependent case supplies the distinction.
Evidence in the complete study note
Static checks occur before execution: type compatibility, duplicate declarations within a restricted scope, valid names, argument counts, return compatibility and control-flow placement. A break is valid only in constructs allowed by the language; in C/C++ it can exit a loop or switch. A compiler may annotate an AST or create typed IR; there is no mandatory uniquely named output tree.COMP21
Dynamic checks depend on runtime values, such as some bounds and null checks. Static analysis can prove some accesses safe or faulty; “all memory errors cannot be statically checked” is too strong. Unreachable code is not universally a semantic error: some languages reject it in specified cases, others merely warn or optimize it away.COMP21
Choice by choice
A · incorrect — Type compatibility is a static semantic check.
B · incorrect — Duplicate declarations can be checked statically within the relevant scope.
C · incorrect — Placement in an allowed loop or switch is a static check.
D · correct — The stipulated input-dependent bounds need runtime validation.
Question 90
Which tool is used to collect codes separately compiled or assembled in different object files
into a file that is directly executable?
A. Linker
B. Loader
C. Assembler
D. Preprocessor
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
A linker combines separately compiled object files and required libraries, resolves their external symbol references and relocates addresses to produce the executable form. An assembler translates assembly into object code before this combination. A loader places the resulting executable in memory and starts it. A preprocessor handles source directives before compilation. These tool roles distinguish object-file combination from translation, source expansion and program loading.
Evidence in the complete study note
A preprocessor handles directives such as file inclusion and macros. An assembler translates assembly to object code. A linker combines object files and libraries, resolves external symbols and performs relocation. A loader maps an executable into memory and starts it. Compilation alone does not necessarily produce a ready executable.COMP02
A cross-compiler runs on a host platform and generates code for a different target. Multiple targets require appropriate backends, not a special definition of cross-compilation. A retargetable compiler supports changing target descriptions. Incremental compilation recompiles affected fragments or dependent units after edits; it is more than literally replacing changed lines. One-pass versus multipass counts traversals, not supported targets.COMP02
Choice by choice
A · correct — The linker combines object files, resolves symbols and performs relocation.
B · incorrect — The loader maps an already produced executable into memory.
C · incorrect — An assembler translates assembly source into object code.
D · incorrect — A preprocessor handles source directives rather than combining object files.
Question 91
Among phases of compiling process, in which phase a sequence of characters are converted into a
tokens?
A. Code optimization
B. Syntax analysis
C. Semantic analysis
D. Lexical analysis
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
PDF pp5,8 gives lexical analysis a character-stream input and a sequence-of-tokens output.
Evidence in the complete study note
A token is a category with optional attribute, such as (ID, symbol-entry) or (INT_LITERAL,42). A lexeme is the actual character sequence, such as total or 42. A pattern specifies which lexemes belong to a token class. The scanner emits an ordered token stream, not an unordered mathematical set.COMP04
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
Choice by choice
A · incorrect — Optimization changes intermediate code (p7).
B · incorrect — Syntax analysis groups tokens already recognized (p5).
C · incorrect — Semantic analysis checks meaningful fit (p6).
D · correct — The exact input-output description is on p8.
Question 92
Which phase of the compiler is responsible for recognizing tokens and building a symbol
table?
A. Lexical Analysis
B. Syntax Analysis
C. Semantic Analysis
D. Code Generation
Hint / Module Reference (Where to Read)
Ask whether the required information is a declaration’s identity and attributes, program structure or the ordered source tokens.
Token recognition uniquely identifies lexical analysis on p5. However, p6 and p17 assign type/name entries to semantic and declaration processing, so building the symbol table must mean contributing lexical identifier entries, not constructing every attribute exclusively.
Evidence in the complete study note
Scanning may intern a spelling first; semantic analysis determines the declaration and type. Implementations differ, so first interaction is conventional rather than universal.COMP19
A token is a category with optional attribute, such as (ID, symbol-entry) or (INT_LITERAL,42). A lexeme is the actual character sequence, such as total or 42. A pattern specifies which lexemes belong to a token class. The scanner emits an ordered token stream, not an unordered mathematical set.COMP04
Choice by choice
A · correct — P5 explicitly recognizes tokens; A is supported for that decisive responsibility.
B · incorrect — Parsing groups tokens rather than recognizing the character stream (p5).
C · incorrect — P6 stores types in the symbol table but does not perform lexical token recognition.
D · incorrect — P7 converts intermediate code into machine code.
Question 93
What is the primary ordered output of lexical analysis passed to the parser?
A. Abstract Syntax Tree (AST)
B. Ordered token stream
C. Intermediate Code
D. Assembly Code
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
Lexical analysis groups characters into lexemes and emits an ordered token stream, including token categories and relevant attributes. The parser consumes that stream to build grammatical structure. A symbol table may be updated as an auxiliary service, but it is not the primary ordered output. ASTs, intermediate code and assembly belong to later processing stages in the conventional pipeline.
Evidence in the complete study note
Grouping characters into token classes is lexical analysis; grouping tokens into expressions and statements is syntax analysis.COMP41
Trees store hierarchical constructs, while a symbol table stores declaration metadata.COMP41
A token is a category with optional attribute, such as (ID, symbol-entry) or (INT_LITERAL,42). A lexeme is the actual character sequence, such as total or 42. A pattern specifies which lexemes belong to a token class. The scanner emits an ordered token stream, not an unordered mathematical set.COMP04
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
Choice by choice
A · incorrect — AST construction follows scanning during parsing or syntax-directed work.
B · correct — The ordered token stream is the parser’s input.
C · incorrect — Intermediate code follows syntactic and semantic processing.
D · incorrect — Assembly is a possible later target output.
Question 94
Which phase of the compiler is responsible for checking the correctness of the program's
structure?
A. Lexical Analysis
B. Syntax Analysis
C. Semantic Analysis
D. Code Generation
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
PDF p5 groups tokens by grammar and catches most syntactic errors. Program structure here means syntactic structure, so B applies.
Evidence in the complete study note
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
A parse tree shows grammar productions: root S, internal nonterminals, and terminal leaves, with ε sometimes shown for empty productions. Its left-to-right yield is the input.COMP09
Choice by choice
A · incorrect — Recognizes lexical units rather than their grammatical arrangement (p5).
B · correct — Checks grammar-governed hierarchy and syntactic errors (p5).
C · incorrect — Checks meaning and type mismatch (p6).
D · incorrect — Translates intermediate code into machine code (p7).
Question 95
Which component of the compiler generates an Abstract Syntax Tree (AST)?
A. Lexical Analyzer
B. Parser
C. Semantic Analyzer
D. Code Generator
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
PDF p5 gives parsing the tree-building role. P12 says syntax-directed actions execute according to parsing, and pp12–13 give operator/operand syntax-tree constructors. Together these support parser as the component building the abstract structural tree.
Evidence in the complete study note
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
A parse tree shows grammar productions: root S, internal nonterminals, and terminal leaves, with ε sometimes shown for empty productions. Its left-to-right yield is the input.COMP09
Choice by choice
A · incorrect — Lexical analysis emits tokens (p8).
B · correct — Parsing builds a tree (p5), with syntax-directed tree constructors on pp12–13.
C · incorrect — Semantic analysis may annotate the existing tree (p6); it is not the phase assigned general syntactic tree construction.
D · incorrect — Code generation translates intermediate code (p7).
Question 96
What does the semantic analysis phase of the compiler focus on?
A. Identifying syntax errors
B. Analyzing the meaning of program statements
C. Generating intermediate code
D. Translating source code to machine code
Hint / Module Reference (Where to Read)
Ask whether the required information is a declaration’s identity and attributes, program structure or the ordered source tokens.
Correct answer: B — Analyzing the meaning of program statements
PDF p6 defines semantic analysis through meaningful fit and type-mismatch checks, directly supporting B.
Evidence in the complete study note
Static checks occur before execution: type compatibility, duplicate declarations within a restricted scope, valid names, argument counts, return compatibility and control-flow placement. A break is valid only in constructs allowed by the language; in C/C++ it can exit a loop or switch. A compiler may annotate an AST or create typed IR; there is no mandatory uniquely named output tree.COMP21
Dynamic checks depend on runtime values, such as some bounds and null checks. Static analysis can prove some accesses safe or faulty; “all memory errors cannot be statically checked” is too strong. Unreachable code is not universally a semantic error: some languages reject it in specified cases, others merely warn or optimize it away.COMP21
Choice by choice
A · incorrect — Most syntactic errors are assigned to parsing on p5.
B · correct — Meaningful compatibility is the explicit semantic task (p6).
C · incorrect — Intermediate generation is separately headed on p6.
D · incorrect — Machine-code translation is code generation (p7).
Question 97
Which phase of the compiler performs type checking and enforces semantic rules?
A. Lexical Analysis
B. Syntax Analysis
C. Semantic Analysis
D. Code Generation
Hint / Module Reference (Where to Read)
Check operand compatibility and permitted conversions under the stated language rules; distinguish grammatical structure from semantic meaning.
PDF p6 explicitly names type checking as one of the most important semantic-analysis tasks.
Evidence in the complete study note
A type checker verifies that operations are defined for their operands. In a simple strict language, integer mod requires two integers; array indexing requires an array and integer index; an if condition requires Boolean; assignment requires equal or convertible types. Function calls check parameter count and compatibility, and returns match result types.COMP22
Type inference derives types from constraints: if x is integer and + expects numeric operands, infer the expression type from numeric promotion rules. It is a static technique even without explicit annotations. Operator overloading supplies multiple operation meanings, not a substitute for type checking. int x="hello" is a type mismatch in ordinary C++/Java; division by zero and bounds violations are not automatically operand-type mismatches.COMP22
Choice by choice
A · incorrect — Scanning recognizes tokens (p5).
B · incorrect — Parsing checks grammatical hierarchy (p5).
C · correct — Type checking is explicitly here (p6).
D · incorrect — Code generation converts intermediate code (p7).
Question 98
Which phase of the compiler translates the intermediate representation into the target
machine code?
A. Lexical Analysis
B. Syntax Analysis
C. Semantic Analysis
D. Code Generation
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
PDF p7 states that code generation converts intermediate code to machine code.
Evidence in the complete study note
Code generation lowers checked IR to a target form. Instruction selection chooses target operations; register allocation chooses where values reside; scheduling orders instructions while respecting dependencies; storage layout assigns offsets and follows ABI requirements. Register assignment names actual physical registers after allocation decisions.COMP34
For t=a+b, a simple target could emit LOAD R1,a; LOAD R2,b; ADD R3,R1,R2; STORE t,R3. Other targets may combine loads with arithmetic or keep t in a register. Machine idioms, register availability and instruction order affect execution time.COMP34
Choice by choice
A · incorrect — Scanning works on source characters (p5).
B · incorrect — Parsing groups tokens (p5).
C · incorrect — Semantic analysis checks types and meaning (p6).
D · correct — Matches the explicit conversion on p7.
Question 99
What is the primary goal of the code optimization phase in compiler design?
A. To reduce the size of the source code
B. To eliminate syntax errors
C. To improve the performance of the generated code
D. To generate human-readable code
Hint / Module Reference (Where to Read)
Trace whether computation is evaluated, moved, shared or removed. Preserve observable effects and use the stated arithmetic and target assumptions.
Correct answer: C — To improve the performance of the generated code
PDF p7 names improvement in time, space, or power; p17 adds faster execution, efficient memory, and preserving meaning. Thus improving generated-code performance is the best statement.
Evidence in the complete study note
Constant folding evaluates constant expressions during compilation: 3*4→12. Constant propagation substitutes known values: x=3; y=x+2 becomes y=3+2 before folding. Copy propagation substitutes a copied name while its source remains unchanged. Dead-code elimination removes unreachable code or computations whose values are unused and whose evaluation has no necessary side effects.COMP30
Choice by choice
A · incorrect — Source text length is not the optimization goal.
B · incorrect — Syntax errors are caught by parsing (p5); optimization assumes meaningful code to improve.
C · correct — Matches the performance goal on p17.
D · incorrect — Human readability is not the goal listed on pp7,17.
Question 100
For E→E+E|E*E|id, which technique resolves the ambiguity by requiring * to bind more tightly than + and both operators to associate left?
A. Parsing with explicit operator precedence and left-associativity rules
B. Lexical analysis
C. Semantic analysis
D. Leftmost derivation
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
Correct answer: A — Parsing with explicit operator precedence and left-associativity rules
The grammar permits multiple groupings of expressions such as id+id*id. An explicit precedence and associativity policy selects multiplication before addition and left association within each level. A parser may enforce this through declarations or a grammar rewrite. Lexical analysis and generic semantic checking do not themselves establish that policy, and taking a leftmost derivation does not remove the competing parse trees.
Evidence in the complete study note
A grammar is ambiguous if at least one terminal string has two different parse trees, equivalently two leftmost derivations. Merely changing derivation order on the same tree does not establish ambiguity. E→E+E|E*E|id allows different trees for id+id*id.COMP10
Use E→E+T|T, T→T*F|F, F→(E)|id to give * higher precedence and both operators left associativity. For subtraction, a−b−c then groups (a−b)−c. The dangling-else grammar permits else to attach to either nested if; a nearest-unmatched-if rule or grammar rewrite resolves it. Taking a leftmost derivation by itself does not resolve ambiguous interpretation.COMP10
Choice by choice
A · correct — The stated policy selects the intended grouping.
B · incorrect — Token recognition does not determine operator grouping.
C · incorrect — Generic semantic checking supplies no stated grouping policy.
D · incorrect — An ambiguous grammar can have multiple leftmost derivations.
Question 101
What is the purpose of semantic rules in a programming language?
A. To define the syntax of the language
B. To specify the order of execution of statements
C. To enforce the correct use of language constructs
D. To optimize the generated code
Hint / Module Reference (Where to Read)
Ask whether the required information is a declaration’s identity and attributes, program structure or the ordered source tokens.
Correct answer: C — To enforce the correct use of language constructs
PDF p6 checks that program components fit together meaningfully and p14 requires semantic conventions to hold. C captures those constraints on use of language constructs.
Evidence in the complete study note
Static checks occur before execution: type compatibility, duplicate declarations within a restricted scope, valid names, argument counts, return compatibility and control-flow placement. A break is valid only in constructs allowed by the language; in C/C++ it can exit a loop or switch. A compiler may annotate an AST or create typed IR; there is no mandatory uniquely named output tree.COMP21
Dynamic checks depend on runtime values, such as some bounds and null checks. Static analysis can prove some accesses safe or faulty; “all memory errors cannot be statically checked” is too strong. Unreachable code is not universally a semantic error: some languages reject it in specified cases, others merely warn or optimize it away.COMP21
Choice by choice
A · incorrect — Grammatical structure is assigned to syntax analysis (p5).
B · incorrect — Execution order alone does not capture the type/compatibility constraints on pp6,14.
C · correct — Correct semantic use follows the cited compatibility and convention checks.
D · incorrect — Optimization is separately concerned with efficiency (p7).
Question 102
Which of the following is responsible for recognizing keywords and identifiers in a
programming language?
A. Lexical Analyzer
B. Parser
C. Semantic Analyzer
D. Code Generator
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
PDF p5 lists identifiers and keywords among lexical tokens, and p8 explains their token classes.
Evidence in the complete study note
A token is a category with optional attribute, such as (ID, symbol-entry) or (INT_LITERAL,42). A lexeme is the actual character sequence, such as total or 42. A pattern specifies which lexemes belong to a token class. The scanner emits an ordered token stream, not an unordered mathematical set.COMP04
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
Choice by choice
A · correct — Recognizes the token classes explicitly listed on pp5,8.
B · incorrect — Parser consumes tokens already recognized (p9).
C · incorrect — Semantic analysis checks type and meaning (p6).
D · incorrect — Code generation produces machine code (p7).
Question 103
Which phase of the compiler is responsible for checking the syntax of the program?
A. Lexical Analysis
B. Syntax Analysis
C. Semantic Analysis
D. Code Generation
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
PDF p5 names syntax analysis Parsing and assigns it grammatical hierarchy and most syntactic-error detection.
Evidence in the complete study note
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
A parse tree shows grammar productions: root S, internal nonterminals, and terminal leaves, with ε sometimes shown for empty productions. Its left-to-right yield is the input.COMP09
Choice by choice
A · incorrect — Scanning identifies lexemes, not grammar structure (p5).
B · correct — Directly matches the syntax-checking phase on p5.
C · incorrect — P6 concerns semantic errors such as type mismatch.
D · incorrect — P7 concerns machine-code generation.
Question 104
What is the main goal of the semantic analysis phase in compiler design?
A. To check the syntax of the program
B. To generate intermediate code
C. To perform type checking and enforce semantic rules
D. To translate the source code to machine code
Hint / Module Reference (Where to Read)
Check operand compatibility and permitted conversions under the stated language rules; distinguish grammatical structure from semantic meaning.
Correct answer: C — To perform type checking and enforce semantic rules
PDF p6 checks meaningful fit, detects semantic errors, and explicitly emphasizes type checking.
Evidence in the complete study note
A type checker verifies that operations are defined for their operands. In a simple strict language, integer mod requires two integers; array indexing requires an array and integer index; an if condition requires Boolean; assignment requires equal or convertible types. Function calls check parameter count and compatibility, and returns match result types.COMP22
Type inference derives types from constraints: if x is integer and + expects numeric operands, infer the expression type from numeric promotion rules. It is a static technique even without explicit annotations. Operator overloading supplies multiple operation meanings, not a substitute for type checking. int x="hello" is a type mismatch in ordinary C++/Java; division by zero and bounds violations are not automatically operand-type mismatches.COMP22
Choice by choice
A · incorrect — Syntactic structure is checked in parsing (p5).
B · incorrect — Intermediate generation is a separate phase (p6).
C · correct — Matches both semantic compatibility and type checking on p6.
D · incorrect — Machine-code conversion belongs to code generation (p7).
Question 105
What is the purpose of an Abstract Syntax Tree (AST)?
A. To store the program's symbol table
B. To generate assembly code
C. To visualize the program's control flow
D. To represent the hierarchical structure of the program
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
Correct answer: D — To represent the hierarchical structure of the program
PDF pp12–13 represents a-4+c through identifier/number leaves and operator nodes linked by child pointers. This encodes the expression hierarchy, supporting D.
Evidence in the complete study note
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
A parse tree shows grammar productions: root S, internal nonterminals, and terminal leaves, with ε sometimes shown for empty productions. Its left-to-right yield is the input.COMP09
Choice by choice
A · incorrect — P13 leaves may point to a symbol-table entry, but the whole tree is not the symbol table.
B · incorrect — P7 assigns machine-code production to code generation; that is not the tree definition.
C · incorrect — The illustrated tree encodes expression operators and operands, not control-flow paths.
D · correct — Operator-child nesting on pp12–13 represents program syntax hierarchy.
Question 106
What does the symbol table in a compiler store?
A. Intermediate code
B. Machine code
C. Source code
D. Information about identifiers and their attributes
Hint / Module Reference (Where to Read)
Ask whether the required information is a declaration’s identity and attributes, program structure or the ordered source tokens.
Correct answer: D — Information about identifiers and their attributes
PDF p17 puts names and types in the symbol table; p6 adds variables, function parameters, and array dimensions. P13 points identifier leaves to table entries. This is identifier information and attributes.
Evidence in the complete study note
A symbol table maps names or symbol identities to attributes: type, scope, width, storage offset, parameter signature, constant information or linkage. A hash table gives expected O(1) insertion/lookup with suitable hashing; a stack of scope tables supports lexical nesting. Search the nearest scope first, insert declarations in the current scope, and remove visibility when leaving it.COMP19
Scanning may intern a spelling first; semantic analysis determines the declaration and type. Implementations differ, so first interaction is conventional rather than universal. Not every punctuation token needs a symbol-table entry; literals may use a separate literal table. A hash table is an implementation, not the information’s semantic role.COMP19
Choice by choice
A · incorrect — Intermediate code has separate statement representations (pp15–16).
B · incorrect — Machine code is output of code generation (p7).
C · incorrect — The cited table entries are names/types, not the full source text.
D · correct — Names and type attributes are explicitly stored (pp6,17).
Question 107
Which phase of the compiler performs type checking?
A. Lexical Analysis
B. Syntax Analysis
C. Semantic Analysis
D. Code Generation
Hint / Module Reference (Where to Read)
Check operand compatibility and permitted conversions under the stated language rules; distinguish grammatical structure from semantic meaning.
PDF p6 explicitly places type checking in semantic analysis.
Evidence in the complete study note
A type checker verifies that operations are defined for their operands. In a simple strict language, integer mod requires two integers; array indexing requires an array and integer index; an if condition requires Boolean; assignment requires equal or convertible types. Function calls check parameter count and compatibility, and returns match result types.COMP22
Type inference derives types from constraints: if x is integer and + expects numeric operands, infer the expression type from numeric promotion rules. It is a static technique even without explicit annotations. Operator overloading supplies multiple operation meanings, not a substitute for type checking. int x="hello" is a type mismatch in ordinary C++/Java; division by zero and bounds violations are not automatically operand-type mismatches.COMP22
Choice by choice
A · incorrect — Scanning turns characters into tokens (p5).
B · incorrect — Parsing groups tokens and checks syntax (p5).
C · correct — P6 explicitly names this task.
D · incorrect — Generation converts intermediate to machine code (p7).
Question 108
What is the purpose of intermediate code in compiler design?
A. To optimize the program's execution
B. To generate assembly code
C. To represent the program's semantics in a platform-independent form
D. To visualize the program's control flow
Hint / Module Reference (Where to Read)
Identify what the representation stores, what it omits and which later transformations it must support; separate a representation property from an algorithmic task.
Correct answer: C — Represent program meaning in a reusable, substantially platform-independent intermediate form.
COMP26 identifies separation of source analysis and target implementation as IR’s architectural purpose, allowing reuse across targets. C expresses that purpose best. Optimization and assembly generation are operations enabled by the representation, while a control-flow graph is one possible representation aspect. Platform independence is a design benefit here, not a claim that every IR has no target details.
Evidence in the complete study note
IR separates source analysis from target implementation, allowing optimizers and backends to be reused. It should be easy to generate, analyze, transform and lower.COMP26
Ordinary TAC arithmetic has at most one operation, two sources and one destination: t1=c*d; t2=b+t1; a=t2. Quadruples store (op,arg1,arg2,result); triples omit an explicit result field and refer to instruction positions. Indirect triples reference a separate ordering list, easing rearrangement. Trees describe expressions; DAGs share common subexpressions, while quadruples/triples are instruction-record structures.COMP26
Choice by choice
A · incorrect — Optimization is enabled by IR, but it is not the general representational purpose distinguishing this choice.
B · incorrect — Assembly is one possible later output; an IR need not be tied to assembly generation.
C · correct — A reusable representation of program semantics separates front-end meaning from target-specific implementation.
D · incorrect — Control-flow visualization is one possible use and does not exhaust the purpose of IR.
Question 109
Which of the following is used to generate a lexical analyzer for a programming language?
A. Finite Automaton
B. Context-Free Grammar
C. Pushdown Automaton
D. Turing Machine
Hint / Module Reference (Where to Read)
Follow the representation at each construction step and apply the pattern or state-set rules consistently, including empty cases.
COMP06 describes converting regular expressions to an NFA and then a DFA. This is the automaton construction used for ordinary generated token recognizers. CFGs and pushdown machinery address nested syntax rather than the regular token-pattern mechanism; a Turing machine is not the specific scanner model in the supplied construction.
Evidence in the complete study note
A common generator pipeline is regular expressions → NFA using Thompson construction → DFA using subset construction; minimization is optional. For concatenation rs, connect r’s final state to s’s start by ε. Alternation introduces branching ε paths; star adds a way to skip and repeat the fragment.COMP06
The ε-closure of states includes those reachable by zero or more ε edges. A DFA state is a set of NFA states; its a-transition is ε-closure(move(set,a)). Start with the NFA start closure, repeatedly add unseen subsets, and mark subsets containing an NFA final state as accepting. Token identity and rule priority annotate accepting states; the empty subset acts as a dead state.COMP06
Choice by choice
A · correct — NFA/DFA finite automata implement recognition of regular token patterns in the stated generator pipeline.
B · incorrect — CFGs describe nested syntactic structure rather than the regular scanner-automaton construction.
C · incorrect — Pushdown machinery adds a stack for context-free structure and is not the ordinary token-recognizer construction.
D · incorrect — A Turing machine is more general but is not the specific model used in this scanner-generation pipeline.
Question 110
What is the purpose of a lexical analyzer in a compiler?
A. To check the syntax of the program
B. To generate intermediate code
C. To perform type checking
D. To recognize and tokenize the input source code
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
Correct answer: D — To recognize and tokenize the input source code
PDF p8 gives the scanner a high-level source-program input and sequence-of-tokens output.
Evidence in the complete study note
A token is a category with optional attribute, such as (ID, symbol-entry) or (INT_LITERAL,42). A lexeme is the actual character sequence, such as total or 42. A pattern specifies which lexemes belong to a token class. The scanner emits an ordered token stream, not an unordered mathematical set.COMP04
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
Choice by choice
A · incorrect — Syntax checking belongs to parsing (p5).
B · incorrect — Intermediate generation is separate (p6).
C · incorrect — Type checking belongs to semantic analysis (p6).
D · correct — Directly matches p8 input and output.
Question 111
Which listed notation directly specifies ordinary token patterns using alternation, concatenation and repetition, rather than a general production notation or a tree of one program?
A. Regular Expressions
B. Context-Free Grammars
C. Backus-Naur Form (BNF)
D. Abstract Syntax Trees (AST)
Hint / Module Reference (Where to Read)
Follow the representation at each construction step and apply the pattern or state-set rules consistently, including empty cases.
Classical regular expressions combine alternation, concatenation and repetition to specify ordinary token patterns. CFGs and BNF are production-based grammar descriptions and can also describe regular languages, so mere expressive capability would not distinguish them. An AST represents the analyzed structure of a particular program. The revised comparison asks for the direct pattern notation characterized by its operators, making regular expressions the specific answer.
Evidence in the complete study note
Regular expressions use concatenation, alternation r|s, Kleene star r* for zero or more, and r+ for one or more. In a simplified alphabet, identifier = Letter(Letter|Digit)*; it permits a single letter and forbids a leading digit. A C-like ASCII rule commonly also allows underscore:
[A-Za-z_][A-Za-z0-9_]*
State the convention instead of claiming this covers every language’s identifiers.COMP05
Backus–Naur form, or BNF, is a notation for context-free grammar production rules. It describes how syntactic constructs are formed; it is different from an abstract syntax tree representing one particular program.COMP-S02
An AST omits grammar scaffolding and punctuation; expression operands are leaves and operators internal nodes. The parser can build either representation, depending on implementation.COMP09
Choice by choice
A · correct — Regular expressions directly use the stated pattern-combination operators.
B · incorrect — A CFG is a general production grammar, not the direct expression notation described.
C · incorrect — BNF is a notation for context-free productions.
D · incorrect — An AST represents one analyzed program structure rather than the permitted token patterns.
Question 112
Which listed parsing approaches can handle arbitrarily nested parenthesized expressions for suitable grammars and stack-based implementations? Select all that apply.
A. LL Parsing
B. LR Parsing
C. Recursive Descent Parsing
D. Operator Precedence Parsing
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
Correct answers (select all): A, B, C, D — LL Parsing; LR Parsing; Recursive Descent Parsing; Operator Precedence Parsing
Nested parentheses require remembering unfinished surrounding expressions. LL and LR parsers use a parsing stack, recursive descent uses the call stack, and suitable operator-precedence expression parsing also uses stack structure and precedence relations. Each can therefore handle the stipulated nested expressions for an appropriate grammar. The existence of nesting alone does not distinguish one of these parser families from the others.
Evidence in the complete study note
LL, LR and recursive-descent parsers can all handle nested parentheses for suitable grammars. An explicit or implicit stack, not the LR label alone, supports unbounded nesting.COMP18
Operator-precedence parsing is a restricted bottom-up expression-parsing method using a stack and precedence relations. With a suitable expression grammar, the stack retains unfinished surrounding expressions while nested parentheses are processed.COMP-S01
Choice by choice
A · correct — LL can parse a suitable nested-expression grammar using its stack.
B · correct — LR can recognize the nesting with bottom-up stack actions.
C · correct — Recursive descent processes nested expressions through recursive calls.
D · correct — A suitable operator-precedence parser supports parenthesized subexpressions.
Question 113
Which parsing technique builds the parse tree from the bottom-up?
A. LL Parsing
B. LR Parsing
C. Recursive Descent Parsing
D. Top-Down Parsing
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
LR parsing constructs the parse tree bottom-up, reducing handles that correspond to a rightmost derivation in reverse. LL methods construct from the start symbol toward the input and are top-down. Recursive descent normally implements one procedure per nonterminal, also expanding top-down. The generic top-down option states the opposite construction direction. These are implementation and derivation distinctions, not a ranking of their execution speed.
Evidence in the complete study note
Top-down parsing starts with S and expands productions toward the input, usually constructing a leftmost derivation. Recursive descent typically has one procedure per nonterminal. A general recursive-descent implementation can backtrack; a predictive parser chooses a production using lookahead without backtracking. LL(1) scans Left to right, produces a Leftmost derivation and uses one lookahead token.COMP11
Bottom-up parsing starts from input and reduces toward S, constructing a rightmost derivation in reverse.COMP15
Choice by choice
A · incorrect — LL parsing expands a leftmost derivation from the start symbol.
B · correct — LR parsing reduces input handles and builds bottom-up.
C · incorrect — Recursive-descent procedures expand grammar nonterminals top-down.
D · incorrect — Top-down construction starts from the root, the opposite direction.
Question 114
Which is the most specific listed name for a stack-based expression parsing method using pairwise operator-precedence relations in a suitable conflict-free operator grammar?
A. Precedence Parsing
B. Operator Precedence Parsing
C. LR Parsing
D. LL Parsing
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
Operator-precedence parsing applies precedence relations to a suitable operator grammar to choose expression parsing actions. The question specifies that concrete method rather than asking for a universal cure for shift/reduce conflicts. Precedence parsing is a broader label, while LR and LL name larger parser families without supplying these particular relations. Therefore B is the most specific match to the described technique.
Evidence in the complete study note
An operator grammar conventionally forbids adjacent nonterminals on a RHS and usually ε productions. Operator-precedence parsing additionally requires conflict-free precedence relations.COMP18
Operator-precedence parsing is a restricted bottom-up expression-parsing method using a stack and precedence relations. With a suitable expression grammar, the stack retains unfinished surrounding expressions while nested parentheses are processed.COMP-S01
Top-down parsing starts with S and expands productions toward the input, usually constructing a leftmost derivation. Recursive descent typically has one procedure per nonterminal. A general recursive-descent implementation can backtrack; a predictive parser chooses a production using lookahead without backtracking. LL(1) scans Left to right, produces a Leftmost derivation and uses one lookahead token.COMP11
Choice by choice
A · incorrect — Precedence parsing is broader than the specific method requested.
B · correct — Operator-precedence parsing directly names this method.
C · incorrect — LR alone does not specify the operator-precedence method.
D · incorrect — LL alone does not specify the operator-precedence method.
Question 115
Which listed parsing categories have a standard table-driven implementation that uses lookahead to select the next parsing action? Select all that apply. For C, mean ordinary procedure-based recursive descent with choices encoded directly in code.
A. LL Parsing
B. LR Parsing
C. Recursive Descent Parsing
D. Top-Down Parsing
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
Correct answers (select all): A, B, D — LL Parsing; LR Parsing; Top-Down Parsing
A nonrecursive LL parser consults a nonterminal/lookahead table to select productions. LR parsers use ACTION and GOTO tables for shifts, reductions and state changes. Table-driven predictive parsing is also a top-down implementation, so the broader D category applies. The stipulated ordinary recursive-descent alternative encodes decisions directly in procedures instead of consulting an explicit parsing table. Thus A, B and D are selected.
Evidence in the complete study note
Both LL and LR can use parsing tables.COMP18
A nonrecursive predictive parser stores grammar symbols on an explicit stack and consults a table.COMP11
Choice by choice
A · correct — Table-driven LL selects productions from lookahead entries.
B · correct — LR uses ACTION/GOTO tables.
C · incorrect — The stipulated implementation encodes decisions in procedures rather than an explicit table.
D · correct — Nonrecursive predictive parsing is a table-driven top-down method.
Question 116
Which parsing technique is more suitable for handling left-recursive grammar rules?
A. LL Parsing
B. LR Parsing
C. Recursive Descent Parsing
D. Top-Down Parsing
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
COMP12 states that suitable left-recursive grammars are handled by LR parsers, while ordinary unmodified recursive descent can recurse forever without consuming input. LL/top-down prediction generally needs left recursion removed first. This directly supports LR as the suitable choice, without claiming LR accepts every possible left-recursive grammar.
Evidence in the complete study note
Immediate left recursion has A→Aα. For A→Aα|β, where β does not start with A, introduce a new nonterminal A′ and use:
A→βA′
A′→αA′|ε
This preserves the generated language; tree shape changes, so semantic actions must preserve intended associativity. Indirect left recursion follows a cycle through other nonterminals and also needs removal for ordinary predictive descent.COMP12
Left factoring rewrites A→αβ|αγ using:
A→αA′
A′→β|γ
It postpones a choice until after the common prefix. It does not by itself remove ambiguity or guarantee LL(1). LR parsers can handle suitable left-recursive grammars; ordinary unmodified recursive descent can recurse forever before consuming input.COMP12
Choice by choice
A · incorrect — Ordinary LL prediction requires eliminating left recursion rather than directly exploiting it.
B · correct — LR can directly handle suitable left-recursive grammar rules using bottom-up recognition.
C · incorrect — Unmodified recursive descent can recurse indefinitely before consuming input on a left-recursive rule.
D · incorrect — Ordinary top-down prediction needs recursion removal; it is not the suitable direct handling choice.
Question 117
Which of the following is not a top-down parsing algorithm?
A. Recursive Descent Parsing
B. LL Parsing
C. Predictive Parsing
D. LR Parsing
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
Recursive descent, LL parsing and predictive parsing all expand productions from the start symbol toward the input. Predictive parsing uses lookahead to avoid backtracking, while a general recursive-descent implementation may backtrack. LR parsing instead shifts input and reduces handles to build structure bottom-up. Its construction direction therefore excludes it from the top-down family, independent of whether either implementation uses a stack.
Evidence in the complete study note
Top-down parsing starts with S and expands productions toward the input, usually constructing a leftmost derivation. Recursive descent typically has one procedure per nonterminal. A general recursive-descent implementation can backtrack; a predictive parser chooses a production using lookahead without backtracking. LL(1) scans Left to right, produces a Leftmost derivation and uses one lookahead token.COMP11
Bottom-up parsing starts from input and reduces toward S, constructing a rightmost derivation in reverse.COMP15
Choice by choice
A · incorrect — Recursive descent expands nonterminal procedures from the start symbol.
B · incorrect — LL constructs a leftmost derivation top-down.
C · incorrect — Prediction chooses a top-down production using lookahead.
D · correct — LR is bottom-up, reducing handles from the input.
Question 118
Which listed method can retain multiple parse possibilities for a general ambiguous CFG rather than requiring an ordinary deterministic LL/LR grammar?
A. LL Parsing
B. Generalized LR parsing (GLR)
C. Recursive Descent Parsing
D. Top-Down Parsing
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
A general ambiguous grammar has multiple parse trees for at least one input. Generalized LR parsing can handle those possibilities, whereas ordinary deterministic LL/LR grammars must be unambiguous. A separate disambiguation policy may still be needed to select intended meaning. Recursive descent and top-down labels alone do not provide a generalized multi-parse method, so the GLR alternative uniquely answers the question.
Evidence in the complete study note
LL, LR and recursive-descent parsers can all handle nested parentheses for suitable grammars. An explicit or implicit stack, not the LR label alone, supports unbounded nesting. Both LL and LR can use parsing tables. Deterministic LL/LR grammars must be unambiguous; a general ambiguous grammar requires rewriting, disambiguation policy or a generalized method such as GLR.COMP18
An operator grammar conventionally forbids adjacent nonterminals on a RHS and usually ε productions. Operator-precedence parsing additionally requires conflict-free precedence relations. Ordinary right-linear regular grammars also lack adjacent nonterminals, so that property alone does not uniquely identify the operator-grammar category. Regular patterns are chiefly lexical specifications; CFGs chiefly describe nested syntax.COMP18
Choice by choice
A · incorrect — Ordinary deterministic LL requires an unambiguous predictive grammar.
B · correct — GLR is the generalized method identified for ambiguous grammars.
C · incorrect — Ordinary recursive descent alone does not specify a generalized multi-parse algorithm.
D · incorrect — Top-down direction alone does not handle general ambiguity.
Question 119
What is the main goal of a compiler?
A. Execution of programs
B. Translation of programs
C. Optimization of programs
D. Debugging of programs
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
PDF p2 defines a compiler as reading a program in one language and translating it to an equivalent program in another.
Evidence in the complete study note
A compiler translates a source program into an equivalent target representation while preserving defined observable behavior. The target may be machine code, assembly, bytecode or another source language. A transpiler is a source-to-source compiler, not a fundamentally separate noncompiler technology. A compiler preserves language semantics, not the programmer’s unstated intention.COMP01
An interpreter executes a program representation; it need not work one source line at a time. Systems can compile to bytecode and then interpret or JIT-compile it. AOT compilation happens before execution; JIT compilation happens during execution and may use runtime profiles. Neither is universally faster; startup cost, optimization and workload matter.COMP01
Choice by choice
A · incorrect — Execution is not the defining translation task on p2.
B · correct — Exactly matches the compiler definition on p2.
C · incorrect — Optimization is an application/stage, not the defining goal (pp2,7).
D · incorrect — Testing may use compiler technology (p2), but debugging is not its defining goal.
Question 120
Which phase of the compiler analyzes the source code to identify the basic syntactic
structures?
A. Lexical Analysis
B. Syntax Analysis
C. Semantic Analysis
D. Code Generation
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
PDF p5 assigns identifying expressions, statements, and declarations through grammatical grouping to syntax analysis. Here syntactic structures means those higher-level constructs.
Evidence in the complete study note
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
A parse tree shows grammar productions: root S, internal nonterminals, and terminal leaves, with ε sometimes shown for empty productions. Its left-to-right yield is the input.COMP09
Choice by choice
A · incorrect — Scanning recognizes tokens, the lexical units used by parsing (p5).
B · correct — P5 explicitly identifies expressions, statements and declarations here.
C · incorrect — Semantic analysis checks meaningful compatibility (p6).
D · incorrect — Code generation translates IC to machine code (p7).
Question 121
Which phase of the compiler assigns meaning to the syntactic structures and performs type
checking?
A. Lexical Analysis
B. Syntax Analysis
C. Semantic Analysis
D. Code Generation
Hint / Module Reference (Where to Read)
Check operand compatibility and permitted conversions under the stated language rules; distinguish grammatical structure from semantic meaning.
PDF p6 explicitly checks meaningful fit and performs type checking, which identifies semantic analysis.
Evidence in the complete study note
A type checker verifies that operations are defined for their operands. In a simple strict language, integer mod requires two integers; array indexing requires an array and integer index; an if condition requires Boolean; assignment requires equal or convertible types. Function calls check parameter count and compatibility, and returns match result types.COMP22
Type inference derives types from constraints: if x is integer and + expects numeric operands, infer the expression type from numeric promotion rules. It is a static technique even without explicit annotations. Operator overloading supplies multiple operation meanings, not a substitute for type checking. int x="hello" is a type mismatch in ordinary C++/Java; division by zero and bounds violations are not automatically operand-type mismatches.COMP22
Choice by choice
A · incorrect — Lexical analysis recognizes tokens (p5).
B · incorrect — Syntax analysis checks grammar structure (p5).
C · correct — Matches both meaningful compatibility and type checking on p6.
D · incorrect — Code generation converts intermediate code (p7).
Question 122
Which of the following represents the correct order of compiler phases?
A. Code Generation, Semantic Analysis, Lexical Analysis, Syntax Analysis
B. Lexical Analysis, Syntax Analysis, Semantic Analysis, Code Generation
C. Syntax Analysis, Lexical Analysis, Semantic Analysis, Code Generation
D. Semantic Analysis, Syntax Analysis, Lexical Analysis, Code Generation
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
PDF pp5–7 orders lexical, syntax, semantic, intermediate generation, optimization, and generation. B preserves the relative order of the four listed phases, though it omits two intervening stages.
Evidence in the complete study note
The conventional sequence is lexical analysis → syntax analysis → semantic analysis → intermediate-code generation → optimization → target-code generation. Scanning turns characters into tokens; parsing builds structure; semantics checks declarations and types; synthesis produces implementation code. A phase is a logical activity; a pass is a traversal that can combine activities.COMP03
The front end handles source-language rules; a middle end analyzes and transforms IR; the backend handles target details. Symbol-table management and error reporting support multiple phases rather than forming one mandatory seventh final phase. Optimization can occur at several levels, including after instruction selection. “Final phase” means code generation in the standard six-phase teaching pipeline.COMP03
Choice by choice
A · incorrect — Starts with generation before analysis, reversing the pp5–7 sequence.
B · correct — Preserves the pp5–7 relative order: lexical, syntax, semantic, generation.
C · incorrect — Syntax must consume lexical tokens (p5), so it cannot precede lexical analysis.
D · incorrect — Semantics is phase 3 after lexical and syntax analysis (pp5–6).
Question 123
Which data structure is commonly used in symbol tables during the compilation process?
A. Stack
B. Queue
C. Hash Table
D. Linked List
Hint / Module Reference (Where to Read)
Ask whether the required information is a declaration’s identity and attributes, program structure or the ordered source tokens.
COMP19 explicitly says a hash table offers expected constant-time insertion and lookup with suitable hashing. That makes it the conventional structure for the name-to-attribute mapping. A stack can organize nested scope tables, and lists are possible implementation choices, but the common keyed lookup structure asked for here is the hash table.
Evidence in the complete study note
A symbol table maps names or symbol identities to attributes: type, scope, width, storage offset, parameter signature, constant information or linkage. A hash table gives expected O(1) insertion/lookup with suitable hashing; a stack of scope tables supports lexical nesting. Search the nearest scope first, insert declarations in the current scope, and remove visibility when leaving it.COMP19
Scanning may intern a spelling first; semantic analysis determines the declaration and type. Implementations differ, so first interaction is conventional rather than universal. Not every punctuation token needs a symbol-table entry; literals may use a separate literal table. A hash table is an implementation, not the information’s semantic role.COMP19
Choice by choice
A · incorrect — A stack manages nested scope order, while the keyed mapping within a scope commonly uses hashing.
B · incorrect — FIFO queue order does not directly provide the keyed lookup role of a symbol table.
C · correct — Hashing commonly implements efficient name-to-attribute insertion and lookup.
D · incorrect — A linked list is possible but does not provide the expected constant-time keyed lookup highlighted in COMP19.
Question 124
Which phase of the compiler performs optimization techniques to improve the efficiency of
the generated code?
A. Lexical Analysis
B. Syntax Analysis
C. Semantic Analysis
D. Code Optimization
Hint / Module Reference (Where to Read)
Trace whether computation is evaluated, moved, shared or removed. Preserve observable effects and use the stated arithmetic and target assumptions.
PDF p7 explicitly improves intermediate code by removing inefficiencies; p17 names faster execution and efficient memory as goals.
Evidence in the complete study note
Constant folding evaluates constant expressions during compilation: 3*4→12. Constant propagation substitutes known values: x=3; y=x+2 becomes y=3+2 before folding. Copy propagation substitutes a copied name while its source remains unchanged. Dead-code elimination removes unreachable code or computations whose values are unused and whose evaluation has no necessary side effects.COMP30
Choice by choice
A · incorrect — Lexical analysis tokenizes (p5).
B · incorrect — Syntax analysis parses (p5).
C · incorrect — Semantic analysis checks meaningful fit (p6).
D · correct — The named improvement phase on pp7,17 is code optimization.
Question 125
Which of the following is not a typical optimization performed by a compiler?
A. Constant Folding
B. Loop Unrolling
C. Dead Code Elimination
D. Syntax Analysis
Hint / Module Reference (Where to Read)
Trace whether computation is evaluated, moved, shared or removed. Preserve observable effects and use the stated arithmetic and target assumptions.
Constant folding evaluates known expressions, loop unrolling replicates a loop body to reduce branch overhead, and dead-code elimination removes unnecessary computation when effects permit. Each transforms an existing program while preserving its required behavior. Syntax analysis instead checks and organizes grammatical structure in the frontend. It is necessary compiler work, but it is not an optimization transformation of the kind named by the other alternatives.
Evidence in the complete study note
Constant folding evaluates constant expressions during compilation: 3*4→12.COMP30
Dead-code elimination removes unreachable code or computations whose values are unused and whose evaluation has no necessary side effects.COMP30
Unrolling replicates a body to reduce branch overhead and expose parallelism; handle remaining iterations and increased code size.COMP32
The conventional sequence is lexical analysis → syntax analysis → semantic analysis → intermediate-code generation → optimization → target-code generation. Scanning turns characters into tokens; parsing builds structure; semantics checks declarations and types; synthesis produces implementation code.COMP03
Choice by choice
A · incorrect — Constant folding replaces constant expressions with computed values.
B · incorrect — Unrolling replicates loop iterations, handling remainders and code-size costs.
C · incorrect — Dead-code elimination removes unreachable or unused effect-free computations.
D · correct — Syntax analysis recognizes grammatical structure rather than optimizing code.
Question 126
Which phase of the compiler generates the target code?
A. Lexical Analysis
B. Syntax Analysis
C. Semantic Analysis
D. Code Generation
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
PDF p7 states that code generation converts intermediate code to machine code, the target in this question.
Evidence in the complete study note
Code generation lowers checked IR to a target form. Instruction selection chooses target operations; register allocation chooses where values reside; scheduling orders instructions while respecting dependencies; storage layout assigns offsets and follows ABI requirements. Register assignment names actual physical registers after allocation decisions.COMP34
For t=a+b, a simple target could emit LOAD R1,a; LOAD R2,b; ADD R3,R1,R2; STORE t,R3. Other targets may combine loads with arithmetic or keep t in a register. Machine idioms, register availability and instruction order affect execution time.COMP34
Choice by choice
A · incorrect — Lexical analysis emits tokens (p8).
B · incorrect — Syntax analysis emits a tree (p5).
C · incorrect — Semantic analysis checks compatibility (p6).
D · correct — Machine-code output is the explicit code-generation role (p7).
Question 127
Which of the following is an advantage of using an intermediate representation during the
compilation process?
A. Faster compilation speed
B. Improved error detection
C. Portability across different platforms
D. Reduced memory usage
Hint / Module Reference (Where to Read)
Identify what the representation stores, what it omits and which later transformations it must support; separate a representation property from an algorithmic task.
COMP26 explains that IR separates source analysis from target implementation, allowing optimizers and backends to be reused. This supports retargeting and portability across platforms. Introducing IR does not inherently promise faster compilation, better error detection or lower memory use; it can add processing stages and data structures while improving architecture.
Evidence in the complete study note
IR separates source analysis from target implementation, allowing optimizers and backends to be reused. It should be easy to generate, analyze, transform and lower.COMP26
Ordinary TAC arithmetic has at most one operation, two sources and one destination: t1=c*d; t2=b+t1; a=t2. Quadruples store (op,arg1,arg2,result); triples omit an explicit result field and refer to instruction positions. Indirect triples reference a separate ordering list, easing rearrangement. Trees describe expressions; DAGs share common subexpressions, while quadruples/triples are instruction-record structures.COMP26
Choice by choice
A · incorrect — An extra representation and processing stage do not inherently guarantee faster compilation.
B · incorrect — Error detection depends on analyses and language rules; it is not the stated architectural advantage.
C · correct — Separating source meaning from target lowering enables reuse across different platforms.
D · incorrect — IR introduces storage and does not guarantee reduced compiler memory consumption.
Question 128
What is the shared compiler service that supports detecting, recovering from and reporting lexical, syntax and semantic errors?
A. Lexical Analysis
B. Syntax Analysis
C. Semantic Analysis
D. Error Handling
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
Error handling and reporting is a shared service supporting multiple compilation phases. Scanning detects malformed tokens, parsing detects invalid token arrangements, and semantic analysis detects name, scope or type violations. These are contributors rather than one phase responsible for every error category. Naming the shared service makes D the appropriate complete answer without denying the diagnostic responsibilities of the other phases.
Evidence in the complete study note
Panic-mode recovery skips input until a synchronizing token such as ; or } permits parsing to resume. Phrase-level recovery makes a local insertion/deletion. Report the location and cause while avoiding cascades of misleading diagnostics. Lexical, syntax and semantic phases each detect their own errors; error handling is a shared service.COMP39
Lex/flex generates scanners from patterns and actions. Yacc means Yet Another Compiler Compiler; Yacc/Bison generates parsers from grammar rules and semantic actions. Typical specification files have definitions, %% rules, and %% user code. Classic Yacc uses LALR; Bison supports additional LR and generalized modes. Scanner generation does not replace the CFG parser.COMP39
Choice by choice
A · incorrect — Lexical analysis handles lexical errors but is not the complete shared service.
B · incorrect — Syntax analysis handles parsing errors but is not the complete shared service.
C · incorrect — Semantic analysis handles semantic errors but is not the complete shared service.
D · correct — Error handling names the shared support service.
Question 129
Which of the following is true about syntax-directed translation?
A. It only involves the lexical analysis phase.
B. It involves the generation of intermediate code from the parse tree.
C. It is concerned with the optimization of the generated code.
D. It is performed during the code generation phase.
Hint / Module Reference (Where to Read)
Track where each computed value comes from and when each production action runs. Distinguish the representation from its attached information.
Correct answer: B — It can generate intermediate code using parse-tree structure and semantic actions.
COMP25 says syntax-directed actions may compute types, values, AST pointers or generated code. Generating IR from grammatical structure is therefore a supported use of syntax-directed translation. B describes that standard use without limiting it to lexical analysis or a single final phase. Optimization may use other analyses, and syntax-directed translation is not defined solely by optimization.
Evidence in the complete study note
A syntax-directed translation scheme embeds executable actions in productions; the actions run while translating a source program, not while generating the compiler. Attributes may compute types, values, AST pointers or generated code. The scheme defines an input-to-output translation, not merely an input language.COMP25
Create an identifier leaf with mkleaf(id,entry), a number with mkleaf(num,value), and an operator node with mknode(op,left,right). For a−4+c, construct +(−(a,4),c). Postorder traversal prints postfix: a 4 − c +. A stack evaluator pushes operands and pops right then left operands for an operator. Infix-to-postfix is useful for stack machines but not mandatory for all compilers.COMP25
Choice by choice
A · incorrect — Syntax-directed translation is tied to grammatical productions and semantic actions, not solely tokenization.
B · correct — Semantic actions associated with parsed structure can compute and emit an intermediate representation.
C · incorrect — Optimization is not the defining task; translation actions can construct many forms of semantic output.
D · incorrect — It is not restricted to final target-code generation; actions can run while parsing and constructing IR.
Question 130
What is the general defining role of semantic rules attached to productions in a syntax-directed definition, rather than one possible specialized use?
A. To define the syntactic structure of the language.
B. To define computations of attributes such as types, values, environments and generated code.
C. To perform optimization techniques on the intermediate code.
D. To define the order of evaluation of expressions.
Hint / Module Reference (Where to Read)
Track where each computed value comes from and when each production action runs. Distinguish the representation from its attached information.
Correct answer: B — To define computations of attributes such as types, values, environments and generated code.
The grammar productions define syntactic structure, while semantic rules define computations of attributes associated with grammar symbols. Those attributes may represent types, values, environments or generated code. Assigning types and constraining evaluation dependencies are examples rather than exhaustive definitions. Optimization may occur in a particular translation, but is not the general defining role of all such rules.
Evidence in the complete study note
A syntax-directed definition is a CFG with attributes on grammar symbols and semantic rules on productions. An annotated parse tree displays computed attribute values; it is not itself an inherited or synthesized attribute. Synthesized attributes flow from children to a parent; inherited attributes carry context from parent or siblings.COMP24
For E→E1+T, E.val=E1.val+T.val synthesizes an expression value. A declaration’s type environment passed into its body is inherited. S-attributed definitions use only synthesized attributes and fit LR reduction-time evaluation naturally; suitable LL parsers can also compute them. L-attributed definitions restrict dependencies so a left-to-right traversal can evaluate inherited context. Attribute dependency cycles can prevent evaluation.COMP24
Choice by choice
A · incorrect — Productions, rather than semantic rules, specify the grammatical structure.
B · correct — Computing attributes is the general defining role.
C · incorrect — Optimization is a possible specialized transformation, not the general definition.
D · incorrect — Evaluation order is a specialized concern rather than the complete role.
Question 131
Which phase of the compiler is responsible for type checking?
A. Lexical Analysis
B. Syntax Analysis
C. Semantic Analysis
D. Code Generation
Hint / Module Reference (Where to Read)
Check operand compatibility and permitted conversions under the stated language rules; distinguish grammatical structure from semantic meaning.
PDF p6 explicitly names type checking as a major task of semantic analysis.
Evidence in the complete study note
A type checker verifies that operations are defined for their operands. In a simple strict language, integer mod requires two integers; array indexing requires an array and integer index; an if condition requires Boolean; assignment requires equal or convertible types. Function calls check parameter count and compatibility, and returns match result types.COMP22
Type inference derives types from constraints: if x is integer and + expects numeric operands, infer the expression type from numeric promotion rules. It is a static technique even without explicit annotations. Operator overloading supplies multiple operation meanings, not a substitute for type checking. int x="hello" is a type mismatch in ordinary C++/Java; division by zero and bounds violations are not automatically operand-type mismatches.COMP22
Choice by choice
A · incorrect — Lexical analysis recognizes tokens (p5).
B · incorrect — Syntax analysis checks grammatical hierarchy (p5).
C · correct — Type checking is explicitly assigned here (p6).
D · incorrect — Code generation converts IC to machine code (p7).
Question 132
What is type checking in a compiler?
A. Verifying the syntax of the program.
B. Detecting lexical errors in the program.
C. Ensuring that the operations on variables are well-defined and compatible.
D. Generating the intermediate code for the program.
Hint / Module Reference (Where to Read)
Check operand compatibility and permitted conversions under the stated language rules; distinguish grammatical structure from semantic meaning.
Correct answer: C — Ensuring that the operations on variables are well-defined and compatible.
PDF p14 defines type checking as enforcing type safety and lists incompatible operands; p15 makes assignment produce type_error when the identifier and expression types differ. Thus C expresses compatible operations.
Evidence in the complete study note
A type checker verifies that operations are defined for their operands. In a simple strict language, integer mod requires two integers; array indexing requires an array and integer index; an if condition requires Boolean; assignment requires equal or convertible types. Function calls check parameter count and compatibility, and returns match result types.COMP22
Type inference derives types from constraints: if x is integer and + expects numeric operands, infer the expression type from numeric promotion rules. It is a static technique even without explicit annotations. Operator overloading supplies multiple operation meanings, not a substitute for type checking. int x="hello" is a type mismatch in ordinary C++/Java; division by zero and bounds violations are not automatically operand-type mismatches.COMP22
Choice by choice
A · incorrect — Grammatical syntax is handled by parsing (p5).
B · incorrect — Token recognition is lexical analysis (p8), not type compatibility.
C · correct — Compatible operations and assignments match pp14–15.
D · incorrect — Intermediate generation is distinct from semantic checking (pp6,15).
Question 133
Which of the following is an example of a static type checking technique?
A. Type inference
B. Dynamic typing
C. Run-time type checking
D. Operator overloading
Hint / Module Reference (Where to Read)
Check operand compatibility and permitted conversions under the stated language rules; distinguish grammatical structure from semantic meaning.
COMP22 defines type inference as deriving types from constraints and explicitly calls it static even without explicit type annotations. Dynamic typing and runtime checks concern execution-time behavior. Operator overloading defines several meanings for an operation, but is not a replacement for the checking technique itself. Thus only type inference is the named static technique.
Evidence in the complete study note
A type checker verifies that operations are defined for their operands. In a simple strict language, integer mod requires two integers; array indexing requires an array and integer index; an if condition requires Boolean; assignment requires equal or convertible types. Function calls check parameter count and compatibility, and returns match result types.COMP22
Type inference derives types from constraints: if x is integer and + expects numeric operands, infer the expression type from numeric promotion rules. It is a static technique even without explicit annotations. Operator overloading supplies multiple operation meanings, not a substitute for type checking. int x="hello" is a type mismatch in ordinary C++/Java; division by zero and bounds violations are not automatically operand-type mismatches.COMP22
Choice by choice
A · correct — Type inference derives expression types from constraints before execution and is explicitly a static technique.
B · incorrect — Dynamic typing does not name the requested before-execution type-inference technique.
C · incorrect — Runtime type checking occurs during execution, so it is not static checking.
D · incorrect — Overloading supplies operation meanings; COMP22 distinguishes it from type checking itself.
Question 134
Which attribute is specifically recorded for each variable in a type-oriented symbol table and distinguishes its typing information from the name that identifies the entry?
A. To store the types of variables used in the program.
B. To store the names of variables used in the program.
C. To store the intermediate code generated during parsing.
D. To store the syntax rules of the programming language.
Hint / Module Reference (Where to Read)
Ask whether the required information is a declaration’s identity and attributes, program structure or the ordered source tokens.
Correct answer: A — To store the types of variables used in the program.
A symbol table associates a name or declaration identity with attributes. In a type-oriented table, the relevant attribute is the variable’s type, used to check whether operations and assignments are compatible. Names identify the records but do not themselves give typing information. Intermediate instructions and grammar rules belong to other representations and are not the per-variable typing attribute requested.
Evidence in the complete study note
A symbol table maps names or symbol identities to attributes: type, scope, width, storage offset, parameter signature, constant information or linkage. A hash table gives expected O(1) insertion/lookup with suitable hashing; a stack of scope tables supports lexical nesting. Search the nearest scope first, insert declarations in the current scope, and remove visibility when leaving it.COMP19
Scanning may intern a spelling first; semantic analysis determines the declaration and type. Implementations differ, so first interaction is conventional rather than universal. Not every punctuation token needs a symbol-table entry; literals may use a separate literal table. A hash table is an implementation, not the information’s semantic role.COMP19
Choice by choice
A · correct — Variable types provide the requested typing attribute.
B · incorrect — Names identify entries but are not their type attributes.
C · incorrect — IR instructions are not the per-variable type attribute.
D · incorrect — Syntax rules describe the language rather than variable types.
Question 135
In ordinary C++ with no custom conversions, which offered example is specifically a type mismatch rather than a syntax, value-domain or layout issue?
A. Syntax error in an if-else statement.
B. Division of a number by zero.
C. int x="hello";
D. Incorrect indentation in the program.
Hint / Module Reference (Where to Read)
Check operand compatibility and permitted conversions under the stated language rules; distinguish grammatical structure from semantic meaning.
An ordinary C++ declaration int x="hello" attempts to initialize an integer from a string literal and is a type mismatch under the stated rules. Division by zero can involve correctly typed operands and is instead a value-domain fault. Incorrect indentation is layout, while malformed if-else syntax concerns grammatical arrangement. The option illustrates an incompatible-type example.
Evidence in the complete study note
A type checker verifies that operations are defined for their operands. In a simple strict language, integer mod requires two integers; array indexing requires an array and integer index; an if condition requires Boolean; assignment requires equal or convertible types. Function calls check parameter count and compatibility, and returns match result types.COMP22
Type inference derives types from constraints: if x is integer and + expects numeric operands, infer the expression type from numeric promotion rules. It is a static technique even without explicit annotations. Operator overloading supplies multiple operation meanings, not a substitute for type checking. int x="hello" is a type mismatch in ordinary C++/Java; division by zero and bounds violations are not automatically operand-type mismatches.COMP22
Choice by choice
A · incorrect — This explicitly describes a syntax error rather than a type mismatch.
B · incorrect — A zero divisor is a value issue even with compatible numeric types.
C · correct — A string literal is not a compatible ordinary integer initializer.
D · incorrect — Indentation does not establish an incompatible operand type.
Question 136
Which advantage of static type checking specifically concerns detecting incompatible operations before the program executes?
A. Improved program performance.
B. Enhanced code optimization.
C. Early detection of potential runtime errors.
D. Simplified debugging process.
Hint / Module Reference (Where to Read)
Check operand compatibility and permitted conversions under the stated language rules; distinguish grammatical structure from semantic meaning.
Correct answer: C — Early detection of potential runtime errors.
Static type checking can reject an incompatible operation during compilation, before that operation causes a run-time type error. This is the direct timing benefit asked for. Type information may also aid optimization, and diagnostics may make debugging easier, but those are additional consequences rather than the specific before-execution detection property. Type checking does not by itself guarantee faster code or eliminate all possible run-time errors.
Evidence in the complete study note
A type checker verifies that operations are defined for their operands. In a simple strict language, integer mod requires two integers; array indexing requires an array and integer index; an if condition requires Boolean; assignment requires equal or convertible types. Function calls check parameter count and compatibility, and returns match result types.COMP22
Type inference derives types from constraints: if x is integer and + expects numeric operands, infer the expression type from numeric promotion rules. It is a static technique even without explicit annotations. Operator overloading supplies multiple operation meanings, not a substitute for type checking. int x="hello" is a type mismatch in ordinary C++/Java; division by zero and bounds violations are not automatically operand-type mismatches.COMP22
Choice by choice
A · incorrect — Faster execution is not guaranteed and does not state detection before execution.
B · incorrect — Optimization may use types but is a different benefit from the requested early rejection.
C · correct — Compile-time rejection detects incompatible operations before execution.
D · incorrect — Debugging may be easier, but that broad consequence does not specify the requested detection timing.
Question 137
What is the primary goal of type checking in a compiler?
A. To ensure syntactic correctness of the program.
B. To generate efficient machine code.
C. To enforce programming language rules and constraints.
D. To provide support for code reuse through libraries.
Hint / Module Reference (Where to Read)
Check operand compatibility and permitted conversions under the stated language rules; distinguish grammatical structure from semantic meaning.
Correct answer: C — To enforce programming language rules and constraints.
PDF p14 defines type checking as semantic checks enforcing type safety and says the compiler checks source-language semantic conventions. C is the offered broad rule-enforcement description, limited here to type constraints.
Evidence in the complete study note
A type checker verifies that operations are defined for their operands. In a simple strict language, integer mod requires two integers; array indexing requires an array and integer index; an if condition requires Boolean; assignment requires equal or convertible types. Function calls check parameter count and compatibility, and returns match result types.COMP22
Type inference derives types from constraints: if x is integer and + expects numeric operands, infer the expression type from numeric promotion rules. It is a static technique even without explicit annotations. Operator overloading supplies multiple operation meanings, not a substitute for type checking. int x="hello" is a type mismatch in ordinary C++/Java; division by zero and bounds violations are not automatically operand-type mismatches.COMP22
Choice by choice
A · incorrect — Syntax correctness is the parsing task (p5).
B · incorrect — Machine-code efficiency is an optimization goal (pp7,17).
C · correct — Type-related semantic conventions and constraints match p14.
D · incorrect — Library reuse is not a type-checking goal stated in the module.
Question 138
Which of the following is an example of a type coercion or type conversion?
A. Assigning a floating-point value to an integer variable.
B. Assigning a value to an uninitialized variable.
C. Declaring a variable without specifying its type.
D. Using an undeclared variable in the program.
Hint / Module Reference (Where to Read)
Check operand compatibility and permitted conversions under the stated language rules; distinguish grammatical structure from semantic meaning.
Correct answer: A — Converting a floating-point value when assigning to an integer variable, where the language permits it.
COMP23 gives C++ int x=3.14 as an ordinary conversion yielding 3 when representable. That is the listed example of conversion, with the language caveat that Java needs a permitted cast and C++ brace initialization rejects narrowing. The remaining choices concern initialization, inference or undeclared names rather than converting one value type to another.
Evidence in the complete study note
Coercion is an implicit conversion permitted by the language; a cast requests an explicit conversion. Widening often increases representable range, but can still lose precision: Java int→float is widening although large integers round. Java int→long is exact. Narrowing can lose range or fractional information.COMP23
In C++ ordinary int x=3.14 converts to 3 when representable; it is not inherently a type error. int x{3.14} is rejected as narrowing. C++ floating-to-integer conversion discards the fraction and has undefined behavior if the truncated value is unrepresentable. Java ordinary double→int assignment needs a permitted explicit cast. Mixing char and int is ordinarily valid after promotion in C++/Java; do not import a fictitious universal ban.COMP23
Choice by choice
A · correct — Floating-to-integer assignment performs conversion where permitted; exact legality and precision loss depend on the language.
B · incorrect — First assigning to a variable is initialization or assignment, not inherently a change of value type.
C · incorrect — Omitting an explicit declaration type may invoke inference; it does not itself convert a value.
D · incorrect — An undeclared name is a name-resolution problem rather than an example of value conversion.
Question 139
Which listed approaches are bottom-up and therefore are not top-down parsers? Select all that apply. Assume predictive recursive descent for A.
A. Recursive-descent parser
B. Shift-reduce parser
C. Non-recursive predictive parser
D. LR parser
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
Correct answers (select all): B, D — Shift-reduce parser; LR parser
Shift-reduce parsing starts from the input and reduces recognized handles toward the start symbol. LR is a bottom-up family using that strategy. Recursive descent and nonrecursive prediction instead expand productions top-down for suitable grammars. Therefore both B and D fail the top-down description. This directional distinction avoids an unsupported efficiency ranking between recursive and table-driven predictive implementations.
Evidence in the complete study note
Top-down parsing starts with S and expands productions toward the input, usually constructing a leftmost derivation. Recursive descent typically has one procedure per nonterminal. A general recursive-descent implementation can backtrack; a predictive parser chooses a production using lookahead without backtracking. LL(1) scans Left to right, produces a Leftmost derivation and uses one lookahead token.COMP11
Bottom-up parsing starts from input and reduces toward S, constructing a rightmost derivation in reverse.COMP15
Choice by choice
A · incorrect — Predictive recursive descent is top-down.
B · correct — Shift-reduce is bottom-up.
C · incorrect — Nonrecursive prediction is top-down.
D · correct — LR is bottom-up.
Question 140
Which one of the following is a type of compiler that compiles only the changed lines from
source code and updates the object code accordingly?
A. Retargetable compiler
B. One pass compiler
C. Incremental compiler
D. Parallelizing compiler
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
COMP02 defines incremental compilation as recompiling affected fragments or dependent units after edits. This is the compiler category intended by updating code after source changes. The question’s only changed lines wording is simplified: real dependency tracking can require recompiling more than literal edited lines. Retargeting and one-pass organization describe different properties.
Evidence in the complete study note
A preprocessor handles directives such as file inclusion and macros. An assembler translates assembly to object code. A linker combines object files and libraries, resolves external symbols and performs relocation. A loader maps an executable into memory and starts it. Compilation alone does not necessarily produce a ready executable.COMP02
A cross-compiler runs on a host platform and generates code for a different target. Multiple targets require appropriate backends, not a special definition of cross-compilation. A retargetable compiler supports changing target descriptions. Incremental compilation recompiles affected fragments or dependent units after edits; it is more than literally replacing changed lines. One-pass versus multipass counts traversals, not supported targets.COMP02
Choice by choice
A · incorrect — Retargetable compilers support changing target descriptions rather than selecting edited source fragments.
B · incorrect — One pass counts traversals of the program, not whether edits trigger selective recompilation.
C · correct — Incremental compilation updates affected fragments after edits, accounting for dependencies beyond literal changed lines.
D · incorrect — Parallelizing compilation is not the category defined by selective recompilation after source changes.
Question 141
Which technique of code optimization shifts computations from run time to compile time by
evaluating constant expressions at compile time and replacing them with their values?
A. Copy propagation
B. Compile time evaluation
C. Code motion
D. Dead code elimination
Hint / Module Reference (Where to Read)
Trace whether computation is evaluated, moved, shared or removed. Preserve observable effects and use the stated arithmetic and target assumptions.
PDF p18 lists constant folding and illustrates R2 = 3 * 2. Evaluating this constant expression early gives 6, eliminating that runtime computation. B describes this operation as compile time evaluation, although constant folding would be the module’s exact name.
Evidence in the complete study note
Constant folding evaluates constant expressions during compilation: 3*4→12. Constant propagation substitutes known values: x=3; y=x+2 becomes y=3+2 before folding. Copy propagation substitutes a copied name while its source remains unchanged. Dead-code elimination removes unreachable code or computations whose values are unused and whose evaluation has no necessary side effects.COMP30
Choice by choice
A · incorrect — P18 copy propagation example copies r1 into r2, not evaluates a constant arithmetic expression.
B · correct — Evaluating 3 * 2 to 6 is the constant-folding example on p18, matching the stem.
C · incorrect — P18 code movement relocates a block outside a loop, not necessarily evaluating it at compilation.
D · incorrect — P18 dead-code elimination removes unreachable statements, rather than computing constant values.
Question 142
For const int x=8; const int y=16; if(x>y){int z=x+y;}, which techniques directly evaluate the known condition and remove its unreachable body? Select all that apply. Arithmetic simplification means algebraic identity rewriting here.
A. Code motion
B. Dead code elimination
C. Compile time evaluation
D. Arithmetic simplification
Hint / Module Reference (Where to Read)
Trace whether computation is evaluated, moved, shared or removed. Preserve observable effects and use the stated arithmetic and target assumptions.
Correct answers (select all): B, C — Dead code elimination; Compile time evaluation
Both x and y are known constants, so evaluating 8>16 at compile time yields false. The body can never execute and dead-code elimination can remove it. These are distinct but compatible transformations, corresponding to B and C in this option order. Code motion relocates computations, while algebraic identity simplification is not the decisive operation on this constant-false condition.
Evidence in the complete study note
For const int x=8,y=16; if(x>y){int z=x+y;}, propagate the constants, fold 8>16 to false, then remove the unreachable branch. Both compile-time evaluation and dead-code elimination apply.COMP30
Algebraic simplification removes identities when valid: integer x+0→x.COMP31
Choice by choice
A · incorrect — No relocation is needed to evaluate or delete the branch.
B · correct — The unreachable branch body can be removed.
C · correct — The condition is evaluated from known constants at compile time.
D · incorrect — No algebraic identity rewrite is the decisive step.
Question 143
What is the difference between a compiler and an interpreter?
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
Answer: A compiler translates; an interpreter executes a representation.
COMP01 distinguishes translating source into an equivalent target from executing a program representation. Bytecode systems may combine compilation, interpretation and JIT, so the distinction is not simply all-at-once versus line-by-line execution.
Evidence in the complete study note
A compiler translates a source program into an equivalent target representation while preserving defined observable behavior. The target may be machine code, assembly, bytecode or another source language. A transpiler is a source-to-source compiler, not a fundamentally separate noncompiler technology. A compiler preserves language semantics, not the programmer’s unstated intention.COMP01
An interpreter executes a program representation; it need not work one source line at a time. Systems can compile to bytecode and then interpret or JIT-compile it. AOT compilation happens before execution; JIT compilation happens during execution and may use runtime profiles. Neither is universally faster; startup cost, optimization and workload matter.COMP01
Question 144
What is the difference between lexical analysis and syntax analysis?
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
Answer: Lexical analysis groups characters into tokens; syntax analysis groups tokens into structures.
COMP41 separates character-to-token classification from token-to-expression or statement structure. The scanner recognizes lexemes such as identifiers and operators and emits an ordered token stream. The parser checks how those tokens form grammatical constructs and can build a parse tree or AST; legal tokens can still appear in an illegal syntactic arrangement.
Evidence in the complete study note
A token is a category with optional attribute, such as (ID, symbol-entry) or (INT_LITERAL,42). A lexeme is the actual character sequence, such as total or 42. A pattern specifies which lexemes belong to a token class.COMP04
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained.COMP04
A parse tree shows grammar productions: root S, internal nonterminals, and terminal leaves, with ε sometimes shown for empty productions. Its left-to-right yield is the input. An AST omits grammar scaffolding and punctuation; expression operands are leaves and operators internal nodes. The parser can build either representation, depending on implementation.COMP09
Question 145
What is the purpose of a symbol table?
Hint / Module Reference (Where to Read)
Ask whether the required information is a declaration’s identity and attributes, program structure or the ordered source tokens.
Answer: A symbol table associates names with declaration attributes.
COMP19 maps names or identities to type, scope, width, offsets, signatures and linkage information. These records support declaration lookup and semantic checks; a hash table is one implementation rather than the purpose itself.
Evidence in the complete study note
A symbol table maps names or symbol identities to attributes: type, scope, width, storage offset, parameter signature, constant information or linkage. A hash table gives expected O(1) insertion/lookup with suitable hashing; a stack of scope tables supports lexical nesting. Search the nearest scope first, insert declarations in the current scope, and remove visibility when leaving it.COMP19
Scanning may intern a spelling first; semantic analysis determines the declaration and type. Implementations differ, so first interaction is conventional rather than universal. Not every punctuation token needs a symbol-table entry; literals may use a separate literal table. A hash table is an implementation, not the information’s semantic role.COMP19
Question 146
What is the difference between top-down and bottom-up parsing?
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
Answer: Top-down expands from the start symbol; bottom-up reduces input toward it.
COMP15 describes bottom-up recognition as input reductions toward S, reversing a rightmost derivation. COMP11 describes top-down expansion from S toward the input, normally a leftmost derivation.
Evidence in the complete study note
Top-down parsing starts with S and expands productions toward the input, usually constructing a leftmost derivation. Recursive descent typically has one procedure per nonterminal. A general recursive-descent implementation can backtrack; a predictive parser chooses a production using lookahead without backtracking. LL(1) scans Left to right, produces a Leftmost derivation and uses one lookahead token.COMP11
Bottom-up parsing starts from input and reduces toward S, constructing a rightmost derivation in reverse. A handle is a production RHS occurrence whose reduction is the next step of that reverse derivation. Not every substring matching a RHS is a handle in the current context.COMP15
Question 147
What is intermediate code and why is it used?
Hint / Module Reference (Where to Read)
Identify what the representation stores, what it omits and which later transformations it must support; separate a representation property from an algorithmic task.
Answer: IR separates source analysis from target lowering and enables reuse.
COMP26 defines IR’s role in separating source meaning from target implementation so analysis, optimization and backends can be reused. ASTs, graphs, TAC and bytecode are possible forms. A useful IR is easy to generate, analyze, transform and lower; portability does not require every IR to exclude all target-specific details.
Evidence in the complete study note
IR separates source analysis from target implementation, allowing optimizers and backends to be reused. It should be easy to generate, analyze, transform and lower.COMP26
Ordinary TAC arithmetic has at most one operation, two sources and one destination: t1=c*d; t2=b+t1; a=t2. Quadruples store (op,arg1,arg2,result); triples omit an explicit result field and refer to instruction positions. Indirect triples reference a separate ordering list, easing rearrangement. Trees describe expressions; DAGs share common subexpressions, while quadruples/triples are instruction-record structures.COMP26
Question 148
Which of the following is NOT a valid token type produced during lexical analysis?
A. Keyword |
B. Parse tree node
C. Identifier |
D. Numeric literal
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
Correct answer: B — Parse-tree node is not a lexical token type.
COMP04 lists keywords, identifiers and literals among token classes. A parse-tree node belongs to the grammatical structure built after scanning, not the lexical class of a source lexeme. Consequently only parse-tree node is the invalid token-type choice, while the other three are ordinary scanner output categories.
Evidence in the complete study note
A token is a category with optional attribute, such as (ID, symbol-entry) or (INT_LITERAL,42). A lexeme is the actual character sequence, such as total or 42. A pattern specifies which lexemes belong to a token class. The scanner emits an ordered token stream, not an unordered mathematical set.COMP04
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
Choice by choice
A · incorrect — Keywords are explicitly listed as a valid lexical token class.
B · correct — Parse-tree nodes represent grammatical structure, not a lexical token category emitted by a scanner.
C · incorrect — Identifiers are an ordinary lexical token class.
D · incorrect — Numeric literals are literals and therefore valid token categories.
Question 149
What algorithm is commonly used to convert a Non-deterministic Finite Automaton (NFA) to a Deterministic Finite Automaton (DFA) in lexer construction?
A. Thompson's construction |
B. Subset construction (Powerset construction)
C. Cocke-Younger-Kasami (CYK) |
D. Earley's algorithm
Hint / Module Reference (Where to Read)
Follow the representation at each construction step and apply the pattern or state-set rules consistently, including empty cases.
Correct answer: B — Subset (powerset) construction.
COMP06 distinguishes Thompson construction, which builds an NFA from a regular expression, from subset construction, which determinizes the NFA. Each DFA state represents an NFA-state subset, with epsilon closure when needed. CYK and Earley are grammar-parsing algorithms rather than this automaton determinization, so the powerset option is the relevant stage.
Evidence in the complete study note
A common generator pipeline is regular expressions → NFA using Thompson construction → DFA using subset construction; minimization is optional.COMP06
The ε-closure of states includes those reachable by zero or more ε edges. A DFA state is a set of NFA states; its a-transition is ε-closure(move(set,a)). Start with the NFA start closure, repeatedly add unseen subsets, and mark subsets containing an NFA final state as accepting. Token identity and rule priority annotate accepting states; the empty subset acts as a dead state.COMP06
CYK and Earley are context-free grammar parsing algorithms. They determine grammatical structure or membership of an input sequence. They are different tasks from Thompson construction, which builds a token-recognizing NFA from a regular expression, and subset construction, which turns an NFA into a DFA.COMP-S02
Choice by choice
A · incorrect — Thompson construction goes from regular expression to NFA rather than NFA to DFA.
B · correct — Subset construction creates DFA states from sets of NFA states.
C · incorrect — CYK performs CFG membership parsing and does not determinize a lexical NFA.
D · incorrect — Earley is a grammar-parsing method rather than the stated NFA-to-DFA construction.
Question 150
Given the grammar: E → E + T | T, T → T * F | F, F → (E) | id — this grammar enforces:
A. Right-associativity for both + and * |
B. Left-associativity for both + and *, with * having higher precedence than +
C. Right-associativity for + and left-associativity for * |
D. No precedence or associativity rules
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
Correct answer: B — Both operators associate left; multiplication has higher precedence.
COMP10 states exactly these productions and their effect. Multiplication occurs within T below the addition level E, so it binds more tightly. The recursive operand on the left of E→E+T and T→T*F enforces left association for each operator. Parentheses in F can override the default grouping.
Evidence in the complete study note
Use E→E+T|T, T→T*F|F, F→(E)|id to give * higher precedence and both operators left associativity. For subtraction, a−b−c then groups (a−b)−c.COMP10
Choice by choice
A · incorrect — The recursive nonterminal is on the left, producing left rather than right association.
B · correct — Separate T multiplication and E addition levels give higher multiplication precedence and left association.
C · incorrect — Addition is left-recursive too, so it does not have the claimed right association.
D · incorrect — The grammar explicitly encodes both precedence levels and associativity.
Question 151
For a reduced CFG (all symbols reachable and productive), which conditions prevent it from being LL(1)? Select all that apply. In A, overlap means a shared terminal in competing RHS FIRST sets.
A. Two productions for the same non-terminal have overlapping FIRST sets |
B. The grammar contains a left-recursive rule
C. The grammar is ambiguous |
D. A and B only
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
Correct answers (select all): A, B, C — Two productions for the same non-terminal have overlapping FIRST sets |; The grammar contains a left-recursive rule; The grammar is ambiguous |
A shared FIRST terminal for alternatives of one nonterminal creates a predictive-table collision. Reachable left recursion prevents ordinary LL(1) prediction, and an ambiguous useful grammar cannot have a unique LL(1) parse. Thus A, B and C are all obstructions. The combined D alternative wrongly says only A and B, excluding ambiguity, so it is not a complete correct selection.
Evidence in the complete study note
For every A→α, put it in M[A,a] for each terminal a in FIRST(α). If α is nullable, also enter it under every symbol in FOLLOW(A). More than one production in a cell is a conflict. Pairwise SELECT sets must be disjoint; SELECT(α)=FIRST(α)−{ε}, plus FOLLOW(A) when α is nullable. This also detects two nullable alternatives.COMP14
Indirect left recursion follows a cycle through other nonterminals and also needs removal for ordinary predictive descent.COMP12
LR parsers can handle suitable left-recursive grammars; ordinary unmodified recursive descent can recurse forever before consuming input.COMP12
Deterministic LL/LR grammars must be unambiguous; a general ambiguous grammar requires rewriting, disambiguation policy or a generalized method such as GLR.COMP18
Choice by choice
A · correct — Shared FIRST terminals create competing table entries.
B · correct — Reachable left recursion rules out ordinary LL(1) parsing.
C · correct — A useful ambiguous grammar is not LL(1).
D · incorrect — The word only wrongly excludes the valid ambiguity obstruction.
Question 152
Which of the following is an example of a synthesized attribute in attribute grammars?
A. The type of an expression computed from its sub-expressions |
B. The scope environment passed down to a block
C. The inherited type context for a function body |
D. The enclosing loop level passed to a break statement
Hint / Module Reference (Where to Read)
Track where each computed value comes from and when each production action runs. Distinguish the representation from its attached information.
Correct answer: A — Expression type computed from subexpressions is synthesized.
COMP24 defines synthesized attributes by flow from children to a parent. Computing an expression’s type from its subexpressions fits this direction. Scope, type context and enclosing-loop information passed down from surrounding constructs instead supply inherited context. The direction of dependency, rather than the fact that types are involved, distinguishes these choices.
Evidence in the complete study note
A syntax-directed definition is a CFG with attributes on grammar symbols and semantic rules on productions. An annotated parse tree displays computed attribute values; it is not itself an inherited or synthesized attribute. Synthesized attributes flow from children to a parent; inherited attributes carry context from parent or siblings.COMP24
For E→E1+T, E.val=E1.val+T.val synthesizes an expression value. A declaration’s type environment passed into its body is inherited. S-attributed definitions use only synthesized attributes and fit LR reduction-time evaluation naturally; suitable LL parsers can also compute them. L-attributed definitions restrict dependencies so a left-to-right traversal can evaluate inherited context. Attribute dependency cycles can prevent evaluation.COMP24
Choice by choice
A · correct — The parent expression derives its type from child subexpressions, which is synthesized upward flow.
B · incorrect — A scope environment passed down to a block is inherited contextual information.
C · incorrect — A type context supplied to a function body flows from its surroundings, so it is inherited.
D · incorrect — Enclosing-loop context is passed inward to a break statement rather than synthesized from its children.
Question 153
What is the primary purpose of Three-Address Code (TAC) as an intermediate representation?
A. To directly execute on the target CPU |
B. To provide a machine-independent representation suitable for optimization and code generation
C. To replace the symbol table |
D. To encode only arithmetic expressions
Hint / Module Reference (Where to Read)
Identify what the representation stores, what it omits and which later transformations it must support; separate a representation property from an algorithmic task.
Correct answer: B — An optimization-friendly intermediate representation for later target generation.
COMP26 gives reuse and separation as the purpose of IR and describes TAC as simple instruction records. TAC is normally not directly executed by a native CPU, does not replace declaration metadata and is not limited to arithmetic: branches and assignments are also representable. B states its architectural optimization/code-generation role most directly.
Evidence in the complete study note
IR separates source analysis from target implementation, allowing optimizers and backends to be reused. It should be easy to generate, analyze, transform and lower.COMP26
Ordinary TAC arithmetic has at most one operation, two sources and one destination: t1=c*d; t2=b+t1; a=t2. Quadruples store (op,arg1,arg2,result); triples omit an explicit result field and refer to instruction positions. Indirect triples reference a separate ordering list, easing rearrangement. Trees describe expressions; DAGs share common subexpressions, while quadruples/triples are instruction-record structures.COMP26
Choice by choice
A · incorrect — TAC is normally intermediate and requires lowering rather than direct execution on the target CPU.
B · correct — TAC provides analyzable intermediate operations supporting reuse, optimization and later target-code generation.
C · incorrect — A symbol table retains declaration metadata and is not replaced by the instruction representation.
D · incorrect — TAC can encode control transfers and other operations, not only arithmetic expressions.
Question 154
The 'maximal munch' rule in lexical analysis means:
A. The lexer always produces the shortest possible token |
B. The lexer always produces the longest possible token matching the current position
C. Keyword tokens are prioritized over identifiers |
D. Comments are included in the token stream
Hint / Module Reference (Where to Read)
Follow the representation at each construction step and apply the pattern or state-set rules consistently, including empty cases.
Correct answer: B — Choose the longest matching lexeme at the current position.
COMP07 defines longest matching lexeme selection at each input position. Equal-length matches use rule order, which is a separate tie-breaking rule; keywords do not override a longer identifier such as ifx. Comments are normally skipped rather than retained merely because maximal munch is used. This establishes B as the definition.
Evidence in the complete study note
At each input position, choose the longest matching lexeme; if equal lengths match multiple flex rules, choose the earliest rule. Thus ifx is an identifier rather than if followed by x; <= and ++ are each one operator token. An implementation may recognize an identifier first and then consult a keyword table.COMP07
Choice by choice
A · incorrect — Shortest-match selection is the opposite of maximal munch.
B · correct — The lexer consumes the longest available match beginning at the current input position.
C · incorrect — Keyword priority can break equal-length rule ties but does not define longest match.
D · incorrect — Comment retention is independent of longest match; ordinary comments are skipped.
Question 155
In bottom-up parsing, a 'shift-reduce conflict' occurs when:
A. There are two possible reductions for the same stack top |
B. The parser cannot decide whether to shift the next input token or reduce the current stack contents
C. The grammar is left-recursive |
D. The FOLLOW set is empty
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
Correct answer: B — A competing shift and reduction on the same situation.
COMP17 defines a shift/reduce conflict as a choice between consuming a token and reducing. Two competing reductions describe reduce/reduce instead. Left recursion may be entirely acceptable to LR, and an empty FOLLOW set is not the definition of this table conflict. The conflict concerns competing actions for the same state and lookahead.
Evidence in the complete study note
SLR(1) uses LR(0) states and FOLLOW(A) for reduction by a completed A production. Canonical LR(1) attaches context-specific lookahead to items. LALR(1) merges canonical states with the same LR(0) core, combining lookaheads; merging can introduce reduce/reduce conflicts. The standard grammar-class hierarchy is LR(0)⊆SLR(1)⊆LALR(1)⊆LR(1), with increasing capability and often table size.COMP17
A shift/reduce conflict offers both consuming a token and reducing; reduce/reduce offers two reductions. An SLR or LALR conflict does not by itself prove the grammar ambiguous. Canonical LR(1) handles LR(1) grammars, not every unambiguous CFG. Precedence and associativity can resolve suitable expression conflicts; changing parser names alone does not repair all ambiguity.COMP17
Choice by choice
A · incorrect — Two possible reductions define a reduce/reduce conflict, a different conflict type.
B · correct — The same parser situation permits both shifting input and reducing the recognized right-hand side.
C · incorrect — LR can handle suitable left recursion; that property does not itself define a shift/reduce conflict.
D · incorrect — FOLLOW-set emptiness does not express competing shift and reduction actions.
Question 156
Which optimization technique moves loop-invariant computations outside the loop body?
A. Strength reduction |
B. Loop unrolling
C. Loop-invariant code motion (LICM) |
D. Dead code elimination
Hint / Module Reference (Where to Read)
Trace whether computation is evaluated, moved, shared or removed. Preserve observable effects and use the stated arithmetic and target assumptions.
COMP32 explains that an expression whose inputs remain unchanged can be moved to a preheader when safe on newly executed paths. That is loop-invariant code motion. Strength reduction changes operation cost, unrolling replicates the body, and dead-code elimination removes unused or unreachable work. Hoisting also requires safety, not merely unchanged operands.
Evidence in the complete study note
A loop-invariant expression has unchanged inputs during a loop. Hoist it to a preheader only when evaluation is safe on the paths where it will newly run. Induction variables change by a loop-invariant increment, such as i=i+1. For repeated t=4*i, maintain a running t increased by 4 when equivalent, reducing repeated multiplication.COMP32
Loop fusion or jamming combines loops with compatible bounds and safe dependence order. Unrolling replicates a body to reduce branch overhead and expose parallelism; handle remaining iterations and increased code size. Loop-invariant code motion, fusion, unrolling and strength reduction are different transformations. A finite taxonomy needs a criterion: machine dependent/independent versus local/global/loop are different classifications.COMP32
Choice by choice
A · incorrect — Strength reduction substitutes a cheaper equivalent operation rather than necessarily moving it outside a loop.
B · incorrect — Unrolling replicates loop bodies instead of hoisting invariant computations.
C · correct — LICM moves invariant computations to an appropriate outside location when executing them there is safe.
D · incorrect — Dead-code elimination removes unnecessary computations rather than relocating a needed invariant value.
Question 157
What does 'register spilling' mean in the context of register allocation?
A. Allocating the same register to two variables |
B. Storing a variable in memory instead of a register because no register is available
C. Using floating-point registers for integer values |
D. Eliminating unnecessary register copies
Hint / Module Reference (Where to Read)
Match stored information to its lifetime, access path and calling-convention role; distinguish compile-time organization from run-time storage.
Correct answer: B — Store selected values in memory and insert loads/stores when registers do not suffice.
COMP36 says spilling places selected values in memory when the register assignment cannot fit available registers. Loads and stores then connect memory-resident values to instructions needing registers. Register sharing can be legal for nonoverlapping live ranges, while copy elimination and choosing a different register class are separate operations rather than this storage fallback.
Evidence in the complete study note
A value is live where it can be used before redefinition. In the interference model, values that must coexist in distinct registers are connected by an edge; each register is a color. Nonoverlapping live ranges may share a register. If a valid assignment cannot fit the available registers, spilling places selected values in memory and inserts loads/stores.COMP36
The general graph k-colorability decision problem is NP-complete for fixed k≥3; optimal register assignment/spill minimization is a hard optimization problem in general, so practical allocators use heuristics.COMP36
Choice by choice
A · incorrect — Register sharing may be legal for disjoint live ranges and does not itself describe spilling.
B · correct — Spilling moves selected values to memory because a feasible register-only assignment is unavailable.
C · incorrect — Using another register class is not the definition of writing spilled values to memory.
D · incorrect — Removing redundant register copies is a different optimization from memory-backed spilling.
Question 158
For Java numeric conversions such as int→long and int→float, which statement correctly describes widening?
A. Converting a wider type to a narrower type, possibly losing information |
B. Converting to a numeric type with a wider representable range; some widening conversions can still lose precision.
C. Declaring a variable with an explicit type annotation |
D. Assigning a value to a pointer of a different type
Hint / Module Reference (Where to Read)
Check operand compatibility and permitted conversions under the stated language rules; distinguish grammatical structure from semantic meaning.
Correct answer: B — Converting to a numeric type with a wider representable range; some widening conversions can still lose precision.
Java int→long is widening and exact, while int→float is also widening even though some large integer values round. Widening therefore does not universally guarantee preservation of every bit of precision. Narrowing goes toward a more restricted representation; type annotations and arbitrary pointer changes are separate concepts. Option B captures the relevant larger-range conversion without making the false no-loss promise.
Evidence in the complete study note
Coercion is an implicit conversion permitted by the language; a cast requests an explicit conversion. Widening often increases representable range, but can still lose precision: Java int→float is widening although large integers round. Java int→long is exact. Narrowing can lose range or fractional information.COMP23
In C++ ordinary int x=3.14 converts to 3 when representable; it is not inherently a type error. int x{3.14} is rejected as narrowing. C++ floating-to-integer conversion discards the fraction and has undefined behavior if the truncated value is unrepresentable. Java ordinary double→int assignment needs a permitted explicit cast. Mixing char and int is ordinarily valid after promotion in C++/Java; do not import a fictitious universal ban.COMP23
Choice by choice
A · incorrect — This describes narrowing rather than widening.
B · correct — Widening can increase range while still losing precision, as int→float illustrates.
C · incorrect — An explicit annotation declares a type rather than converting a value.
D · incorrect — An arbitrary pointer-type change does not define Java numeric widening.
Question 159
Which of the following data structures is most commonly used to implement a symbol table for fast insertion and lookup?
A. Sorted linked list |
B. Hash table
C. Binary search tree |
D. Stack
Hint / Module Reference (Where to Read)
Ask whether the required information is a declaration’s identity and attributes, program structure or the ordered source tokens.
COMP19 directly identifies hashing as giving expected constant-time insertion and lookup under suitable hashing. A stack supports nested scope order but is not the primary keyed mapping. Lists and trees are possible alternatives, yet neither is the specific common expected-constant-time structure emphasized in the note and requested by the stem.
Evidence in the complete study note
A symbol table maps names or symbol identities to attributes: type, scope, width, storage offset, parameter signature, constant information or linkage. A hash table gives expected O(1) insertion/lookup with suitable hashing; a stack of scope tables supports lexical nesting. Search the nearest scope first, insert declarations in the current scope, and remove visibility when leaving it.COMP19
Scanning may intern a spelling first; semantic analysis determines the declaration and type. Implementations differ, so first interaction is conventional rather than universal. Not every punctuation token needs a symbol-table entry; literals may use a separate literal table. A hash table is an implementation, not the information’s semantic role.COMP19
Choice by choice
A · incorrect — A sorted linked list generally requires linear search and does not supply the highlighted expected constant lookup.
B · correct — Hash tables commonly implement expected O(1) symbol insertion and lookup.
C · incorrect — A search tree is possible, but the note specifically identifies hashing for the usual fast keyed implementation.
D · incorrect — A stack organizes scope nesting rather than providing fast arbitrary name lookup within a scope.
Question 160
A grammar is said to be 'left-factored' when:
A. All productions are left-recursive |
B. Productions for the same non-terminal that share a common prefix are rewritten to factor out the prefix
C. The grammar has no ε-productions |
D. The grammar can be parsed by a bottom-up parser only
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
Correct answer: B — Common prefixes are factored out of alternatives.
COMP12 rewrites A→αβ|αγ as A→αA′ and A′→β|γ. The transformation postpones the alternative choice until after consuming the common prefix. It does not mean making productions left-recursive, removing all epsilon rules or restricting parsing to bottom-up methods; left factoring alone also does not guarantee LL(1).
Evidence in the complete study note
Left factoring rewrites A→αβ|αγ using:
A→αA′
A′→β|γ
It postpones a choice until after the common prefix. It does not by itself remove ambiguity or guarantee LL(1). LR parsers can handle suitable left-recursive grammars; ordinary unmodified recursive descent can recurse forever before consuming input.COMP12
Choice by choice
A · incorrect — Left recursion and left factoring are distinct properties and transformations.
B · correct — Factoring extracts shared prefixes and delays selection between the remaining suffix alternatives.
C · incorrect — Factoring does not require removing every epsilon production.
D · incorrect — Factored grammars can support top-down prediction; bottom-up exclusivity is not a defining condition.
Question 161
What is 'constant propagation' in compiler optimization?
A. Evaluating constant expressions at compile time |
B. Replacing uses of a variable with its known constant value at each program point
C. Removing code that has no effect on program output |
D. Moving constants from memory to registers
Hint / Module Reference (Where to Read)
Trace whether computation is evaluated, moved, shared or removed. Preserve observable effects and use the stated arithmetic and target assumptions.
Correct answer: B — Replace uses with their known constant values.
COMP30 gives x=3; y=x+2 becoming y=3+2 before folding. Replacing x by its known value is propagation; evaluating 3+2 is folding. Removing unnecessary code or choosing register locations addresses different transformations. The program-point qualification matters because the value must still be known on all relevant incoming paths.
Evidence in the complete study note
Constant folding evaluates constant expressions during compilation: 3*4→12. Constant propagation substitutes known values: x=3; y=x+2 becomes y=3+2 before folding. Copy propagation substitutes a copied name while its source remains unchanged. Dead-code elimination removes unreachable code or computations whose values are unused and whose evaluation has no necessary side effects.COMP30
Choice by choice
A · incorrect — Evaluating an already constant expression is constant folding, which can follow propagation.
B · correct — Propagation substitutes a variable’s established constant value at uses where that fact holds.
C · incorrect — Removing effect-free unused or unreachable work is dead-code elimination.
D · incorrect — Memory-to-register placement is not the substitution of a known compile-time value.
Question 162
In an LR parsing table, what does a 'reduce/reduce conflict' indicate?
A. Two different productions can both be used to reduce the same stack contents with the same lookahead |
B. The parser must both shift and reduce on the same input symbol
C. The grammar has a dangling else problem |
D. The grammar contains ε-productions
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
Correct answer: A — Two competing reductions for the same parser state/lookahead.
COMP17 defines reduce/reduce as two reductions being available. In a parsing table that means the same state and lookahead permit different completed productions. A shift competing with reduction is another conflict type. Dangling else is a grammar ambiguity example, and epsilon productions alone do not guarantee any reduce/reduce collision.
Evidence in the complete study note
SLR(1) uses LR(0) states and FOLLOW(A) for reduction by a completed A production. Canonical LR(1) attaches context-specific lookahead to items. LALR(1) merges canonical states with the same LR(0) core, combining lookaheads; merging can introduce reduce/reduce conflicts. The standard grammar-class hierarchy is LR(0)⊆SLR(1)⊆LALR(1)⊆LR(1), with increasing capability and often table size.COMP17
A shift/reduce conflict offers both consuming a token and reducing; reduce/reduce offers two reductions. An SLR or LALR conflict does not by itself prove the grammar ambiguous. Canonical LR(1) handles LR(1) grammars, not every unambiguous CFG. Precedence and associativity can resolve suitable expression conflicts; changing parser names alone does not repair all ambiguity.COMP17
Choice by choice
A · correct — The table offers two different production reductions for the same state and lookahead.
B · incorrect — Simultaneous shift and reduce actions define shift/reduce rather than reduce/reduce.
C · incorrect — Dangling else commonly creates an attachment ambiguity, not the definition of two competing reductions.
D · incorrect — Epsilon rules can appear in conflict-free grammars and do not alone imply this collision.
Question 163
Which compiler phase is primarily responsible for detecting the incompatible assignment in the Java declaration int x = "hello";?
A. Lexical analysis |
B. Syntax analysis
C. Semantic analysis |
D. Code generation
Hint / Module Reference (Where to Read)
Check operand compatibility and permitted conversions under the stated language rules; distinguish grammatical structure from semantic meaning.
The declaration has recognizable tokens and a valid declaration-shaped syntax, but assigns a string to an integer variable. Under Java’s type rules this violates assignment compatibility, so semantic analysis and type checking identify the error. Scanning recognizes the identifier, type keyword and literal; parsing organizes them. Code generation uses the checked representation later. The named language removes any assumption that every statically typed language has identical implicit conversions.
Evidence in the complete study note
A lexical error prevents forming a legal token, such as an invalid character or unterminated literal. A syntax error is an illegal token arrangement, such as a missing delimiter. A semantic error violates name, scope or type rules after grammatical recognition. A wrong algorithm can compile successfully; compilers do not detect all logical mistakes.COMP08
int x="hello" is a type mismatch in ordinary C++/Java; division by zero and bounds violations are not automatically operand-type mismatches.COMP22
Choice by choice
A · incorrect — The individual tokens are recognizable; the error is their type compatibility.
B · incorrect — The declaration’s grammar structure is not the primary problem.
C · correct — Semantic type checking rejects the string-to-integer assignment.
D · incorrect — Code generation follows the frontend type check rather than defining this compatibility rule.
Question 164
In Thompson's construction for building an NFA from a regular expression, the NFA for the concatenation r1r2 is built by:
A. Merging the start states of both NFAs |
B. Adding an ε-transition from the accepting state(s) of the NFA for r1 to the start state of the NFA for r2
C. Creating a new start state with ε-transitions to both NFAs |
D. Taking the cross product of the two NFAs
Hint / Module Reference (Where to Read)
Follow the representation at each construction step and apply the pattern or state-set rules consistently, including empty cases.
Correct answer: B — Connect the first fragment’s accepting end to the second start with ε.
COMP06 directly gives the concatenation rule: connect r’s final state to s’s start by epsilon. This forces any complete path through the first fragment to continue through the second in order. Branching epsilon paths instead implement alternation; merged starts and product constructions do not implement the specified Thompson concatenation step.
Evidence in the complete study note
A common generator pipeline is regular expressions → NFA using Thompson construction → DFA using subset construction; minimization is optional. For concatenation rs, connect r’s final state to s’s start by ε. Alternation introduces branching ε paths; star adds a way to skip and repeat the fragment.COMP06
The ε-closure of states includes those reachable by zero or more ε edges. A DFA state is a set of NFA states; its a-transition is ε-closure(move(set,a)). Start with the NFA start closure, repeatedly add unseen subsets, and mark subsets containing an NFA final state as accepting. Token identity and rule priority annotate accepting states; the empty subset acts as a dead state.COMP06
Choice by choice
A · incorrect — Merging starts does not force a complete r1 match followed by an r2 match.
B · correct — The epsilon connection joins the first accepting end to the second start without consuming input.
C · incorrect — A new branching start with epsilon alternatives implements union rather than concatenation.
D · incorrect — A state cross product is not the Thompson fragment connection for concatenation.
Question 165
What is the 'dangling else' problem?
A. An else branch that can never be reached due to preceding conditions |
B. Ambiguity in grammars that allows an else to be matched with either of two if statements
C. An else clause that lacks a body |
D. An else used outside an if statement
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
Correct answer: B — Ambiguous attachment of else to one of two nested ifs.
COMP10 describes an else that can attach to either nested if and resolves it with nearest-unmatched-if policy or a grammar rewrite. That grammatical ambiguity is the dangling-else problem. It does not mean unreachable code, a missing body or an else outside any if, which are different semantic or syntactic situations.
Evidence in the complete study note
The dangling-else grammar permits else to attach to either nested if; a nearest-unmatched-if rule or grammar rewrite resolves it. Taking a leftmost derivation by itself does not resolve ambiguous interpretation.COMP10
Choice by choice
A · incorrect — Unreachability concerns control-flow feasibility, not the competing grammatical attachment of else.
B · correct — The ambiguity is whether else belongs to the inner or outer unmatched if.
C · incorrect — A missing else body is a syntax defect rather than the classic attachment ambiguity.
D · incorrect — An else outside any if is not the two-attachment situation defining dangling else.
Question 166
Which representation explicitly uses basic blocks as vertices and possible transfers as edges, making it the direct structural basis for dominator and natural-loop analysis?
A. Abstract Syntax Tree (AST) |
B. Three-Address Code (TAC)
C. Static Single Assignment (SSA) form |
D. Control Flow Graph (CFG)
Hint / Module Reference (Where to Read)
Identify what the representation stores, what it omits and which later transformations it must support; separate a representation property from an algorithmic task.
A control-flow graph explicitly records basic blocks and their possible successor transfers. Dominator relationships describe which blocks occur on every path to another block; back edges to dominating headers identify natural loops. TAC can populate the blocks, and SSA can coexist with this graph, but neither alone names the requested vertex/edge structure. An AST emphasizes source syntax rather than this control-flow representation.
Evidence in the complete study note
A basic block is a maximal straight-line instruction sequence entered at its beginning and exited at its end. Leaders are the first instruction, every jump target, and each instruction after a branch. Start a block at each leader and continue until the next leader.COMP28
A control-flow graph has blocks as vertices and possible next-block transfers as edges, including fall-through. A node D dominates N when every entry-to-N path passes through D. For an edge N→H where H dominates N, H is a loop header of a natural loop. This structure supports loop analysis. An expression DAG records value dependencies, not arbitrary control flow.COMP28
Choice by choice
A · incorrect — An AST represents source hierarchy rather than the specified block-transfer graph.
B · incorrect — TAC gives instructions, not by itself the requested graph.
C · incorrect — SSA is a definition-naming discipline that can coexist with a CFG.
D · correct — A CFG explicitly provides the specified blocks, edges and path structure.
Question 167
In Static Single Assignment (SSA) form, what is the purpose of a 'φ (phi) function'?
A. To represent a conditional branch in the control flow graph |
B. To select the correct version of a variable at join points where multiple control flow paths merge
C. To mark the entry point of a function |
D. To represent a loop-back edge in the CFG
Hint / Module Reference (Where to Read)
Identify what the representation stores, what it omits and which later transformations it must support; separate a representation property from an algorithmic task.
Correct answer: B — Select the incoming variable version corresponding to the predecessor taken.
COMP27 defines phi at a join as choosing an incoming value according to the actual predecessor path. It is not a conditional branch instruction, a function-entry marker or a back edge, and does not average its operands. The function reconciles distinct definition names when different paths reach the same use.
Evidence in the complete study note
A conditional expression can generate if a<b goto Ltrue; goto Lfalse; labels join control paths. Short-circuit AND evaluates the right operand only after a true left operand; OR only after a false one. Translating both eagerly can change side effects. For a zero-based array with element width w and lower bound L, element i uses base+(i−L)*w, assuming fixed-width contiguous storage.COMP27
SSA gives each definition a distinct name. At a join, x3=φ(x1 from B1,x2 from B2) chooses the incoming value according to the predecessor actually taken; it is not an arithmetic average. SSA is a naming discipline over IR and commonly coexists with a control-flow graph.COMP27
Choice by choice
A · incorrect — A phi function selects an incoming value; it does not transfer control between blocks.
B · correct — It merges definition versions by selecting the value associated with the predecessor actually taken.
C · incorrect — Function entry is a control-flow location, not the value-selection purpose of phi.
D · incorrect — A back edge represents loop control transfer rather than a merge of SSA values.
Question 168
The FOLLOW set of the start symbol S always contains:
A. ε (epsilon) |
B. The end-of-input marker $
C. The first terminal of every production |
D. Nothing; FOLLOW(S) is always empty
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
COMP13 explicitly places $ in FOLLOW(S), representing that a completed start-symbol derivation can be followed by end of input. FOLLOW never contains epsilon. Possible initial terminals belong to FIRST, not automatically FOLLOW. Therefore the marker is guaranteed even when other following terminals depend on the grammar.
Evidence in the complete study note
FIRST(α) contains terminals that can begin strings derived from α, plus ε when α can vanish. For a sequence, add FIRST of each symbol except ε, continue while symbols are nullable, and add ε only if every symbol is nullable.COMP13
FOLLOW(A) contains possible next terminals after A, plus end marker $ where appropriate; never ε. Put $ in FOLLOW(S). For B→αAβ, add FIRST(β)−{ε} to FOLLOW(A); if β is nullable, add FOLLOW(B). Repeat all rules until no sets grow.COMP13
Choice by choice
A · incorrect — FOLLOW contains terminals and possibly the end marker, never epsilon.
B · correct — The end-of-input marker is placed in FOLLOW of the start symbol by initialization.
C · incorrect — Initial terminals are FIRST information and are not automatically following terminals.
D · incorrect — FOLLOW(S) is not empty because it contains the end marker.
Question 169
For an unsigned fixed-width integer x with width greater than three and modular arithmetic, which optimization replaces x = x * 8 with x = x << 3?
A. Constant folding |
B. Dead code elimination
C. Strength reduction |
D. Loop unrolling
Hint / Module Reference (Where to Read)
Trace whether computation is evaluated, moved, shared or removed. Preserve observable effects and use the stated arithmetic and target assumptions.
The transformation replaces multiplication by a power of two with an equivalent shift under the stated unsigned model. This is strength reduction when the target makes that replacement cheaper. It does not evaluate a constant-only expression because x remains variable, does not remove an unused statement, and does not replicate loop iterations. The explicit arithmetic model matters because signed-language overflow or shift rules can make a superficially similar rewrite invalid.
Evidence in the complete study note
Algebraic simplification removes identities when valid: integer x+0→x. Strength reduction replaces an operation with an equivalent cheaper form, such as unsigned x*8→x<<3 for a valid width and shift count. Target costs determine whether it is actually cheaper.COMP31
Signed C/C++ overflow and shift rules differ from unsigned modular arithmetic; a mathematical identity is not automatically a legal transformation.COMP33
Unrolling replicates a body to reduce branch overhead and expose parallelism; handle remaining iterations and increased code size.COMP32
Choice by choice
A · incorrect — The operand x remains variable, so this is not evaluation of an all-constant expression.
B · incorrect — The assignment remains and still computes a needed result.
C · correct — Replacing an operation by an equivalent cheaper form is strength reduction.
D · incorrect — No loop body is replicated.
Question 170
In a compiler's code generator, 'calling convention' refers to:
A. The order in which source files are compiled |
B. The agreed-upon protocol for how functions pass arguments, return values, and manage the stack
C. The naming convention for generated labels |
D. The format of debug information in the object file
Hint / Module Reference (Where to Read)
Match stored information to its lifetime, access path and calling-convention role; distinguish compile-time organization from run-time storage.
Correct answer: B — The protocol for arguments, results, registers and stack management.
COMP37 defines the locations of arguments/results, saved-register responsibilities, stack alignment and frame duties as the calling convention. These permit caller and callee to agree on the runtime call interface. Source-file build order, label spelling and debug format concern other compiler/toolchain conventions rather than this execution protocol.
Evidence in the complete study note
Static storage lasts throughout execution; stack frames support nested calls and recursion; heap storage supports lifetimes beyond a call. A frame may contain parameters, return address, saved registers, locals and temporaries. Sizes, alignment and offsets are target-dependent; a two-byte int is an example, not a C++ guarantee.COMP37
A calling convention specifies argument and result locations, caller/callee-saved registers, stack alignment and frame responsibilities. Escape analysis asks whether an object/reference can outlive or be accessed outside a region such as its allocating call. Proven nonescaping allocations may use stack storage or be eliminated by scalar replacement, provided identity and lifetime semantics remain correct.COMP37
Choice by choice
A · incorrect — Compilation order concerns build organization rather than the runtime interface between callers and callees.
B · correct — The calling convention specifies argument/result passing and register/stack responsibilities.
C · incorrect — Label naming is separate from the runtime storage and control-transfer call protocol.
D · incorrect — Debug information format is not the protocol used to invoke and return from functions.
Question 171
What does 'peephole optimization' involve?
A. Optimizing entire functions at once |
B. Examining and replacing small sequences of generated instructions with more efficient equivalents
C. Inlining small functions at call sites |
D. Eliminating unreachable basic blocks
Hint / Module Reference (Where to Read)
Trace whether computation is evaluated, moved, shared or removed. Preserve observable effects and use the stated arithmetic and target assumptions.
Correct answer: B — Examine short instruction sequences and replace them with better equivalents.
COMP31 defines peephole optimization by short instruction windows and lists redundant-load removal, machine idioms and jump-chain shortening. B states that method directly. Whole-function optimization has a broader scope; inlining changes calls to bodies, and unreachable-block removal is a particular control-flow simplification rather than the definition of examining small windows.
Evidence in the complete study note
Peephole optimization examines short instruction windows. It can remove redundant loads/stores, replace machine idioms and shorten jump chains: jump L1 where L1 immediately jumps L2 can become jump L2.COMP31
Choice by choice
A · incorrect — Whole-function scope is broader than the short instruction windows defining peephole optimization.
B · correct — The optimizer inspects short instruction sequences and substitutes equivalent more efficient forms.
C · incorrect — Inlining expands calls into bodies rather than defining the local instruction-window method.
D · incorrect — Unreachable-block removal is one control-flow optimization, not the defining peephole inspection mechanism.
Question 172
Which statement correctly compares LALR(1) with SLR(1) and canonical LR(1), allowing the case where no equal-core canonical states need merging?
A. LALR(1) is weaker than SLR(1) |
B. LALR(1) has no more states than canonical LR(1) and can resolve some conflicts SLR(1) cannot.
C. LALR(1) and SLR(1) produce identical parsing tables for all grammars |
D. LALR(1) requires more lookahead than SLR(1)
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
Correct answer: B — LALR(1) has no more states than canonical LR(1) and can resolve some conflicts SLR(1) cannot.
LALR combines lookaheads of canonical LR(1) states with equal LR(0) cores. This gives no more states than the canonical machine, with a reduction when distinct equal-core states merge. LALR can handle some grammars beyond SLR because its lookaheads are more precise. Both use one lookahead token, and their tables are not identical for every grammar.
Evidence in the complete study note
SLR(1) uses LR(0) states and FOLLOW(A) for reduction by a completed A production. Canonical LR(1) attaches context-specific lookahead to items. LALR(1) merges canonical states with the same LR(0) core, combining lookaheads; merging can introduce reduce/reduce conflicts. The standard grammar-class hierarchy is LR(0)⊆SLR(1)⊆LALR(1)⊆LR(1), with increasing capability and often table size.COMP17
A shift/reduce conflict offers both consuming a token and reducing; reduce/reduce offers two reductions. An SLR or LALR conflict does not by itself prove the grammar ambiguous. Canonical LR(1) handles LR(1) grammars, not every unambiguous CFG. Precedence and associativity can resolve suitable expression conflicts; changing parser names alone does not repair all ambiguity.COMP17
Choice by choice
A · incorrect — The hierarchy places SLR within LALR rather than the reverse.
B · correct — This states both the correct state-count bound and the greater parsing capability.
C · incorrect — The methods can use different reduction lookaheads and tables.
D · incorrect — Both use one lookahead token.
Question 173
In data flow analysis, 'live variable analysis' is a:
A. Forward may-analysis |
B. Backward may-analysis
C. Forward must-analysis |
D. Backward must-analysis
Hint / Module Reference (Where to Read)
Track which facts can hold along one path and which must hold along every path. Apply the specified direction, transfer rule and join operation.
COMP29 explicitly calls liveness backward may-analysis. A value is live if some future path reads it before redefinition, so information flows backward from successor uses and combines possible uses rather than requiring every path. This distinguishes both the direction and may-versus-must dimensions requested by the options.
Evidence in the complete study note
Liveness is backward may-analysis: a value might be read before redefinition on some future path. OUT[B]=union of IN over successors; IN[B]=USE[B]∪(OUT[B]−DEF[B]). Iterate to a fixed point. Liveness supports register allocation and dead-value removal. Definite-assignment analysis asks whether initialization occurs on every path before use; reaching definitions alone does not prove this.COMP29
Choice by choice
A · incorrect — May is appropriate, but liveness propagates from future uses backward rather than forward.
B · correct — Liveness asks whether some future path uses a value before redefinition, a backward may property.
C · incorrect — Both direction and must quantification differ from the liveness definition.
D · incorrect — Backward direction fits, but liveness requires a possible use, not use on every path.
Question 174
The 'closure' operation in NFA-to-DFA subset construction computes:
A. The set of all NFA states reachable from a given set of states using only ε-transitions |
B. The set of all NFA states reachable using any number of any transitions
C. The minimal DFA equivalent to the NFA |
D. The FIRST set of a non-terminal
Hint / Module Reference (Where to Read)
Follow the representation at each construction step and apply the pattern or state-set rules consistently, including empty cases.
Correct answer: A — States reachable by zero or more ε transitions.
COMP06 defines epsilon closure as all states reachable without consuming input through zero or more epsilon edges. Zero moves includes the starting set itself. Arbitrary labeled transitions would consume symbols and belong to a different reachability relation; minimization and FIRST-set computation are separate algorithms. A therefore matches the closure used in subset construction.
Evidence in the complete study note
A common generator pipeline is regular expressions → NFA using Thompson construction → DFA using subset construction; minimization is optional. For concatenation rs, connect r’s final state to s’s start by ε. Alternation introduces branching ε paths; star adds a way to skip and repeat the fragment.COMP06
The ε-closure of states includes those reachable by zero or more ε edges. A DFA state is a set of NFA states; its a-transition is ε-closure(move(set,a)). Start with the NFA start closure, repeatedly add unseen subsets, and mark subsets containing an NFA final state as accepting. Token identity and rule priority annotate accepting states; the empty subset acts as a dead state.COMP06
Choice by choice
A · correct — Epsilon closure includes the starting set and every state reachable using only epsilon edges.
B · incorrect — Arbitrary symbol transitions consume input and are not part of epsilon closure.
C · incorrect — Closure supplies subsets during determinization; it does not itself minimize the resulting DFA.
D · incorrect — FIRST is a grammar lookahead set, not epsilon reachability among NFA states.
Question 175
For a real-machine backend, which listed optimization chiefly depends on the target’s instruction latencies and execution resources?
A. Constant folding |
B. Dead code elimination
C. Instruction scheduling |
D. Loop-invariant code motion
Hint / Module Reference (Where to Read)
Trace whether computation is evaluated, moved, shared or removed. Preserve observable effects and use the stated arithmetic and target assumptions.
Instruction scheduling chooses a legal instruction order while considering target resources and latencies. It is therefore the target-dependent backend choice in this comparison. Constant folding computes known expressions, dead-code elimination removes unnecessary computation while preserving effects, and loop-invariant motion relocates safe unchanged expressions. Their validity depends on program semantics, but these three need not be organized around a particular processor’s scheduling resources.
Evidence in the complete study note
Instruction scheduling orders selected target instructions while preserving dependencies. A target-aware scheduler also considers instruction latencies and the processor resources needed by each operation. This is a backend optimization whose performance choices depend on the target machine, even when a reusable scheduling framework serves many targets.COMP-S04
By contrast, constant folding, dead-code elimination and safe loop-invariant motion can be expressed on a target-neutral IR using values, control flow and side-effect rules. Target costs can still influence whether a legal transformation is worthwhile. Machine independence therefore describes the abstraction of a pass, not freedom from all language semantics or implementation costs.COMP-S04
Choice by choice
A · incorrect — Folding evaluates known expressions from program semantics rather than scheduling machine resources.
B · incorrect — Dead-code elimination uses reachability, use and side-effect information.
C · correct — Instruction scheduling considers target execution resources and instruction latencies.
D · incorrect — Invariant motion uses loop values, paths and safety conditions rather than target issue scheduling.
Question 176
In a context-free grammar, a 'sentential form' is:
A. A string consisting only of terminal symbols |
B. Any string of terminals and non-terminals derivable from the start symbol
C. A string that cannot be further reduced |
D. The right-hand side of a production rule
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
Correct answer: B — Any terminal/nonterminal string derivable from the start symbol.
COMP09 defines a sentential form as any string of terminals and nonterminals derivable from S. Terminal-only sentences are a special case, not the full definition. A production right side need not itself be reachable from S, and irreducibility does not define derivability. B captures the required reachability and permits both kinds of symbols.
Evidence in the complete study note
A context-free grammar G=(N,T,P,S) has nonterminals N, terminals T, productions P and start S. A production A→α rewrites one nonterminal. A sentential form is any string of terminals/nonterminals derivable from S; a sentence contains only terminals. A leftmost derivation rewrites the leftmost remaining nonterminal; a rightmost one rewrites the rightmost.COMP09
A parse tree shows grammar productions: root S, internal nonterminals, and terminal leaves, with ε sometimes shown for empty productions. Its left-to-right yield is the input. An AST omits grammar scaffolding and punctuation; expression operands are leaves and operators internal nodes. The parser can build either representation, depending on implementation.COMP09
Choice by choice
A · incorrect — Terminal-only strings are sentences, a subset of sentential forms rather than their full definition.
B · correct — Derivability from the start symbol with terminals and possibly nonterminals is the defining property.
C · incorrect — A sentential form can still contain expandable nonterminals; inability to reduce is not required.
D · incorrect — A right-hand side is not necessarily reachable from the grammar’s start symbol.
Question 177
What is 'function inlining' and what is its primary risk?
A. Replacing a function call with the function body; risk is incorrect semantics |
B. Replacing a function call with the function body; risk is increased code size (code bloat)
C. Moving a function to a different module; risk is linker errors |
D. Specializing a function for specific argument values; risk is type errors
Hint / Module Reference (Where to Read)
Match stored information to its lifetime, access path and calling-convention role; distinguish compile-time organization from run-time storage.
Correct answer: B — Replace a call with its body; excessive code size is a risk.
COMP38 defines inlining as substituting a suitably renamed body while preserving argument evaluation, returns and side effects. It can remove call overhead but increase code size and instruction-cache pressure. Correct inlining preserves semantics; corruption is an implementation bug rather than its defining trade-off. Moving modules or specializing arguments describes different transformations.
Evidence in the complete study note
Inlining replaces a call with a suitably renamed copy of its body, preserving argument evaluation, returns and side effects. It can remove call overhead and expose optimization opportunities, but may increase code size and instruction-cache pressure. A recursive function cannot simply be expanded without limit.COMP38
Virtual dispatch chooses an overridden method based on a receiver’s runtime class. A common implementation uses a per-class virtual-method table and an object pointer to the table; the call loads the selected entry. This is an implementation strategy, not a universal language requirement. Name mangling distinguishes linker symbols, often for overloads; it is not itself runtime method selection. Proven receiver types may permit devirtualization.COMP38
Choice by choice
A · incorrect — Inlining must preserve semantics; incorrect behavior is a bug rather than the normal primary trade-off stated here.
B · correct — Body substitution can reduce call overhead while increasing generated code size.
C · incorrect — Moving a function between modules is not call-site body substitution.
D · incorrect — Argument specialization is a different optimization and does not define general function inlining.
Question 178
Which of the following best describes the 'handle' in bottom-up parsing?
A. The leftmost terminal in the input string |
B. A substring of the current sentential form that matches the right-hand side of a production and whose reduction leads to a valid parse
C. The top element of the parsing stack |
D. The lookahead token used for parsing decisions
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
Correct answer: B — The RHS occurrence whose next reverse-rightmost reduction leads toward the valid parse.
COMP15 defines a handle as a production RHS occurrence whose reduction is the next reverse-rightmost derivation step. B is the closest complete description: its valid-parse condition must mean that next legitimate step, not merely any matching substring. Neither a single stack item nor the lookahead alone specifies that contextual production occurrence.
Evidence in the complete study note
Bottom-up parsing starts from input and reduces toward S, constructing a rightmost derivation in reverse. A handle is a production RHS occurrence whose reduction is the next step of that reverse derivation. Not every substring matching a RHS is a handle in the current context.COMP15
Shift pushes the next input token and a state; reduce replaces a recognized RHS by its LHS and consults GOTO; accept recognizes completion; error reports an invalid situation. For A→XYZ, pop three grammar symbols and their states, expose state q, then push A and GOTO[q,A]. “Go” is not a separate standard shift-reduce ACTION, although GOTO is essential table machinery.COMP15
Choice by choice
A · incorrect — The leftmost terminal need not be the handle and does not identify a production RHS occurrence.
B · correct — Read valid reduction as the next reverse-rightmost step; contextual validity distinguishes a handle from arbitrary matches.
C · incorrect — A handle can span multiple symbols and is not simply the top stack element.
D · incorrect — Lookahead guides action selection but is not the substring being reduced.
Question 179
In the context of code generation, what is a 'basic block'?
A. A block of memory allocated on the heap |
B. A maximal straight-line sequence of instructions with one entry point and one exit point
C. A function or procedure in the source code |
D. A group of related variable declarations
Hint / Module Reference (Where to Read)
Identify what the representation stores, what it omits and which later transformations it must support; separate a representation property from an algorithmic task.
Correct answer: B — A maximal straight-line sequence with entry at the beginning and exit at the end.
COMP28 directly defines this sequence as a basic block. Maximality means it is not arbitrarily shortened while retaining the same entry/exit structure. Heap allocation, whole functions and related declarations describe different entities; a function may contain many basic blocks separated by branch targets and control transfers.
Evidence in the complete study note
A basic block is a maximal straight-line instruction sequence entered at its beginning and exited at its end. Leaders are the first instruction, every jump target, and each instruction after a branch. Start a block at each leader and continue until the next leader.COMP28
A control-flow graph has blocks as vertices and possible next-block transfers as edges, including fall-through. A node D dominates N when every entry-to-N path passes through D. For an edge N→H where H dominates N, H is a loop header of a natural loop. This structure supports loop analysis. An expression DAG records value dependencies, not arbitrary control flow.COMP28
Choice by choice
A · incorrect — A heap memory region is storage, not a straight-line control-flow unit.
B · correct — This matches the maximal straight-line single-entry, end-exit definition in COMP28.
C · incorrect — A function may contain branches and multiple basic blocks rather than one straight-line block.
D · incorrect — Related declarations are not the instruction sequence defined by control-flow boundaries.
Question 180
What is 'alias analysis' and why is it important for optimization?
A. Determining which variables have the same name in different scopes; important for scope resolution |
B. Determining whether two pointer expressions can refer to the same memory location; important because aliasing restricts reordering and CSE
C. Detecting variables with the same type; important for type coercion |
D. Finding duplicate function names; important for linking
Hint / Module Reference (Where to Read)
Trace whether computation is evaluated, moved, shared or removed. Preserve observable effects and use the stated arithmetic and target assumptions.
Correct answer: B — Determine whether references may denote the same memory, constraining transformations.
COMP33 asks whether references can designate the same memory. A write through p can invalidate a value loaded through q unless nonaliasing or another proof permits reuse. Therefore alias facts constrain CSE and reordering. Identical spellings, types or function names concern scope, typing or linkage rather than memory-location overlap.
Evidence in the complete study note
Optimization preserves defined observable behavior, including required side effects and exceptions. Alias analysis asks whether references can denote the same memory. After *p=5, a previous load through q cannot be reused unless p and q are known not to alias or an equivalent proof applies. Function calls can also invalidate memory facts.COMP33
Do not move a potentially trapping division outside a loop that might execute zero times. Floating-point reassociation can change rounding and NaN behavior. Signed C/C++ overflow and shift rules differ from unsigned modular arithmetic; a mathematical identity is not automatically a legal transformation. Dependence analysis must show that fusion or scheduling preserves the required order of memory accesses.COMP33
Choice by choice
A · incorrect — Equal spelling in different scopes concerns declaration identity rather than whether references share memory.
B · correct — Potential shared locations determine whether writes can invalidate reused loads or reordered memory operations.
C · incorrect — Equal types do not prove shared addresses and are not the alias-analysis question.
D · incorrect — Duplicate linker names concern symbol resolution rather than potential overlap of referenced memory.
Question 181
Which statement about recursive-descent parsers is TRUE?
A. They cannot handle left-recursive grammars without modification |
B. They inherently support all context-free grammars
C. They require a parsing table to function |
D. They build the parse tree bottom-up
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
Correct answer: A — Ordinary recursive descent needs modification to handle left recursion.
COMP12 explains that ordinary unmodified recursive descent can recurse forever on left recursion before consuming a token. Removing left recursion or changing the algorithm is therefore necessary for that direct implementation. Recursive descent is top-down and normally procedural, so it does not inherently require an explicit table or support every CFG unchanged.
Evidence in the complete study note
Immediate left recursion has A→Aα. For A→Aα|β, where β does not start with A, introduce a new nonterminal A′ and use:
A→βA′
A′→αA′|ε
This preserves the generated language; tree shape changes, so semantic actions must preserve intended associativity. Indirect left recursion follows a cycle through other nonterminals and also needs removal for ordinary predictive descent.COMP12
Left factoring rewrites A→αβ|αγ using:
A→αA′
A′→β|γ
It postpones a choice until after the common prefix. It does not by itself remove ambiguity or guarantee LL(1). LR parsers can handle suitable left-recursive grammars; ordinary unmodified recursive descent can recurse forever before consuming input.COMP12
Choice by choice
A · correct — Without transformation or algorithmic modification, left recursion can cause infinite recursive calls before input consumption.
B · incorrect — Ordinary recursive descent is not an unrestricted parser for every context-free grammar.
C · incorrect — Procedures can encode production choices directly; an explicit parsing table is not required.
D · incorrect — Recursive descent expands productions top-down rather than constructing a reverse-rightmost bottom-up parse.
Question 182
In attribute grammar terminology, which of the following is an 'inherited' attribute?
A. The value of an expression node computed from its children |
B. The type environment passed from a function declaration down to its body
C. The size of an array determined from its element type and length |
D. The result type of an arithmetic operation
Hint / Module Reference (Where to Read)
Track where each computed value comes from and when each production action runs. Distinguish the representation from its attached information.
Correct answer: B — A type environment passed from a declaration into its body is inherited.
COMP24 explicitly gives the declaration’s type environment passed into its body as an inherited attribute. This carries context inward rather than computing a parent from child values. Expression values, array sizes computed from components and arithmetic result types are ordinarily synthesized examples when obtained from the node’s own child information.
Evidence in the complete study note
A syntax-directed definition is a CFG with attributes on grammar symbols and semantic rules on productions. An annotated parse tree displays computed attribute values; it is not itself an inherited or synthesized attribute. Synthesized attributes flow from children to a parent; inherited attributes carry context from parent or siblings.COMP24
For E→E1+T, E.val=E1.val+T.val synthesizes an expression value. A declaration’s type environment passed into its body is inherited. S-attributed definitions use only synthesized attributes and fit LR reduction-time evaluation naturally; suitable LL parsers can also compute them. L-attributed definitions restrict dependencies so a left-to-right traversal can evaluate inherited context. Attribute dependency cycles can prevent evaluation.COMP24
Choice by choice
A · incorrect — Computing an expression from its children is synthesized upward flow.
B · correct — The surrounding declaration supplies type context to the nested body, matching the explicit inherited example.
C · incorrect — Computing size from element information and length is a synthesized result, not supplied surrounding context.
D · incorrect — An operation’s result type derived from operands is normally synthesized from its child information.
Question 183
A compiler emits the error 'variable used before initialization'. This is detected during:
A. Lexical analysis |
B. Syntax analysis
C. Semantic analysis / data flow analysis |
D. Code generation
Hint / Module Reference (Where to Read)
Track which facts can hold along one path and which must hold along every path. Apply the specified direction, transfer rule and join operation.
COMP29 distinguishes definite assignment, which asks whether initialization occurs on every incoming path, from reaching definitions alone. Such control/data-flow facts go beyond recognizing legal tokens or grammar. The error therefore belongs to semantic/data-flow analysis before target emission, even though exact acceptance and diagnostic rules depend on the language.
Evidence in the complete study note
Liveness is backward may-analysis: a value might be read before redefinition on some future path. OUT[B]=union of IN over successors; IN[B]=USE[B]∪(OUT[B]−DEF[B]). Iterate to a fixed point. Liveness supports register allocation and dead-value removal. Definite-assignment analysis asks whether initialization occurs on every path before use; reaching definitions alone does not prove this.COMP29
Choice by choice
A · incorrect — Scanning recognizes identifier tokens but does not prove initialization along every control-flow path.
B · incorrect — A grammatically valid variable use can still occur before initialization.
C · correct — Semantic data-flow analysis checks that required initialization precedes each use on every relevant path.
D · incorrect — Target generation ordinarily consumes checked input rather than supplying the primary definite-assignment analysis.
Question 184
In graph-coloring register allocation, what is an 'interference graph'?
A. A graph where nodes represent machine instructions and edges represent data dependencies |
B. A graph where nodes represent variables and edges connect pairs of variables that are simultaneously live
C. A graph where nodes represent registers and edges represent compatibility |
D. A graph representing the control flow of the program
Hint / Module Reference (Where to Read)
Match stored information to its lifetime, access path and calling-convention role; distinguish compile-time organization from run-time storage.
Correct answer: B — A graph connecting values that must coexist in distinct registers.
COMP36 models concurrently needed values as vertices joined by interference edges, with physical registers represented by colors. Thus the variable/live-range graph in B is the intended model. Instruction dependencies and control-flow edges have different meanings; a graph of register compatibility reverses the allocation model’s vertices and does not express live-value interference.
Evidence in the complete study note
A value is live where it can be used before redefinition. In the interference model, values that must coexist in distinct registers are connected by an edge; each register is a color. Nonoverlapping live ranges may share a register. If a valid assignment cannot fit the available registers, spilling places selected values in memory and inserts loads/stores.COMP36
The general graph k-colorability decision problem is NP-complete for fixed k≥3; optimal register assignment/spill minimization is a hard optimization problem in general, so practical allocators use heuristics.COMP36
Choice by choice
A · incorrect — Instruction-dependency edges constrain scheduling rather than describing interference among live values.
B · correct — Variables or live ranges form vertices; an edge requires distinct registers for simultaneously needed values.
C · incorrect — Registers are colors in this model, not the vertices whose live ranges interfere.
D · incorrect — A CFG connects basic blocks by possible transfers, not values by register interference.
Question 185
What is 'dead code' in the context of compiler optimization?
A. Code that causes a runtime error |
B. Code that is syntactically incorrect
C. Code that is unreachable or whose computed results are never used |
D. Code that depends on uninitialized variables
Hint / Module Reference (Where to Read)
Trace whether computation is evaluated, moved, shared or removed. Preserve observable effects and use the stated arithmetic and target assumptions.
Correct answer: C — Unreachable code or unused computations without required effects.
COMP30 permits removing unreachable code and unused computations only when evaluation has no necessary side effects. C states the intended two dead-code categories, with this semantic caveat. Runtime faults, syntax defects and uninitialized uses are different error categories, not definitions of code being safely removable. An unused volatile read or effectful call may still be required.
Evidence in the complete study note
Constant folding evaluates constant expressions during compilation: 3*4→12. Constant propagation substitutes known values: x=3; y=x+2 becomes y=3+2 before folding. Copy propagation substitutes a copied name while its source remains unchanged. Dead-code elimination removes unreachable code or computations whose values are unused and whose evaluation has no necessary side effects.COMP30
Choice by choice
A · incorrect — A runtime fault does not make arbitrary reachable code safely removable as dead code.
B · incorrect — Syntactically invalid code is a compilation error, not the definition of dead computation.
C · correct — Unreachability or unused results identify candidates, provided necessary observable side effects are preserved.
D · incorrect — An uninitialized dependency is an analysis or correctness issue, not automatically dead code.
Question 186
What is the precise relationship between the general term compiler and the term transpiler?
A. A transpiler is a source-to-source compiler; compilers can also target assembly, machine code or bytecode.
B. A compiler is faster than a transpiler
C. A transpiler performs more optimizations than a compiler |
D. There is no meaningful distinction
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
Correct answer: A — A transpiler is a source-to-source compiler; compilers can also target assembly, machine code or bytecode.
A compiler translates a source program to an equivalent target representation, which may be machine code, assembly, bytecode or another source language. A transpiler is the source-to-source subtype of compiler. This gives a meaningful target-based distinction while retaining the shared category. Speed and optimization count depend on implementations and workloads; neither defines the relationship between the two terms.
Evidence in the complete study note
A compiler translates a source program into an equivalent target representation while preserving defined observable behavior. The target may be machine code, assembly, bytecode or another source language. A transpiler is a source-to-source compiler, not a fundamentally separate noncompiler technology. A compiler preserves language semantics, not the programmer’s unstated intention.COMP01
An interpreter executes a program representation; it need not work one source line at a time. Systems can compile to bytecode and then interpret or JIT-compile it. AOT compilation happens before execution; JIT compilation happens during execution and may use runtime profiles. Neither is universally faster; startup cost, optimization and workload matter.COMP01
Choice by choice
A · correct — A transpiler is a compiler whose target is another source language.
B · incorrect — There is no universal speed ordering.
C · incorrect — Optimization count does not define the subtype.
D · incorrect — The source-to-source target is a meaningful distinction.
Question 187
In the context of lexical analysis, 'lexeme' vs 'token' means:
A. Lexeme is the abstract category; token is the actual text |
B. Lexeme is the actual sequence of characters in the source; token is the abstract category with optional attribute value
C. They are synonymous terms |
D. Lexeme refers to keywords only; token refers to all other units
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
Correct answer: B — Lexeme is the source text; token is its category with optional attributes.
COMP04 directly distinguishes the actual character sequence from its token category and optional attribute. For example, total is a lexeme that may produce an ID token associated with a symbol entry. Neither term is restricted to keywords; the same distinction applies to identifiers, numeric literals, operators and other lexical units.
Evidence in the complete study note
A token is a category with optional attribute, such as (ID, symbol-entry) or (INT_LITERAL,42). A lexeme is the actual character sequence, such as total or 42. A pattern specifies which lexemes belong to a token class. The scanner emits an ordered token stream, not an unordered mathematical set.COMP04
Keywords, identifiers, literals, operators and punctuation are token classes. Whitespace and comments are usually skipped while line/column positions are retained. In indentation-sensitive or newline-sensitive languages, layout can carry tokens. Parse-tree construction is a parser task; scanning can intern identifier spellings, but declaration scope and types need later analysis.COMP04
Choice by choice
A · incorrect — This reverses the roles: the lexeme is concrete text and the token identifies its class.
B · correct — The concrete source sequence is the lexeme; category and optional information form the token.
C · incorrect — The note explicitly separates the two abstractions rather than treating them as synonyms.
D · incorrect — Lexemes include identifiers, literals and operators, not just keywords.
Question 188
Under the general interference-graph model with fixed k≥3, which task is an NP-complete decision problem?
A. Converting an NFA to a DFA |
B. Constructing a LL(1) parsing table
C. Deciding whether an arbitrary interference graph can use k registers without spilling, for fixed k≥3
D. Computing FIRST sets for a CFG
Hint / Module Reference (Where to Read)
Match stored information to its lifetime, access path and calling-convention role; distinguish compile-time organization from run-time storage.
Correct answer: C — Deciding whether an arbitrary interference graph can use k registers without spilling, for fixed k≥3
In the general interference model, simultaneously needed values are adjacent and registers are colors. Deciding whether the graph can be colored with k registers without spilling is general graph k-colorability, NP-complete for fixed k≥3. Optimal allocation is instead an optimization task. The other alternatives are construction or fixed-point tasks and do not state this membership-plus-hardness decision problem.
Evidence in the complete study note
A value is live where it can be used before redefinition. In the interference model, values that must coexist in distinct registers are connected by an edge; each register is a color. Nonoverlapping live ranges may share a register. If a valid assignment cannot fit the available registers, spilling places selected values in memory and inserts loads/stores.COMP36
The general graph k-colorability decision problem is NP-complete for fixed k≥3; optimal register assignment/spill minimization is a hard optimization problem in general, so practical allocators use heuristics.COMP36
Choice by choice
A · incorrect — NFA determinization is a construction task, even when its output is exponential.
B · incorrect — LL(1) table construction is not the specified graph-coloring decision task.
C · correct — No-spill allocation is k-colorability under the stipulated general model.
D · incorrect — FIRST-set computation is a fixed-point task rather than this NP-complete decision form.
Question 189
What is the 'reaching definitions' data flow problem used for?
A. Determining which variables are live at each program point |
B. Determining which variable assignments might reach a given program point without being overwritten
C. Determining which expressions are available at each program point |
D. Determining which functions can be called from a given call site
Hint / Module Reference (Where to Read)
Track which facts can hold along one path and which must hold along every path. Apply the specified direction, transfer rule and join operation.
Correct answer: B — Assignments that may reach a point without being overwritten.
COMP29 directly defines reaching definitions as assignments that can arrive at a point without a replacement definition on the path. Its join is union because one possible path suffices. Liveness asks about future uses, available expressions asks about previous computations on every path, and possible call targets is a separate analysis question.
Evidence in the complete study note
Reaching definitions is forward may-analysis: which assignments can reach this point without a replacement definition? OUT=GEN∪(IN−KILL), with IN the union of predecessor OUT sets. Available expressions is usually forward must-analysis: an expression has been computed on every relevant path and its operands have not changed. Join with intersection.COMP29
Choice by choice
A · incorrect — Future reads before redefinition are the liveness question, not reaching definitions.
B · correct — This is the exact assignment-and-no-overwrite property defined for reaching definitions.
C · incorrect — Available expressions concerns prior computations with unchanged operands, not assignment definitions.
D · incorrect — Possible function targets concern call-graph or points-to analysis rather than reaching assignment definitions.
Question 190
In predictive (LL(1)) parsing, when should the parser use an ε-production A → ε?
A. When the lookahead token is in FIRST(A) |
B. When the lookahead token is in FOLLOW(A) and no other production for A begins with that token
C. When the stack is empty |
D. Whenever the next token is not a keyword
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
Correct answer: B — Use ε on an appropriate FOLLOW(A) lookahead with no competing alternative.
COMP14 enters a nullable alternative under the left-hand nonterminal’s FOLLOW symbols and requires no conflicting production in that cell. An epsilon reduction consumes no input. FIRST(A) alone can refer to a nonempty alternative, while stack emptiness and token being a keyword do not define nullable-alternative selection. Thus B supplies the correct lookahead rule.
Evidence in the complete study note
For every A→α, put it in M[A,a] for each terminal a in FIRST(α). If α is nullable, also enter it under every symbol in FOLLOW(A). More than one production in a cell is a conflict. Pairwise SELECT sets must be disjoint; SELECT(α)=FIRST(α)−{ε}, plus FOLLOW(A) when α is nullable. This also detects two nullable alternatives.COMP14
Initialize stack with $S. Match and pop terminals; for a nonterminal consult its row and lookahead, then push the chosen RHS in reverse. An ε production consumes no input. Accept when stack and input reach $. For A→a|ε with b∈FOLLOW(A), choose a on lookahead a and ε on b.COMP14
Choice by choice
A · incorrect — A FIRST terminal may require a nonempty alternative; FIRST(A) alone does not select epsilon.
B · correct — FOLLOW lookahead selects the nullable alternative when its predictive table cell has no competing production.
C · incorrect — An empty stack is not the rule for selecting a production for a pending nonterminal.
D · incorrect — Keyword status has no general relation to a nonterminal’s nullable-production table entries.
Question 191
Which of the following correctly describes a 'dominator' in a control flow graph?
A. A node that is executed before all other nodes unconditionally |
B. Node D dominates node N if every path from the entry node to N must pass through D
C. The node with the most outgoing edges |
D. The unique successor of every conditional branch
Hint / Module Reference (Where to Read)
Identify what the representation stores, what it omits and which later transformations it must support; separate a representation property from an algorithmic task.
Correct answer: B — Every entry-to-N path passes through D.
COMP28 defines domination relative to a particular node N: every path from entry to N must pass D. This is not a claim that D precedes every node in the program, nor is domination measured by out-degree or being a unique successor. The definition concerns unavoidable traversal on paths reaching the specified node.
Evidence in the complete study note
A basic block is a maximal straight-line instruction sequence entered at its beginning and exited at its end. Leaders are the first instruction, every jump target, and each instruction after a branch. Start a block at each leader and continue until the next leader.COMP28
A control-flow graph has blocks as vertices and possible next-block transfers as edges, including fall-through. A node D dominates N when every entry-to-N path passes through D. For an edge N→H where H dominates N, H is a loop header of a natural loop. This structure supports loop analysis. An expression DAG records value dependencies, not arbitrary control flow.COMP28
Choice by choice
A · incorrect — A dominator is defined relative to a node, not necessarily as preceding all program nodes.
B · correct — This exactly states the all-entry-to-N-paths definition in COMP28.
C · incorrect — The number of outgoing edges does not establish unavoidable traversal on paths.
D · incorrect — Branch successor uniqueness is unrelated to the general dominator definition.
Question 192
In SLR(1) parsing, the reduce action for production A → α is triggered when the lookahead is in:
A. FIRST(A) |
B. FOLLOW(A)
C. FIRST(α) |
D. FOLLOW(α)
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
Correct answer: B — FOLLOW(A), once the item for A→α is complete.
COMP17 says SLR uses LR(0) states and FOLLOW(A) for reduction by a completed A production. The completed item establishes that the right side has been recognized; FOLLOW restricts which lookaheads permit reducing it. FIRST information predicts beginnings instead, and FOLLOW of an arbitrary right-hand string is not the table rule used here.
Evidence in the complete study note
SLR(1) uses LR(0) states and FOLLOW(A) for reduction by a completed A production. Canonical LR(1) attaches context-specific lookahead to items. LALR(1) merges canonical states with the same LR(0) core, combining lookaheads; merging can introduce reduce/reduce conflicts. The standard grammar-class hierarchy is LR(0)⊆SLR(1)⊆LALR(1)⊆LR(1), with increasing capability and often table size.COMP17
A shift/reduce conflict offers both consuming a token and reducing; reduce/reduce offers two reductions. An SLR or LALR conflict does not by itself prove the grammar ambiguous. Canonical LR(1) handles LR(1) grammars, not every unambiguous CFG. Precedence and associativity can resolve suitable expression conflicts; changing parser names alone does not repair all ambiguity.COMP17
Choice by choice
A · incorrect — FIRST(A) concerns beginnings of derived strings rather than lookaheads after a completed A.
B · correct — SLR places a completed A-production reduction under the lookaheads in FOLLOW(A).
C · incorrect — FIRST of the right side predicts starting tokens, not permitted post-recognition reduction lookaheads.
D · incorrect — SLR uses FOLLOW of the left-hand nonterminal A, not this right-side expression.
Question 193
What is 'escape analysis' and how does it help optimization?
A. Analysis to detect out-of-bounds array accesses; helps prevent security vulnerabilities |
B. Analysis to determine whether an object's reference can 'escape' the function where it is created; enables stack allocation of non-escaping objects
C. Analysis to find unreachable exception handlers; enables dead code elimination |
D. Analysis to track pointer arithmetic; enables bounds checking elimination
Hint / Module Reference (Where to Read)
Match stored information to its lifetime, access path and calling-convention role; distinguish compile-time organization from run-time storage.
Correct answer: B — Determine whether references outlive or escape a region, enabling safe allocation changes.
COMP37 asks whether an object/reference can outlive or be accessed outside its allocating region. A proven nonescaping object may use stack storage or be eliminated when lifetime and identity are preserved. Bounds checking, exception reachability and pointer arithmetic are separate analyses and do not define the reference-escape property described.
Evidence in the complete study note
Static storage lasts throughout execution; stack frames support nested calls and recursion; heap storage supports lifetimes beyond a call. A frame may contain parameters, return address, saved registers, locals and temporaries. Sizes, alignment and offsets are target-dependent; a two-byte int is an example, not a C++ guarantee.COMP37
A calling convention specifies argument and result locations, caller/callee-saved registers, stack alignment and frame responsibilities. Escape analysis asks whether an object/reference can outlive or be accessed outside a region such as its allocating call. Proven nonescaping allocations may use stack storage or be eliminated by scalar replacement, provided identity and lifetime semantics remain correct.COMP37
Choice by choice
A · incorrect — Array bounds concern index validity rather than whether references leave their allocation region.
B · correct — Reference escape information can justify stack allocation when lifetime and identity remain correct.
C · incorrect — Unreachable exception handlers concern control-flow reachability, not reference lifetime or external access.
D · incorrect — Pointer arithmetic tracking does not by itself define escape beyond a function or allocation region.
Question 194
Which of the following is a valid reason why LALR(1) parsers may have reduce/reduce conflicts that canonical LR(1) parsers do not?
A. LALR(1) uses a larger parsing table than canonical LR(1) |
B. LALR(1) merges LR(1) states with the same core but different lookaheads, potentially merging incompatible lookahead sets
C. LALR(1) does not support left-recursive grammars |
D. LALR(1) computes FOLLOW sets incorrectly
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
Correct answer: B — Merging equal-core LR(1) states can combine incompatible reduction lookaheads.
COMP17 directly explains that LALR merges canonical states with identical LR(0) cores while unioning their lookahead sets. Distinctions that prevented competing reductions in separate states can disappear, creating reduce/reduce conflicts. This is not due to incorrect FOLLOW computation or rejection of left recursion; the loss comes from deliberate state merging.
Evidence in the complete study note
SLR(1) uses LR(0) states and FOLLOW(A) for reduction by a completed A production. Canonical LR(1) attaches context-specific lookahead to items. LALR(1) merges canonical states with the same LR(0) core, combining lookaheads; merging can introduce reduce/reduce conflicts. The standard grammar-class hierarchy is LR(0)⊆SLR(1)⊆LALR(1)⊆LR(1), with increasing capability and often table size.COMP17
A shift/reduce conflict offers both consuming a token and reducing; reduce/reduce offers two reductions. An SLR or LALR conflict does not by itself prove the grammar ambiguous. Canonical LR(1) handles LR(1) grammars, not every unambiguous CFG. Precedence and associativity can resolve suitable expression conflicts; changing parser names alone does not repair all ambiguity.COMP17
Choice by choice
A · incorrect — Merging aims to reduce state count, and a larger table is not the reason for new conflicts.
B · correct — Combining lookaheads of equal-core states can make previously separated reductions compete.
C · incorrect — LALR can handle suitable left-recursive grammars, as other LR methods can.
D · incorrect — The conflict can arise from correct merging, without any erroneous FOLLOW-set computation.
Question 195
Which is a common implementation mechanism for runtime virtual dispatch in an object-oriented language, when the receiver’s class cannot be resolved statically?
A. Static binding of function calls at compile time |
B. A virtual method table (vtable) per class, with function pointers resolved at runtime
C. Inline expansion of all polymorphic calls |
D. Name mangling to distinguish overloaded functions
Hint / Module Reference (Where to Read)
Match stored information to its lifetime, access path and calling-convention role; distinguish compile-time organization from run-time storage.
Correct answer: B — A virtual method table (vtable) per class, with function pointers resolved at runtime
A common implementation stores virtual-method entries in a per-class vtable and lets an object refer to the appropriate table. A virtual call selects the entry using the receiver’s runtime class. Static binding alone does not provide that selection for an unknown class. Mandatory inlining is not generally possible, and name mangling distinguishes linker symbols rather than selecting overrides at runtime.
Evidence in the complete study note
Inlining replaces a call with a suitably renamed copy of its body, preserving argument evaluation, returns and side effects. It can remove call overhead and expose optimization opportunities, but may increase code size and instruction-cache pressure. A recursive function cannot simply be expanded without limit.COMP38
Virtual dispatch chooses an overridden method based on a receiver’s runtime class. A common implementation uses a per-class virtual-method table and an object pointer to the table; the call loads the selected entry. This is an implementation strategy, not a universal language requirement. Name mangling distinguishes linker symbols, often for overloads; it is not itself runtime method selection. Proven receiver types may permit devirtualization.COMP38
Choice by choice
A · incorrect — Static binding alone does not choose by an unknown runtime class.
B · correct — A per-class vtable is the common mechanism described in the note.
C · incorrect — Unknown runtime receivers prevent mandatory inlining of all polymorphic calls.
D · incorrect — Name mangling identifies symbols rather than selecting overrides.
Question 196
Which of the following is true about a 'well-formed' grammar for LL(1) parsing?
A. It may contain left recursion |
B. For every non-terminal A with productions A → α1 | α2 | ... | αn, no two alternatives share a common token in their FIRST sets, and if any αi derives ε, then FIRST(αj) and FOLLOW(A) are disjoint for all j ≠ i
C. It must be ambiguous |
D. It must have at least one ε-production
Hint / Module Reference (Where to Read)
Use construction direction, lookahead and grammar restrictions. Distinguish algorithm families, implementations and coverage before comparing them.
Correct answer: B — Disjoint predictive selections, including nullable FIRST/FOLLOW constraints.
COMP14 requires that alternatives for a nonterminal select disjoint lookahead sets. B gives the standard FIRST separation and nullable-alternative FOLLOW restriction; shared epsilon alternatives would also violate pairwise FIRST disjointness. Left recursion and useful ambiguity are not acceptable LL(1) properties, and epsilon productions are optional rather than required.
Evidence in the complete study note
For every A→α, put it in M[A,a] for each terminal a in FIRST(α). If α is nullable, also enter it under every symbol in FOLLOW(A). More than one production in a cell is a conflict. Pairwise SELECT sets must be disjoint; SELECT(α)=FIRST(α)−{ε}, plus FOLLOW(A) when α is nullable. This also detects two nullable alternatives.COMP14
Initialize stack with $S. Match and pop terminals; for a nonterminal consult its row and lookahead, then push the chosen RHS in reverse. An ε production consumes no input. Accept when stack and input reach $. For A→a|ε with b∈FOLLOW(A), choose a on lookahead a and ε on b.COMP14
Choice by choice
A · incorrect — Ordinary LL(1) grammars cannot retain left recursion that recurs without input consumption.
B · correct — Disjoint alternative selections prevent multiple productions from occupying the same predictive table cell.
C · incorrect — A useful ambiguous grammar cannot give a unique deterministic LL(1) parse.
D · incorrect — A grammar may be LL(1) without any epsilon production.
Question 197
The primary difference between a 'compiler' and a 'just-in-time (JIT) compiler' is:
A. A JIT compiler produces faster code than an ahead-of-time compiler always |
B. A JIT compiler compiles code at runtime (during program execution), allowing it to use runtime profiling information for optimization, while an AOT compiler compiles before execution
C. A JIT compiler does not perform any optimization |
D. A JIT compiler only works for interpreted languages
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
Correct answer: B — JIT compiles during execution; AOT compiles before execution.
COMP01 defines AOT before execution and JIT during execution, possibly using runtime profiles. Both are compilation, so the heading compiler versus JIT is better understood as AOT versus JIT. The timing contrast in B is correct, while no universal speed guarantee, absence of optimization or restriction to interpreted languages follows.
Evidence in the complete study note
A compiler translates a source program into an equivalent target representation while preserving defined observable behavior. The target may be machine code, assembly, bytecode or another source language. A transpiler is a source-to-source compiler, not a fundamentally separate noncompiler technology. A compiler preserves language semantics, not the programmer’s unstated intention.COMP01
An interpreter executes a program representation; it need not work one source line at a time. Systems can compile to bytecode and then interpret or JIT-compile it. AOT compilation happens before execution; JIT compilation happens during execution and may use runtime profiles. Neither is universally faster; startup cost, optimization and workload matter.COMP01
Choice by choice
A · incorrect — Neither AOT nor JIT is universally faster; startup and workload affect the comparison.
B · correct — Runtime compilation can use execution profiles, whereas AOT performs compilation before the run.
C · incorrect — JIT may optimize using runtime information rather than performing no optimization.
D · incorrect — JIT is an execution-time compilation strategy, not a technique restricted to a separately defined interpreted-language category.
Question 198
What is the main purpose of syntax-directed translation in a compiler?
A. To interleave semantic analysis with syntax analysis using attributes attached to
grammar symbols
B. To generate optimized machine code directly
C. To tokenize the source code
D. To replace the parser with a finite automaton
Hint / Module Reference (Where to Read)
Track where each computed value comes from and when each production action runs. Distinguish the representation from its attached information.
Correct answer: A — Associate semantic computations with grammatical structure and attributes.
COMP24 attaches attributes and semantic rules to grammar symbols and productions; COMP25 executes translation actions during processing. This permits semantic work to follow parsing structure, as A states. It does not inherently bypass IR to optimized machine code, reduce to tokenization, or replace the parser with a finite automaton.
Evidence in the complete study note
A syntax-directed definition is a CFG with attributes on grammar symbols and semantic rules on productions.COMP24
A syntax-directed translation scheme embeds executable actions in productions; the actions run while translating a source program, not while generating the compiler. Attributes may compute types, values, AST pointers or generated code. The scheme defines an input-to-output translation, not merely an input language.COMP25
Choice by choice
A · correct — Attributes and rules connect grammatical structure to semantic computations during translation.
B · incorrect — Direct optimized machine-code production is not the required or exclusive purpose of syntax-directed translation.
C · incorrect — Tokenization is lexical analysis rather than grammar-directed semantic computation.
D · incorrect — Finite automata recognize ordinary token patterns and do not replace general nested-syntax parsing.
Question 199
Straight directed translation uses:
A. Purely lexical rules
B. Backtracking algorithms
C. Grammar without attributes
D. Grammar with sematic rule
Hint / Module Reference (Where to Read)
Track where each computed value comes from and when each production action runs. Distinguish the representation from its attached information.
Correct answer: D — Grammar with semantic rules, reading the misspelled term as syntax-directed translation.
The stem’s Straight directed translation appears to be a damaged rendering of syntax-directed translation. Under that explicit reading, COMP24 defines a CFG with attributes and semantic rules, and COMP25 embeds translation actions in productions. D expresses that structure despite its spelling error. The other choices omit semantics or prescribe unrelated implementation details.
Evidence in the complete study note
A syntax-directed definition is a CFG with attributes on grammar symbols and semantic rules on productions.COMP24
A syntax-directed translation scheme embeds executable actions in productions; the actions run while translating a source program, not while generating the compiler. Attributes may compute types, values, AST pointers or generated code. The scheme defines an input-to-output translation, not merely an input language.COMP25
Choice by choice
A · incorrect — Pure lexical rules do not supply grammar-directed semantic attributes and computations.
B · incorrect — Backtracking is a parsing implementation choice, not the defining translation structure.
C · incorrect — A grammar without semantic attributes or rules does not describe the syntax-directed definition requested.
D · correct — Reading sematic as semantic, this is the grammar-plus-semantic-rules structure of syntax-directed translation.
Question 200
A compiler has produced checked three-address code for a function. Which description incorrectly places the ensuing target-lowering task within the standard compilation pipeline?
A. Code generation can be considered as the start phase of compilation
B. The target program is the output of the code generator
C. Checked intermediate code is supplied as input to the code generator.
D. It used to produce the target code for three-address statements.
Hint / Module Reference (Where to Read)
Identify each activity’s input and output. Distinguish character recognition, grammatical structure, semantic checks and target implementation.
Correct answer: A — Code generation can be considered as the start phase of compilation
Code generation uses checked intermediate code to produce target instructions after the frontend has analyzed the source. It can lower each three-address operation into a suitable target sequence. Lexical analysis, not code generation, begins the standard pipeline. The input condition here means checked IR suitable for lowering; it is not a claim that all possible program bugs have been proved absent.
Evidence in the complete study note
The conventional sequence is lexical analysis → syntax analysis → semantic analysis → intermediate-code generation → optimization → target-code generation. Scanning turns characters into tokens; parsing builds structure; semantics checks declarations and types; synthesis produces implementation code. A phase is a logical activity; a pass is a traversal that can combine activities.COMP03
Code generation lowers checked IR to a target form.COMP34
Choice by choice
A · correct — Target lowering follows scanning, parsing, semantic checks and IR construction; it does not start compilation.
B · incorrect — The generator’s output is target code.
C · incorrect — Checked IR is the stated input to target lowering.
D · incorrect — Three-address statements can be translated into target instructions.