09 November 2009

Building a simple Expression language with JJTree/Javacc . My Notebook

Last year, I described how to use the JAVACC a parser/scanner generator for java. This WE, I've played with JJTREE: JJTree is a preprocessor for JavaCC that inserts parse tree building actions at various places in the JavaCC source.. Here I describe how to build a simple expression language to find an object in a simple 'JSON 'object only built with arrays, java.util.List, java.util.Map, String, etc... . For example: exectuting a[5].year on {"d":12345, "b":null, "c":false, "a":["Hello", "World", true, false, null, {"name":"Pierre", "year":2009}]} would return: 2009

The JSONPath.jjt header


options {
/** create a pure parser */
STATIC=false;
DEBUG_PARSER=false;
ERROR_REPORTING=true;
NODE_USES_PARSER=false;
/** this class will build the nodes, must implement:"static SimpleNode JSONPathCompiler.jjtCreate(int id)" */
NODE_FACTORY="JSONPathCompiler";
/** The node of the Abstract Syntax Tree will extend this class */
NODE_CLASS="JSONNode";
}

The tokens


Defines the regular expressions to be recognized by the lexer.
TOKEN: {
<#LETTER: ["_","a"-"z","A"-"Z"] >
| <#DIGIT: ["0"-"9"] >
| <DOT: ".">
| <INTEGER: <DIGIT> (<DIGIT>)* >
| <IDENTIFIER: <LETTER> (<LETTER>|<DIGIT>)*>
| <OPEN_ARRAY: "[">
| <CLOSE_ARRAY: "]">
}

The grammar


An expression is at least an 'object' or an 'array' followed by any number of 'objects' or 'arrays'. '#EXPRESSION' means that we want this node to be named 'JJTEXPRESSION' instead of the default, 'JJTexpr'. This expression with return a JSONNode.
JSONNode expr() #EXPRESSION:{}
{
(array() | object() ) ( array() | <DOT> object() )* <EOF>
{
/** jjtThis is the current AST node */
return jjtThis;
}
}
An array is an integer surrounded by two brackets. The AST node created by Javacc contains an object called 'value' holding whatever your want (here, the value of the index ).
void array() #ARRAY:{Token i;}
{
<OPEN_ARRAY> i=<INTEGER> <CLOSE_ARRAY>
{
jjtThis.value=new Integer(i.image);
}
}
An object/map is just a name.
void object() #OBJECT: { Token name;}
{
( name=<IDENTIFIER> )
{
jjtThis.value= name.image;
}
}

The Custom AST node

By default, all the node are an instance of the class SimpleNode generated by JJTree. Here, I've choosen to use a custom node extending SimpleNode.
public static class JSONNode
extends SimpleNode
{
JSONNode(int i)
{
super(i);
}
(...)
}

static SimpleNode jjtCreate(int id)
{
return new JSONNode(id);
}
(...)

Implementing the expression language


The method 'eval' will implement the expression language itself. For example, a node of type "JJTEXPRESSION:" will get the values of its children, a node of type "JJTARRAY" will test if the object is a list or an array and will use the index stored in value to retrieve the indexed data.
public Object eval(Object o)
{
if(o==null) return null;
switch(this.id)
{
case JJTEXPRESSION:
{
if(getChildrenCount()==0) return null;
for(int i=0;o!=null && i< getChildrenCount();++i)
{
o=at(i).eval(o);
}
return o;
}
case JJTARRAY:
{
int index= Integer.class.cast(this.value);
if(o instanceof java.util.List)
{
java.util.List L=java.util.List.class.cast(o);
if(index<0 || index>= L.size()) return null;
return L.get(index);
}
else if(o.getClass().isArray())
{
Object L[]=(Object[])o;
if(index<0 || index>= L.length) return null;
return L[index];
}
return null;
}
case JJTOBJECT:
{
if(o instanceof java.util.Map)
{
java.util.Map M=java.util.Map.class.cast(o);
return M.get(this.value);
}
return null;
}

default:return null;
}
}


Compiling Testing


$(JCC)/jjtree JSONPath.jjt
$(JCC)/javacc JSONPath.jj
javac JSONPathCompiler.java
java JSONPathCompiler <expression>

Results


Compiling a[5]
Eval {"d":12345, "b":null, "c":false, "a":["Hello", "World", true, false, null, {"name":"Pierre", "year":2009}]}
Result is:{name=Pierre, year=2009}

Compiling a[1]
Eval {"d":12345, "b":null, "c":false, "a":["Hello", "World", true, false, null, {"name":"Pierre", "year":2009}]}
Result is:World

Compiling a[1][3][0]
Eval {"d":12345, "b":null, "c":false, "a":["Hello", "World", true, false, null, {"name":"Pierre", "year":2009}]}
Result is:null

Compiling d
Eval {"d":12345, "b":null, "c":false, "a":["Hello", "World", true, false, null, {"name":"Pierre", "year":2009}]}
Result is:12345

Compiling a[5].year
Eval {"d":12345, "b":null, "c":false, "a":["Hello", "World", true, false, null, {"name":"Pierre", "year":2009}]}
Result is:2009

