Computer Science
System Software

Compiler Construction

A course at Oxford Brookes University, February 2024
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.
  • understand attributed grammars and their use for specifying languages and their translation
  • learn to transfer these skills also to general software engineering tasks (e.g. parsing of structured data files or argument lists)
  • learn how 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 them 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) conditions, implementation of a parser
  • Semantic analysis: syntax-directed translation, attributed 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 Compilers 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.mj: sample MicroJava program
BuggyScannerInput.mj: buggy MicroJava program to be tested with TestScanner

Level 1: Parsing
Parser.java (skeleton file)
TestParser.java
BuggyParserInput.mj: buggy MicroJava program to be tested with TestParser

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
BuggySemanticInput.mj: buggy MicroJava program revealing semantic errors

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 part1 and part2.