Reflection-Based S-Expression Parser

/** Parse the string.
* @param s the string to be parsed
* @return the expression of type E */
public E parse(String s) {
println(“parse ‘”+s+”‘”);
RestoreStringTokenizer st = new RestoreStringTokenizer(s.trim());
return parse(st);
}

/** Parse the tokens in the tokenizer.
* @param s the tokenizer with the tokens
* @return the expression of type E */
protected E parse(RestoreStringTokenizer s) {
// position to restore everything
final int sPos = s.getPosition();

// read (
parseWhitespace(s);
String word = s.nextToken();
println(“word: ‘”+word+”‘”);
if (!word.equals(“(“)) {
s.restorePosition(sPos);
throw new ParseException();
}

// read S-expression name
parseWhitespace(s);
word = s.nextToken();
println(“word: ‘”+word+”‘”);
if (!_classes.containsKey(word)) {
// don’t know what that is, restore
s.restorePosition(sPos);
throw new ParseException();
}

// known subclass of E
Class c = _classes.get(word);
println(“Class: “+c.getSimpleName());
parseWhitespace(s);

// position to restore after trying out a constructor
final int sTryCtorPos = s.getPosition();

Constructor ctor;
for(Constructor ctor2: c.getDeclaredConstructors()) {
println(“\ttrying ctor “+ctor2);

// this is necessary since c.getDeclaredConstructors() returns Constructor
// but we want Constructor
try { ctor = c.getConstructor(ctor2.getParameterTypes()); }
catch(NoSuchMethodException nsme) { throw new AssertionError(“Should never happen.”); }

// try to parse the arguments for this constructor
Object[] args = new Object[ctor.getParameterTypes().length];
int argIndex = 0;
try {
for(Class paramC: ctor.getParameterTypes()) {
// primitive types and their boxed types
if ((paramC==int.class) || (paramC==Integer.class)) {
args[argIndex] = parseLeaf(s,Integer.class);
}
else if ((paramC==boolean.class) || (paramC==Boolean.class)) {
args[argIndex] = parseLeaf(s,Boolean.class);
}
else if ((paramC==long.class) || (paramC==Long.class)) {
args[argIndex] = parseLeaf(s,Long.class);
}
else if ((paramC==double.class) || (paramC==Double.class)) {
args[argIndex] = parseLeaf(s,Double.class);
}
else if ((paramC==float.class) || (paramC==Float.class)) {
args[argIndex] = parseLeaf(s,Float.class);
}
else if ((paramC==byte.class) || (paramC==Byte.class)) {
args[argIndex] = parseLeaf(s,Byte.class);
}
else if ((paramC==short.class) || (paramC==Short.class)) {
args[argIndex] = parseLeaf(s,Short.class);
}
// char or Character
else if ((paramC==char.class) || (paramC==Character.class)) {
// parse as string
Object temp = parseLeaf(s,String.class);
// must be exactly one character
if (temp.toString().length()!=1) throw new ParseException();
args[argIndex] = new Character(temp.toString().charAt(0));
}
// strings
else if (paramC==String.class) {
args[argIndex] = parseLeaf(s,String.class);
}
// recursively parse expressions of type E
else if (_expClass.equals(paramC)) {
args[argIndex] = parse(s);
}
// try to use a subparser
else if (_subParsers.containsKey(paramC)) {
// try one of the subparsers
args[argIndex] = _subParsers.get(paramC).parse(s);
}
else {
// don’t know what that is
// restore happens below
throw new ParseException();
}
++argIndex;
}
}
catch(ParseException pe) {
// this constructor didn’t work out, we need to restore and try another constructor
s.restorePosition(sTryCtorPos);
// continue with next constructor
continue;
}
try {
// we read all values required for this constructor
// make sure that the next token is )
parseWhitespace(s);
word = s.nextToken();
println(“word: ‘”+word+”‘”);
if (!word.equals(“)”)) {
// it wasn’t ), we need to restore and try another constructor
s.restorePosition(sTryCtorPos);
// continue with next constructor
continue;
}
parseWhitespace(s);

// successfully used this constructor
println(“new “+ctor.getDeclaringClass().getSimpleName()+” “+
java.util.Arrays.toString(args));
E e = (E)ctor.newInstance(args);
return e;
}
catch(Exception e) {
// something went wrong using this constructor, we need to restore and try another
s.restorePosition(sTryCtorPos);
// continue with next constructor
continue;
}
}

s.restorePosition(sPos);
throw new ParseException();
}

