Parsing expressions in Java

Here's a familiar example from computer science, rendered in Java. The code below defines a recursive descent Parser that knows how to decipher simple arithmetic expressions according to the following LL(1) grammar:

``````
term = factor {(mulop) factor} end
factor = word | number | "(" expr ")" end
word = name ["(" expr] ["," expr] ")"] end
mulop = "*" | "/"

import java.io.*;
import java.util.*;

/**
* Calc: test the Parser.
* Distribution per LGPL; no warranty.
*
* @author John B. Matthews
*/
public class Calc {

public static void main(String argv[]) {
eval("-1 + 2", 1);
eval("+1 - 2", -1);
eval("-1 + -2", -3);
eval("-7 + 2 * 3", -1);
eval("-7 + 1 + 2 + 3", -1);
eval("-1 * (-5.5 - 2.5)", 8);
eval("1.0 * 2.0 * 3.0 / 6.0", 1);
eval("18.0 / 3.0 / 1.5 / 4.0", 1);
eval("2 * (3 * (4 + 5)) / 9 / 6", 1);
eval("2 \$ 2", 42);
eval("2 * !2 + 2", 42);
eval("fu(2 + 3)", 42);
eval("min(2; 3)", 42);
eval("cos@2 + 3)", 42);
eval("tan(2 * 3} + 1", 42);
eval("e", Math.E);
eval("pow(e, 1)", Math.E);
eval("pi", Math.PI);
eval("4 * atan(1)", Math.PI);
eval("ln(e)", 1);
eval("exp(ln(1))", 1);
eval("sin(pi / 2)", 1);
eval("sqrt(2 * 2)", 2);
eval("max(1, 2 + 3)", 5);
eval("min(3 - 1, 1)", 1);
}

private static void eval(String s, double x) {

Parser p = Parser.parse(s);
double v = p.value();

if (p.isValid()) {
System.out.println((v == x) + ": " + s + " = " + v);
} else {
System.out.println("error check: " + p.error() + ": " + s);
}
}
}

/**
* Parse via recursive descent using the following LL(1) grammar:
* <code>
*   term = factor {(mulop) factor} end
* factor = word | number | "(" expr ")" end
*   word = name ["(" expr] ["," expr] ")"] end
*  addop = "+" | "-"
*  mulop = "*" | "/"
* </code>
*
* @param s the string to be evaluated.
*
* @see <a href="http://en.wikipedia.org/wiki/Recursive_descent_parser">
* Recursive descent parser</a>.
* @author John B. Matthews
*/
class Parser extends Object {
private StreamTokenizer tokens;
private int token;
private double value;
private String error;

private Parser(String s) {
tokens.ordinaryChar(Symbol.SLASH.toChar());

getToken();
value = expr();
if (!tokenIs(Symbol.END))
putError("syntax error");
}

public static Parser parse(String s) { return new Parser(s); }

public boolean isValid() { return error == null; }

public double value() { return value; }

public String error() { return error; }

private double expr() {
int sign = 1;
accept(Symbol.PLUS);
if (accept(Symbol.MINUS)) {
sign = -1;
}
double value = sign * term();
if (accept(Symbol.PLUS)) {
value += term();
}
if (accept(Symbol.MINUS)) {
value -= term();
}
}
return value;
}

// term = factor {(mulop) factor} end
private double term() {
double value = factor();
while (Symbol.isMulOp(token)) {
if (accept(Symbol.STAR)) {
value *= factor();
}
if (accept(Symbol.SLASH)) {
value /= factor();
}
}
return value;
}

// factor = word | number | "(" expr ")" end
private double factor() {
double value = 0;
if (tokenIs(Symbol.WORD)) {
value = word();
} else if (tokenIs(Symbol.NUMBER)) {
value = tokens.nval;
getToken();
} else if (accept(Symbol.OPEN)) {
value = expr();
expect(Symbol.CLOSE);
} else {
putError("factor error");
getToken();
}
return value;
}

// word = name ["(" expr] ["," expr] ")"] end
private double word() {
double value = 0;
String name = tokens.sval;
getToken();
if (fa != null) {
int count = fa.getCount();
if (count == 0) {
value = fa.eval();
} else if (accept(Symbol.OPEN)) {
double[] args = new double[count];
for (int i = 0; i < count; i++) {
args[i] = expr();
if (i < count - 1)
expect(Symbol.COMMA);
}
value = fa.eval(args);
expect(Symbol.CLOSE);
} else putError("missing " + Symbol.OPEN.toChar());
} else putError("undefined " + name);
return value;
}

