Extend the syntax analyzer built in Project 10 into a full-scale Jack compiler. In particular, gradually replace the software modules that generate passive XML code with software modules that generate executable VM code.
The main tool needed is the programming language in which you will implement the compiler. You will also need an executable copy of the Jack operating system, as explained below. Finally, you will need the VM Emulator, to test the code generated by your compiler on a set of test programs supplied in project 11.zip and listed below.
Complete the Jack compiler implementation. The output of the compiler should be VM code designed to run on the virtual machine built in projects 7 and 8. Use your compiler to compile all the Jack programs listed below. Make sure that each translated program executes according to its documentation.
First, read ECS chapter 11. This pdf may also be insightful.
Next, focus on the code in your project10 directory for Stage I.
Start by building the compiler's symbol table module and using it to extend the syntax analyzer built in Project 10. Presently, whenever an identifier is encountered in the program, say foo, the syntax analyzer outputs the XML line "<identifier> foo </identifier>". Instead, have your analyzer output the following information as part of its XML output (using some format of your choice):
var
statement) or used (e.g. the identifier stands for a variable in an expression)Example: <identifier cat="var" declared="true" index="0" > allKindsOfAwesome </identifier>
You should build and test your symbol table module and the above capability by running your (extended) syntax analyzer on the test Jack programs supplied in Project 10. Once the output of your extended syntax analyzer will include the above information, it means that you have developed a complete executable capability to understand the semantics of Jack programs. At this stage you can make the switch to a full-scale compiler, and start generating VM code instead of XML output. This can be done by gradually morphing the code of the extended syntax analyzer into a full compiler.
Within your src
directory, create a subdir named project11
. Extract the contents of project11.zip into it.
Add, commit and push the new files.
There are six application programs designed to unit-test your compiler features incrementally. Test your compiler on these programs in the given order. This way, you will be implicitly guided to build the compiler's code generation capabilities in stages, according to the demands of each test program.
The Operating System: The Jack OS -- the subject of Chapter 12 -- was written in the Jack language. The source OS code was then translated (by an error-free Jack compiler) into a set of VM files, collectively known as the Jack OS. Each time we want to run an application program on the VM Emulator, we must load into the emulator not only the application's .vm files, but also all the OS .vm files. This way, when an application-level VM function calls some OS-level VM function, they will find each other in the same environment.
Testing Method: Normally, when you compile a program and run into some problems, you conclude that the program is screwed up and proceed to debug it. In this project the setting is exactly the opposite. All the test programs that we supply are error-free. Therefore, if their compilation yields any errors, it's the compiler that you have to fix, not the test programs. For each test program, we recommend going through the following routine:
Each of the programs listed below is designed to gradually unit-test specific language handling capabilities of your compiler.
Test Program |
Description |
Purpose |
Seven: |
Computes
the value of |
Tests how your compiler handles a simple program containing an arithmetic
expression with integer constants (without variables), a |
Conversion to binary:
|
Unpacks
a 16-bit number into its binary representation. The program takes the
16-bit value stored in
|
Tests how your compiler handles all the procedural elements of the Jack language, i.e. expressions (without arrays or method calls), functions, and all the language statements. The program does not test the handling of methods, constructors, arrays, strings, static variables and field variables. |
Square Dance:
|
A simple interactive "game" that enables moving a black square around the screen using the keyboard’s four arrow keys. While moving, the size of the square can be increased and decreased by pressing the "z" and "x" keys, respectively. To quit the game, press the "q" key. To test if your compiler has translated the program correctly, run the translated code in the VM Emulator and make sure that it works according to the above description. |
Tests how your compiler handles the object oriented constructs of the Jack language: constructors, methods, fields and expressions that include method calls. The program does not test the handling of static variables. |
Average: |
Computes the average of a user-supplied sequence of integers. To test if your compiler has translated the program correctly, run the translated code in the VM Emulator and follow the instructions displayed on the screen. |
Tests how your compiler handles arrays and strings. |
Pong: |
A ball is moving randomly on the screen, bouncing off the screen "walls". The user can move a small bat horizontally by pressing the keyboard’s left and right arrow keys. Each time the bat hits the ball, the user scores a point and the bat shrinks a little, to make the game harder. If the user misses and the ball hits the bottom horizontal line, the game is over. To test if your compiler has translated this program correctly, run the translated code in the VM Emulator and play the game (make sure to score some points, to test the part of the program that displays the score on the screen). |
Provides a complete test of how your compiler handles objects, including the handling of static variables. |
Complex Arrays: |
Performs five complex calculations using arrays. For each such calculation, the program prints on the screen the expected result versus the actual result (as performed by the compiled program). To test if your compiler has translated the program correctly, run the translated code in the VM Emulator and make sure that the actual results are identical to the expected results. |
Tests how your compiler handles complex array references and expressions. |
There are no intermediate milestones for this project -- but remember, you're building a friggin compiler and it will take time!