Compiler Construction With Embedded Xinu
Contents
Overview
Having students construct a compiler which targets a runtime that uses their own, or a provided, Xinu operating system is one of the potential tracks for a professor that is Teaching With Xinu.
Including Embedded Xinu in a compiler construction course allows students to explore the compilation of high level language constructs that rely on interacting with the underlying runtime. Many traditional compilers courses simply target a processor or simulator, but by targeting a platform (a processor and operating system combination) one can extend the source language to include more advanced language features such as I/O operations and thread creation, manipulation, and concurrency. This also allows students to run their test cases on real hardware and see these programs actually interacting with a real runtime. In modern programming these high level language features are vital, and it is important for students to see what the processor and runtime are doing when they use these features in their own programs.
Course Outcomes
Course development can parallel learning objectives and topics associated with many Programming Language Translation or Compiler Construction courses. [1] However, by targeting a platform with an operating system students can also focus on learning how compilers interact with the runtime to achieve thread concurrency and synchronization; topics which many traditional compilers courses avoid. [2, 3, 4]
Topics
- Lexical Analysis
- Syntax Analysis
- Semantic Analysis
- IR Translation
- Instruction Selection
- Register Allocation
Learning Objectives
- Recognize various classes of grammars, languages, and automata, and employ these to solve common software problems.
- Explain the major steps involved in compiling a high-level programming language down to a low-level target machine language.
- Construct and use the major components of a modern compiler.
- Work together effectively in teams on a substantial software implementation project.
Potential Course Structure
The course outlined below describes a compiler construction course focusing on a semester long project in which students build most of the pieces of a complete working compiler. For this example course we take the compiler project from Appel and Palsberg's Modern Compiler Implementation in Java [2] and modify it to target a MIPS platform running the Xinu operating system.
Course Outline
| Week | Topics | Assignments Track One | |||||
| 01 | Introduction | Project 1: Interpreter | |||||
| 02 | Lexical Analysis, Automata | Project 2: Scanner | |||||
| 03 | Syntax Analysis, Grammars | Homework 1: Automata and Grammars | |||||
| 04 | Parser Generators | Project 3: Parser | |||||
| 05 | Abstract Syntax Trees | ||||||
| 06 | Semantic Analysis | Project 4: Semantic Analysis | |||||
| 07 | Activation Records | ||||||
| 08 | IR Translation | ||||||
| 09 | Basic Blocks | Project 5: Translation | |||||
| 10 | Instruction Selection | Homework 2: Activation Records | |||||
| 11 | Liveness Analysis | ||||||
| 12 | Register Allocation | ||||||
| 13 | Register Allocation | Project 6: Instruction Selection | |||||
| 14 | Advanced Topics | ||||||
| 15 | Advanced Topics | Homework 3: Register Allocation |
Books
References
[1] Course topics and learning objectives have been adapted from the ACM's Computing Curricula 2001 Computer Science.
[3] A. V. Aho, M. Lam, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques and Tools. Pearson, 2nd edition, 1985.
[4] S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann, 1997.
This work funded in part by NSF grant DUE-CCLI-0737476.
