Content
1. Overview
2. Abstract Syntax Tree (AST)
3. Type Checking
1. Type Checker
2. Compound Type Equivalence
3. Type Compatibility
4. Scoping
4. Runtime Environment
1. Data Representation
2. Storage Classes
3. Runtime Stack
4. Memory Management
Overview
Parsing → Abstract syntax tree (AST) ← semantic analysis
Abstract Syntax Tree (AST)
- Parse tree: structure of derivation of input sentence
- Interior nodes: non-terminals
- Leaf nodes: terminals
- Abstract syntax tree: structure of input sentence; does not include keywords and punctuations
- Interior nodes: operators
- Leaf nodes: operands
Type Checking
- Declaration
- Types & operations
- Assignment
- Function parameters
- Singly or multiply typed
- Static (compile time) or dynamic type checking (runtime)
- Type conversion
- ...
Type Checker
Type + language constructs → type + semantic rules
- Interpreter: variables first encountered have type info stored in symbol table
- Compiler: symbol table discarded after compilation
Compound Type Equivalence
type
little = array[1..5] of integer;
small = array[1..5] of integer;
big = array[1..10] of integer;
var
a, b: array[1..5] of integer;
c: array[1..5] of integer;
d, e: little;
f, g: small;
h, i: big;
* d..i: named types
* a..c: anonymous types
* c structurally equivalent to a, b, d..g
Complex types (list, tables, queues, ...) harder to check!
Type Compatibility
- Type coercion:
int
coerced todouble
- Subtypes: e.g. subclassing in OO; C's
enum
subtype ofint
Scoping
Lexical area in which a variable is visible.
- One symbol table per scope
- One global symbol table, each scope has a number; variables assigned scope numbers
- Static & dynamic scoping of function call
- Static: where function is defined
- Dynamic: where function is called
- Keep track of:
- Location of global variables
- Location of local variables
- Location of functions
Runtime Environment
Statically linked libraries, dynamically linked libraries, OS, I/O, memory allocation/deallocation... may be written in other languages; need an interface between target program & runtime external functions.
Data Representation
Many machines support the same primitive types, but not pointers, arrays, structs, objects, ...
Storage Classes
Lifetime of a variable.
- Global: lifetime = program
- Local: lifetime = call/block
- Static: lifetime = program, used within functions only
- Dynamic: lifetime = that of the pointer pointing to it
Runtime Stack
- Parameters passing
- By value
- By value-result
- By reference
- By name
- ...
- Flow
- Before function call, calling routine:
- Save registers
- Push args onto stack
- Setup static links if appropriate
- Push return address onto stack
- Jump to target
- During function call, target routine:
- Setup frame pointer
- Make space for local variables
- Do job...
- Tear down frame pointer & static links
- Restore saved registers
- Jump back
- After function call, calling routing:
- Remove return address & params from stack
- Restore saved registers
- Continue...
- Before function call, calling routine:
Memory Management
new
/delete
in C++, malloc
in C, garbage collection in Java, ...