/** Fetch the next token in the stream. */
private void getToken() {
try {
token = tokens.nextToken();
} catch (IOException e) {
putError("i/o error " + e.getMessage());
}
}

/** Return true if the current token matches the given symbol. */
private boolean tokenIs(Symbol symbol) {
}

/** Require a matching symbol; gerate an error if it's unexpected. */
private void expect(Symbol symbol) {
if (accept(symbol)) return;
putError("missing " + symbol.toChar());
}

/** Advance if the current token matches the given symbol. */
private boolean accept(Symbol symbol) {
if (tokenIs(symbol)) {
getToken();
return true;
}
return false;
}

/** Generate an error; ignore line numbers. */
private void putError(String s) {
if (error == null)
error = s + " at " + tokens.toString().replaceAll(",.*\$", "");
}
}

/**
* Enumerate the terminal symbols recognized by the Parser.
* Each symbol's token field is initialized with a value that
* matches one returned by StreamTokenizer's nextToken() method.
*/
enum Symbol {
PLUS   ('+'), MINUS ('-'), STAR  ('*'), SLASH ('/'),
OPEN   ('('), CLOSE (')'), COMMA (','),
END    (StreamTokenizer.TT_EOF),
WORD   (StreamTokenizer.TT_WORD),
NUMBER (StreamTokenizer.TT_NUMBER);

private int token;

private Symbol(int token) {
this.token = token;
}

/** Return this symbol's token. */
public int token()  {
return this.token;
}

/** If printable, return character for this symbol's token. */
public char toChar() {
if (this.token < 32) return '\ufffd';
else return (char) this.token;
}

/** Return if the given token matches PLUS or MINUS. */
public static boolean isAddOp(int token) {
}

/** Return if the given token matches STAR or SLASH. */
public static boolean isMulOp(int token) {
}
}

/**
* Enumerate the available functions. Although an enum may define
* <i>constant-specific</i> methods, an included adpter or interface
* is perhaps easier to read, initialize and maintain.
*/
enum Function {
E    (new E()),
PI   (new Pi()),
LN   (new Ln()),
EXP  (new Exp()),
SIN  (new Sin()),
COS  (new Cos()),
TAN  (new Tan()),
ATAN (new Atan()),
SQRT (new Sqrt()),
MAX  (new Max()),
MIN  (new Min()),
POW  (new Pow());

/** Construct a Function with the specified adapter. **/
this.fa = fa;
}

/** Return a Function's adapter by name; null if unknown. */
public static FunctionAdapter lookup(String name) {
Function f;
try {
f = Enum.valueOf(Function.class, name.toUpperCase());
} catch (RuntimeException e) {
return null;
}
return f.fa;
}
}

/**
* Adapt to functions with a variable number of arguments.
* Concrete implementations should override getCount() to indicate
* the expected number of arguments. The default is one.
*/
public int getCount() { return 1; }
abstract double eval(double... args);
}

public int getCount() { return 0; }
public double eval(double... args) { return Math.E; }
}

public int getCount() { return 0; }
public double eval(double... args) { return Math.PI; };
}

public double eval(double... args) { return Math.log(args[0]); }
}

public double eval(double... args) { return Math.exp(args[0]); }
}

public double eval(double... args) { return Math.sin(args[0]); }
}

public double eval(double... args) { return Math.cos(args[0]); }
}

public double eval(double... args) { return Math.tan(args[0]); }
}

public double eval(double... args) { return Math.atan(args[0]); }
}

public double eval(double... args) { return Math.sqrt(args[0]); }
}

public int getCount() { return 2; }
public double eval(double... args) { return Math.max(args[0], args[1]); }
}

public int getCount() { return 2; }
public double eval(double... args) { return Math.min(args[0], args[1]); }
}

public int getCount() { return 2; }
public double eval(double... args) { return Math.pow(args[0], args[1]); }
}

```
```

Acknowledgements:

Arachnophilia for nicely formatted listings.

Disclaimer:

Sorry, I cannot accept liability arising out of use of this program including (but not limited to) the time you waste playing with it. Happy parsing!