Compiler Construction Past Paper

Frontend

Grammar

Lexical (regex, FSA) & Syntax analysis/Parsing (CFG, PDA)

Recursive Descent

LL(k)

LR(k), SLR(k)

Type Checking

Simplification

remove type information, remove locations

Backend

Translation

CPS, defunctionalise, etc

JARGON

closure

VM

stack-oriented intermediate code

(fun x -> e') e'' 
(i) evaluates e'' and pushes the result on the stack
(ii) creates a closure (c,k) for (fun x -> e') in the heap 
and pushes a pointer to it on the stack.
> c = the address of the first instruction in e' 
> k = the number of free variables of e' (excluding x) 
[pop off k values from the stack and placed in the closure.]
(iii) apply the top of the stack to the argument below.
return

LOOKUP STACK_LOCATION -2  # fetch the argument v from the stack
CALL sum                  # sum(v)
PUSH 3                  
ADD                       # sum(v) + 3
RETURN

Mixed topics

Garbage Collection

Past Papers

Opt

Exception

stack-oriented code

Linking

.data                  <-     .symtbl     ->        .strtab
D0: 00 00 00 01                 S0: D0 N0            N0:  a
                                                     N1:  \0
                                      ^
                                      |
.text                  <-     .rela.text
T8: LOAD R1, 0(R2) # a          R0: T8 S0

Run-time Memory

Stack

Bootstrapping