HackerDan.com

The following is a tutorial on using java CUP with JFlex for the project 2 assignment in CS4413/CS5413 at Lakehead University

Install and Setup

It is assumed that you have java and jflex (see http://hackerdan.com/programing/using-jflex/) installed and working.

Download CUP from http://www2.cs.tum.edu/projects/cup/ (direct link: http://www2.cs.tum.edu/projects/cup/java-cup-11a.jar)

Move java-cup-11a.jar onto your class path or add the directory java-cup-11a.jar is in to your class path.

For example, if java-cup-11a.jar is in /home/dan/comp_class/java-cup-11a, add /home/dan/comp_class/java-cup-11a to your class path. See http://hackerdan.com/programing/using-jflex/ for details on changing environment variables.

Create a directory named parser (this is where your code will go), and copy all the files included with the project from WebCT. The following files should be included:

lexer.flex
Driver.java
LEXSymbol.java
parser.cup
SrcLoc.java
test2.cmm
test1.cmm

Note that lexer.flex is different from project 1 and contains a complete lexer for use with this project. Also note that the Token class has been replaced by LEXSymbol.java which functions differently. You can use your solution from project 1 in place of lexer.flex but it will likely need some heavy modifications.

If you have JFlex installed from project 1 and a working java compiler everything should be ready to go.

Using Java CUP

First run JFlex on the lexer.java file to generate Lexer.java (see http://hackerdan.com/programing/using-jflex/ for details).


Add your changes to parser.cup (fill out the nonterminals, precedences and grammar sections, see the next section for tips) and run:

java -jar /home/dan/comp_class/java-cup-11a.jar parser.cup


This should generate parser.java and sym.java and have output similar to:

------- CUP v0.11a beta 20060608 Parser Generation Summary -------
0 errors and 0 warnings
42 terminals, 18 non-terminals, and 90 productions declared,
producing 192 unique parse states.
0 terminals declared but not used.
0 non-terminals declared but not used.
0 productions never reduced.
0 conflicts detected (0 expected).
Code written to "parser.java", and "sym.java".
---------------------------------------------------- (v0.11a beta 20060608)



If you get Errors that look like the following:

Error: Syntax error @ Symbol: LBRACK (unknown:82/19 - unknown:82/20)
Error : Illegal use of reserved word
......

It means there is a syntax error on the given line (in this case 82).



If you get a warning such as:

Warning : Scanner at 122(10): Unrecognized character '{' -- ignored

It means there is an illegal character in your .cup file (many of the common regex and EBNF characters are not supported in Java CUP).

If you get a warning such as:

Warning : Terminal "UMINUS" was declared but never used

It means one of your terminals or none terminal which was declared in your .cup was never used in your grammar. In some cases this is ok.

If you get a warning such as:

Warning : *** Reduce/Reduce conflict found in state #12
between lvalue ::= ID (*)
and type ::= ID (*)
under symbols: {ID}
Resolved in favor of the first production.

It means a conflict was found in your grammar where two rules have identical right parts and the parser is basically guessing which one to use. For example:

nterm1 ::= ID;
nterm2 ::= ID;

Will cause this error as the rules are the same.

If you get a warning such as:

Warning : *** Shift/Reduce conflict found in state #12
between lvalue ::= ID (*)
under symbol ID
Resolved in favor of shifting.

It means there is a conflict in your grammar where after shifting two rules are identical, for example:

nterm1 ::= TERM '+' nterm3;
nterm2 ::= TERM '+' ID;
nterm3 ::= ID;

In this case nterm1 and nterm2 are identical after ID is substituted in for nterm3.


Although grammar conflicts are warnings, they should not be ignored as they indicate there is likely a problem with your grammar despite the syntax being valid.

Warnings such as:

Warning : *** Production "formal ::= type ID " never reduced

mean that rule can never be reached from the given “start with” rule. This is a problem if you expect that rule to be part of your parser.


Keep fixing any warnings and errors until generation succeeds with no errors. Next we need to compile the generated code:

Compile LEXSymbol.java (from WebCT):

javac -classpath .:/home/dan/comp_class/java-cup-11a/java-cup-11a.jar parser/LEXSymbol.java

Replace /home/dan/comp_class/java-cup-11a/java-cup-11a.jar with the full path to java-cup-11a.jar on your system in the above and following examples (or set up your classpath so the -classpath argument is not needed).

Compile sym.java (generated by Java CUP):

javac -classpath .:/home/dan/comp_class/java-cup-11a/java-cup-11a.jar parser/sym.java

Compile parser.java (generated by Java CUP):

javac -classpath .:/home/dan/comp_class/java-cup-11a/java-cup-11a.jar parser/parser.java

Compile Lexer.java (generated by JFlex):

javac -classpath .:/home/dan/comp_class/java-cup-11a/java-cup-11a.jar parser/Lexer.java

Compile Driver.java (from WebCT):

javac -classpath .:/home/dan/comp_class/java-cup-11a/java-cup-11a.jar parser/Driver.java

If there were any errors or warnings while compiling, there is a issue with one of your specification files (.cup or .flex), something wrong with your environment variables (class path issue), or an issue relating to how your java package is set up.

Once everything is compiled you may run your parser like so:

java -classpath .:/home/dan/comp_class/java-cup-11a/java-cup-11a.jar parser.Driver parser/test.cmm

where the second argument is the path to your .cmm code file.

If there was an issue with your grammar or the code in the .cmm file is not valid, you will get error such as:

Syntax error parser/test.cmm:22:2 Got: 'else'

if the .cmm is valid you should go back to your .cup file and try to fix any issues and regenerate and recompile everything.

A successful run (assuming the code file is valid) will look like:

parsing [parser/test.cmm]
Lexeme for comment [/* Foo Class */]
Lexeme for comment [/* Main Class */]
Parsing Completed. Top symbol = #0

At this point you should have a parser capable of validating  a C– file, which is all that is required for the project. However if you would like to use Java CUP to make a C– interpreter capable of running simple C– code there are a few more steps needed which you can read about in the PDFs on the following link: http://www.cs.auckland.ac.nz/~bruce-h/lectures/330ChaptersPDF/ (particularly chapter 9).

Parser Specification

Java CUP’s specification file has five main sections:

Preliminaries
Any settings or emended code that will affect how the parser.java file is generated. In our case this section is provided for us and should not need any changes.

Code between “parser code {:” and “:}” is placed in the parser class in the generated parser.java file.

Terminals
This section lists all terminals that may be used in the parsers’ grammar. These terminals are the tokens from our JFlex scanner and in this case are provided for us.

The format of the terminal line is as follows:

terminal [TYPE] TERM [, TERM]*;

Where the optional TYPE parameter specifies what type the terminal objects listed are of and the TERM parameters list the terminals that may be used in the grammar section.

Non Terminals
Non terminals are the rules of the grammar and follow the same format as in the terminal section. Each terminal must be defined before it may be used and as with the terminals the type parameter is optional.

Example:

nonterminal classList, classDed, deck, formals, statement, assignment;

Note that both terminal and non terminal names cannot be CUP reserved words (”code”, “action”, “parser”, “terminal”, “non”, “nonterminal”, etc).

Precedences

Often grammar is ambiguous and this section lets us state the precedences and associatively of terminals outside of our grammar (allowing us to keep the grammar simple, and still resolve ambiguity). This section is optional if your grammar has no ambiguity.

The format is as follows:

precedence (left | right | nonassoc) terminal [, terminal]*;

These lines set the order of precedence, from highest to lowest, from bottom to top. For example:


precedence left ADD, SUBTRACT;
precedence left TIMES, DIVIDE;

Resolves the ambiguity in grammar such as:
A ::= A ADD A | A SUBTRACT A | A DIVIDE A | A TIMES A | a

with ADD and SUBTRACT having a lower precedence than TIMES and DIVIDE (multiplication and division will be performed before the addition and subtraction).

Any terminal not listed will be given the lowest precedence. See http://www2.cs.tum.edu/projects/cup/manual.html for more information.

Grammar

Finally the grammar section allows the specification of the parsers’ grammar in a BNF like format. Note that this format is not the same as the EBNF format that the grammar for C– is given in, and some rules and changes will need to be added and made.

The starting rule is specified with the “start with” tag as shown below:

start with classList;

An example of a simple grammar is shown below:

start with A;

A ::= A ADD A
| A SUBTRACT A
| A DIVIDE A
| A TIMES A
| a;


This is a simplistic explanation of the grammars in CUP, for more info see: http://www2.cs.tum.edu/projects/cup/manual.html.

Project Hints

• Don’t modify the code in Driver.java,  SrcLoc.java, or LEXSymbol.java. There should be no need for this project, however, looking over how they work will help in creating your parser and understanding how it works.
• Don’t modify the code in parser.java or Lexer.java manually, they should be generated via Java CUP and JFlex respectively. You can embed code in the specification file that will be placed in the generated .java file, however, there should be no need for this project.
• Make sure you have your class path settings right or give the full path to the Java CUP jar like in the examples given.
• Make sure you have the java package set up correctly. All class and java files should be in the parser package and in a directory with the same name.
• Don’t ignore warnings from Java CUP, they almost always indicate that something is wrong and needs fixing.
• If you use the given .jflex file the only file you need to submit is the .cup file, however, you may also include example outputs, test cases and screenshots.
• If you don’t use the given .jflex make sure to include yours and any .java files it uses. Also ensure that you note any changes you made. Your lexer from project 1 may need some changes to work with Java CUP, use the given .jflex files as an example.
• The grammar given in the project for C– will need changes to work with Java CUP, but should be equivalent.
• If you make any improvements to the given grammar, make sure to note them and why they were added so they are not marked as incorrect.
• Make sure to put your name and student number on everything (you would be surprised how many students forget this).
• Use Java CUP 11a beta 20060608 executable standalone Jar-package (this is what I will use to mark your project)

Resources

Java CUP

• Java CUP: http://www2.cs.tum.edu/projects/cup
• Java CUP Manual: http://www2.cs.tum.edu/projects/cup/manual.html
• Java CUP Download: http://www2.cs.tum.edu/projects/cup/java-cup-11a.jar

JFlex

• JFlex: http://jflex.de/
• JFlex Download: http://jflex.de/jflex-1.4.3.zip
• JFlex Manual: http://jflex.de/manual.html

Lectures/Tutorials

• Bruce Hutton’s Lecture Notes: http://www.cs.auckland.ac.nz/~bruce-h/lectures/330ChaptersPDF/

Examples

• CUP grammar for the Java programming language: http://www2.cs.tum.edu/projects/cup/javagrm.tar.gz
• CUP/JFLex interoperability: http://www2.cs.tum.edu/projects/cup/minimal.tar.gz
• CUP/JFLex sample project: http://www2.cs.tum.edu/projects/cup/demo.zip

The following is a tutorial on using JFlex for the project 1 assignment in CS4413/CS5413 at Lakehead University




Step 1: Download and Setup JFlex


The first step is to download and setup jflex (assuming you have java installed and setup correctly).

The link to download it is: http://jflex.de/jflex-1.4.3.zip
Once you have the zip file downloaded unzip it into a folder where you would like to install it. This can be any folder as long as your user account has permission to run the programs in it. In my case (using linux) I have installed it to /home/dan/compilers/jflex-1.4.3.



Next you need to add the bin directory in jflex-1.4.3 to the system’s path. How to do this is different on each OS.



For windows XP:
1. Start -> Control Panel -> System -> Advanced
2. Click on Environment Variables, under System Variables, find PATH, and click on it.
3. In the Variable Value text box add ;my_path_to_jflex\jflex-1.4.3\bin\ to the end  where “my_path_to_jflex” is your path to the jflex folder you installed. For example if you installed jflex to C:\Users\Dan\jflex-1.4.3 the text that you would add to the path would be ;C:\Users\Dan\jflex-1.4.3\bin\  make sure to not to delete the contents of the text box and only add to them.
4. Click OK -> OK -> OK untill you are back to the desktop.

See http://support.microsoft.com/kb/310519 for more information on system variables in xp.



For windows Vista and 7:
1. Click on the start menu and type “edit the system environment variables” into the search box in till you see the control panel short cut come up.
2. Click “edit the system environment variables” and then click Environment Variables on the window that pops up.
3. From the System variables list find Path and double click on it.
4. In the Variable Value text box add ;my_path_to_jflex\jflex-1.4.3\bin\ to the end where “my_path_to_jflex” is your path to the jflex folder you installed. For example if you installed jflex to C:\Users\Dan\jflex-1.4.3 the text that you would add to the path would be ;C:\Users\Dan\jflex-1.4.3\bin\ make sure to not to delete the contents of the text box and only add to them.
5. Click OK -> OK -> OK untill you are back to the desktop.



For Linux/Unix using the bash shell:
1. Open ~/.bashrc in your favorite editor (ex. nano ~/.bashrc).
2. At the end of the file add:

PATH=$PATH:your_path_to_jflex/jflex-1.4.3/bin
export PATH

Where your_path_to_jflex is your path to the folder where you installed jflex. For example my PATH line is PATH=$PATH:/home/dan/compilers/jflex-1.4.3/bin
3. Save the file.



Once you have updated the path on your system you may need to logout and back in or restart your shell before the changes take effect.



Windows users will also have to edit the jflex.bat file in jflex-1.4.3/bin and set JFLEX_HOME in the file to their correct value.

JFLEX_HOME should point to the directory where jflex is installed. For example if jflex was installed to C:\Users\Dan\jflex-1.4.3\ the line should be: set JFLEX_HOME = C:\Users\Dan\jflex-1.4.3\

Next the lines following the “only needed for JDK 1.1.x” and “for JDK 1.1.x” comments should be removed or commented out. And finally the “rem” on the last line should be removed. The file should look something like this:

@echo off
REM Please adjust the paths JFLEX_HOME and JAVA_HOME to suit your needs
REM (please do not add a trailing backslash)

set JFLEX_HOME=C:UsersDanjflex-1.4.3

REM -------------------------------------------------------------------

set CLPATH=%JAVA_HOME%libclasses.zip;%JFLEX_HOME%libJFlex.jar

REM for JDK 1.2
java -Xmx128m -jar %JFLEX_HOME%libJFlex.jar %1 %2 %3 %4 %5 %6 %7 %8 %9

Linux users may want to take a look at the jflex-1.4.3/bin/jflex script however, it should be fine by default.




Step 2: Using JFlex



Jflex can be used via it’s GUI or via the command line. To use the GUI simply type jflex on the command line/shell and the GUI should run. To pass an input file to jflex via the command line simply type jflex input_file where input_file is the name of the lexical specification file (in our case lexer.flex).



GUI
1. Click the browse button for the Lexical specification field and select your Lexical Specification file (lexer.flex).
2. If you want to output the java class in a different directory then listed in the output directory filed, click the browse button by the output field and select the new output directory.
3. Click generate.
4. Look at the Messages text box. If there are warnings or errors there is likely something wrong with the contents of your lexer.flex file, go through it and fix any errors and try to generate it again. If there are no errors or warnings your lexical analyzer should be created in the output directory as a .java file (in our case Lexer.java).



Command Line
1. Use the command line or shell to navigate to the directory with your lexical specification (lexer.flex).
2. Type in jflex input_file where input_file is the name of your specification (lexer.flex).
3. If there are warnings or errors there is likely something wrong with the contents of your lexer.flex file, go through it and fix any errors and try to generate it again.
4. If there were no errors or warnings your lexical analyzer should now be output in the same folder as a .java file (in our case Lexer.java).

For more details on install and running jflex see http://jflex.de/installing.html




Step 3: Using the Lexical Analyzer



For this assignment a Driver.java and Token.java file were given to you that contain the code to use the lexical analyzer generated as Lexer.java. To use them on the C– code provided you must first compile the java code using javac. Since Driver, Token and Lexer are all in the same package they must be in the same directory named lexer. To compile the code simple issue the following commands in your shell/command line:


javac Token.java
javac Lexer.java
javac Driver.java


If there was an error comping the Lexer.java file, there likely was a problem with your lexical specification.



If all the code complied with no errors or warnings you should be able to run the Driver program on some C– code by issuing the fallowing command:


java Driver cmm_file


Where cmm_file is the text file contain the C– code. For example if the code file is test.cmm the line should be java Driver test.cmm.

Ideally there should be not errors and the output should match the example output given (assuming you used the example input in test.cmm).




Assignment Tips

• Make sure all your class files are in the same folder named lexer and that this folder is in the java class path.
• There should be no need to make any changes to any of the .java files. All the work should be done in the lexer.flex file.
• Take a look at the contents of the Token.java file, the tokens that are returned by nextToken in the scanner should be of this type.
• Make sure to test your scanner on the given sample input/output.
• You can find the jflex documentation here: http://jflex.de/manual.html which will help you in creating the lexer.flex specification.
• http://www.cs.auckland.ac.nz/~bruce-h/lectures/330ChaptersPDF/ is also a good resource for using JFlex and CUP.

On Friday the 23rd, I travelled to University of Toronto to meet with Dr. Greg Wilson, several lecturers and the GSoC students who are working on their projects in one of the computer labs. The first item of the day was lunch with the other GSoC students at Ogrady’s (a local bar and grill) where I got to know them and more about the projects they where working on as well as more about the University of Toronto. The university is some what unique in location from others I have been to in Canada in that it’s camps is right in the city and there are no clear borders where the camps stops and the city begins. The constant activity and close proximity to everything you need is a nice change from being out in the rural land out side of Waterloo and even the smaller and less populated city of Thunder Bay and makes me almost wish I had done my undergrad in Toronto (I will definately have to apply to University of Toronto for graduate studies after I graduate from Lakehead).

The next event of the day was meeting with Dr. Wilson and the lecturers to hear their ideas for what visualisations and statistics they would like to see in a grade book plug in for Moodle (more on Moodle and the specifics of my project in my next post). The meeting consisted of going around the room and getting input from each lecturer about what they would like to see in such a plug in and the results were quite promising with many ideas for visualisations I had not yet considered and hearing from the teaching side of things which I have little experience with as a student. Over the weekend I have been going through my notes of the meeting and trying to sort out what ideas will fit in the scope of the project, what ideas are doable and what these visualisations might look like. One concern that was raised at the meeting and will have to be dealt with in relating to what statistics and visualisations will be protecting the personal information and privacy of the student and what information (if any) should instructors have about a students past performance in their program or classes.