**Compiler Design** **Reed College CSCI 394 Fall 2023**       ![](images/gears-top.jpg)
(#) Overview An in-depth look at the design and construction of programming language compilers, covering the basic phases of the compilation process, including syntactic analysis and parsing, semantic analysis, intermediate representations of code, dataflow analysis, register allocation, code generation, and other optimizations. Students will develop a working compiler and run-time system for a programming language. Time permitting, the course surveys advanced techniques such as compilation of functional programming languages or compilation for high-performance hardware. Prerequisite: Computer Science 389 or consent of the instructor. Lecture-conference. This semester we will use C++ to compile Python to MIPS assembly. **Prerequisites:** CSCI 389.
**Meets:** 2:40-4:00 MW in Bio 19.
**Instructor:** Jim Fix
**Office:** Library 314
Jim's office hours are posted [here](http://jimfix.github.io/teaching.html). ---
`01000011010011110100110101010000010010010100110001000101010100100101001100100001` ![](images/gears-mid.jpg) `01000011010011110100110101010000010010010100110001000101010100100101001100100001`
(#) Core Dump **Week 1-2**: introduction to language tools • front end overview
• a grammar for Straight-Line PYthon
• abstract syntax trees
• hand lexing
• recursive-descent parsing
**Reading**: Appel Ch 1 (and some of 2-4)
[**Homework 1**](slpy.html) the SLPY interpreter
**Week 3-4**: lexicographic analysis
• regular expressions
• (non-deterministic) finite automata
• `lex` and `flex`
**Reading**: Appel Ch 2
[**Homework 2**](flex.html) Flexing Python
**Week 5-7**: syntactic analysis
• grammars
• LR parsing
• `yacc` and `bison`
**Reading**: Appel Ch 3 & 4
[**Homework 3**](dwislpy.html) Python functions, conditionals, and loops
**Week 8-9**: semantic analysis
• inference rule notation
• type checking
• return behavior analysis
**Reading**: Appel Ch 5
[**Homework 4**](chckpy.html) checked Python **Week 10-11**: IRs and CFGs; code generation
• syntax-driven translation into intermediate representation
• basic blocks with "goto" labels gives control flow as a graph
• MIPS calling conventions and frame layout
**Reading**: Appel Chs 6, 7, 8, & 9
[**Homework 5**](dwislpyc.html) generating MIPS with frame `lw`/`sw`
**Weeks 12-13** data-flow analysis; register allocation
**Reading**: Appel Chs 10, 11, & 17 (w/ 19)
(#) Control Flow Graph We will cover chapters 1-11;17 of the Tiger book as shown below.
(#) Source Text
![](images/tiger-cover.jpg width=300 height=300) ![](images/dragon-cover.jpg width=300 height=300))
• Andrew Appel, [*Modern Compiler Implementation in C*](https://www.cs.princeton.edu/~appel/modern/c/), "The Tiger Book".
• Aho, Sethi, Ullman, [*Compilers: Principles, Techniques, and Tools*](https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools#First_edition), "The Dragon Book".
(#) a.out