Use Java Cup to parse Tiny programs (6 points+1 bonus)

Due date: Feb 27/29

Where to submit

You must 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.

You must 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 must fully understand the grammar and implement that grammar correctly so that your parser can cope with all situations.

Purpose

Use JavaCup to parse Tiny programs. Your program will be able to judge whether a program is valid or not with respect to its syntax.

Assignment Specification

This assignment is to parse Tiny program using JavaCUP.

You need to write a JavaCUP file and a JLex file so that a parser for Tiny language can be generated. The parser will be able to tell whether a Tiny program is syntactically correct. You need to rewrite EBNF grammar into CFG that is acceptable by JavaCUP. Comments in Tiny program should be thrown away in the scanner.

We will run the following commands to generate the scanner and the parser. You can modify the lex file you created in assignment 2.

   >java JLex.Main A3.lex
   >java java_cup.Main -parser A3Parser -symbols A3Symbol < A3.cup 
   >javac A3.lex.java A3Parser.java A3Symbol.java A3User.java 
   >java A3User

The program A3User invokes the parser and is defined as below:

import java.io.*;
class A3User {
  public static void main(String[] args) throws Exception {
       File inputFile = new File ("A3.tiny");
       A3Parser parser= new A3Parser(new A3Scanner(new FileInputStream(inputFile)));
       Integer result =(Integer)parser.parse().value;
       FileWriter fw=new FileWriter(new File("A3.output"));
       fw.write("Number of methods: "+ result.intValue());
       fw.close();
  }
}

If your lex and cup files are correct, all of those command and especially A3User will run smoothly without any error report, and an A3.output file will be created which should consists of one line as follows:

Number of methods: numberOfMehtodsInA2Input

If your programs are not correct, during the process there will be some error messages.

Here is a sample A3.tiny file and A3.output file. For incorrect Tiny programs such as A31.tiny and A32.tiny, your parser will report an error and no A3.output file is generated.

Note that you don't need to write any Java programs. The parser and the scanner are generated from your cup and lex specifications. Also, we will test your program on our own data.

What to submit

You need to turn in 2 files: the JLex file, named A3.lex, which can be used to generate the scanner; the javaCUP file, named A3.cup, which can be used to generate the parser.

Steps to work on the assignment

Run calc.lex and calc.cup example.

Change calc.lex and calc.cup to A3.lex and A3.cup. You need to change every occcurrence of Calc to A2 in the lex, cup, and script file. Make sure that you can run A3. In this step, try to understand how A3.lex and A3.cup work together. For example, in the following calc.lex file, CalcScanner needs to be changed to A3Scanner, CalcSymbol needs to be changed to A3Symbol.

 
import java_cup.runtime.*;
%%

%implements java_cup.runtime.Scanner
%type Symbol
%function next_token
%class CalcScanner
%eofval{ return null;
%eofval}

IDENTIFIER = [a-zA-Z_][a-zA-Z0-9_]*
NUMBER = [0-9]+
%%
"+" { return new Symbol(CalcSymbol.PLUS); }
"-" { return new Symbol(CalcSymbol.MINUS); }
"*" { return new Symbol(CalcSymbol.TIMES); }
"/" { return new Symbol(CalcSymbol.DIVIDE); }
{NUMBER} { return new Symbol(CalcSymbol.NUMBER, new Integer(yytext()));}  
\r|\n {}
. {}

Remove the evaluation function. This assignment won't evaluagte the values of expressions, hence we should remove that functionality. To do so, we need to remove the RESULT assignment statements in the cup file:

 
terminal          PLUS, MINUS, TIMES, DIVIDE, LPAREN, RPAREN;
terminal Integer  NUMBER;
non terminal Integer expr;
precedence left PLUS, MINUS;
precedence left TIMES, DIVIDE;
expr      ::= expr:e1 PLUS expr:e2 {: RESULT = new Integer(e1.intValue()+ e2.intValue()); :}  
            | expr:e1 MINUS expr:e2  {: RESULT = new Integer(e1.intValue()- e2.intValue()); :} 
            | expr:e1 TIMES expr:e2  {: RESULT = new Integer(e1.intValue()* e2.intValue()); :} 
            | expr:e1 DIVIDE expr:e2  {: RESULT = new Integer(e1.intValue()/ e2.intValue()); :} 
            | LPAREN expr:e RPAREN {: RESULT = e; :} 
	    | NUMBER:e {: RESULT= e; :}
	    ;

That is, your A3.cup file should look like this:

 
terminal          PLUS, MINUS, TIMES, DIVIDE, LPAREN, RPAREN;
terminal Integer  NUMBER;
non terminal Integer expr;
precedence left PLUS, MINUS;
precedence left TIMES, DIVIDE;
expr      ::= expr PLUS expr {:  :}  
            | expr MINUS expr  {: :} 
....
	    ;

Note that lables like e1 and e2 are removed, along with the action code inside the brackets {: and :} .

Expand A3.cup file with one more rule

terminal          PLUS, MINUS, TIMES, DIVIDE, LPAREN, RPAREN;
terminal Integer  NUMBER;
non terminal Integer expr;
precedence left PLUS, MINUS;
precedence left TIMES, DIVIDE;
expr      ::= expr:e1 PLUS expr:e2 {: RESULT = new Integer(e1.intValue()+ e2.intValue()); :}  
            | expr:e1 MINUS expr:e2  {: RESULT = new Integer(e1.intValue()- e2.intValue()); :} 
            | expr:e1 TIMES expr:e2  {: RESULT = new Integer(e1.intValue()* e2.intValue()); :} 
            | expr:e1 DIVIDE expr:e2  {: RESULT = new Integer(e1.intValue()/ e2.intValue()); :} 
            | LPAREN expr:e RPAREN {: RESULT = e; :} 
	    | NUMBER:e {: RESULT= e; :}
	    ;

Common Errors

Shift/reduce error: Most probably it is because that your grammar is ambiguious. You can either remove the ambiguity as we discussed in class, or add Precedence rules. The simplest way to remove the ambiguity is to remove reduldant rules.

Marking scheme

yourMark=0;
if ( A3.lex and A3.cup  files not submitted or file names are incorrect) return; 
if (  A3.lex.java && A3Parser.java && A3Symbol are generated after the second command) {
   if ( generated programs are compiled correctly && 
        A3Scanner.class, A3Parser.class and A3Symbol.class are generated) {
            for (each of the 12 test A3.tiny) {
                  if (A3.tiny is valid && A3.output is generated && method count is correct)  {
                                 yourMark+=0.5;
                  if (A3.tiny is not a correct Tiny program && A3.output is not generated )
                                 yourMark+=0.5;
             }
          }
      }
 } 
yourMark+= (size of your lex and cup file<500)?0.5*500/fileSize:0; 
for (each day of your late submission)  yourMark=yourMark*0.7;