2.1 src/main/scala/project2/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 understanding of what is happening behind the scene.

2.2 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 calls the function entry_point and prints the result to stdout. Our compiler will generate the file gen/gen.s, which will be assembled and linked by gcc:

gcc bootstrap.c gen.s -o out

Running out will then print the result of our compiled expression. This file is the same as in Project 1.

2.3 src/main/scala/project2/Main.scala🔗

The main function is defined in this file. The data flow in this file can be viewed as:

Read from file / Read from command line -> Parser -> Semantic analyzer -> Interpreter or compiler

You will be implementing several different parsers in order to test them through the main function.

The AST generated will be then provided to the semantic analyzer. If there is no error, then the code (represented as AST) is going to be interpreted or compiled. The skeleton provides you with the ValueInterpreter and StackCompiler for your reference. You will have to write StackInterpreter and X86Compiler.

As our language becomes more complex, it will become more useful to read the input code from a source file. You may find some sample programs in the examples/ folder. Here are some examples to run the code:

$ sbt
sbt:Project2> run
Usage: run PROG [OPTION]
   or: run FILE [OPTION]
OPTION: compX86, intStack, intValue (default)
sbt:Project2> run examples/valid_arithm.scala          // interpreter with the reference interpreter
sbt:Project2> run examples/valid_arithm.scala compX86  // x86 compiler (your implementation)
sbt:Project2> run examples/valid_arithm.scala intStack // stack interpreter (your implementation)

It is still possible to run code from the command line, as in project 1. For example:

$ sbt
sbt:Project2> run "val x = 5; x"
sbt:Project2> run "val x = 5; x" compX86
sbt:Project2> run "val x = 5; x" intStack

2.4 src/main/scala/project2/Language.scala🔗

This class contains the definition of our intermediate language (AST).

2.5 src/main/scala/project2/Parser.scala🔗

As we discussed in class, parsing the file one character at a time is not enough when we introduce more complex constructs. Also, our single digit numbers were a little bit limiting. The Scanner class defined in this file tokenizes the code. You will have to implement the getNum method. Check out the other methods implemented there, as they are going to be useful for the next part.

The rest of the file is the definition of each parser we are building, starting from a generic precedence arithmetic parser to the full language we want to target, including variables, if statements, and loops. You need to finish the TODOs in this file. You should read the comments and code carefully before proceeding.

2.6 src/main/scala/project2/SemanticAnalyzer.scala🔗

While the parser is in charge of verifying that the input string follows the defined syntax, the semantic analyzer verifies that the program described is meaningful and follows the typing rules. For example:

val x = 2; x = 5

Using the functions error and warn (defined in SemanticAnalyzer.scala), you need to enforce the following semantic rules:

• Unary operators support "+", "-". Otherwise raise: undefined unary operator.

• Binary operators support "+", "-", "/", "*". Otherwise raise: undefined binary operator.

• Boolean operators support "==", "!=", "<=", ">=", "<", ">". Otherwise raise: undefined boolean operator.

• val can not be assigned. Otherwise raise: reassignment to val.

• Identifier needs to be defined in the current scope before being used. Otherwise raise: undefined identifier.

• Note that we allow a variable to be declared multiple times (variable shadowing). The last definition will be used when a reference to it is found. In this case only a warning is raised.

2.7 src/main/scala/project2/Interpreter.scala🔗

A definitional interpreter is an executable program written in a host language (or meta-language, which is Scala in our case) that defines the semantics and behavior of a target object language (which is the language to be implemented). Optional reading material: Definitional Interpreters for Higher-Order Programming Languages. John C. Reynolds. 1972, 1998

As we have seen in class, now that our programming language accepts more than just mathematical expressions, we need to define the required behavior of our enriched language. An interpreter is used to define the semantics.

For reference, we already provide you with an interpreter (ValueInterpreter) that is fully functional. Your job is to complete the stack-based interpreter.

2.8 src/main/scala/project2/Compiler.scala🔗

In this file, one compiler (StackCompiler) emitting Scala-like code has already been implemented. You need to implement the second compiler that can convert our AST into x86-64 assembly code. Pay attention to the connection between the interpreter and compiler, as the interpreter implementation should guide you in the implementation of the compiler.

In the previous project, we considered 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 efficient, but can not handle arbitrarily complex expressions. For this assignment, there is a given stack-based compiler, and you will implement the register-based approach.

2.9 src/test/scala/project2/*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. Every task should have at least 2 tests otherwise points will be deducted. There are some functions given to you in order to make the implementation easier.