CSC444

Instructor: Doug Lea
Class: T-Th: 8am
Office/Lab hours: T-W-Th 11:00am-12:30pm.
Prereqs: CSC344 (365 and 322 strongly encouraged)
Course home page: http://gee.cs.oswego.edu/dl/csc444

Overview

The design and implementation of programming language compilers performing parsing, analysis of program representations, code generation, optimization, and language run-time support; with applications to related tools including intepretors, static analyzers, development environments, and virtual machines.

Topics

• Parsing: Tokenization of regular languages; top-down and bottom up parsing of context-free languages
• Static analysis: Abstract Syntax trees; type checking and static semantics checking
• Properties of target platforms, including architectures, procedure conventions, initialization, memory management, run-time support.
• Code generation: Mapping instructions and storage to processors; virtual machine representations;
• Optimization: Data flow graphs; forward, backward, and iterative techniques

Outcomes

• [Design] Choose among relevant approaches, techniques, and tools for parsing, static analysis, code generation, optimization, and run-time support.
• [Development] Design, implement, and test a compiler for a small language.

Textbook

This is the reference-quality "Dragon book" providing definitive treatments of most topics in compilation.

Links to online readings and materials

• Simple arithmetic recursive descent parser.
• Recursive descent parser for regexp
• Predictive parser for regexp
• SLR table for regexp grammar
• LR1/LALR table for regexp grammar
• SLR SLR example
• Sample source and bytecode
• within-block optimization example

Links to optional readings

• ANSI C grammar
• Choosing parsers
• Comparison of parser generators
• Pratt parsing; Pratt parser; operator precedence parsing
• GLR parsing (example)
• PEG grammars and packrat parsing
• Parser combinators
• CYK and Earley parsers
• Java Language Specification
• Hindley-Milner type systems
• Intermediate representations
• ErrorProne
• JVMS
• Stanford Optimization course

Software links

• MiniJava
• Flex
• SableCC
• jlex
• Antlr
• Bison
• Polyglot
• Jasmin assembler
• Jasmin assembler home
• Java ASM
• Soot
• SootUp

Requirements

Two exams (final exam is take-home style) (25%)

Exam questions mainly cover the theory of operation of parsing, analysis, code generation, optimization, and run-time support.

Exercises (10%)

two short assigments

• Exercise 1 (2 parts)

Project (65%)

A compiler for a small language, submitted in approximately 4 parts

1. Create a parser for your dialect of Minijava using any parser generator tool or framework. Include evidence of successful parse of all Minijava sample programs as well as at least three examples with your extensions. Demonstrate appropriate user error handling, and (partial) recovery using synchronizing tokens, using test programs with syntax errors.
2. Add symbol resolution and type-checking. Create unit tests and include results for cases of expression and invocation errors, duplicate declarations, overload/override errors, and illegal inheritance.
3. Generate and run code for all of the sample programs.
4. (Optional) Use an optimization framework to add an optimization and regenerate and run sample programs.

Campus references

See the CS and College course policies and resources.

If you have a disabling condition, which may interfere with your ability to successfully complete this course, please contact the Office of Disability Services.

SUNY Oswego is committed to Intellectual Integrity. Any form of intellectual dishonesty is a serious concern and therefore prohibited. The full policy can be found at http://www.oswego.edu/integrity