/****************************************************************************************** * Parser.java version 1.0 Jun 16 1996 * * Parser.java version 2.0 Aug 25 1996 * * Parser.java version 2.1 Oct 14 1996 * * Parser.java version 2.11 Oct 25 1996 * * * * Copyright (c) 1996 Yanto Suryono. All Rights Reserved. * * * * Permission to use, copy, and distribute this software for NON-COMMERCIAL purposes * * and without fee is hereby granted provided that this copyright notice appears in all * * copies and this software is not modified in any way * * * * Please send bug reports and/or corrections/suggestions to * * Yanto Suryono * ******************************************************************************************/ public class Parser { // global variables private int varcount; // number of variables private String varname[]; // variables' name private double varvalue[]; // value of variables private double number[]; // numeric constants in defined function private String function = ""; // function definition private String postfixcode = ""; // the postfix code private boolean valid = false; // postfix code status private int error = 0; // error code private boolean ISBOOLEAN = false; // boolean flag private boolean INRELATION = false; // relation flag // variables used during parsing private int position; // parsing pointer private int start; // starting position of identifier private int num; // number of numeric constants private char character; // current character // variables used during evaluating private boolean radian; // radian unit flag // error codes private static final int MAX_NUM = 100; // max numeric constants private static final int NO_FUNCS = 24; // no. of built-in functions private static final int STACK_SIZE = 50; // evaluation stack size // constants private static final double DEGTORAD = Math.PI / 180; private static final double LOG10 = Math.log(10); // error codes public static final int NO_ERROR = 0; public static final int SYNTAX_ERROR = 1; public static final int PAREN_EXPECTED = 2; public static final int UNCOMPILED_FUNCTION = 3; public static final int EXPRESSION_EXPECTED = 4; public static final int UNKNOWN_IDENTIFIER = 5; public static final int OPERATOR_EXPECTED = 6; public static final int PAREN_NOT_MATCH = 7; public static final int CODE_DAMAGED = 8; public static final int STACK_OVERFLOW = 9; public static final int TOO_MANY_CONSTS = 10; public static final int COMMA_EXPECTED = 11; public static final int INVALID_OPERAND = 12; public static final int INVALID_OPERATOR = 13; // postfix codes public static final int FUNC_OFFSET = 100; public static final int VAR_OFFSET = 200; public static final char PI_CODE = (char)253; public static final char E_CODE = (char)254; public static final char NUMERIC = (char)255; public static final char JUMP_CODE = (char)1; // Jump, followed by n : Displacement public static final char LESS_THAN = (char)2; // Relation less than (<) public static final char GREATER_THAN = (char)3; // Relation greater than (>) public static final char LESS_EQUAL = (char)4; // Relation less than or equal (<=) public static final char GREATER_EQUAL = (char)5; // Relation greater than or equal (>=) public static final char NOT_EQUAL = (char)6; // Relation not equal (<>) public static final char EQUAL = (char)7; // Relation equal (=) public static final char IF_CODE = (char)8; // Conditional statement IF, followed by a conditional block : // * Displacement (Used to jump to condition FALSE code) // * Condition TRUE code // * Jump to next code outside conditional block // * Condition FALSE code // * ENDIF public static final char ENDIF = (char)9; public static final char AND_CODE = (char)10; // Boolean AND public static final char OR_CODE = (char)11; // Boolean OR public static final char NOT_CODE = (char)12; // Boolean NOT // built in functions String funcname[] = { "sin", "cos", "tan", "ln", "log", "abs", "int", "frac", "asin", "acos", "atan", "sinh", "cosh", "tanh", "asinh", "acosh", "atanh", "ceil", "floor", "round", "exp", "sqr", "sqrt", "sign" }; // object constructor public Parser(int variablecount) { varcount = variablecount; varname = new String[variablecount]; varvalue = new double[variablecount]; number = new double[MAX_NUM]; radian = true; } // set angle unit to radian (default) public void useRadian() { radian = true; } // set angle unit to degree public void useDegree() { radian = false; } // get error code of recent process public int getErrorCode() { return error; } // get error position public int getErrorPosition() { if (error != NO_ERROR) return position; else return 0; } // get error string public String getErrorString() { String s = ""; switch (error) { case NO_ERROR : s = "no error"; break; case SYNTAX_ERROR : s = "syntax error"; break; case PAREN_EXPECTED : s = "paren expected"; break; case UNCOMPILED_FUNCTION : s = "uncompiled function"; break; case EXPRESSION_EXPECTED : s = "expression expected"; break; case UNKNOWN_IDENTIFIER : s = "unknown identifier"; break; case OPERATOR_EXPECTED : s = "operator expected"; break; case PAREN_NOT_MATCH : s = "parenthesis not match"; break; case CODE_DAMAGED : s = "internal code damaged"; break; case STACK_OVERFLOW : s = "execution stack overflow"; break; case TOO_MANY_CONSTS : s = "too many constants"; break; case COMMA_EXPECTED : s = "comma expected"; break; case INVALID_OPERAND : s = "invalid operand type"; break; case INVALID_OPERATOR : s = "invalid operator"; break; } return s; } // set variable's name public void defineVariable(int index, String name) { if (index > varcount) return; varname[index-1] = name; } // set variable's value by using variable's position public void setVariable(int index, double value) { if (index > varcount) return; varvalue[index-1] = value; } // set variable's value by using variable's name public void setVariable(String name, double value) { for (int i=0; i < varcount; i++) { if (varname[i].equals(name)) { varvalue[i] = value; break; } } } // skip spaces and set current character to 'character' private void skip_spaces() { try { while (function.charAt(position-1) == ' ') position++; character = function.charAt(position-1); } catch(StringIndexOutOfBoundsException e) { error = PAREN_NOT_MATCH; return; } } // advance parsing pointer and set current character to 'character' private void get_next_character() { position++; try { character = function.charAt(position-1); } catch(StringIndexOutOfBoundsException e) { error = PAREN_NOT_MATCH; return; } } // add postfix code private void addcode(char code) { postfixcode += code; } // scan a number. legal format: xxx[.xxx[e[+|-]xxx]] private void scan_number() { String numstr = ""; double value; if (num == MAX_NUM) { error = TOO_MANY_CONSTS; return; } do { numstr += character; get_next_character(); if (error != NO_ERROR) return; } while ((character >= '0') && (character <= '9')); if (character == '.') { do { numstr += character; get_next_character(); if (error != NO_ERROR) return; } while ((character >= '0') && (character <= '9')); } if (character == 'e') { numstr += character; get_next_character(); if (error != NO_ERROR) return; if ((character == '+') || (character == '-')) { numstr += character; get_next_character(); if (error != NO_ERROR) return; } while ((character >= '0') && (character <= '9')) { numstr += character; get_next_character(); if (error != NO_ERROR) return; } } try { value = Double.valueOf(numstr).doubleValue(); } catch(NumberFormatException e) { error = SYNTAX_ERROR; position = start; return; } number[num++] = value; addcode(NUMERIC); } // scan a non-number identifier. can be a variable or a function call private void scan_variable_or_function() { String stream = ""; if ((character == '*') || (character == '/') || (character == '^') || (character == ')') || (character == ',')) { error = SYNTAX_ERROR; return; } do { stream += character; get_next_character(); if (error != NO_ERROR) return; } while (!( (character == ' ') || (character == '+') || (character == '-') || (character == '*') || (character == '/') || (character == '^') || (character == '(') || (character == ')') || (character == ',') || (character == '<') || (character == '>') || (character == '=') || (character == '&') || (character == '|') )); if (stream.equals("pi")) { addcode(PI_CODE); return; } else if (stream.equals("e")) { addcode(E_CODE); return; } // if if (stream.equals("if")) { skip_spaces(); if (error != NO_ERROR) return; if (character != '(') { error = PAREN_EXPECTED; return; } scan_and_parse(); if (error != NO_ERROR) return; if (character != ',') { error = COMMA_EXPECTED; return; } addcode(IF_CODE); String savecode = new String(postfixcode); postfixcode = ""; scan_and_parse(); if (error != NO_ERROR) return; if (character != ',') { error = COMMA_EXPECTED; return; } addcode(JUMP_CODE); savecode += (char)(postfixcode.length()+2); savecode += postfixcode; postfixcode = ""; scan_and_parse(); if (error != NO_ERROR) return; if (character != ')') { error = PAREN_EXPECTED; return; } savecode += (char)(postfixcode.length()+1); savecode += postfixcode; postfixcode = new String(savecode); get_next_character(); if (error != NO_ERROR) return; return; } // built-in function for (int i = 0; i < NO_FUNCS; i++) { if (stream.equals(funcname[i])) { skip_spaces(); if (error != NO_ERROR) return; if (character != '(') { error = PAREN_EXPECTED; return; } scan_and_parse(); if (error == NO_ERROR) { if (character != ')') { error = PAREN_EXPECTED; return; } get_next_character(); if (error != NO_ERROR) return; addcode((char)(i + FUNC_OFFSET)); } return; } } for (int i = 0; i < varcount; i++) { if (stream.equals(varname[i])) { addcode((char)(i + VAR_OFFSET)); return; } } error = UNKNOWN_IDENTIFIER; position = start; } // get an identifier starting at current parsing pointer private void getidentifier() { boolean negate = false; get_next_character(); skip_spaces(); if (error != NO_ERROR) return; if (character == '!') { get_next_character(); skip_spaces(); if (error != NO_ERROR) return; if (character != '(') { error = PAREN_EXPECTED; return; } scan_and_parse(); if (error != NO_ERROR) return; if (character != ')') { error = PAREN_EXPECTED; return; } if (!ISBOOLEAN) { error = INVALID_OPERAND; return; } addcode(NOT_CODE); get_next_character(); if (error != NO_ERROR) return; return; } ISBOOLEAN = false; while ((character == '+') || (character == '-')) { if (character == '-') negate = !negate; get_next_character(); skip_spaces(); if (error != NO_ERROR) return; } start = position; if ((character >= '0') && (character <= '9')) scan_number(); else if (character == '(') { scan_and_parse(); if (error != NO_ERROR) return; get_next_character(); if (error != NO_ERROR) return; } else scan_variable_or_function(); if (error != NO_ERROR) return; skip_spaces(); if (error != NO_ERROR) return; if (negate) addcode('_'); } // arithmetic level 3 (highest). power calculation private void level3() { byte repcount = 0; if (ISBOOLEAN) { error = INVALID_OPERAND; return; } do { getidentifier(); if (ISBOOLEAN && (error == NO_ERROR)) { error = INVALID_OPERAND; return; } repcount++; } while (character == '^'); for (int i = 1; i <= repcount; i++) addcode('^'); } // aritmetic level 2. multiplication and division private void level2() { if (ISBOOLEAN) { error = INVALID_OPERAND; return; } do { char operator = character; getidentifier(); if (ISBOOLEAN && (error == NO_ERROR)) { error = INVALID_OPERAND; return; } if (character == '^') level3(); addcode(operator); } while ((character == '*') || (character == '/')); } // arithmetic level 1 (lowest). addition and substraction private void level1() { if (ISBOOLEAN) { error = INVALID_OPERAND; return; } do { char operator = character; getidentifier(); if (ISBOOLEAN && (error == NO_ERROR)) { error = INVALID_OPERAND; return; } if (character == '^') level3(); else if ((character == '*') || (character == '/')) level2(); addcode(operator); } while ((character == '+') || (character == '-')); } private void relation_level() { char code = (char)0; if (INRELATION) { error = INVALID_OPERATOR; return; } INRELATION = true; if (ISBOOLEAN) { error = INVALID_OPERAND; return; } switch (character) { case '=': code = EQUAL; break; case '<': code = LESS_THAN; get_next_character(); if (error != NO_ERROR) return; if (character == '>') code = NOT_EQUAL; else if (character == '=') code = LESS_EQUAL; else position--; break; case '>': code = GREATER_THAN; get_next_character(); if (error != NO_ERROR) return; if (character == '=') code = GREATER_EQUAL; else position--; break; } scan_and_parse(); INRELATION = false; if (error != NO_ERROR) return; if (ISBOOLEAN) { error = INVALID_OPERAND; return; } addcode(code); ISBOOLEAN = true; } private void boolean_level() { if (!ISBOOLEAN) { error = INVALID_OPERAND; return; } char operator = character; scan_and_parse(); if (error != NO_ERROR) return; if (!ISBOOLEAN) { error = INVALID_OPERAND; return; } switch (operator) { case '&': addcode(AND_CODE); break; case '|': addcode(OR_CODE); break; } } // main routine of scanning and parsing process private void scan_and_parse() { getidentifier(); do { if (error == NO_ERROR) { switch (character) { case '+': case '-': level1(); break; case '*': case '/': level2(); break; case '^': level3(); break; case ',': case ')': return; case '=': case '<': case '>': relation_level(); break; case '&': case '|': boolean_level(); break; default : error = OPERATOR_EXPECTED; } } } while (error == NO_ERROR); } // parse defined function public void parse() { if (valid) return; position = 0; error = NO_ERROR; num = 0; postfixcode = ""; INRELATION = false; ISBOOLEAN = false; scan_and_parse(); if ((error == NO_ERROR) && (position != function.length())) error = PAREN_NOT_MATCH; if ((error == SYNTAX_ERROR) && (postfixcode == "")) error = EXPRESSION_EXPECTED; valid = (error == NO_ERROR); } // define a function. postfix-code becomes invalid public void define(String definition) { function = definition + ")"; function.toLowerCase(); valid = false; } // built-in function call private double built_in_function(int function, double parameter) { switch (function) { case 0: if (radian) return Math.sin(parameter); else return Math.sin(parameter * DEGTORAD); case 1: if (radian) return Math.cos(parameter); else return Math.cos(parameter * DEGTORAD); case 2: if (radian) return Math.tan(parameter); else return Math.tan(parameter * DEGTORAD); case 3: return Math.log(parameter); case 4: return Math.log(parameter) / LOG10; case 5: return Math.abs(parameter); case 6: return Math.rint(parameter); case 7: return parameter-Math.rint(parameter); case 8: if (radian) return Math.asin(parameter); else return Math.asin(parameter) / DEGTORAD; case 9: if (radian) return Math.acos(parameter); else return Math.acos(parameter) / DEGTORAD; case 10: if (radian) return Math.atan(parameter); else return Math.atan(parameter) / DEGTORAD; case 11: return (Math.exp(parameter)-Math.exp(-parameter))/2; case 12: return (Math.exp(parameter)+Math.exp(-parameter))/2; case 13: double a = Math.exp(parameter); double b = Math.exp(-parameter); return (a-b)/(a+b); case 14: return Math.log(parameter + Math.sqrt(parameter * parameter + 1)); case 15: return Math.log(parameter + Math.sqrt(parameter * parameter - 1)); case 16: return Math.log((1 + parameter) / (1 - parameter)) / 2; case 17: return Math.ceil(parameter); case 18: return Math.floor(parameter); case 19: return Math.round(parameter); case 20: return Math.exp(parameter); case 21: return parameter * parameter; case 22: return Math.sqrt(parameter); case 23: if (parameter == 0.0d) return 0; else if (parameter > 0.0d) return 1; else return -1; default: error = CODE_DAMAGED; return Double.NaN; } } // evaluate function's value public double evaluate() { double stack[]; int stack_pointer = -1; int code_pointer = 0; int index = 0; int destination; char code; if (!valid) { error = UNCOMPILED_FUNCTION; return 0; } stack = new double[STACK_SIZE]; error = NO_ERROR; while (true) { try { code = postfixcode.charAt(code_pointer++); } catch (StringIndexOutOfBoundsException e) { return stack[0]; } try { switch (code) { case '+': stack[stack_pointer-1] += stack[stack_pointer]; stack_pointer--; break; case '-': stack[stack_pointer-1] -= stack[stack_pointer]; stack_pointer--; break; case '*': stack[stack_pointer-1] *= stack[stack_pointer]; stack_pointer--; break; case '/': stack[stack_pointer-1] /= stack[stack_pointer]; stack_pointer--; break; case '^': stack[stack_pointer-1] = Math.pow(stack[stack_pointer-1], stack[stack_pointer]); stack_pointer--; break; case '_': stack[stack_pointer] = -stack[stack_pointer]; break; case JUMP_CODE : destination = code_pointer + (int)postfixcode.charAt(code_pointer++); while (code_pointer < destination) { if (postfixcode.charAt(code_pointer++) == NUMERIC) index++; } break; case LESS_THAN : stack_pointer--; stack[stack_pointer] = (stack[stack_pointer] < stack[stack_pointer+1]) ? 1.0 : 0.0; break; case GREATER_THAN : stack_pointer--; stack[stack_pointer] = (stack[stack_pointer] > stack[stack_pointer+1]) ? 1.0 : 0.0; break; case LESS_EQUAL : stack_pointer--; stack[stack_pointer] = (stack[stack_pointer] <= stack[stack_pointer+1]) ? 1.0 : 0.0; break; case GREATER_EQUAL : stack_pointer--; stack[stack_pointer] = (stack[stack_pointer] >= stack[stack_pointer+1]) ? 1.0 : 0.0; break; case EQUAL : stack_pointer--; stack[stack_pointer] = (stack[stack_pointer] == stack[stack_pointer+1]) ? 1.0 : 0.0; break; case NOT_EQUAL : stack_pointer--; stack[stack_pointer] = (stack[stack_pointer] != stack[stack_pointer+1]) ? 1.0 : 0.0; break; case IF_CODE : if (stack[stack_pointer--] == 0.0) { destination = code_pointer + (int)postfixcode.charAt(code_pointer++); while (code_pointer < destination) { if (postfixcode.charAt(code_pointer++) == NUMERIC) index++; } } else code_pointer++; break; case ENDIF : break; // same as NOP case AND_CODE : stack_pointer--; if ((stack[stack_pointer] != 0.0) && (stack[stack_pointer+1] != 0.0)) stack[stack_pointer] = 1.0; else stack[stack_pointer] = 0.0; break; case OR_CODE : stack_pointer--; if ((stack[stack_pointer] != 0.0) || (stack[stack_pointer+1] != 0.0)) stack[stack_pointer] = 1.0; else stack[stack_pointer] = 0.0; break; case NOT_CODE : stack[stack_pointer] = (stack[stack_pointer] == 0.0) ? 1.0 : 0.0; break; case NUMERIC : stack[++stack_pointer] = number[index++]; break; case PI_CODE : stack[++stack_pointer] = Math.PI; break; case E_CODE : stack[++stack_pointer] = Math.E; break; default: if ((int)code >= VAR_OFFSET) stack[++stack_pointer] = varvalue[(int)code-VAR_OFFSET]; else if ((int)code >= FUNC_OFFSET) stack[stack_pointer] = built_in_function((int)code-FUNC_OFFSET, stack[stack_pointer]); else { error = CODE_DAMAGED; return Double.NaN; } } } catch (ArrayIndexOutOfBoundsException e) { error = STACK_OVERFLOW; return Double.NaN; } } } public void debug() { int code_pointer = 0; int index = 0; char code; String s = ""; if (!valid) { error = UNCOMPILED_FUNCTION; return; } while (true) { try { code = postfixcode.charAt(code_pointer++); } catch (StringIndexOutOfBoundsException e) { System.out.println(s); return; } switch (code) { case '+': s += "+ "; break; case '-': s += "- "; break; case '*': s += "* "; break; case '/': s += "/ "; break; case '^': s += "^ "; break; case '_': s += "_ "; break; case JUMP_CODE : s += "JMP "; s += String.valueOf((int)postfixcode.charAt(code_pointer++)); s += " "; break; case LESS_THAN : s += "LT "; break; case GREATER_THAN : s += "GT "; break; case LESS_EQUAL : s += "LE "; break; case EQUAL : s += "EQ "; break; case NOT_EQUAL : s += "NE "; break; case IF_CODE : s += "IF "; s += String.valueOf((int)postfixcode.charAt(code_pointer++)); s += " "; break; case ENDIF : s += "EI "; break; case AND_CODE : s += "& "; break; case OR_CODE : s += "| "; break; case NOT_CODE : s += "! "; break; case NUMERIC : s += String.valueOf(number[index++]); s += " "; break; case PI_CODE : s += "pi "; break; case E_CODE : s += "e "; break; default : s = "xf "; break; } } } }