For this project, you will implement a compiler, interpreter, or translator for a language with a specific, domain-specific task. The project may be completed individually or in a team of up to three students. The tasks are split into sprints, each with its own deadline:
Each sprint will be submitted to your git repository. You will need to submit a brief report describing what was implemented (or not) and noting any important design decisions. You will also need to submit a script that runs your code and demonstrates that the submission meets the requirement for the phase. If you choose a target we cannot easily access (for example, if you are compiling a ROM), then you may submit a video or artifacts in lieu of a script.
Your first task is to form a team and inform Andrew. Send an email including the utorids of yourself and your teammates. (Please copy all of your teammates on the email, so that I know that they aren't being "volunteered" onto a team.) Your email should also include a brief description of your proposed project. In particular, tell me (a) what your input language will be, (b) what your target will be, and (c) why you think this project is particularly interesting. In response, I will prepare a git repository for you and send feedback on the project proposal.
You are free to select the domain for your project, including the input language and the target. However, the input language and target must have a few specific attributes. First, the input language must include:
Second, the target must be clearly defined, and ideally, it would allow you to execute or otherwise validate your output. For example, compiling to C is easy, and it would allow you to easily execute your code. Compiling to a document would also lead to easy validation. Compiling to a specific architecture (like MIPS or x86) would be more difficult, and you should allocate extra time early in the term to make sure you can compile to the target.
The goal of the language specification is to convince us that you have a viable project. You will be submitting a two-page PDF document that includes a description of the project (polished from the proposal) and one (or more) examples that demonstrate how the compiler will be used. In addition, you will submit a text file containing the lexical specification for the language. The lexical specification should be formatted as a grammar, as demonstrated in the week 2 exercise.
As you prepare your documents, consider these criteria that will be used to evaluate it:
In addition to the required documents, you may wish to begin working on Sprint 1. In particular, you may wish to prepare a text document specifying the syntax for your language. The two text specifications will be used to prepare a scanner, using flex, and a parser, using cup.
In the last phase, you created the lexical specification for your language. In this phase, you'll write the context free (parsing) grammar and then implement both. We hope the examples we have completed over the past few weeks will be useful. You may wish to start by reviewing the parsing exercise from week 4.
The primary deliverable for this sprint is code (the scanner and parser), but you will also need to prepare documents and artifacts that will help us to evaluate whether your code is operating correctly. We will expect:
These criteria will be used to evaluate your submission:
The next section, the backend, could present significant challenges for many of you. If you're compiling to an executable format, the amount of detail you need to know (and implement) to actually product executable code will be daunting. If you're building a source-to-source translator, there's the possibility that your target will not work as you expect. Either way: I recommend pushing to finish sprint 1 quickly, so you that you can spend extra time on the backend.
The primary deliverable for this sprint is the backend code -- the code that translates the output of your parser into your target language. However, like the last sprint, you will also need to prepare documents and artifacts that will help us to evaluate whether your compiler is operating correctly. We will expect:
These criteria will be used to evaluate your submission:
The final two sprints are opportunities to extend your compiler with new features, to implement error checking, or to improve the quality of the code generated. While our original intention was for you to perform some sort of extension to the type system in the first sprint and some sort of analysis and optimization in the second, that split may not make sense for your particular project. Instead, you could, if necessary, implement two analyses / optimizations.
Possible examples of a type extension include adding support for a new type (pointers? compound types like structs? functions as first class objects?), implementing type checking or type inference, or enhancing the scopying system. Possible analyses and optimizations include peephole optimizations (performed in the backend), creation and use of a dataflow IR in the middle end, static code analysis (to detect potential errors), or the addition of pragmas to guide code generation.
When selecting an extension, please consider (1) viability and (2) demonstrability. For the former: will you have time to complete the extension, given the number of people on your team, the deadline, and impending assigments in other courses? For the latter: will you be able to demonstrate that the feature works, both to the graders (Michael and Andrew) and to attendees of the demo session? Will the feature you choose be interesting to attendees of the demo session, and does it provide an opportunity to showcase your work to others?
Like the last two sprints, you will need to prepare documents and artifacts that will help us to evaluate whether your extensions are complete and correct. We will expect you to submit:
For both sprints, we will be evaluating:
In addition, for the final sprint, we will be evaluating the correctness, robustness (ability to handle errors or unexpected intputs), and quality of the design of your final, overall submission.
In the last class meeting of the term, you will demo your project to the other members of the class -- and to members of the broader UTM computer science community. The demo is slightly before the final due date for the project, so it is expected that your compiler won't be quite finished, but you should be very sure that the version you are demoing is stable. You may wish to create a branch immediately after sprint 3 as a backup.
On the demo day, half the groups will present in the first hour, and the other half will present in the second hour. When you're not presenting, you will be visiting the other groups to see their projects. Each group will set up at a table, using the whiteboard and the TV attached to their table to display any materials they need. You'll present a (1) description of your compiler, (2) motivation for creating it, and (3) a demonstration of an interesting feature (one of the extensions?) to people visiting your table.
The format of the demo will require that your pitch and demonstration be succinct. You'll need to pack a lot of information (at least "what" and "why") into 2-3 minutes. Michael and Andrew will visit each group to hear the pitch. We will be evaluating:
At the end of the demo, any visitors will be asked to vote on the ``most polished presentation,'' ``most interesting project,'' and ``most impressive feature.'' The projects winning those accolades will get ... the adulation of your peers. And a bonus on the demo mark.