Project 1: Arithmetic Expressions
Quick links
• Course Home
• Piazza
• Scala 3 Book
• X86 Cheat Sheet
Due: TBD
1 Introduction
The goal of this project is to setup the environment and to learn how to parse and translate mathematical expressions into x86-64 assembly code. Our approach will be simple and the objective is to highlight some of the key aspects and ideas behind a compiler.
For this first project, we are going to keep things very simple and take very small steps. Make sure that you understand everything correctly before going to the next step.
At the end of the project, we will be able to parse mathematical expressions with single digit numbers, addition, substraction, multiplication, division, and parentheses. Our parser will generate an intermediate representation in the form of Abstract Syntax Trees (AST). The definition of the AST is the one used during the lecture.
In parallel, we will implement a generator that converts the AST into x86-64 code.
Here is a small example of what we will be able to generate for expression "2+3" by the end of the project:
[info] Running project1.Runner 2+3
============= AST ================
Plus(Lit(2),Lit(3))
==================================
============ OUTPUT ==============
.text
.global entry_point
entry_point:
push %rbp # save stack frame for C convention
mov %rsp, %rbp
# beginning generated code
movq $2, %rbx
movq $3, %rcx
addq %rcx, %rbx
movq %rbx, %rax
# end generated code
# %rax contains the result
mov %rbp, %rsp # reset frame
pop %rbp
ret
==================================
Result: 52 Setup
The first step of this assignment is to set up your environment as described in the Getting Started page. If you have any trouble installing the tools for the course, ask the for help on Piazza as soon as possible. Instructor/TAs or other students might help troubleshoot and solve your issue.
You can do the project on your own machine or lab machines and then upload your submission on Canvas.
The project has been designed and tested for Linux/Mac OS. If you have only Windows installed on your laptop, consider running Linux in a VM (e.g. VirtualBox) or using WSL, or use the lab machines for the project.
Note: Our compiler generates x86-64 assembly code. The test suits will compile and execute the generated x86-64 code. If you use a Mac machine with Apple silicon, these code can be executed via Rosetta emulation but the performance might be poor.
Download the skeleton file proj1.zip and unzip it:
unzip proj1.zip
cd proj1TODO: kick-the-tire test
3 Project Structure
Once you have setup the environment and your favorite Scala editor/IDE, you can open the project directory proj1 and browse the files.
A description of the different files is provided below. The two files you need to complete are Parser.scala and Generator.scala. Each parser that we are going to implement builds on top of another, so you need to implement them in the order by following the comments in the code. We will implement two different generators using two different strategies. It is recommended to implement the StackASMGenerator class when it is suggested in the Parser.scala file, and implement the RegASMGenerator class at the end.
3.1 Build Tool and build.sbt
The Scala Build Tool (sbt) is an open source build tool for Scala and Java projects. The build file build.sbt file contain the information necessary to compile this project. File project/build.properties specifies the sbt version to use. You should not have to modify them.
To use sbt, launch a terminal and go to the project directory (proj1) and enter sbt. It will lauch an sbt console. You will see prompt like this:
sbt:Project1>You can run the program from there (note that the following is not implemented yet and you will see incorrect output "Result: 1"):
sbt:Project1> run "1+3*(5-8)"To exercise the tests defined in the src/test/main/project1 directory, you can run:
sbt:Project1> testNote that in the skeleton, only a few tests are given. You will need to write your own tests to cover the new features you implement. It is a good practice to write tests before implementing a new feature.
3.2 src/main/scala/project1/Util.scala
This file defines multiple classes that are used to generate the code and run it on your machine. Nothing needs to be modified, but it is recommended to read it and have an idea of what is happening behind the scenes.
3.3 gen/bootstrap.c
As we are generating X86-64 assembly code which is OS independent, we will be using GCC/Clang to do the heavy lifting for us. The bootstrap file is a generic C file that is calling a function entry_point and is printing the result to stdout. Our compiler will generate the file gen/gen.s and will be assembled and linked by gcc:
gcc bootstrap.c gen.s -o outRunning out will then print the result of our compiled expression.
The ASMRunner class and assemble function defined in Util.scala defines the details of that on different operating systems. In Main.scala, you will see the whole pipeline.
3.4 src/main/scala/project1/Main.scala
The main function is defined in this file. During this project, you will be implementing many different parsers in order to test them through the main function. You will need to modify the parser or generator you want to use.
3.5 src/main/scala/project1/Exp.scala
This file contains the AST definition of our intermediate language. This is the language we are using in class; please refer to the lecture for more information.
3.6 src/main/scala/project1/Parser.scala
The class SimpleParser defined in this file is the basic parser that we are going to use for this project. It reads a stream of characters one at a time and can extract a single digit number (getNum) or a single letter name (getName). It does not handle whitespaces.
We keep the parser very simple at the beginning to focus on the important concepts. Later on, we will improve it to handle multiple digits numbers and more expressions. We will also support handling whitespaces.
The rest of the file is the definition of each parser we are building, starting from single number expressions to the full language we want to target. What you have to do for this project is highlighted with TODOs in the code. We encourage you to read the comments and code carefully before proceeding.
3.7 src/main/scala/project1/Generator.scala
In this file, we define the generators that can convert our AST into x86-64 assembly code.
We consider two different ways of generating the assembly code, each of which has pros and cons: Stack-based code, which is not very efficient but can handle arbitrarily complex expressions; and Register-based code, which is more efficient but can not handle arbitrarily complex expressions. We will see later that compilers use a hybrid approach.
You need to finish the TODOs in this file as well.
3.8 src/test/scala/project1/*Test.scala
These files contain unit tests for the first parsers. You can run test in the sbt console to execute them.
In order to get full credits, you must write your own tests for the others. There are some functions given to you in order to make the implementation easier.
4 Submission
You should turn in the proj1 directory. Please run an sbt clean before packaging and submitting.
To submit your project, create a ZIP file named proj1.zip of the proj1 directory and upload it to the corresponding assignment on Canvas.
Verify your submission by downloading the ZIP file you uploaded on Canvas and extracting its content. The uncompressed content should be the proj1 folder containing the code. Your submission ZIP file should have the exact same structure as the skeleton ZIP file.
Your submitted code must compile, i.e. running sbt compile gives no errors. If your code does not compile, your submission will not be graded and you will receive 0 points for the whole project.
Late Submission Policy: Projects are due at 11:59pm on the due date. Succeeding projects build upon previous ones and will reveal solutions of preceding projects, so late submissions will not be accepted. Submitted after the deadline will receive 0 points.
5 Grading
Your project will be tested against a set of unit tests. The weights of each task will be distributed as follow:
Task |
| Weight |
parseTerm |
| 20% |
parseFactor |
| 20% |
StackASMGenerator |
| 30% |
RegASMGenerator |
| 30% |