Given S → AB, A → a | ε, B → b, what is FIRST(S)?
A {ε, b}
B {b}
C {a}
D {a, b}
Answer: D. {a, b}. A may begin with a or vanish, in which case B contributes b.
Because B can derive ε in A → BC, what else can begin A?
A FOLLOW(C)
B FOLLOW(A)
C LAST(B)
D FIRST(C)
Answer: D. FIRST(C). When B is nullable, a string derived from C may begin the right-hand side.
In S → ( A ), which symbol enters FOLLOW(A)?
A $
B )
C A
D (
Answer: B. ). The right parenthesis appears immediately after A in the production.
With S → AB, A → a, B → b | ε, what is FOLLOW(A)?
A {$}
B {b}
C {b, $}
D {a, $}
Answer: C. {b, $}. B may begin with b or vanish; since S is the start symbol, its end marker also follows A.
Rewrite E → E + T | T without immediate left recursion: which form is correct?
A E→TE’; E’→+TE’|ε
B E→T+E’; E’→E
C E→+TE’; E’→E|ε
D E→E’T; E’→T+E’
Answer: A. E→TE’; E’→+TE’|ε. The rewrite starts E with T and moves repeated +T parts into a right-recursive tail.
When A → a | ε and a ∈ FOLLOW(A), what can an LL(1) table show?
A Lexical ambiguity
B Shift/reduce conflict
C No conflict
D FIRST/FOLLOW conflict
Answer: D. FIRST/FOLLOW conflict. The rule A→a and the nullable alternative compete on lookahead a.
State-based shift/reduce decisions belong to which parser family?
A LL
B LR
C Recursive descent
D Lexical scanner
Answer: B. LR. LR parsers use states and actions to decide whether to shift or reduce.
Beyond an LR(0) core, an LR(1) item carries what?
A One lookahead token
B Two grammar starts
C A register class
D A parse tree
Answer: A. One lookahead token. An LR(1) item includes a lookahead terminal in addition to the production and dot position.
For production A→β, SLR permits reduction on which terminals?
A FOLLOW(β)
B FIRST(β)
C All terminals
D FOLLOW(A)
Answer: D. FOLLOW(A). SLR uses the FOLLOW set of the production’s left-hand nonterminal to place reductions.
Compared with canonical LR(1), what quantity does LALR seek to reduce?
A AST nodes
B Token length
C Number of parser states
D Grammar terminals
Answer: C. Number of parser states. LALR combines compatible LR states to keep parsing tables smaller.
One LR table conflict offers what choice between actions?
A Scan or link
B Type or coerce
C Shift or reduce
D Emit or spill
Answer: C. Shift or reduce. The parser cannot choose uniquely between shifting input and reducing a handle.
On a valid lookahead, which action does a completed non-start LR item suggest?
A Enter a new scope
B Emit a machine opcode
C Reduce by its rule
D Shift the next token
Answer: C. Reduce by its rule. A completed item represents a recognized production body that can be reduced when its lookahead permits.
Without braces, the usual convention attaches else to which if?
A Reject every else
B Attach else to outermost if
C Use lexical priority
D Bind else to nearest if
Answer: D. Bind else to nearest if. The usual convention associates else with the closest unmatched if.
Possible transfers between basic blocks are recorded in which graph?
A Control-flow graph
B Interference graph
C Symbol table
D Syntax tree
Answer: A. Control-flow graph. A control-flow graph connects basic blocks along possible execution paths.
Which condition keeps a pure arithmetic expression loop-invariant?
A Its inputs stay unchanged
B Its output is printed
C Its block has one edge
D Its token is a keyword
Answer: A. Its inputs stay unchanged. A pure expression remains invariant when none of its operand values changes in the loop.
Reaching-definitions analysis reports what at a program point?
A Tokens already consumed
B Statements never executed
C Definitions that may arrive
D Registers already allocated
Answer: C. Definitions that may arrive. The analysis finds definitions that can reach a point without being overwritten.
At point p, when is variable x live?
A Present in symbol table
B Used before next redefinition
C Defined only once
D Stored in object file
Answer: B. Used before next redefinition. Liveness means a value may be used later before a new definition replaces it.
At a control-flow join, what does φ choose?
A Value from incoming path
B Nearest symbol name
C Target machine opcode
D Value from next token
Answer: A. Value from incoming path. A φ operation selects the value associated with the predecessor path taken.
Unreachable-code elimination can remove which blocks?
A Blocks with many variables
B Blocks containing operators
C Blocks before the lexer
D Blocks unreachable from entry
Answer: D. Blocks unreachable from entry. A block unreachable from the function entry cannot execute.
Filling unresolved branch targets later is called what?
A Unresolved branch targets
B Symbol attributes
C Register colors
D Token patterns
Answer: A. Unresolved branch targets. Backpatching records incomplete jump destinations and fills them once known.
Loop-invariant code motion moves what before a loop?
A Dead-store elimination
B Constant propagation
C Loop-invariant code motion
D Register spilling
Answer: C. Loop-invariant code motion. Loop-invariant code motion hoists safe computations out of repeated loop execution.
In register allocation, what does spilling do?
A Rewriting grammar rules
B Storing a value in memory
C Splitting source tokens
D Moving loops to entry
Answer: B. Storing a value in memory. A spilled value is assigned a memory location when registers are insufficient or unsuitable.
Temporaries connected by an interference-graph edge are what?
A Shared token class
B Same source variable
C Syntactically adjacent
D Live at the same time
Answer: D. Live at the same time. An edge indicates simultaneous liveness, so those temporaries cannot share one register.
Mapping IR operations to machine instructions is called what?
A Lexical analysis
B Instruction selection
C Error recovery
D Type inference
Answer: B. Instruction selection. Instruction selection chooses target instructions that implement intermediate operations.
Instruction scheduling can reorder independent operations for what reason?
A To resolve identifiers
B To reduce execution stalls
C To remove every branch
D To change program results
Answer: B. To reduce execution stalls. Scheduling can place independent work between dependent instructions to reduce processor stalls.