Language translators: compilers and interpreters. The structure of a compiler:
lexical analysis, parsing, semantic analysis, intermediate code generation,
register allocation, global optimization. Bootstrapping a compiler.
Reading: Aho-Sethi-Ullman , ch. 1
A modern compiler : GNAT. The architecture of GNAT: phases, intermediate
representations, important data structures.
Lexical scanning: Token classes, keyword recognition, minimizing the
code-per-character cost of scanning, scanning numeric literals and string
literals. The interface between the scanner and the parser.
Hand-written vs. automatically generated scanners.
Formalism: regular grammars, regular languages, FSA, non-deterministic FSA,
automatic generation of lexical scanners.
Reading: Aho-Sethi-Ullman, ch. 3
Parsing. Abstract syntax vs. concrete syntax. Grammars and the formal
specification of certain aspects of programming languages. Top-down
parsing and recursive descent.
Reading: Aho-Sethi-Ullman , ch. 4.1-4.4
Automatic parser construction. FIRST and FOLLOW functions. LL(1) parsers.
LR parsers. Conflicts in LR grammars and how to resolve them.
Reading: Aho-Sethi-Ullman, ch. 4.7-4.9
Semantic analysis: attributes and their computation, tree-traversals,
visibility and name resolution. Inherited attributes and symbol tables.
Name resolution in block-structured languages.
Reading: Aho-Sethi-Ullman ch. 5
Type checking. Type systems, varieties of strong typing, overload resolution,
polymorphism and dynamic dispatching.
Type-checking and type inference, unification.
Reading: Some programming language text (e.g. Scott). Chapter
6 of Aho-Sethi-Ullman.
Run-time organization: storage allocation, non-local references, parameter
passing, dynamic storage allocation. Exception handling, debugging information.
Reading: Aho-Sethi-Ullman ch. 7
Intermediate code generation: control structures, expressions, simple
register allocation. Aggregates and other high-level constructs.
Reading: Aho-Sethi-Ullman Ch.8
Code generation over basic blocks. Using dags. Global register allocation
and graph coloring.
Reading: Aho-Sethi-Ullman chap. 9.1-9.6
Global optimization: data flow analysis, Single-Assignment form.
Reading: Aho-Sethi-Ullman ch.10
Code generation for RISC machines: delay slots, instruction scheduling,
inlining, loop unrolling.
Instruction selection by tree matching