Compiling x.y
Eval {"d":12345, "b":null, "c":false, "a":["Hello", "World", true, false, null, {"name":"Pierre", "year":2009}]}
Result is:null


Full source code


options {
STATIC=false;
DEBUG_PARSER=false;
ERROR_REPORTING=true;
NODE_USES_PARSER=false;
NODE_FACTORY="JSONPathCompiler";
NODE_CLASS="JSONNode";
}

PARSER_BEGIN(JSONPathCompiler)
import java.lang.reflect.*;

public class JSONPathCompiler
{
public static class JSONNode
extends SimpleNode
{
JSONNode(int i)
{
super(i);
}

public int getChildrenCount()
{
return this.children==null?0:children.length;
}

public JSONNode at(int index)
{
return (JSONNode)(
this.children==null ||
index<0 ||
index>=this.children.length ?
null:
this.children[index]
);
}

public String getName()
{
return JSONPathCompilerTreeConstants.jjtNodeName[this.id];
}

public void dump(String prefix)
{
System.out.println(prefix+toString());
if( children!=null && children.length>0)
{
System.out.println(prefix+" [");
for (int i = 0; children!=null && i < children.length; ++i)
{
System.out.print(prefix+" ("+(i+1)+")");
SimpleNode c= (SimpleNode)children[i];
if(c==null)
{
System.out.println("null");
}
else
{
c.dump(prefix+" ");
}
}
System.out.println(prefix+" ]");
}
}



public Object eval(Object o)
{
if(o==null) return null;
switch(this.id)
{
case JJTEXPRESSION:
{
if(getChildrenCount()==0) return null;
for(int i=0;o!=null && i< getChildrenCount();++i)
{
o=at(i).eval(o);
}
return o;
}
case JJTARRAY:
{
int index= Integer.class.cast(this.value);
if(o instanceof java.util.List)
{
java.util.List L=java.util.List.class.cast(o);
if(index<0 || index>= L.size()) return null;
return L.get(index);
}
else if(o.getClass().isArray())
{
Object L[]=(Object[])o;
if(index<0 || index>= L.length) return null;
return L[index];
}
return null;
}
case JJTOBJECT:
{
if(o instanceof java.util.Map)
{
java.util.Map M=java.util.Map.class.cast(o);
return M.get(this.value);
}
return null;
}

default:
System.err.println("Doesn't handle "+this.id);
break;
}
return null;
}
}



static SimpleNode jjtCreate(int id)
{
return new JSONNode(id);
}

public static void main(String args[])
{
try
{
java.io.StringReader r= new java.io.StringReader(args[0]);
JSONPathCompiler app= new JSONPathCompiler(r);
JSONNode x=JSONNode.class.cast(app.expr());
//x.dump("[xpath]");
java.util.Map<String,Object> o1=new java.util.HashMap<String,Object>();
java.util.HashMap o2=new java.util.HashMap<String,Object>();
java.util.List<Object> o3=new java.util.ArrayList<Object>();

o1.put("a",o3);
o1.put("b",null);
o1.put("c",Boolean.FALSE);
o1.put("d",12345);

o3.add("Hello");
o3.add("World");
o3.add(Boolean.TRUE);
o3.add(Boolean.FALSE);
o3.add(null);
o3.add(o2);

o2.put("name","Pierre");
o2.put("year",2009);

Object o=x.eval(o1);
System.err.println("Compiling <code>"+args[0]+"</code>");
System.err.println("Eval <code>"+o1+"</code>");
System.err.println("Result is:<code>"+o+"</code>");
}
catch(Exception err)
{
err.printStackTrace();
}
}
}
PARSER_END(JSONPathCompiler)

SKIP :
{
" "
| "\t"
| "\n"
| "\r"
}

TOKEN: {
<#LETTER: ["_","a"-"z","A"-"Z"] >
| <#DIGIT: ["0"-"9"] >
| <DOT: ".">
| <INTEGER: <DIGIT> (<DIGIT>)* >
| <IDENTIFIER: <LETTER> (<LETTER>|<DIGIT>)*>
| <OPEN_ARRAY: "[">
| <CLOSE_ARRAY: "]">
}



JSONNode expr() #EXPRESSION:{}
{
(array() | object() ) ( array() | <DOT> object() )* <EOF>
{
return jjtThis;
}
}

void array() #ARRAY:{Token i;}
{
<OPEN_ARRAY> i=<INTEGER> <CLOSE_ARRAY>
{
jjtThis.value=new Integer(i.image);
}
}

void object() #OBJECT: { Token name;}
{
( name=<IDENTIFIER> )
{
jjtThis.value= name.image;
}
}

That's it.
Pierre

3 comments:

Tom Copeland said...

A good tutorial! The only thing I'd add is that the ERROR_REPORTING option is true by default, so it doesn't need to be set in the options header. Good stuff!

l-carnitine said...

I think, it is very easy to develop any single expression with the help of JJTree/Javacc because Java itself is an one platform independent environment.

Anonymous said...

Thank you for this example.
I will use it as a starting point for a more expressive query language.
Thanks,
Jochen