MCS-287 Lab 2: Parsing (Spring 2006)

Due: March 22, 2006


In this lab, you will complete a recursive descent parser for Jay, starting from a skeleton. You will also test your parser by running it on various input files and seeing the corresponding abstract syntax trees printed out.

Plan of work

Start by downloading and reading the skeleton version of as well as the other file you will need, The comment at the start of the first one tells you what changes you need to make. The second one doesn't need any changes; you just need to make use of it.

In addition to these two files, you will need the file from the prior lab. If you were not successful in the prior lab, you should talk with me about this. At worst, I can give you a copy of my version of this file. However, I'd prefer to save that for extreme cases; my preference would be to work with you on resolving outstanding issues in your version.

As in the lexical analyzer, you shouldn't feel compelled to replace each instance of ... with the actual missing Java code before doing any testing. You can start by commenting most of them out or replacing them with an appropriate placeholder like

e = null;

You can then test the parts you have written and incrementally alternate between writing more and testing more.

To compile and test the parser, you would give the following two commands in a shell, assuming that you have your testing input in a file called testInput1.jay:

javac *.java
java ConcreteSyntax testInput1.jay

The result of this test should be a syntax error message if testInput1.jay does not contain a legal Jay program, or a big nested parenthesized structure describing the abstract syntax tree.

Your goal in testing is to show that each feature works correctly. Your tests can include the Jay program in Figure 2.19 on page 43, but make sure that they also include programs that exercise other parts of the grammar.

What you should turn in

Please turn in a printout of your final version of You should also turn in evidence of your testing of this final version. Remember that your goal in the tests is to show that each case works. Repeating the same case excessively many times will distract from that goal.

Course web site:
Instructor: Max Hailperin <>