Welcome to COMP 3173

In this project, you will be required to implement a full-featured1 compiler for a simple programming language called ???(TBD). More specifically, you will implement the following components:

           ┌───────────┐    ┌──────────┐    ┌───────────┐    ┌───────────┐
           │   Lexer   ├───▶│  Parser  ├───▶│TypeChecker├───▶│Interpreter│
           └───────────┘    └──────────┘    └───────────┘    └───────────┘

By the end of this project, you will be able to:

  • Understand the detailed process of how a DFA works and how to implement it.
  • Understand how parser generator works and write your own a simple parser generator.
  • Understand how AST can be evaluated and how typechecking works.

Moreover, you will also learn some state of the art techniques used in the open-source compiler, such as how to make compiler diagnostics more user-friendly:

Error: Expect a bool guard in if expression
   ╭─[<unknown>:1:1]
   │
 1 │ if let a = 1 in a then 1 else 2
   │    ───────┬──────
   │           ╰──────── expect a bool
───╯
1

usually a “full-featured” compiler should include backend components like code generation, optimization, etc. But in this project, we will only focus on the frontend components.

Last Updated: 2024 Sep 03 01:18:56

Project Specification

For each of the tasks, we provide stub classes that contain the API that you must implement. You should not modify the signatures for the pre-defined functions in these classes. If you modify the signatures, our grading test code will not work and you will get no credit for the project.

If a class already has some data members and methods, you should not remove them. For example, the Automata class has two pre-defined attributes states and start.

class Automata:
    def __init__(self, states: list[State], start: State):
        self.states = states
        self.start = start
        # <<<<< Start of Your Implementation >>>>>
        # Feel free to add more attributes if needed
        ...
        # <<<<< End of Your Implementation >>>>>

By convention, we use a special comment

# <<<<< Start of Your Implementation >>>>>
...
# <<<<< End of Your Implementation >>>>>

to indicate the region where you should add your implementation. You can add any code in this region, including new attributes, methods, and helper functions.

Basic

We expect the students taking this course to have some basic knowledge of Python or at least some general programming experience. If you are absolutely new to programming, you may need to put in some extra effort to catch up.

For Beginner

Particularly, we recommend the beginners to go through the following resource(s):

For Intermediate

For those who are already familiar with Python and want to learn more advanced topics (it is not compulsory for this project, but it will help you write better code), we recommend the following resource(s):

Not Sure?

If you not sure about your Python skills, you can use the following checklist to evaluate yourself:

  • Anything related to OOP, such as classes, objects, inheritance, override, overload, etc.
  • TBD …