Combine Java CUP with Katja

This short tutorial shows how to use Katja together with Java CUP. The complete code of this tutorial including the necessary JAR files is available as ZIP archive:

A language for Formulas

Assume you want to write a parser and evaluator for simple formulas such as:

false \\/ !false \\/ foo(x y z)

These formulas follow the following grammar (in BNF:)

formula   ::= expr
expr      ::= 'false'
            | '!' expr
            | expr '\\/' expr
            | predicate
predicate ::= name '(' params ')'
            | name '(' ')'
variable  ::= name
params    ::= variable
            | variable params
name      ::= 'A-Za-z'*


In order to follow the tutorial you have to do the following preparations: 1. Create a fresh folder to do the tutorial 2. Inside that folder create the folders “bin”, “formulas”, and “tests” 3. Copy the files “JFlex.jar”, “katja.jar”, and “java-cup.jar” into your tutorial folder

The Katja File

At first we start with the abstract syntax description by giving a Katja-File (“formulas.katja”)

specification Formulas

backend java {
  package formulas.ast
  import java.lang.String
  import java.lang.Integer

external String

Formula    ( Expr top )

Expr = False     ( )
     | Or        ( Expr left, Expr right )
     | Not       ( Expr expr )
     | Predicate ( String name, VariableList params )

VariableList * Variable
Variable   ( String name )

We now use the following command to generate the classes for building the AST.

java -jar katja.jar -b java -o -j formulas.katja

This command will generate two files, namely the files “Formulas.jar”, which contains the generated classes, and the file “katja.common.jar” which contains the common Katja classes, that are needed at runtime. The

The Java CUP File

We now write the Java CUP file that uses the generated Katja code to build up the AST (“formulas.cup”)

package formulas;

import static formulas.ast.Formulas.*;
import formulas.ast.*;
import java_cup.runtime.Symbol;

terminal Symbol FALSE, NOT, OR, LPAREN, RPAREN;
terminal String NAME;
non terminal Formula formula;
non terminal Expr expr;
non terminal Predicate predicate;
non terminal VariableList params;
non terminal Variable variable;

precedence left OR;
precedence right NOT;

formula ::= expr:e {: RESULT = Formula(e); :} ;

expr ::= FALSE:f
         {: RESULT = False(); :}
       | NOT expr:e
         {: RESULT = Not(e); :}
       | expr:e1 OR expr:e2
         {: RESULT = Or(e1,e2); :}
       | predicate:p
         {: RESULT = p; :}

predicate ::= NAME:n LPAREN params:p RPAREN
          {: RESULT = Predicate(n,p); :}
            | NAME:n LPAREN RPAREN
          {: RESULT = Predicate(n,VariableList()); :}

params ::= variable:v
           {: RESULT = VariableList(v); :}
        | variable:v params:p
           {: RESULT = p.add(v); :}

variable ::= NAME:n {: RESULT = Variable(n); :} ;

We use the following command to generate the Java source files from the CUP file:

java -cp java-cup.jar java_cup.Main -destdir formulas -parser FormulaParser formulas.cup

JFlex File

For generating the scanner wie use JFlex and define the following JFlex file (“formulas.jflex”)

package formulas;
import java_cup.runtime.*;
%class FormulaScanner

name  = [A-Za-z]*
ws = [ \\t\\n\\r]
{ws}*       { }
"false"     { return new Symbol(sym.FALSE, yyline, yycolumn); }
"!"         { return new Symbol(sym.NOT, yyline, yycolumn); }
"\\\\/"        { return new Symbol(sym.OR, yyline, yycolumn);  }
"("         { return new Symbol(sym.LPAREN, yyline, yycolumn); }
")"         { return new Symbol(sym.RPAREN, yyline, yycolumn); }
{name}      { return new Symbol(sym.NAME, yyline, yycolumn, yytext()); }
<<EOF>>     { return new Symbol(sym.EOF, yyline, yycolumn); }

To generate the scanner we use the following command:

java -jar JFlex.jar -d formulas formulas.jflex

Compile the generated sources

The following command compiles the sources into the “bin” folder:

javac -cp java-cup.jar:Formulas.jar:katja.common.jar -d bin formulas/*.java

Create a Main Class

We now create a main class “formulas/” to call the parser:

package formulas;


import formulas.ast.Formula;

public class Main {

   public static void main(String[] args) throws Exception {
      final InputStream s = new FileInputStream(args[0]);
      final FormulaScanner scanner = new FormulaScanner(s);
      final FormulaParser parser = new FormulaParser(scanner);
      final Formula f = (Formula) parser.parse().value;

We can compile this class as before:

javac -cp java-cup.jar:Formulas.jar:katja.common.jar -d bin formulas/*.java


Finally, we can create a test file “tests/test1.formula” and call the Main class:

java -cp bin:Formulas.jar:java-cup.jar:katja.common.jar formulas.Main tests/test1.formula