This course includes four extensive lab projects.
- These projects are designed to minimize boilerplate programming, and focus on understanding conceptually difficult problems at a deep level.
- You may use any language you want, except for Perl, Python, or Haskell.
- I recommend C, C++, or Java. Please check any other languages with me before attempting the projects.
- If you want to use a functional language, consider OCaml, which supports the necessary constant-time arrays and mutations.
- Projects 2 and 4 build on Project 1's code. Thus you will have to use the same language.
- These projects must be completed individually. You can discuss the algorithmic aspects of the projects with your fellow students, but code must be written alone.
- As a heuristic, if you are working on paper or a whiteboard, you are good. If you are looking at code, you are not.
- Some projects will have an associated lab report.
- All projects must be submitted via Git repository. We will use GitHub classroom.
- Start early and pace yourself. Many programming tasks are more difficult to complete in a single stretch than over days or weeks. Some of these projects are impossible to complete in a single stretch. Expect to spend significant time analyzing the problem throughout the implementation.
- Some (possibly all) projects will contain a checkpoint, where you are expected to have working code for a simplified version of the problem. These checkpoints count towards the project grade.
Project 1: Lexing and Parsing ILOC code.
In this project, you will construct an lexer and parser for a subset of the ILOC assembly language. You will take as input an ILOC file, and print either the stream of tokens, an intermediate representation, or ILOC code. A significant part of the project is the hand-written, character by character, lexer.
Project 2: Register Allocation for Straight Line Code
In this project, you will construct an allocator that takes a block of ILOC code that uses an unbounded number of registers, and returns an equivalent block of code that uses only a fixed number of registers.
Project 3: An LL(1) Parser Generator
In this project, you will construct an LL(1) parser generator that will take a language specification, and returns both human-readable information, and LL(1) tables suitable for parsing.
Project 4: Instruction Scheduling
In this project, you will construct an instruction scheduler for straight-line code, targeting a virtual machine with heterogeneous functional units.