Project 9 - The Compiler (a)

In this part of the course you will have to read chapter 9 of the book (Compiler (a)), after reading the chapter you will have to read the following instructions to be able to implement project 9.

Instructions:

Objectives: Develop a syntactic analyzer that parses Jack programs according to the Jack grammar. The output of the analyzer should be written in XML format, following the example given in Fig. 9-6 in the book.

The contract: Write the Jack Analyzer program. Use it to parse the three .jack files that we supply. Your Analyzer should generate three corresponding .xml files. These files should be identical to the compare-files supplied by us.

Test Programs

We developed a simple interactive game, called Square Dance, which will be used to test your compiler in both chapters 9 and 10. Although the function of this application is irrelevant to the compilation process and to these chapters, we describe it briefly. Square Dance is a trivial “game” that enables you to move 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. The game implementation is organized in three classes:

• Class Main: Initializes a new game and starts it.
• Class Square: Implements an animated square. A square object has a screen location and size properties, and methods for drawing, erasing, moving, and size changing.
• Class SquareGame: Runs the game according to the game rules.

These classes are written in Jack. It may be a good idea to take a look at the source code and get a general feeling of how the application is working. If you want, you can also compile the three classes using the supplied Jack compiler, and then play the game on the VM Emulator. These activities are completely irrelevant to the analyzer implementation, but they serve to highlight the fact that the test programs are not just plain text (although this is perhaps the best way to think about them in the context of this project).

Test files: We provide three sets of files:

Source code: Main.jack, Square.jack, SquareGame.jack

Tokenizer output (compare files): Main.txt, Square.txt, SquareGame.txt

Analyzer output (compare files): Main.xml, Square.xml, SquareGame.xml

Since the output files that your tokenizer and analyzer will create will have the same names and extensions as the compare files, we suggest putting the latter files in a separate directory.

Stage 1: Tokenizer

First, implement the Jack tokenizer. When applied to a text file that contains Jack code, the tokenizer should produce a list of tokens, stored in a text file. Each token should be printed in a separate line along with its classification: symbol, keyword, identifier, integer constant, and string constant. The classification should be recorded using XML tags. For example, the input “let x=5+yy; let city=”Paris”;” should generate the following output:

<keyword>    let    </keyword>
<identifier> x      </identifier>
<symbol>     =      </symbol>
<integerConstant> 5 </integerConstant>
<symbol>     +      </symbol>
<identifier> yy     </identifier>
<symbol>     ;        </symbol>
<keyword>    let     </keyword>
<identifier> city    </identifier>
<symbol>     =      </symbol>
<symbol>     Paris   </symbol>
<symbol>     ;      </symbol>

A slight difficulty, and a solution: Four of the symbols used in the Jack language (<,>,",&) are also used for XML markup, and thus they cannot appear as data in XML files.  To solve the problem, your tokenizer should output these tokens as &lt, &gt, &quot, and &amp, respectively.  For example, in order for the text “<symbol> & </symbol>” to be displayed in an XML viewer, the source XML should be written as “<symbol> &amp </symbol>”.

Testing: As a temporary convention, give the output files of your tokenizer the extension “.txt”. Apply your tokenizer to the three test files: Main.jack, Square.jack, and SquareGame.jack. This should generate the three output files Main.txt, Square.txt, and SquareGame.txt. Next, use the TextComparer utility to compare your output files to the three supplied compare files.

Stage 2: Parser

Next, implement the Compilation Engine. Write each method of the engine, as specified in the API, and make sure that it emits the correct XML output.

Implementation tips:

• The indentation of the XML is only for readability. The XML viewer ignores white space.
• Note that conceptually speaking, the output of the tokenizer is embedded within the XML output. In other words, the parser builds the language “super structure” on top of the terminal tokens.
• You may want to start by writing a parser that can handle everything except expressions. For example, assume that the only expressions that the input source code can contain may be single identifiers, and handle everything else. Next, extend the parser to handle expressions as well.

Testing: Give the output files of your analyzer the extension “.xml”. Apply your analyzer to the three test files: Main.jack, Square.jack, and SquareGame.jack. This should generate the three output files Main.xml, Square.xml, and SquareGame.xml. Next, use the TextComparer utility to compare your output files to the three supplied compare files.

Resources

• ComparisonFiles.zip , SquareDance.zip (download): Extract to an empty directory, and keep the default directory structure as is.

• Chapter 9 of the book - "Compiler (a)". 

• Appendix A - HDL.

• Appendix B - Test Script Language.

• TextComparer (Software)

• Guidelines for submitting.

• Submission is done through the Administratives page.