CSU665 Compilers	(4 SH)

 

 
Studies the construction of compilers and integrates material from
earlier courses in programming languages, automata theory, computer
architecture, and software design.  Examines syntax trees; static
semantics; type checking; typical machine architectures and their
software structures; code generation; lexical analysis; and parsing
techniques.  Uses a hands-on approach with a substantial term project.

 

 
CSU380, CSU660

 

 
There are many good textbooks for this course, including:

Aho, Sethi, and Ullman.  Compilers: Principles, Techniques, and Tools.
Addison Wesley, 1986.

Andrew Appel.  Modern Compiler Implementation in Java, Second Edition,
Cambridge University Press.  (Also available: "in ML", "in C".)

Charles Fischer, Richard LeBlanc, and Ron Cytron.  Crafting a Compiler.
Addison-Wesley.

 

 
Semantic analysis 
    abstract syntax trees 
    simple type checking 
    scope of declarations 
    lexical addresses
Machine architecture from the compiler's perspective
    run-time structures
        expressed values
        environments, closures, objects
        continuations
    procedure calls
    registers
    runtime invariants
    instruction sets
Code generation 
    values and extent 
    garbage collection 
    instruction selection 
    register allocation 
    major optimizations 
    assembly
Construction of lexical analyzers 
    regular expressions 
    nondeterministic finite automata
    deterministic finite automata
    minimal deterministic finite automata 
Construction of efficient parsers
    LL or LR grammars
    deterministic top-down or bottom-up parsing
    syntax-directed translation
    construction of abstract syntax trees
    error recovery

 

 
Upon completion of this course, a student should

    have written a substantial portion of a compiler for a simple
    programming language

    understand the abstract syntax tree representation of programs

    understand at least one technique for expressing the scope and
    typing rules of a programming language

    understand the use of lexical addresses to generate code that
    refers to variables

    be able to write a code generator for a simple programming language

    be able to convert regular expressions into deterministic
    finite automata that recognize the generated language

    understand either LL or LR parsing well enough to write, from
    scratch, an efficient parser for the language generated by a
    simple LL(1) grammar

 

 
The course outcomes will be measured and verified by:
    Course project: a complete compiler for a small language

        The instructor should provide enough design, structure,
        and code for students to complete this project successfully.

        It is recommended that the project be broken up into three
        to five  programming assignments.  Possibilities include:

            abstract data type (ADT) of abstract syntax trees (ASTs)
            ADTs for symbols and compile-time environments
            lexical analyzer
            parser
            type checker
            static attribution of details needed for code generation
                (e.g. lexical addresses, record sizes, field offsets,
                tail calls)
            code generator
            assembler
            garbage collector

        It is recommended that the early assignments be graded
        by reading the code in addition to executing it.

     Midterm exam (optional at discretion of instructor)

     Final exam (optional at discretion of instructor)

     Electronic portfolio (optional at discretion of instructor)


 

 
CS U665 is an elective course that traditionally has been taken by
juniors and seniors who are unusually good at programming and often
have some industrial programming experience.  The compiler project
builds on their programming experience, and the course as a whole
explains some of the mysterious things that students have witnessed
while using compilers.  After building a complete compiler, students
are well-prepared to accept responsibility for significant programming
tasks.

 

 
Omitted.

Note: CS U665 has been mentioned as one model for a proposed "capstone"
course in our curricula.