Original URL: http://www.theregister.co.uk/2006/05/23/javacc_parser_analyser/

JavaCC: Don't talk back

Implementing a parser-analyser

By John Hunt

Posted in Developer, 23rd May 2006 15:23 GMT

In many cases, with the advent of XML, if data must be exchanged, or information read, a simple solution is to mark that document up using XML and then parse it using an XML parser.

However, in some situations the documents to be processed may not be in XML format. This could be because of legacy systems, external constraints or because they adhere to other standards. In such situations you still need to parse the documents to ensure that they conform to whatever standard is expected, to analyse the contents of such documents to determine the information they provide and to take some action based on that information. To do this you may implement your own parser-analyser or you could choose to look at an existing parser generator tool. Probably the best stabled parser generator tool is JavaCC (Java Compiler Compiler).

Java CC is a parser generator in the best tradition of tools such as YACC (Yet Another Compiler Compiler). JavaCC started out life as Jack and was developed by Sun Microsystems. It was then passed to a company called Metamata and renamed JavaCC. It is now an open source project and is very widely used.

JavaCC offers the Java developer a tool that processes a grammar specification and produces a set of Java classes that can read and analyse input that matches that grammar. JavaCC also provides additional tools that can be used with the main JavaCC tool such as the JJTree tree building tool for displaying grammars. The grammar to be analysed is defined in a BNF-like notation that is quick to learn and allows Java to be embedded within it (to allow callbacks to your own Java code).

Obtaining JavaCC

You can download JavaCC from the official JavaCC website. From here you can download the latest version of the JavaCC classes (or indeed the source if you so wish). What you get when you download JavaCC Binary distribution is:

You can also find sample JavaCC Grammars here.

A useful textbook is Aho, R. Sethi, and J.D. Ullman, Compilers: Principles, Techniques and Tools, Prentice Hall, 1986. You can buy it at Cash 'n' Carrion.

A Sample Grammar

A JavaCC grammar file can be divided into a number of parts. These parts are:

Each of these is described in a little more detail below:

A List of Options

The developer can influence the way in which the grammar is processed using these options (which may also be specified from the command line if the JavaCC command is being used). In the following example, we declare the LOOKAHEAD option that specifies number of tokens to look ahead before making a decision at a choice point during parsing:

options {
   LOOKAHEAD=2;
}