/** Parse a leaf of class c, which must have a unary constructor taking a String, from
* the tokenizer s.
* @param s tokenizer from which to parse
* @param c the class, which has a unary constructor taking a String, for that we want to create a value
* @return parsed value of class c */
protected Object parseLeaf(RestoreStringTokenizer s, Class c) {
// position so we can undo this attempt to parse
final int sPos = s.getPosition();

String word = null;
try {
// get the unary constructor taking String
Constructor ctor = c.getDeclaredConstructor(String.class);

// skip whitespace, get the string, skip whitespace
parseWhitespace(s);
word = s.nextToken();
println(“word: ‘”+word+”‘”);
Object o = ctor.newInstance(word);
parseWhitespace(s);

return o;
}
catch(NoSuchMethodException nsme) {
// something went wrong, restore and abort
s.restorePosition(sPos);
throw new ParseException();
}
catch(InstantiationException ie) {
// something went wrong, restore and abort
s.restorePosition(sPos);
throw new ParseException();
}
catch(IllegalAccessException iae) {
// something went wrong, restore and abort
s.restorePosition(sPos);
throw new ParseException();
}
catch(InvocationTargetException ite) {
// something went wrong, restore and abort
s.restorePosition(sPos);
throw new ParseException();
}
}

/** Parse whitespace. Stop before the next non-whitespace token, or when there are no
* more tokens.
* @param s tokenizer from which to parse whitespace */
protected void parseWhitespace(RestoreStringTokenizer s) {
String word;
int sPrevPos;
while(s.hasMoreTokens()) {
sPrevPos = s.getPosition();
word = s.nextToken();
if (!word.trim().equals(“”)) {
s.restorePosition(sPrevPos);
break;
}
}
}

/** Debug method to print, comment System.out.println call out to disable debug printing */
public static void println(Object o) {
// System.out.println(o.toString());
}

/** This tokenizer stores all read tokens in a stack so they can easily be
* restored. This isn’t as memory as it could be, but it’s good enough for
* small examples. */
public static class RestoreStringTokenizer extends StringTokenizer {
/** Stack of read tokens. */
private Stack _read = new Stack();
/** Stack of restored tokens. */
private Stack _restored = new Stack();
/** Create a new string tokenizer that can restore positions. */
public RestoreStringTokenizer(String s) { super(s,” ()”,true); }
/** Return the current position. */
public int getPosition() { return _read.size(); }
/** Rewind to a previous position. This only goes backward, not forward. */
public void restorePosition(int pos) {
while(_read.size()>pos) {
_restored.push(_read.pop());
}
}
// overridden methods from StringTokenizer
public int countTokens() { return _restored.size() + super.countTokens(); }
public boolean hasMoreTokens() { return (_restored.size()>0) || super.hasMoreTokens(); }
public boolean hasMoreElements() { return hasMoreTokens(); }
public String nextToken() {
String token = (_restored.size()>0) ? _restored.pop() : super.nextToken();
_read.push(token);
return token;
}
public Object nextElement() { return nextToken(); }
public String nextToken(String delim) {
if (_restored.size()>0) return _restored.pop();
return super.nextToken(delim);
}
}

public static void main(String[] args) {
lint2_cond.UnstagedLint.Exp e = parse
(lint2_cond.UnstagedLint.Exp.class,”(Ifz (Int 1) (Int 10) (Mul(Int 3)(Add(Int 5)(Int 10))))”);
System.out.println(new lint2_cond.UnstagedLint.Program(e).peval(lint2_cond.UnstagedLint.env0));

lint.DataTypes.Value v = parse(lint.DataTypes.Value.class, “(IntValue 1)”);
System.out.println(v);

lint.DataTypes.Exp e2 =
new LintParser(lint.DataTypes.Exp.class)
.addSubParser(new LintParser(lint.DataTypes.Value.class))
.parse(“(Add (Val (IntValue 1)) (Val (IntValue 2)))”);
System.out.println(new lint.DataTypes.Program(e2).peval(lint.DataTypes.env0, lint.DataTypes.fenv0));

lint.DataTypes.Exp e3 =
LintParser.parse(lint.DataTypes.Exp.class, “(Add (Val (IntValue 1)) (Val (IntValue 2)))”,
new LintParser(lint.DataTypes.Value.class));
System.out.println(new lint.DataTypes.Program(e3).peval(lint.DataTypes.env0, lint.DataTypes.fenv0));

}
}[/cc]

Here is the definition of a simple language for arithmetic expressions that uses the parser:

[cc lang=”java” lines=”20″]package lint1_arithmetic;

