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:
expr = [addop] term {(addop) term} endterm = factor {(mulop) factor} endfactor = word | number | "(" expr ")" endword = name ["(" expr] ["," expr] ")"] endaddop = "+" | "-"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> * expr = [addop] term {(addop) term} end * 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) { Reader reader = new StringReader(s); tokens = new StreamTokenizer(reader); 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; } // expr = [addop] term {(addop) term} end private double expr() { int sign = 1; accept(Symbol.PLUS); if (accept(Symbol.MINUS)) { sign = -1; } double value = sign * term(); while (Symbol.isAddOp(token)) { 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; FunctionAdapter fa = Function.lookup(name); 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) { return token == symbol.token(); } /** 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 token == PLUS.token || token == MINUS.token; } /** Return if the given token matches STAR or SLASH. */ public static boolean isMulOp(int token) { return token == STAR.token || token == SLASH.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()); private FunctionAdapter fa; /** Construct a Function with the specified adapter. **/ private Function(FunctionAdapter fa) { 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. */abstract class FunctionAdapter { public int getCount() { return 1; } abstract double eval(double... args);}class E extends FunctionAdapter { public int getCount() { return 0; } public double eval(double... args) { return Math.E; }}class Pi extends FunctionAdapter { public int getCount() { return 0; } public double eval(double... args) { return Math.PI; };}class Ln extends FunctionAdapter { public double eval(double... args) { return Math.log(args[0]); }}class Exp extends FunctionAdapter { public double eval(double... args) { return Math.exp(args[0]); }}class Sin extends FunctionAdapter { public double eval(double... args) { return Math.sin(args[0]); }}class Cos extends FunctionAdapter { public double eval(double... args) { return Math.cos(args[0]); }}class Tan extends FunctionAdapter { public double eval(double... args) { return Math.tan(args[0]); }}class Atan extends FunctionAdapter { public double eval(double... args) { return Math.atan(args[0]); }}class Sqrt extends FunctionAdapter { public double eval(double... args) { return Math.sqrt(args[0]); }}class Max extends FunctionAdapter { public int getCount() { return 2; } public double eval(double... args) { return Math.max(args[0], args[1]); }}class Min extends FunctionAdapter { public int getCount() { return 2; } public double eval(double... args) { return Math.min(args[0], args[1]); }}class Pow extends FunctionAdapter { 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!
Copyright:
©2008, John B. Matthews. Distribution permitted without warranty under the terms of the LGPL.
Last updated 25-Apr-2008