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 Grune, ch. 1
A modern compiler : GNAT. The architecture of GNAT: phases, intermediate
representations, important data structures. How to build GNAT from sources.
How to build modified versions of GNAT, tree-walking routines that use the
intermediate representation of GNAT.
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.
Reading Grune, ch. 2.1
Parsing. Abstract syntax vs. concrete syntax. Grammars and the formal
specification of certain aspects of programming languages. Top-down
parsing and recursive descent.
Reading Grune, ch. 2.2
Automatic parser construction. FIRST and FOLLOW functions. LL(1) parsers.
LR parsers. Conflicts in LR grammars and how to resolve them.
Reading Grune, ch. 2.2
Semantic analysis: attributes and their computation, tree-traversals,
visibility and name resolution. Inherited attributes and symbol tables.
Name resolution in block-structured languages.
Reading Grune, ch. 3
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. Sethi). Chapter
6 of Aho, Sethi and Ullman, section 6.1 of Grune et al.
Run-time organization: storage allocation, non-local references, parameter
passing, dynamic storage allocation. Exception handling, debugging information.
Intermediate code generation: control structures, expressions, simple
register allocation. Aggregates and other high-level constructs.
Reading Grune, ch. 4
Code generation over basic blocks. Using dags.Global register allocation
and graph coloring.
Reading Aho, Sethi and Ullman, ch. 9, Grune et al. Section
Global optimization: data flow analysis, use-def chaining,constant folding,
common subexpression elimination.
Reading Aho, Sethi and Ullman, ch. 10.
Code generation for RISC machines: delay slots, instruction scheduling,
inlining, loop unrolling.
Reading: Muchnick, chap. 9 and 17.
Code generation for VLIW Architectures (guest lecturer: Ben Goldberg).