public class UnstagedLint {

/*
type exp = Int of int
| Var of string
| Add of exp * exp
| Sub of exp * exp
| Mul of exp * exp
| Div of exp * exp
type def = Definition of string * int
type prog = Program of def list * exp
*/

public static interface Exp {
public int eval(Env e);
}

public static class Int implements Exp {
private int _value;
public Int(int value) {
_value = value;
}
public int eval(Env e) {
return _value;
}
}

public static class Var implements Exp {
private String _s;
public Var(String s) {
_s = s;
}
public int eval(Env e) {
return e.get(_s);
}
}

public static abstract class BinOp implements Exp {
protected Exp _left, _right;
public BinOp(Exp left, Exp right) {
_left = left;
_right = right;
}
}

public static class Add extends BinOp {
public Add(Exp left, Exp right) {
super(left, right);
}
public int eval(Env e) {
return _left.eval(e) + _right.eval(e);
}
}

public static class Sub extends BinOp {
public Sub(Exp left, Exp right) {
super(left, right);
}
public int eval(Env e) {
return _left.eval(e) – _right.eval(e);
}
}

public static class Mul extends BinOp {
public Mul(Exp left, Exp right) {
super(left, right);
}
public int eval(Env e) {
return _left.eval(e) * _right.eval(e);
}
}

public static class Div extends BinOp {
public Div(Exp left, Exp right) {
super(left, right);
}
public int eval(Env e) {
return _left.eval(e) / _right.eval(e);
}
}

/*
exception EnvironmentException
let env0 = fun x -> raise EnvironmentException
let fenv0 = env0
let ext env x v = fun y -> if x=y then v else env y
*/

public static class EnvironmentException extends RuntimeException { }

// environment; implemented as a function object from String to Exp
public static interface Env {
public int get(String y);
}
public static final Env env0 = new Env() {
public int get(String s) { throw new EnvironmentException(); }
};

public static Env ext(final Env env, final String x, final int v) {
return new Env() {
public int get(String y) {
if (x.equals(y)) return v; else return env.get(y);
}
};
}

public static class Definition {
private String _name;
private int _v;
public Definition(String name, int v) {
_name = name;
_v = v;
}
public String name() { return _name; }
public int value() { return _v; }
}

public static class Program {
public Definition[] _defs;
public Exp _body;
public Program(Exp body, Definition… defs) {
_defs = defs;
_body = body;
}

public int peval(Env env) {
return peval(env,0);
}

private int peval(final Env env, int defIndex) {
// match p with
if (_defs.length<=defIndex) { // Program ([],e) -> eval e env
return _body.eval(env);
}
else {
// |Program (Definition (n,v)::tl,e) -> peval (Program(tl,e)) (ext env n v)
final Definition d = _defs[defIndex];
return peval(ext(env, d.name(), d.value()),defIndex+1);
}
}
}

/*
let rec eval e env fenv =
match e with
Int i -> i
| Var s -> env s
| Add (e1,e2) -> (eval e1 env fenv)+(eval e2 env fenv)
| Sub (e1,e2) -> (eval e1 env fenv)-(eval e2 env fenv)
| Mul (e1,e2) -> (eval e1 env fenv)*(eval e2 env fenv)
| Div (e1,e2) -> (eval e1 env fenv)/(eval e2 env fenv)

let rec peval p env =
match p with
Program ([],e) -> eval e env
|Program (Definition (s1,i1)::tl,e) -> peval (Program(tl,e)) (ext env s1 i1)

*/

public static Program term10times20plus30 = new Program
(new Add(new Mul(new Var(“x”), new Var(“y”)), new Int(30)),
new Definition(“x”, 10),
new Definition(“y”, 20));

public static Program parsedTerm10times20plus30 = new Program
(parser.LintParser.parse(Exp.class, “(Add (Mul (Var x) (Var y)) (Int 30))”),
new Definition(“x”, 10),
new Definition(“y”, 20));

public static Program termWhatX = new Program
(new Var(“x”));

public static Program parsedTermWhatX = new Program
(parser.LintParser.parse(Exp.class, “(Var x)”));

public static void main(String[] args) {
int i = term10times20plus30.peval(env0);
System.out.println(“term10times20plus30 = “+i);

i = parsedTerm10times20plus30.peval(env0);
System.out.println(“parsedTerm10times20plus30 = “+i);

try {
i = termWhatX.peval(env0);
System.out.println(“termWhatX = “+i);
throw new AssertionError(“This should throw an EnvironmentException”);
}
catch(EnvironmentException ee) { System.out.println(“termWhatX threw “+ee); /* expected */ }

try {
i = parsedTermWhatX.peval(env0);
System.out.println(“parsedTermWhatX = “+i);
throw new AssertionError(“This should throw an EnvironmentException”);
}
catch(EnvironmentException ee) { System.out.println(“parsedTermWhatX threw “+ee); /* expected */ }
}
}[/cc]