Language Specification & Compiler Construction

A course at Oxford Brookes University, February 2012
H. Mössenböck

Goals

• acquire the practical skills to write a simple compiler for an imperative programming language.
• understand the concepts of scanning, parsing, name management in nested scopes, and code generation.
• learn to transfer the skills also to general software engineering tasks (e.g. parsing of structured data files or argument lists)
• learn to use a compiler generator

Contents

The course goes through all phases of a compiler. It shows the theoretical concepts underlying each phase as well as how to implement it efficiently. The students will write a small compiler for a Java-like language. It will translate a source program into the code of virtual machine. The implementation language will be Java.

• Overview: compilers and interpreters, structure of a compiler, single-pass vs. multi-pass compilers
• Scanning: finite automata, scanner implementation
• Parsing: recursive descent parsing, push down automata, terminal start symbols and successors, LL(1) condition, implementation of a parser
• Semantic analysis: syntax-directed translation, attribute grammars
• Symbol table handling: objects, types, scopes
• Code generation
• Compiler generators

Handouts

Handouts
MicroJava Quick Reference

Slides

1. Overview
2. Scanning
3. Parsing
4. Semantic Processing
5. Symbol Table Handling
6. Code Generation
7. Building Generators with Coco/R

Lab

JDK: Java Development Kit from Oracle

The following code templates are necessary for doing the lab described in the handouts.

Level 1: Scanning
Scanner.java (skeleton file)
Token.java
TestScanner.java
sample.mj: sample MicroJava program
Eratos.java: sample Microjava program

Level 1: Parsing
Parser.java (skeleton file)
TestParser.java

Level 2: Symbol table handling
Obj.java
Struct.java
Scope.java
Tab.java (skeleton file)

Level 3: Code generation
Code.java (skeleton file)
Operand.java
Decode.java
Compiler.java
Run.java
Decode.java

Level 4: Compiler Generator Coco/R
Coco/R (download and documentation)
QueryForm example from the slides

Text Book

The text book N.Wirth: Compiler Construction. Addison-Wesley 1996 comes close to the contents of this course. Unfortunately, it is out of print, but it can be downloaded from here.