/**************************************** * Folder: expr Document: Parser.java ****************************************/ // Operator-precedence parser. // Copyright 1996 by Darius Bacon; see the file COPYING. // 14May96: bugfix. // StreamTokenizer treated '-' as a numeric token, not a minus // operator followed by a number. Fix: make '-' an ordinaryChar. // 12May97: Changed the precedence of unary minus to be lower than // multiplication, so -y^2 is like -(y^2), not (-y)^2. package expr; import java.io.*; /** Parses strings representing mathematical formulas with variables. The following operators, in descending order of precedence, are defined: ^ (raise to a power) * / Unary minus (-x) + - ^ associates right-to-left; other operators associate left-to-right. These functions are defined: abs, acos, asin, atan, ceil, cos, exp, floor, (ln added by DP) log, round, sin, sqrt, tan. Each requires one argument enclosed in parentheses. Whitespace outside identifiers is ignored. The syntax-error messages aren't very informative, unfortunately. IWBNI it indicated where in the input string the parse failed, but that'd be kind of a pain since our scanner is a StreamTokenizer. A hook for that info should've been built into StreamTokenizer. Examples: 42 2-3 cos(x^2) + sin(x^2) */ public class Parser { static StreamTokenizer tokens; public static Expr parse (String input) throws Syntax_error { tokens = new StreamTokenizer (new StringBufferInputStream (input)); tokens.ordinaryChar ('/'); tokens.ordinaryChar ('-'); next (); Expr expr = parse_expr (0); if (tokens.ttype != StreamTokenizer.TT_EOF) throw new Syntax_error ("Incomplete expression: " + input); return expr; } static void next () { try { tokens.nextToken (); } catch (IOException e) { throw new RuntimeException ("I/O error: " + e); } } static void expect (int ttype) throws Syntax_error { if (tokens.ttype != ttype) throw new Syntax_error ("'" + (char) ttype + "' expected"); next (); } static Expr parse_expr (int precedence) throws Syntax_error { Expr expr = parse_factor (); loop: for (;;) { int l, r, rator; // The operator precedence table. // l = left precedence, r = right precedence, rator = operator. // Higher precedence values mean tighter binding of arguments. // To associate left-to-right, let r = l+1; // to associate right-to-left, let r = l. switch (tokens.ttype) { case '+': l = 10; r = 11; rator = Expr.ADD; break; case '-': l = 10; r = 11; rator = Expr.SUB; break; case '*': l = 20; r = 21; rator = Expr.MUL; break; case '/': l = 20; r = 21; rator = Expr.DIV; break; case '^': l = 30; r = 30; rator = Expr.POW; break; default: break loop; } if (l < precedence) break loop; next (); expr = Expr.make_app2 (rator, expr, parse_expr (r)); } return expr; } static String[] procs = { "abs", "acos", "asin", "atan", "ceil", "cos", "exp", "floor", "ln", // ln added by DP "log", "round", "sin", "sqrt", "tan" }; static int[] rators = { Expr.ABS, Expr.ACOS, Expr.ASIN, Expr.ATAN, Expr.CEIL, Expr.COS, Expr.EXP, Expr.FLOOR, Expr.LN, // Expr.LN added by DP Expr.LOG, Expr.ROUND, Expr.SIN, Expr.SQRT, Expr.TAN }; static Expr parse_factor () throws Syntax_error { switch (tokens.ttype) { case StreamTokenizer.TT_NUMBER: { Expr lit = Expr.make_literal (tokens.nval); next (); return lit; } case StreamTokenizer.TT_WORD: { for (int i = 0; i < procs.length; ++i) if (procs [i].equals (tokens.sval)) { next (); expect ('('); Expr rand = parse_expr (0); expect (')'); return Expr.make_app1 (rators [i], rand); } Expr var = Expr.make_var_ref (Variable.make (tokens.sval)); next (); return var; } case '(': { next (); Expr enclosed = parse_expr (0); expect (')'); return enclosed; } case '-': next (); return Expr.make_app1 (Expr.NEG, parse_expr (15)); default: throw new Syntax_error ("Expected a factor"); } } }