Revision approach
- Program translation journey
- Characters → tokens → grammatical structure
- Checked meaning → IR → target instructions
- Construction and transformation practice
- Error diagnosis beyond phase names
- Optimization justification
👁 Full explanation
Follow one program from characters to tokens, grammatical structure, checked meaning, intermediate code and target instructions. Practise the constructions and transformations: recognizing a phase name alone is insufficient to diagnose an error or justify an optimization. - Six-item course priority
- Scanner/parser/semantic checker contrasts
- LL versus LR
- Concrete execution traces
👁 Full explanation
Allocate this course its official six-item priority. Compare scanner/parser/semantic checker and LL/LR, then trace concrete examples. - Construction practice checklist
- Token counting
- FIRST/FOLLOW and predictive/LR actions
- Attribute flow
- Three-address code
- Safe optimization
- Language and target assumptions
👁 Full explanation
Practise token counting, FIRST/FOLLOW, predictive and LR actions, attribute flow, three-address code and safe optimization. State language and target assumptions. - Verify source-key claims
- Overlapping choices
- Missing correct results
- Unsupported universal claims
👁 Full explanation
Justify answers using compiler definitions, rules and traces. Check the scope and conditions of each claim using compiler theory.
COMP01
Translation, Interpretation and Compilation Timing
- Compiler translation contract
- Source → equivalent target representation
- Defined observable behavior preserved
- Machine code; assembly; bytecode; source targets
- Transpiler: source-to-source compiler
- Language semantics versus unstated programmer intention
👁 Full explanation
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. - Interpretation, AOT and JIT
- Interpreter: executes program representation
- Line-at-a-time misconception
- Bytecode compilation then interpretation/JIT
- AOT: before execution
- JIT: during execution, runtime profiles
- Speed: startup, optimization, workload
- No universally faster method
👁 Full explanation
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.
4 related practice questions
Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Compiler translation contract
COMP02
Tools, host, target and incremental work
- Translation toolchain
- Preprocessor: inclusion and macros
- Assembler: assembly → object code
- Linker: objects and libraries
- External-symbol resolution and relocation
- Loader: executable mapping and start
- Compilation alone ≠ ready executable
👁 Full explanation
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. - Host, target and compilation organization
- Cross-compiler: host differs from target
- Multiple targets: appropriate backends
- Retargetable: changeable target descriptions
- Incremental: affected fragments and dependent units
- Incremental ≠ changed-line replacement only
- One/multipass: traversal counts, not targets
👁 Full explanation
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.
3 related practice questions
Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Translation toolchain
COMP03
Compiler phases and shared services
[Exam Focus]- Conventional compiler pipeline
- Lexical → syntax → semantic analysis
- IR generation → optimization → target generation
- Scanning: characters → tokens
- Parsing: structure
- Semantics: declarations and types
- Synthesis: implementation code
- Phase: logical activity
- Pass: traversal, possibly combined activities
👁 Full explanation
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. - Compiler organization and services
- Front end: source-language rules
- Middle end: IR analysis/transformation
- Backend: target details
- Shared symbol tables and error reporting
- No mandatory seventh final phase
- Optimization at multiple levels
- Post-instruction-selection optimization possible
- Standard six-phase final: code generation
👁 Full explanation
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.
3 related practice questions
Blueprint: LO3 · Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Conventional compiler pipeline
COMP04
Token, lexeme and pattern
- Token, lexeme and pattern
- Token: category plus optional attribute
- (ID,symbol-entry); (INT_LITERAL,42)
- Lexeme: actual characters total or 42
- Pattern: token-class membership specification
- Scanner output: ordered token stream
- Unordered-set trap
👁 Full explanation
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. - Token classes and scanner boundaries
- Keywords; identifiers; literals; operators; punctuation
- Usually skipped whitespace/comments
- Retained line/column positions
- Indentation/newlines may carry tokens
- Parse trees: parser responsibility
- Scanning may intern identifier spellings
- Scope/types: later analysis
👁 Full explanation
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. - Worked example Five-token declaration
- int x = 42;
- keyword; ID; assignment; integer; semicolon
👁 Full explanation
Scan a statementint x = 42; gives keyword(int), ID(x), assignment(=), integer(42), semicolon(;): five tokens.
21 related practice questions
Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Token, lexeme and pattern
COMP05
Regular expressions for lexical structure
[Exam Focus]- Identifier regular expressions
- Concatenation; alternation r|s
- Kleene r*: zero-or-more
- r+: one-or-more
- Letter(Letter|Digit)*
- Single letter allowed; leading digit forbidden
- C-like ASCII underscore convention
- [A-Za-z_][A-Za-z0-9_]*
- Language-specific identifier rules
👁 Full explanation
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. - Equivalent patterns and nesting limits
- Letter(Letter+|Digit*)* = Letter(Letter|Digit)*
- Repeated letter/digit blocks
- Equivalent-option trap
- Regular patterns: ordinary tokens
- Arbitrary balanced nesting: grammar/stack
👁 Full explanation
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.
3 related practice questions
Blueprint: LO1, LO2 · Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Identifier regular expressions
COMP06
Construct and run a scanner automaton
[Exam Focus]- Scanner-generator automata pipeline
- RE → Thompson NFA → subset DFA
- Optional minimization
- Concatenation: final-to-start ε edge
- Alternation: branching ε paths
- Star: skip and repetition ε paths
👁 Full explanation
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. - Scanner subset construction
- ε-closure: zero-or-more ε reachability
- DFA state: NFA-state set
- Transition: ε-closure(move(set,a))
- Start: NFA start closure
- Repeated unseen-subset discovery
- Accepting subset contains NFA final
- Token identity and rule-priority annotations
- Empty subset: dead state
👁 Full explanation
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.
4 related practice questions
Blueprint: LO2 · Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Scanner-generator automata pipeline
COMP07
Longest match and counting tokens
- Maximal munch and rule priority
- Longest matching lexeme
- Equal-length flex matches: earliest rule
- ifx: identifier, not if+x
- <= and ++: single operators
- Identifier recognition then keyword-table lookup
👁 Full explanation
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. - Loop-header token count
- for (int i = 0; i<=10; i++)
- for,(,int,i,=,0,;
- i,<=,10,;,i,++,)
- Fourteen tokens irrespective of spacing
- Increment: one token
- Comments: no ordinary post-preprocessing parser token
- Choices 4,5,9,10: correct result omitted
👁 Full explanation
For the ordinary C++ header: for (int i = 0; i <= 10; i++) The tokens, split into two display lines, are: for, (, int, i, =, 0, ; i, <=, 10, ;, i, ++, ) There are 14 tokens, irrespective of spacing. The increment operator is one token. A comment contributes no ordinary parser token after preprocessing. For the loop header above, 4,5,9 and 10 are incorrect token counts; the count is 14.
4 related practice questions
Note references: COMP_MOD, COMP_DEEP, COMP_FLEX
- Maximal munch and rule priority
COMP08
Locate the error by evidence
- Compiler-error classification
- Lexical: no legal token formation
- Invalid character; unterminated literal
- Syntax: illegal token arrangement
- Missing delimiter
- Semantic: name, scope, type constraints
- Wrong algorithms may compile
- All-logical-errors detection trap
👁 Full explanation
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. - Malformed fro-line diagnosis
- fro and lowercase o: legal identifiers
- Misspelled keyword ≠ lexical error
- Mismatched syntax: definite
- Undeclared o: possible semantic diagnostic
- Compiler-dependent recovery order and diagnostics
- No silent fro→for or o→0 repair
👁 Full explanation
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. Recovery order and exact diagnostics depend on the compiler. Do not silently replace o by 0 or fro by for.
2 related practice questions
Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Compiler-error classification
COMP09
CFGs, derivations and trees
[Exam Focus]- CFG vocabulary and derivations
- G=(N,T,P,S)
- Nonterminals; terminals; productions; start
- A→α: one nonterminal rewrite
- Sentential form: any S-derived string
- Sentence: terminals only
- Leftmost/rightmost: corresponding remaining nonterminal
👁 Full explanation
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. - Parse tree versus AST
- Parse tree: production structure
- Root S; internal nonterminals
- Terminal leaves; optional ε leaves
- Left-to-right yield: input
- AST: removed scaffolding and punctuation
- Operands: leaves; operators: internal nodes
- Parser may construct either
👁 Full explanation
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.
17 related practice questions
Blueprint: LO1, LO2 · Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- CFG vocabulary and derivations
COMP10
Ambiguity, precedence and associativity
[Exam Focus]- Grammar ambiguity
- One terminal string, two parse trees
- Equivalent: two leftmost derivations
- Same-tree derivation order insufficient
- E→E+E|E*E|id
- id+id*id: alternative grouping
👁 Full explanation
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. - Precedence, associativity and dangling else
- E→E+T|T; T→T*F|F; F→(E)|id
- Multiplication precedence; left association
- a−b−c: (a−b)−c
- Dangling else: alternative nested-if attachments
- Nearest-unmatched-if policy or grammar rewrite
- Leftmost derivation alone ≠ disambiguation
👁 Full explanation
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.
4 related practice questions
Blueprint: LO1, LO2 · Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Grammar ambiguity
COMP11
Top-down parsing
[Exam Focus]- Top-down parsing
- Start S → input expansions
- Usually leftmost derivation
- Recursive descent: procedure per nonterminal
- General descent may backtrack
- Predictive: lookahead choice without backtracking
- LL(1): Left-to-right, Leftmost, one lookahead
👁 Full explanation
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. - Nonrecursive predictive parsing
- Explicit grammar-symbol stack
- Parsing-table consultation
- Same predictive language class
- Recursive/table-driven: linear for suitable fixed grammar
- Names alone do not rank efficiency
👁 Full explanation
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.
8 related practice questions
Blueprint: LO2 · Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Top-down parsing
COMP12
Left Recursion and Prefix Factoring
[Exam Focus]- Left-recursion elimination
- Immediate A→Aα
- A→Aα|β; β not A-leading
- A→βA′; A′→αA′|ε
- Generated language preserved
- Changed tree shape
- Semantic actions preserve intended association
- Indirect cycles through other nonterminals
- Ordinary predictive descent needs removal
👁 Full explanation
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. - Left factoring and parser suitability
- A→αβ|αγ ⇒ A→αA′
- A′→β|γ
- Common-prefix choice postponed
- Factoring ≠ guaranteed unambiguity/LL(1)
- LR handles suitable left recursion
- Unmodified descent: infinite recursion before input
👁 Full explanation
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.
4 related practice questions
Blueprint: LO2 · Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Left-recursion elimination
COMP13
Compute FIRST and FOLLOW
[Exam Focus]- FIRST of a sequence
- Beginning terminals
- ε when sequence vanishes
- Add each FIRST excluding ε
- Continue across nullable symbols
- ε only if all nullable
👁 Full explanation
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. - FOLLOW fixed-point computation
- Next terminals after A
- End marker $, never ε
- $∈FOLLOW(S)
- B→αAβ: FIRST(β)−{ε} into FOLLOW(A)
- Nullable β: FOLLOW(B) into FOLLOW(A)
- Repeat until no growth
👁 Full explanation
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. - Worked example FIRST/FOLLOW worked grammar
- S→AB; A→a|ε; B→b
- FIRST(A)={a,ε}
- FIRST(S)={a,b}
- FOLLOW(A)={b}
- FOLLOW(B)={$}
👁 Full explanation
Small grammarS→AB, A→a|ε, B→b gives FIRST(A)={a,ε}, FIRST(S)={a,b}, FOLLOW(A)={b}, FOLLOW(B)={$}.
1 related practice question
Blueprint: LO2 · Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- FIRST of a sequence
COMP14
Build and use an LL(1) table
[Exam Focus]- LL(1) table construction
- A→α entries under FIRST(α) terminals
- Nullable α: entries under FOLLOW(A)
- Multiple productions per cell: conflict
- SELECT=FIRST(α)−{ε}
- Nullable: add FOLLOW(A)
- Pairwise disjoint SELECT sets
- Two nullable alternatives also conflict
👁 Full explanation
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. - Predictive stack trace
- Initialize $S
- Terminal match and pop
- Nonterminal row plus lookahead
- Push selected RHS reversed
- ε production: no input consumed
- Accept: stack/input both $
- A→a|ε: a-lookahead selects a
- b∈FOLLOW(A): b-lookahead selects ε
👁 Full explanation
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. - Exam trap LL(1) conflict traps
- Useful ambiguous grammars not LL(1)
- Overlapping FIRST
- FIRST/FOLLOW conflicts
- Left recursion
- A-and-B-only key: insufficient exclusion
👁 Full explanation
Ambiguous useful grammars are not LL(1). Check overlapping FIRST sets, FIRST/FOLLOW conflicts and left recursion as well.
3 related practice questions
Blueprint: LO2 · Note references: COMP_MOD, COMP_DEEP, COMP_LL
- LL(1) table construction
COMP15
Bottom-up actions and handles
[Exam Focus]- Bottom-up parsing and handles
- Input reduced toward S
- Reverse rightmost derivation
- Handle: next correct RHS occurrence
- Context determines valid reduction
- Arbitrary matching RHS ≠ handle
👁 Full explanation
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. - Shift-reduce actions and GOTO
- Shift: next token and state
- Reduce: RHS → LHS, then GOTO
- Accept: complete; error: invalid situation
- A→XYZ: pop three symbols/states
- Exposed q → push A,GOTO[q,A]
- Go ≠ separate standard ACTION
- GOTO: essential table machinery
👁 Full explanation
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.
8 related practice questions
Blueprint: LO2 · Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Bottom-up parsing and handles
COMP16
Construct LR(0) item states
[Exam Focus]- LR(0) augmentation and closure
- S′→S
- Item A→α·β: production progress
- Dot before B triggers B→·γ
- Repeat CLOSURE additions
👁 Full explanation
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. - LR(0) canonical collection
- GOTO(I,X): advance dots, take closure
- Initial CLOSURE({S′→·S})
- Nonempty GOTOs for all grammar symbols
- Iterate until no new states
- Canonical collection: item-set collection
- GOTO alone ≠ canonical collection
👁 Full explanation
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. - Worked example LR(0) state example
- S→a
- I0={S′→·S,S→·a}
- GOTO(I0,a)={S→a·}
- GOTO(I0,S)={S′→S·}
- Complete item set: one state
- One-state-per-item trap
👁 Full explanation
One transitionFor S→a, call the initial closure I0: I0 = {S′→·S, S→·a} GOTO(I0,a) = {S→a·} GOTO(I0,S) = {S′→S·} Each complete set above is one state, not one state per item.
1 related practice question
Blueprint: LO2 · Note references: COMP_LR0
- LR(0) augmentation and closure
COMP17
LR families and conflicts
[Exam Focus]- LR parser families
- SLR(1): LR(0) states, FOLLOW reductions
- Canonical LR(1): context-specific item lookaheads
- LALR(1): merge equal LR(0) cores
- Combined lookaheads
- Merging may introduce reduce/reduce conflicts
- LR(0)⊆SLR(1)⊆LALR(1)⊆LR(1)
- Increasing capability, often larger tables
👁 Full explanation
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. - Parser conflicts and limits
- Shift/reduce: consume or reduce
- Reduce/reduce: two reductions
- SLR/LALR conflict ≠ ambiguity proof
- LR(1) handles LR(1) grammars
- Not every unambiguous CFG
- Suitable expression conflicts: precedence/associativity
- Parser renaming ≠ universal ambiguity repair
👁 Full explanation
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.
8 related practice questions
Blueprint: LO2 · Note references: COMP_MOD, COMP_DEEP, COMP_BISON
- LR parser families
COMP18
Parser limits and operator grammars
[Exam Focus]- Nesting and deterministic parser limits
- LL; LR; recursive descent: suitable nesting
- Explicit/implicit stack supports unbounded nesting
- LL and LR: tables possible
- Deterministic LL/LR: unambiguous grammars
- Ambiguous grammar: rewrite or disambiguation
- Generalized method: GLR
👁 Full explanation
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. - Operator grammar conditions
- No adjacent RHS nonterminals
- Usually no ε productions
- Operator precedence: conflict-free relations additionally
- Right-linear grammars also lack adjacent nonterminals
- Property alone: nonunique category
- Regular patterns: chiefly lexical
- CFGs: chiefly nested syntax
👁 Full explanation
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.
4 related practice questions
Blueprint: LO2 · Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Nesting and deterministic parser limits
COMP19
Symbol tables and scope
[Exam Focus]- Symbol-table contents and scope operations
- Names/identities → attributes
- Type; scope; width; storage offset
- Parameter signature; constants; linkage
- Hashing: expected O(1) insertion/lookup
- Stack of lexical scope tables
- Lookup nearest scope first
- Insert current-scope declarations
- Scope exit removes visibility
👁 Full explanation
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. - Symbol-table timing and implementation
- Scanner may intern spelling
- Semantics binds declaration/type
- First interaction: conventional, implementation-dependent
- Punctuation need not have entries
- Literals may use separate table
- Hash table: implementation, not semantic role
👁 Full explanation
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.
9 related practice questions
Blueprint: LO1, LO3 · Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Symbol-table contents and scope operations
COMP20
Names, Types and Advanced Features
[Exam Focus]- Member-call phase responsibilities
- obj.method(x)
- Scanner: identifiers and punctuation
- Parser: member-call structure
- Semantics: receiver, accessibility, argument types
- Overloading: signatures using static types
- Overriding: possible runtime implementation selection
👁 Full explanation
Distinguish lexical recognition, grammatical structure and semantic constraints. In obj.method(x), the scanner recognizes identifiers and punctuation; the parser recognizes a member call; semantic analysis resolves the receiver, accessible member and argument types. Overload resolution chooses among signatures using static types; overriding can select an implementation at runtime. - Scope, closures and generics
- Declaration identity beyond spelling
- Inner int x shadows outer float x
- Closures: captured lexical free variables
- Lifetime beyond creating frame
- Generics: parameter constraints/instantiation checks
- Symbol/type information beyond CFG
- Surface syntax may remain context-free
👁 Full explanation
Nested scopes require declaration identity rather than spelling alone: an inner int x can shadow an outer float x. Closures capture free variables from lexical environments; lifetime can outlive the creating stack frame. Generic functions need parameter constraints or instantiation checks. These features require symbol/type information beyond a CFG, even when their surface syntax is context-free. - Worked example object.resize(3) worked call
- Tokens: id,dot,id,(,integer,)
- Call→Expr . id ( Args )
- Expr→id; Args→Expr|integer|ε
- Call⇒Expr.id(Args)⇒id.id(integer)
- Bind object, resize, 3
- Parser: shape only
- Semantics: scope, accessible member, compatible overload
- Only resize(): parses, argument/type failure
👁 Full explanation
Specify and check a member callFor object.resize(3), the token kinds are id, dot, id, left parenthesis, integer, right parenthesis. One small grammar is Call → Expr . id ( Args ); Expr → id; Args → Expr | integer | ε. Derive Call ⇒ Expr . id ( Args ) ⇒ id . id ( integer ), then bind the tokens object, resize and 3. The parser checks this shape. Name and type analysis then require object to be in scope, resize to be an accessible member and an overload accepting one integer-compatible argument. If only resize() exists, the text still parses but fails the argument/type check.
Blueprint: LO1 · Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Member-call phase responsibilities
COMP21
Semantic checking: static and dynamic
[Exam Focus]- Static semantic checks
- Before execution
- Compatible types; valid names
- Restricted-scope duplicate declarations
- Argument counts; return compatibility
- Control-flow placement
- C/C++ break: loop or switch
- Annotated AST or typed IR
- No mandatory unique output-tree name
👁 Full explanation
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. - Dynamic checks and static proofs
- Runtime-dependent bounds/null checks
- Some accesses statically provable safe/faulty
- Universal static-memory-check impossibility trap
- Unreachable-code rules language-dependent
- Reject specified cases, warn, or eliminate
👁 Full explanation
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.
5 related practice questions
Blueprint: LO1, LO3, LO4 · Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Static semantic checks
COMP22
Type rules, inference and compatibility
[Exam Focus]- Type-checking operation rules
- Strict integer mod: two integers
- Indexing: array plus integer index
- if: Boolean condition
- Assignment: equal/convertible types
- Calls: parameter count and compatibility
- Returns: result-type match
👁 Full explanation
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. - Type inference and error distinctions
- Constraints derive types
- Integer x, numeric +, promotion rules
- Static inference without annotations
- Operator overloading: multiple meanings
- Overloading ≠ replacement for checking
- Ordinary C++/Java int x="hello": mismatch
- Zero division/bounds ≠ automatic type mismatch
👁 Full explanation
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.
12 related practice questions
Blueprint: LO1, LO4 · Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Type-checking operation rules
COMP23
Conversions need a named language
- Conversions and precision
- Coercion: permitted implicit conversion
- Cast: explicit conversion request
- Widening: often increased range
- Java int→float: widening, possible rounding
- Java int→long: exact
- Narrowing: range/fraction loss
👁 Full explanation
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. - Language-specific conversion cases
- C++ int x=3.14: 3 if representable
- C++ int x{3.14}: narrowing rejection
- Floating→integer: fraction discarded
- C++ unrepresentable truncated value: undefined behavior
- Java double→int assignment: explicit permitted cast
- C++/Java char/int: ordinary promotion
- Universal mixed-type ban trap
👁 Full explanation
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.
2 related practice questions
Note references: COMP_CPP, COMP_JAVA, COMP_SHORT
- Conversions and precision
COMP24
Attributes and Syntax-Directed Definitions
[Exam Focus]- Syntax-directed definitions and attributes
- CFG with grammar-symbol attributes
- Semantic rules on productions
- Annotated parse tree: computed attribute values
- Tree ≠ inherited/synthesized attribute
- Synthesized: children → parent
- Inherited: parent/sibling context
👁 Full explanation
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. - Attribute evaluation examples and classes
- E→E1+T; E.val=E1.val+T.val
- Synthesized expression value
- Inherited declaration type environment
- S-attributed: synthesized only
- Natural LR reduction-time evaluation
- Suitable LL evaluation also possible
- L-attributed: restricted left-to-right dependencies
- Dependency cycles may prevent evaluation
👁 Full explanation
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.
10 related practice questions
Blueprint: LO4 · Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Syntax-directed definitions and attributes
COMP25
Translation actions, ASTs and postfix
[Exam Focus]- Syntax-directed translation schemes
- Executable actions embedded in productions
- Actions during source translation
- Not during compiler generation
- Attribute results: types; values; AST pointers; code
- Input-to-output translation
- Beyond input-language recognition
👁 Full explanation
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. - AST construction and postfix evaluation
- Identifier: mkleaf(id,entry)
- Number: mkleaf(num,value)
- Operator: mknode(op,left,right)
- a−4+c AST: +(−(a,4),c)
- Postorder postfix: a 4 − c +
- Stack: push operands
- Pop right, then left
- Stack-machine usefulness
- Infix-to-postfix not universally mandatory
👁 Full explanation
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.
4 related practice questions
Blueprint: LO4 · Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Syntax-directed translation schemes
COMP26
IR and Three-Address Code
- Intermediate-representation purpose
- Source analysis separated from target implementation
- Optimizer/backend reuse
- Easy generation, analysis, transformation, lowering
- Portability architectural benefit
- Possible target-dependent details
- AST; graphs; bytecode; TAC
👁 Full explanation
IR separates source analysis from target implementation, allowing optimizers and backends to be reused. It should be easy to generate, analyze, transform and lower. Portability is an architectural benefit, not proof that every IR omits all target-dependent details. ASTs, graphs, bytecode and TAC can all be IRs. - TAC and instruction records
- Ordinary arithmetic: one operation maximum
- Two sources; one destination
- t1=c*d; t2=b+t1; a=t2
- Quadruple: (op,arg1,arg2,result)
- Triple: position references, no result field
- Indirect triples: separate ordering list
- Easier rearrangement
- Trees: expressions; DAGs: shared subexpressions
- Quadruples/triples: instruction records
👁 Full explanation
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.
9 related practice questions
Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Intermediate-representation purpose
COMP27
Control flow, arrays and SSA
[Exam Focus]- Control-flow and array translation
- if a<b goto Ltrue; goto Lfalse
- Labels join control paths
- Short-circuit AND: true-left permits right
- Short-circuit OR: false-left permits right
- Eager evaluation may change side effects
- Address: base+(i−L)*w
- Element width w; lower bound L
- Fixed-width contiguous-storage assumption
👁 Full explanation
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. - Static single assignment
- Distinct name per definition
- Join: x3=φ(x1 from B1,x2 from B2)
- Incoming value follows actual predecessor
- φ ≠ arithmetic average
- SSA: IR naming discipline
- Coexisting control-flow graph
👁 Full explanation
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.
1 related practice question
Blueprint: LO3 · Note references: COMP_MOD, COMP_DEEP, COMP_SSA
- Control-flow and array translation
COMP28
Basic Blocks, Flow Graphs and Dominators
- Basic blocks and leaders
- Maximal straight-line instruction sequence
- Entry at beginning; exit at end
- Leaders: first instruction
- Every jump target
- Instruction after each branch
- Block continues until next leader
👁 Full explanation
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. - Flow graphs and dominators
- CFG vertices: basic blocks
- Edges: possible next transfers, fall-through
- D dominates N: every entry-to-N path
- Backedge N→H; H dominates N
- H: natural-loop header
- Loop-analysis structure
- Expression DAG: value dependencies
- DAG ≠ arbitrary control flow
👁 Full explanation
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.
4 related practice questions
Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Basic blocks and leaders
COMP29
Data-flow questions and equations
- Forward data-flow analyses
- Reaching definitions: may-analysis
- Assignments reaching without replacement
- OUT=GEN∪(IN−KILL)
- IN: predecessor-OUT union
- Available expressions: must-analysis
- Computed on every relevant path
- Unchanged operands
- Available-expression join: intersection
👁 Full explanation
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. - Liveness and definite assignment
- Liveness: backward may-analysis
- Possible read before future redefinition
- OUT[B]=⋃successors IN
- IN[B]=USE[B]∪(OUT[B]−DEF[B])
- Fixed-point iteration
- Register allocation and dead-value removal
- Definite assignment: initialized on every path
- Reaching definitions alone insufficient
👁 Full explanation
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.
3 related practice questions
Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Forward data-flow analyses
COMP30
Folding, Propagation and Dead Code
- Folding, propagation and elimination
- Constant folding: 3*4→12
- Constant propagation: x=3; y=x+2→y=3+2
- Then fold
- Copy propagation: source remains unchanged
- Dead code: unreachable or unused computation
- Necessary-side-effect exclusion
👁 Full explanation
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. - Combined optimization worked case
- const x=8,y=16; if(x>y){z=x+y;}
- Propagate constants
- Fold 8>16 to false
- Remove unreachable branch
- Compile-time evaluation plus dead-code elimination
- Overlapping optimization choices
- Unused volatile read may remain necessary
- Effectful calls may remain necessary
👁 Full explanation
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. Compare optimizations by their applicability and effect; several transformations may be appropriate. Computing an unused volatile read or effectful call may still be required.
10 related practice questions
Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Folding, propagation and elimination
COMP31
Reuse, Strength Reduction and Peepholes
- Reuse, identities and strength reduction
- CSE: reuse earlier expression value
- Unchanged operands and relevant memory
- DAG sharing
- Valid integer identity: x+0→x
- Strength reduction: equivalent cheaper operation
- Unsigned x*8→x<<3
- Valid width and shift count
- Actual saving depends on target costs
👁 Full explanation
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. - Peephole optimization
- Short instruction windows
- Redundant load/store removal
- Machine-idiom replacement
- Jump-chain shortening
- jump L1; L1→L2 ⇒ jump L2
- Local optimization: broader category
- Peephole: concrete method
- Overlapping choices require requested level
👁 Full explanation
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.
4 related practice questions
Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Reuse, identities and strength reduction
COMP32
Loop Invariants, Induction and Fusion
- Loop invariants and induction variables
- Unchanged expression inputs
- Preheader hoisting: newly executed paths safe
- Induction: loop-invariant increment
- i=i+1
- Repeated t=4*i
- Equivalent running t increased by 4
- Reduced repeated multiplication
👁 Full explanation
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. - Loop transformation contrasts
- Fusion/jamming: compatible bounds, safe dependencies
- Unrolling: replicated body
- Reduced branch overhead, exposed parallelism
- Remainder iterations and code growth
- LICM; fusion; unrolling; strength reduction
- Distinct transformations
- Machine-dependent/independent taxonomy
- Local/global/loop taxonomy
- Classification requires criterion
👁 Full explanation
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.
4 related practice questions
Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Loop invariants and induction variables
COMP33
Optimization legality and aliasing
[Exam Focus]- Optimization legality and aliasing
- Defined observable behavior preserved
- Required side effects and exceptions
- Aliases: same memory possibility
- *p=5 may invalidate q-load
- Reuse requires proven nonaliasing/equivalent proof
- Calls may invalidate memory facts
👁 Full explanation
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. - Unsafe transformation boundary cases
- Potentially trapping division hoist
- Zero-iteration loop trap
- Floating reassociation: rounding/NaN changes
- Signed C/C++ overflow and shifts
- Unsigned modular arithmetic distinction
- Mathematical identity ≠ legal rewrite
- Dependence analysis: required memory-access order
- Fusion/scheduling legality
👁 Full explanation
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.
2 related practice questions
Blueprint: LO3 · Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Optimization legality and aliasing
COMP34
Target code generation
- Target code-generation tasks
- Checked IR → target form
- Instruction selection: target operations
- Register allocation: value locations
- Scheduling: dependency-respecting order
- Storage layout: offsets and ABI
- Register assignment: actual physical names
👁 Full explanation
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. - Target instruction example and variants
- t=a+b
- LOAD R1,a; LOAD R2,b
- ADD R3,R1,R2; STORE t,R3
- Combined load/arithmetic or register-held t
- Machine idioms; register availability; instruction order
- Execution-time effects
- Absolute code; relocatable object; assembly; bytecode
- TAC normally intermediate
- Cannot-ever-be-target universal trap
👁 Full explanation
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. Absolute machine code, relocatable object code, assembly and VM bytecode can be legitimate compiler targets; TAC is normally intermediate, but “cannot ever be target code” is an unjustified universal.
9 related practice questions
Note references: COMP_MOD, COMP_DEEP, COMP_CODEGEN
- Target code-generation tasks
COMP35
Descriptors and getReg
[Exam Focus]- Register and address descriptors
- Register descriptor: current held values
- Address descriptor: all current value locations
- Memory and multiple registers
- Register-only assignment: stale memory copy
- Code-generator bookkeeping
- Descriptors ≠ source types
👁 Full explanation
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. - getReg code-generation sequence
- Select operand/result registers
- Necessary loads → operation → descriptor update
- Prefer suitable existing register
- Reuse dead operand
- Otherwise spill victim
- Store live value lacking current alternative
- Block exit: preserve successor-needed values
👁 Full explanation
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.
2 related practice questions
Blueprint: LO3 · Note references: COMP_DESC
- Register and address descriptors
COMP36
Interference graphs and spilling
- Liveness, interference and spilling
- Live: possible use before redefinition
- Edge: values need distinct coexisting registers
- Registers as colors
- Nonoverlapping live ranges may share
- Insufficient register fit: spill to memory
- Insert loads/stores
👁 Full explanation
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. - Register-allocation complexity limits
- General fixed k≥3 coloring: NP-complete
- Optimal assignment/spill minimization: generally hard
- Practical heuristic allocators
- Restricted graphs/SSA: different properties possible
- Not every allocation algorithm NP-complete
- Decision-model versus optimization distinction
👁 Full explanation
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. Restricted interference graphs or SSA formulations can have different properties. Do not describe every possible register-allocation algorithm as NP-complete merely because a general model is difficult.
3 related practice questions
Note references: COMP_DEEP, COMP_COLOR
- Liveness, interference and spilling
COMP37
Runtime Storage and Calling Conventions
[Exam Focus]- Runtime storage and frames
- Static: entire execution lifetime
- Stack: nested calls and recursion
- Heap: beyond-call lifetimes
- Frame parameters and return address
- Saved registers; locals; temporaries
- Target-dependent sizes, alignment, offsets
- Two-byte int: module example
- Not C++ guarantee
👁 Full explanation
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. - Calling convention and escape analysis
- Argument/result locations
- Caller/callee-saved registers
- Stack alignment and frame responsibilities
- Escape: outlive/access outside allocation region
- Proven nonescape: stack allocation possible
- Scalar replacement: allocation elimination
- Preserved identity and lifetime semantics
👁 Full explanation
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.
2 related practice questions
Blueprint: LO1, LO3 · Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Runtime storage and frames
COMP38
Inlining and dynamic dispatch
[Exam Focus]- Inlining benefits and limits
- Suitably renamed function-body copy
- Preserved argument evaluation, returns, side effects
- Reduced call overhead
- Exposed optimization opportunities
- Increased code size/cache pressure
- Recursive expansion cannot be unlimited
👁 Full explanation
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. - Dynamic dispatch and devirtualization
- Overridden method: receiver runtime class
- Common per-class virtual-method table
- Object pointer to table
- Load selected entry
- Implementation strategy, not universal requirement
- Name mangling: linker-symbol distinctions/overloads
- Mangling ≠ runtime method selection
- Proven receiver type: devirtualization
👁 Full explanation
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.
2 related practice questions
Blueprint: LO1, LO3 · Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Inlining benefits and limits
COMP39
Recovery and compiler-construction tools
- Error recovery methods
- Panic mode: skip to synchronizing token
- Semicolon or closing brace
- Phrase-level: local insertion/deletion
- Location and cause reporting
- Avoid diagnostic cascades
- Lexical, syntax, semantic error detection
- Error handling: shared service
👁 Full explanation
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. - Compiler-construction generators
- Lex/flex: patterns/actions → scanner
- Yacc: Yet Another Compiler Compiler
- Yacc/Bison: grammar/actions → parser
- Definitions; %% rules; %% user code
- Classic Yacc: LALR
- Bison: additional LR/generalized modes
- Scanner generator ≠ CFG parser replacement
👁 Full explanation
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.
2 related practice questions
Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Error recovery methods
COMP40
Expression Translation Through the Compiler
[Exam Focus]- Expression pipeline trace
- a=b+c*d;
- Scanner: names and operators
- Parser: assignment with +(b,*(c,d))
- Semantics: declarations and operand/result types
- float a; int b,c,d;
- Possible result conversion before store
- Language arithmetic rules
👁 Full explanation
For a=b+c*d;, the scanner recognizes names and operators, the parser forms an assignment with +(b,*(c,d)), and semantic analysis resolves declarations and operand/result types. A declaration such as float a; int b,c,d; can require a conversion before storing the numeric result, according to language arithmetic rules. - Expression IR to target trace
- t1=c*d; t2=b+t1
- a=convert_if_needed(t2)
- Constant operands: folding
- Repeated unchanged expressions: sharing
- Target instruction and register selection
- Same a spelling, distinct scoped declarations
- Entering representation and added information
- Evidence for newly diagnosable errors
👁 Full explanation
Generate t1=c*d; t2=b+t1; a=convert_if_needed(t2). Constant operands can fold; repeated unchanged expressions can share values. Finally choose target instructions and registers. The same spelling a can denote different declarations in nested scopes. At each step ask what representation enters, what new information is added, and which errors can now be justified.
Blueprint: LO1, LO3, LO4 · Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Expression pipeline trace
COMP41
Missing and Conflated Lexical Answers
- Lexical-answer repairs
- Primary output: token stream
- Symbol table/AST/assembly: invalid substitutes
- Side structures versus primary output
- Smallest meaningful sequence: token/lexeme conflation
- Required abstraction unspecified
- Loop header: 14 despite missing option
👁 Full explanation
The primary output of lexical analysis is a token stream, rather than a symbol table, AST or assembly; some are side structures. Distinguish a token category from the lexeme text that matches it. Counting the loop header gives 14 tokens, even if no option matches. - Grouping units and storage roles
- Characters → token classes: lexical
- Tokens → expressions/statements: syntax
- Vague syntactic-class stem needs units
- Symbol tables: identifiers and attributes
- Not necessarily every token kind
- Trees: hierarchical constructs
- Symbol tables: declaration metadata
👁 Full explanation
Grouping characters into token classes is lexical analysis; grouping tokens into expressions and statements is syntax analysis. Identify whether an analysis groups characters into tokens or tokens into syntactic constructs. Symbol tables store identifiers and their attributes, not obligatorily every kind of token. Trees store hierarchical constructs, while a symbol table stores declaration metadata.
6 related practice questions
Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Lexical-answer repairs
COMP42
Overlapping Parser Choices
- Overlapping parser choices
- Shift-reduce and LR: both bottom-up
- Negative top-down question: multiple answers
- Recursive/nonrecursive predictive: both potentially efficient
- Nesting/tables: not uniquely LR
- LR choice ≠ ambiguity removal
- Leftmost derivation ≠ disambiguation policy
👁 Full explanation
Shift-reduce and LR are both bottom-up rather than top-down methods. Recursive and nonrecursive predictive parsers can both be efficient. Nested parentheses and parsing tables do not uniquely identify LR. Ambiguity does not disappear merely by choosing LR, and leftmost derivation is not an ambiguity-resolution policy. - LL(1) key and precedence repairs
- Overlapping FIRST; left recursion; ambiguity
- All rule out useful LL(1) grammar
- A-and-B-only key invalid
- Ask all conditions or conflicting cell
- Precedence/operator-precedence: concrete conflict and policy
- Universal shift-reduce solution trap
👁 Full explanation
Overlapping FIRST sets, left recursion and ambiguity can each prevent a useful grammar from being LL(1); do not restrict the check to only the first two. Check all applicable conditions and identify any conflicting table cell. Precedence versus operator-precedence parsing needs a concrete conflict and policy, not a blanket claim that every shift-reduce conflict has one solution.
14 related practice questions
Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Overlapping parser choices
COMP43
Semantic and Translation Claim Repairs
- Semantic activity versus data structure
- Type checking: activity
- Symbol table: data structure
- Both support semantic analysis
- Semantic rules compute attributes
- Types; values; code: nonexhaustive examples
- Symbol records: names and types
👁 Full explanation
Type checking and symbol tables are both important to semantic analysis: one is an activity and one a data structure. Semantic rules generally compute attributes, including but not limited to types, values and code; no listed specialized purpose is automatically exhaustive. Both names and types belong in symbol records. - Semantic and pipeline claim repairs
- Zero division/bounds ≠ clean type-error list
- Indentation/syntax mistakes ≠ clean type errors
- Incompatible operand plus named language
- Conventional final phase: code generation
- Later target optimization possible
- Annotated AST or typed IR
- Representation versus annotation versus phase
- Forced unique tree-name trap
👁 Full explanation
Distinguish division by zero, bounds violations, indentation mistakes and syntax errors from type errors; a type-error example should specify the language and incompatible operands. Code generation is conventionally last in a simplified pipeline even if later target optimization exists. A compiler may emit an annotated AST or typed IR, so distinguish representation, annotation and phase before forcing one tree name.
15 related practice questions
Note references: COMP_MOD, COMP_SHORT, COMP_DEEP
- Semantic activity versus data structure
No matching topics. Clear the search or change the filter.
Blueprint learning outcomes
- LO1 · Specify and analyze the lexical, syntactic and semantic structures of advanced language features
COMP05, COMP09, COMP10, COMP19, COMP20, COMP21, COMP22, COMP37, COMP38, COMP40 - LO2 · Describe techniques for lexical and syntax analysis
COMP05, COMP06, COMP09, COMP10, COMP11, COMP12, COMP13, COMP14, COMP15, COMP16, COMP17, COMP18 - LO3 · Understand the basic principles of compiler design
COMP03, COMP19, COMP21, COMP27, COMP33, COMP35, COMP37, COMP38, COMP40 - LO4 · Describe syntax directed translation and type checking techniques
COMP21, COMP22, COMP24, COMP25, COMP40