Courses

CS 453: Compilers and Systems Software

Objective	To teach the basics of compiler design and implementation, excluding optimization.
Pre-Conditions	[Math243] Set operations: union, intersection, member [CS127b/CS227] Symbol tables: hash tables, key/value pairs [CS127b/CS227] Tree data structures: building, traversing [CS127b/CS227] Recursion over heterogeneous structures (ASTs) [CS340] Assembly language: recursion, registers [CS342] Parsing [CS330] Facility with large (>500 lines) programs [CS318] Unix utilities: "make", debuggers [CS330] Facility with libraries of other people's code
Post-Conditions (Topics)	[2 week] Lexical analysis: Regular expressions, finite-state automata: NFA, DFA, RE->NFA->DFA; Using scanner-generators [3 week] Parsing: Context-free languages: left-most derivations, normal forms LL(1) (recursive-descent) parsing; LR(1) parsing; Using parser-generators [2 weeks] Type-checking [1 week] Activation records [1 week] Translating data references: globals, locals, parameters [1 week] Translating expressions: arithmetic, Boolean [1 week] Translating parameter passing: by-value, by-reference [1 week] Translating control structures: if-then-else, while, procedures [1 week] Instruction selection [1 week] Register allocation: naive Large (>1000 lines) project.

Last revised on 30 April 1997 by John Hartman.