Assignment 5: Write a recursive-descent parser (5 points)

Due date: March 22 ( extended to March 29 11:59pm)

Where to submit

Submit your assignment at the web submission site. We will use your last submission for your final marks for this assignment. For each submission you will get your marks instantly by email. Note that this time the test casess are randomized, which means that it may indicate different error cases even when you submit the same program.

Please test your program on our sample inputs and other cases devised by you before submission.  Passing the sample inputs will not guarantee a high mark. You need to fully understand the grammar and implement that grammar correctly so that your parser can cope with all situations.

Purpose of the Assignment

• learn how to parse a language using recursive descent method;
• learn how to use a scanner. We have learnt how to generate and use a scanner in A4. In A4, scanner, parser, and their generators are all mixed. Now you need to identify the pertinent classes for the scanner, and learn how to invoke the scanner.

Assignment specification

The purpose of this assignment is to understand that topdown recursive parser is easy to construct manually, but it is inefficient when it runs. 

You are required to write a Java program that parses programs written in our Tiny language, without the help of a parser generator. Please follow the recursive-decent parser example given in the lecture. You only need to judge whether a Tiny program is syntactically correct or not. You are not required to handle the ambiguity of the grammar.

You will write a Java class called A5.java, which is the parser for our Tiny language. The main method in A5.java should be:

public static void main(String[] args) throws Exception {
	//construct the token array
	BufferedWriter bw=new BufferedWriter(new FileWriter("a5.output"));
	A5Scanner scanner = new A5Scanner(new FileInputStream(new File("A5.tiny")));
	// note that yylex() is the default method to get the next token in scanner that is generated by JLlex.
	Symbol token; 
	while ((token=scanner.yylex()).sym!= A5Sym.EOF) {
		tokens.add(token);
	}
	tokens.add(token);   // add EOF as the last token in the array
	boolean legal= program() && nextToken().sym==A5Sym.EOF;
	bw.write((legal)?"legal":"illegal");
	bw.close();
}

The commands to test your program are:

 javac A5.java A5Scanner.java A5Sym.java Symbol.java
 java A5

Please make sure that those two commands can run without any other classes. That is, to test your program, you should create a clean directory with no other classes, no JLex, no java_cup. All you have in this directory are those 4 classes and the input file.  

If a5.input is a correct Tiny program,the output file a5.output will contain a single word "legal"; otherwise a word "illegal". Please note that the program may run several minutes to process our sample Tiny program.

Notice how slow this program is and why it is better to use other parsing methods.

In addition to the parser class itself, you need to define the following auxiliary classes:

1. The scanner called A5Scanner.java, which is generated using JLex. You can reuse the scanner that is produced in previous assignments.  The name of the scanner is called A5Scanner. Note the function to get next token is called yylex().
2. Symbol.java: this is the class to represent the tokens. You should use the Symbol.java class from java_cup.runtime package.
3. A5Sym.java: this is the class to store the types of the tokens. You can either manually produce that class, or reuse the token type class generated in assignment 4.

What to submit

You need to submit the following java files:

1. your java parser named A5.java
2. Your scanner named A5Scanner.java
3. Your symbol type class named A5Sym.java

You do not need to submit Symbol.java. It is the same for everyone, and we will provice that class when we run the marking program.

Marking scheme

yourMark=0;
for (each of the 10 tests A5.tiny) {
    if (your program runs longer than 5 minutes) {
        break;
    }
    if (A5.tiny is legal program && a5.output says "legal")  
           yourMark+=0.5;
     if (A5.tiny is not a correct Tiny program && a5.output says "illegal" )
           yourMark+=0.5;
      
 } 
yourMark+=(yourTime>averageTime)?0 : fastestProgram/yourTime;

There will be another bonus mark (maximal one) depending on the speed of your program.
If your program enounters an infinite loop for one test case, we will terminate your program and will not continue the test on other cases.