CIS-4050 (Compiler Design) Home Page

This is the home page for Peter Chapin's Compiler Design course notes for the Spring 2025 semester. Here you will find electronic versions of class slides, homework assignments, program samples, and links to other references of interest. If you are a student taking Compiler Design, you should bookmark this page.

The course syllabus gives an overview of the course and its content, lists course resources, and describes the grading policy and related issues.
The homework submission area and grade book are on Canvas, but all other course resources are here.
I've prepared some general information on submitting assignments.
You can use Microsoft Copilot through the school's subscription. Log in using your VSC credentials.
My home page contains other resources of potential interest.

Topic Summary

The lectures for this course are on Zoom.

2025-01-22. Course introduction. Discussed Homework #1. Reviewed the classic compiler pipeline.
2025-01-27. Finished discussion of the classic compiler pipeline. Introduced Scala.
2025-01-29. Finished the introduction of Scala. Started discussing the DFA for detecting C++ comments.
2024-02-03. Finished discussing the DFA for detecting C++ comments. Discussed Homework #2.
2025-02-05. Finished discussing Homework #2. Introduced using ANTLR to generate the Augusta lexical analyzer.
2025-02-10. More on using ANTLR to generate the Augusta lexical analyzer. Introduced the Augusta grammar.
2025-02-12. More on the Augusta grammar. Demonstrated the ANTLR plugin for IntelliJ and how it displays parse trees.
2025-02-17. Discussed new Augusta syntactic features to be added in upcoming homework: declare statements, enumeration types, type declarations, subtype declarations.
2025-02-19. Discussed parser testing.
2025-02-24. No class (Vacation).
2025-02-26. No class (Vacation).
2025-03-03. Discussed Homework #2. Discussed symbol tables.
2025-03-05. Finished discussing symbol tables. Introduced the ANTLR visitor interface and type checking.
2025-03-10. Discussed type checking and introduced C code generation.
2025-03-12. Showed the high-level structure of the compiler where the compiler pipeline is expressed in code.
2025-03-17. Discussed Homework #4 on type checking. Introduced LLVM.
2025-03-19. More discussion about LLVM. Introduced the concept of control flow graphs.
2025-03-24. Demonstrated Open Watcom. More discussion about flow graphs and their representation in AGC.
2025-03-26. More discussion about the mechanics of type checking in AGC. Discussed the value of using abstract syntax trees in the compiler pipeline (conversation with ChatGPT).
2025-03-31. No class.
2025-04-02. More details on building the symbol table and on the type checking code in AGC. Formally introduced abstract vs. concrete syntax and ASTs.
2025-04-07. No class (Vacation).
2025-04-09. No class (Vacation).
2025-04-14. Introduced LL(1) parsing via recursive descent. Introduced LALR(1) parsing with a demonstration of Bison.
2025-04-16. Introduced the Augusta abstract syntax tree via a sealed trait hierarchy.
2025-04-21. Described the ast-refactor branch in the repository.
2025-04-23. ???
2025-04-28. More on control flow graphs and their implementation.
2025-04-30. Introduced Homework #5 on building the Augusta control flow graph from the AST.

Slides

Introduction.

Homework

Homework #1. Building Augusta. Due: 2025-01-31
Homework #2. Integer Literals. Due: 2025-02-14
Homework #3. ANTLR. Due: 2025-03-07
Homework #4. Type Checking. Due: 2025-04-04
Homework #5. Control Flow Graphs. Due: 2025-05-16

Samples

The NoComment example shows a Scala program that strips comments out of C, C++, and D programs. The sample contains both a functional and imperative form of the solution.
Here is a state machine for recognizing floating point literals in the D language.

Resources/Articles

Scala

We'll be using the Scala programming language as an implementation language. For a development environment we will be using the SBT build tool and either Visual Studio Code or IntelliJ IDEA. You can use another development environment you want, as long as it is able to process SBT projects. However, you may need to do extra configuration to set up another environment.
Slides from my Programming Languages course, adapted to be more generic (these slides are for Scala 2):

Regular Expressions

This Wikipedia article describes Thompson's Construction, which is an algorithm for converting a regular expression to a nondeterministic finite automaton (NFA).
Here are some slides about nondeterministic finite automata by Wayne Goddard at Clemson University.
Here are some other slides about NFAs by Jeffrey Ullman at Standford University. These slides are more "math-y" than the earlier ones, but they show an example of subset construction, a method for converting an NFA to a deterministic finite automaton (DFA).
This Wikipedia article describes methods for minimizing a DFA to remove unnecessary states. Often the DFA produced by subset construction is overly large.

Parsing

Various parser and/or lexical analyzer generators: we will use ANTLR, but there is also Elkhound, Bison, Cup, Flex, and JFlex, to name only a few. A longer list is here
The sbt-antlr4 plugin for SBT allows you to easily use ANTLR-generated code in SBT projects.

JVM, LLVM, and Code Generation

Graph for Scala is a Scala library for manipulating graphs. We'll use it when building control flow graphs and perhaps also for other things.
When we target the Java Virtual Machine, you'll need to understand parts of the Java Virtual Machine specification. We can use Jasmin to convert JVM assembly language into class files.
When we target LLVM you will find the LLVM Documentation and the LLVM Language Reference useful. The language reference documents what our front end must generate.
Here are a couple of resources that describe register allocation via graph coloring. These are notes created by other instructors (one, two).