Other options include STATIC (which indicates whether a static only set of methods should be produced), DEBUG_PARSER (which can be used to include debugging information in the generated parser and IGNORE_CASE (which indicates whether the grammar should be case sensitive or not).

Java Compilation Unit

The Java compilation unit is enclosed between PARSER_BEGIN(name) and PARSER_END(name) . The name that follows PARSER_BEGIN and PARSER_END must be the same and this identifies the name of the generated parser. This allows you to provide definitions to be used with the generated Java parser class. For example, in the following code snippet we import the java.io package and define a main method. This allows the resulting SimpleCalculator parser class to be used stand alone. The main method reads a data file called “test.dat” which is then parsed by the generated SimpleCalculator parser class.

PARSER_BEGIN(SimpleCalculator)
import java.io.*;

public class SimpleCalculator {
   public static void main(String [] args) throws Exception {
      File file = new File("test.dat");
      System.out.println("Reading: " + file.getAbsolutePath());
      FileReader reader = new FileReader("test.dat") ;
      SimpleCalculator sc = new SimpleCalculator(reader);
      while (true) {
         sc.calc();
      }
   }
}

PARSER_END(SimpleCalculator)

The Lexical Specification

Next we have our lexical specification. This defines the tokens to be recognised when parsing data input. For example:

SKIP:
{
   " "
|   "\r"
}

TOKEN:
{
   <NUMBER:(<DIGIT>)>
|  <DIGIT:["0"-"9"]>
|  <EOL: "\n" >

}

This specifies that white space and carriage returns should be skipped. It then defines the set of tokens to be understood by the parser. In this case it means that NUMBERs are defined as being digits in the range 0 to 9. Finally the EOL (or End Of Line) is defined to be a Newline (“/n”).

A list of grammar productions

The final section of the .jj file defines the context-free grammar that is a set of grammar productions (rules) that define what the legal syntax for the input data should be. In the case of a parser to analyse a programming language this would contain the grammar rules for that language. In our case we will define a very simple set of rules that define a very simple syntax. The syntax will allow two integers to be added or subtracted. Thus the set of productions for this grammar might be:

expr := element + element
|  element – element
number := digit
digit := [0 – 9]
EOL = “\n”

We will define this grammar in a JavaCC .jj file. The resultant parser will check the input has a legal format as defined by the grammar file and will then print out the result of the addition or subtraction.

The following is the list of grammar productions defined for our simple example in JavaCC syntax:

void calc():
{ 
    double x;
}
{
   x=expr() <EOL> {System.out.println(x); }   
|  <EOF> {System.exit(0); }
}

double expr():
{
   double a;
   double b;
}
{
   a = element() (
   "+" b=element() {a += b; }
|  "-" b=element() {a -= b;}
   )
   { return a; }
}


double element():
{
   Token t;
}
{
   t=<NUMBER> { System.out.println("t: " + t) ; return Double.parseDouble(t.toString()); }
}

This states that:

A calc element is comprised of

If the expression is found then the value returned is printed out while if an end of file marker is found then the program terminates. Note that in this way call backs can be made to any arbitrary Java code. It is via this mechanism that the parser can be linked into your own code.

Note that the format used to define the grammar is a translation of BNF (Backus-Naur-Form) notation used with the JavaCC compiler.

The remaining grammar productions define what comprises an expression and an element. In particular an expression is defined to be either:

Note in our case we also specify that the two elements should be added or subtracted and the result returned from this production.

Finally an element is defined as being any type of NUMBER. Note that the result of something being a number is that we return that number as a double value.

Generating the Parser

We are now in a position to generate our Java implementation parser class. This is done using the JavaCC program. For example:

JavaCC -NOSTATIC -OUTPUT_DIRECTORY=source SimpleCalculator.jj

The options included on the command line to the JavaCC program specify:

With the javacc.jar file on the classpath, the resulting output generated is:

Java Compiler Compiler Version 4.0 (Parser Generator)
(type "JavaCC" with no arguments for help)
Reading from file SimpleCalculator.jj . . .
File "TokenMgrError.java" does not exist.  Will create one.
File "ParseException.java" does not exist.  Will create one.
File "Token.java" does not exist.  Will create one.
File "SimpleCharStream.java" does not exist.  Will create one.
Parser generated with 0 errors and 1 warnings.

This generates 7 classes as listed below:

ParseException.java
SimpleCalculator.java
SimpleCalculatorConstants.java
SimpleCalculatorTokenManager.java
SimpleCharStream.java
Token.java
TokenMgrError.java

As a combination these classes define the SimpleCalculator parser. If you are interested, the primary class to look at is the SimplerCalculator.java class, as it is this one which is both the entry point and the primary implementation of the parser.

To execute this parser we first need a simple file to process. In our case the file is called test.dat and contains the following:

2 + 3

4 – 6

We can compile the classes for the classes generated by JavaCC (again with the javacc.jar on the classpath). The parser can then be run by issuing the following:

java SimpleCalculator

The result of running the parser is:

Reading: C:\experis\projects\javacc\test.dat
t: 2
t: 3
5.0
t: 4
t: 6
-2.0

Summary

JavaCC is a very powerful tool that can be used to create parsers for a wide range of data formats, including RTF, Visual Basic, Java itself, HTML, MHEG-5, C, C++, Excel files, numeric formula, email headers etc. It can be easily integrated into your own code as well as being used in stand-alone fashion as illustrated here.

Complete Listing of SimpleCalculator.jj

options {
  LOOKAHEAD=2;
}

PARSER_BEGIN(SimpleCalculator)
import java.io.*;

public class SimpleCalculator {
   public static void main(String [] args) throws Exception {
      File file = new File("test.dat");
      System.out.println("Reading: " + file.getAbsolutePath());
      FileReader reader = new FileReader("test.dat") ;
      SimpleCalculator sc = new SimpleCalculator(reader);
      while (true) {
         sc.calc();
      }
   }
}

PARSER_END(SimpleCalculator)

SKIP:
{
   " "
|   "\r"
}

TOKEN:
{
   <NUMBER:(<DIGIT>)>
|  <DIGIT:["0"-"9"]>
|  <EOL: "\n" >

}   

void calc():
{ 
    double x;
}
{
   x=expr() <EOL> {System.out.println(x); }   
|  <EOF> {System.exit(0); }
}

double expr():
{
   double a;
   double b;
}
{
   a = element() (
   "+" b=element() {a += b; }
|  "-" b=element() {a -= b;}
   )
   { return a; }
}


double element():
{
   Token t;
}
{
   t=<NUMBER> { System.out.println("t: " + t) ; return Double.parseDouble(t.toString()); }
}