parser.js

/*!
 Based on ndef.parser, by Raphael Graf(r@undefined.ch)
 http://www.undefined.ch/mparser/index.html

 Ported to JavaScript and modified by Matthew Crumley (email@matthewcrumley.com, http://silentmatt.com/)

 You are free to use and modify this code in anyway you find useful. Please leave this comment in the code
 to acknowledge its original source. If you feel like it, I enjoy hearing about projects that use my code,
 but don't feel like you have to let me know or ask permission.
*/

//  Added by stlsmiths 6/13/2011
//  re-define Array.indexOf, because IE doesn't know it ...
//
//  from http://stellapower.net/content/javascript-support-and-arrayindexof-ie
if (!Array.indexOf) {
	Array.prototype.indexOf = function (obj, start) {
		for (var i = (start || 0); i < this.length; i++) {
			if (this[i] === obj) {
				return i;
			}
		}
		return -1;
	}
}

var Parser = (function (scope) {
	function object(o) {
		function F() {}
		F.prototype = o;
		return new F();
	}

	var TNUMBER = 0;
	var TOP1 = 1;
	var TOP2 = 2;
	var TVAR = 3;
	var TFUNCALL = 4;

	function Token(type_, index_, prio_, number_) {
		this.type_ = type_;
		this.index_ = index_ || 0;
		this.prio_ = prio_ || 0;
		this.number_ = (number_ !== undefined && number_ !== null) ? number_ : 0;
		this.toString = function () {
			switch (this.type_) {
			case TNUMBER:
				return this.number_;
			case TOP1:
			case TOP2:
			case TVAR:
				return this.index_;
			case TFUNCALL:
				return "CALL";
			default:
				return "Invalid Token";
			}
		};
	}

	function Expression(tokens, ops1, ops2, functions, 
		overload_ops1, overload_ops2, simplify_exclude_functions) {

		this.tokens = tokens;
		this.ops1 = ops1;
		this.ops2 = ops2;
		this.functions = functions;
		this.overload_ops1 = overload_ops1;
		this.overload_ops2 = overload_ops2;
		this.simplify_exclude_functions = simplify_exclude_functions;

		this.js_expr_str = this.toString('$_EXPR_OPS_$1', '$_EXPR_OPS_$2');
		this.evaluate = this.toEvalFunction();
	}

	// Based on http://www.json.org/json2.js
  var cx = /[\u0000\u00ad\u0600-\u0604\u070f\u17b4\u17b5\u200c-\u200f\u2028-\u202f\u2060-\u206f\ufeff\ufff0-\uffff]/g,
      escapable = /[\\\'\x00-\x1f\x7f-\x9f\u00ad\u0600-\u0604\u070f\u17b4\u17b5\u200c-\u200f\u2028-\u202f\u2060-\u206f\ufeff\ufff0-\uffff]/g,
      meta = {    // table of character substitutions
          '\b': '\\b',
          '\t': '\\t',
          '\n': '\\n',
          '\f': '\\f',
          '\r': '\\r',
          "'" : "\\'",
          '\\': '\\\\'
      };

	function escapeValue(v) {
		if (typeof v === "string") {
			escapable.lastIndex = 0;
	        return escapable.test(v) ?
	            "'" + v.replace(escapable, function (a) {
	                var c = meta[a];
	                return typeof c === 'string' ? c :
	                    '\\u' + ('0000' + a.charCodeAt(0).toString(16)).slice(-4);
	            }) + "'" :
	            "'" + v + "'";
		}
		return v;
	}

	Expression.prototype = {
		simplify: function (values) {
			values = values || {};
			var nstack = [];
			var newexpression = [];
			var n1;
			var n2;
			var f;
			var L = this.tokens.length;
			var item;
			var i = 0;

			for (i = 0; i < L; i++) {
				item = this.tokens[i];
				var type_ = item.type_;
				var index_ = item.index_;

				if (type_ === TNUMBER) {
					nstack.push(item);
				}
				else if (type_ === TVAR && 
					(index_ in values || index_ in this.functions)) {
					if(index_ in this.functions){
						var name = index_, func = values[name];
						if(typeof func === 'function'){
							this.functions[name] = func;
						}
						item = new Token(TVAR, name, 0, 0);
					}else if(typeof values[index_] === 'function'){
						var func = values[index_];
						this.functions[index_] = func;
						item = new Token(TVAR, index_, 0, 0);					
					}else{
						item = new Token(TNUMBER, 0, 0, values[index_]);	
					}
					nstack.push(item);
				}
				else if (type_ === TOP2 && nstack.length > 1) {
					//comma expr cannot be simplified
					if(index_ !== ','){
						n2 = nstack.pop();
						n1 = nstack.pop();
						f = this.ops2[index_];
						item = new Token(TNUMBER, 0, 0, f(n1.number_, n2.number_));
						nstack.push(item);
					}else{
						n2 = nstack.pop();
						n1 = nstack.pop();
						f = this.ops2[index_];
						var arr = append(n1.list_||n1.number_, n2.number_);
						item = new Token(TNUMBER, 0, 0, f(n1.number_, n2.number_));
						item.list_ = arr;
						nstack.push(item);						
					}
				}
				else if (type_ === TOP1 && nstack.length > 0) {
					n1 = nstack.pop();
					f = this.ops1[index_];
					item = new Token(TNUMBER, 0, 0, f(n1.number_));
					nstack.push(item);
				}else if(type_ === TFUNCALL && nstack.length > 1){
					n1 = nstack.pop();
					f = nstack.pop();
					if(this.simplify_exclude_functions.indexOf(f.index_) < 0){
						var _f = this.functions[f.index_];
						if(n1.type_ === TNUMBER && _f.apply && _f.call){
							n1 = n1.list_ || n1.number_;
							if (Object.prototype.toString.call(n1) == "[object Array]") {
								item = new Token(TNUMBER, 0, 0, _f.apply(undefined, n1));
							}
							else {
								item = new Token(TNUMBER, 0, 0, _f.call(undefined, n1));
							}
							nstack.push(item);
						}else{
							nstack.push(f, n1);
						}
					}else{
						nstack.push(f, n1);
						newexpression.push.apply(newexpression, nstack);
						newexpression.push(item);
						nstack = [];
					}
				}else {
					newexpression.push.apply(newexpression, nstack);
					newexpression.push(item);
					nstack = [];
				}
			}
			newexpression.push.apply(newexpression, nstack);
			nstack = [];

			newexpression = newexpression.map(function(o){
				if(o.list_){
					delete o.list_;
				}
				return o;
			});

			return new Expression(
				newexpression, 
				this.ops1, 
				this.ops2, 
				this.functions,
				this.overload_ops1,
				this.overload_ops2,
				this.simplify_exclude_functions);
		},

		substitute: function (variable, expr) {
			if (!(expr instanceof Expression)) {
				expr = new Parser().parse(String(expr));
			}
			var newexpression = [];
			var L = this.tokens.length;
			var item;
			var i = 0;
			for (i = 0; i < L; i++) {
				item = this.tokens[i];
				var type_ = item.type_;
				if (type_ === TVAR && item.index_ === variable) {
					for (var j = 0; j < expr.tokens.length; j++) {
						var expritem = expr.tokens[j];
						var replitem = new Token(expritem.type_, expritem.index_, expritem.prio_, expritem.number_);
						newexpression.push(replitem);
					}
				}
				else {
					newexpression.push(item);
				}
			}

			var ret = new Expression(
				newexpression, 
				this.ops1, 
				this.ops2, 
				this.functions,
				this.overload_ops1,
				this.overload_ops2,
				this.simplify_exclude_functions);

			return ret;
		},

		toString: function (overload_1, overload_2) {
			var nstack = [];
			var n1;
			var n2;
			var f;
			var L = this.tokens.length;
			var item;
			var i = 0;
			var comma_isclosed = true, comma_prio;

			for (i = 0; i < L; i++) {
				item = this.tokens[i];
				var type_ = item.type_;
				if (type_ === TNUMBER) {
					nstack.push(escapeValue(item.number_));
				}
				else if (type_ === TVAR) {
					nstack.push(item.index_);
				}
				else if (type_ === TOP2) {
					n2 = nstack.pop();
					n1 = nstack.pop();
					f = item.index_;
					if (overload_2 && (f in this.overload_ops2)) {
						comma_isclosed = true;
						nstack.push(overload_2 + "['" + f + "'](" + n1 + "," + n2 + ")");
					}else{
						if(f !== ','){
							if(!comma_isclosed){
								comma_isclosed = true;
								if(!/^\(.*\)$/.test(n1)){
									n1 = "(" + n1 + ")";
								}								
								nstack.push("(" + n1 + f + "(" + n2 + "))");
							}else{
								nstack.push("(" + n1 + f + n2 + ")");
							}
						}else{
							if(!comma_isclosed && comma_prio != null &&
								item.prio_ != comma_prio){
								nstack.push("(" + n1 + ")" + f + "(" + n2 + ")");
							}else{
								nstack.push(n1 + f + n2);
							}
							comma_isclosed = false;
							comma_prio = item.prio_;
						}
					}
				}
				else if (type_ === TOP1) {
					n1 = nstack.pop();
					f = item.index_;
					if (this.ops1[f]) {
						if(overload_1 && (f in this.overload_ops1)){
							comma_isclosed = true;
							nstack.push(overload_1 + "['" + f + "'](" + n1 + ")");
						}else{
							if(!comma_isclosed){
								comma_isclosed = true;
								nstack.push("(" + f + "(" + n1 + "))");
							}else{
								nstack.push("(" + f + n1 + ")");
							}
						}
					}
					else {
						nstack.push(f + "(" + n1 + ")");
					}
				}
				else if (type_ === TFUNCALL) {
					var prev = this.tokens[i - 1];
					comma_isclosed = true;
					n1 = nstack.pop();
					f = nstack.pop();
					if(prev.prio_ - item.prio_ > 10){
						n1 = "(" + n1 + ")";
					}
					if(prev.index_ === ','){
						n1 = "(" + n1 + ")";
					}
					if(!/^\(.*\)$/.test(n1)){
						n1 = "(" + n1 + ")";
					}
					nstack.push(f + n1);
				}
				else {
					throw new Error("invalid Expression");
				}
			}
			if (nstack.length > 1) {
				throw new Error("invalid Expression (parity)");
			}
			return nstack[0].toString();
		},

		variables: function (include_functions) {
			var L = this.tokens.length;
			var vars = [];
			for (var i = 0; i < L; i++) {
				var item = this.tokens[i];
				if (item.type_ === TVAR 
					&& (include_functions || !(item.index_ in this.functions))
					&& (vars.indexOf(item.index_) == -1)) {
					vars.push(item.index_);
				}
			}

			return vars;
		},

		toEvalFunction: function(){
			var expr = this;
			var vars = expr.variables(true);

			return function(values){
				values = values || {};
				var params = [];

				for(var i = 0; i < vars.length; i++){
					var v, key = vars[i];

					if(key in values){
						v = values[key];
					}else{
						var f = expr.functions[key];
						if(f){
							v = f;
						}
					}

					params.push(v);
				}

				var overload_str = 'overload_' + (Math.random() + '').slice(2);
				
				var f = new Function(vars.concat(overload_str + '1', overload_str + '2'), "return " + expr.js_expr_str.replace(/\$_EXPR_OPS_\$/g, overload_str));
				return f.apply(undefined, 
					params.concat(expr.overload_ops1, expr.overload_ops2));
			}
		},

		toJSFunction: function(param_table, values){
			var expr = this;
			if(values) expr = this.simplify(values);

			var vars = expr.variables(true);

			return function(){
				var args = [].slice.call(arguments);
				var params = [];

				for(var i = 0; i < vars.length; i++){
					var v, key = vars[i];
					var idx = param_table.indexOf(key);
					if(idx >= 0){
						v = args[idx];
					}else{
						var f = expr.functions[key];
						if(f){
							v = f;
						}
					}

					params.push(v);
				}

				var overload_str = 'overload_' + (Math.random() + '').slice(2);
				
				var f = new Function(vars.concat(overload_str + '1', overload_str + '2'), "return " + expr.js_expr_str.replace(/\$_EXPR_OPS_\$/g, overload_str));
				return f.apply(undefined, 
					params.concat(expr.overload_ops1, expr.overload_ops2));
			}
		}
	};

	function comma(){
		return arguments[arguments.length - 1];
	}
	function add(a, b) {
		return a + b;
	}
	function sub(a, b) {
		return a - b;
	}
	function mul(a, b) {
		return a * b;
	}
	function div(a, b) {
		return a / b;
	}
	function mod(a, b) {
		return a % b;
	}
	function concat(a, b) {
		return "" + a + b;
	}
	function equal(a, b) {
		return a == b;
	}
	function notEqual(a, b) {
		return a != b;
	}
	function greaterThan(a, b) {
		return a > b;
	}
	function lessThan(a, b) {
		return a < b;
	}
	function greaterThanEqual(a, b) {
		return a >= b;
	}
	function lessThanEqual(a, b) {
		return a <= b;
	}
	function andOperator(a, b) {
		return Boolean(a && b);
	}
	function orOperator(a, b) {
		return Boolean(a || b);
	}
	function sinh(a) {
		return Math.sinh ? Math.sinh(a) : ((Math.exp(a) - Math.exp(-a)) / 2);
	}
	function cosh(a) {
		return Math.cosh ? Math.cosh(a) : ((Math.exp(a) + Math.exp(-a)) / 2);
	}
	function tanh(a) {
		if (Math.tanh) return Math.tanh(a);
		if(a === Infinity) return 1;
		if(a === -Infinity) return -1;
		return (Math.exp(a) - Math.exp(-a)) / (Math.exp(a) + Math.exp(-a));
	}
	function asinh(a) {
		if (Math.asinh) return Math.asinh(a);
		if(a === -Infinity) return a;
		return Math.log(a + Math.sqrt(a * a + 1));
	}
	function acosh(a) {
		return Math.acosh ? Math.acosh(a) : Math.log(a + Math.sqrt(a * a - 1));
	}
	function atanh(a) {
		return Math.atanh ? Math.atanh(a) : (Math.log((1+a)/(1-a)) / 2);
	}
	function log10(a) {
	      return Math.log(a) * Math.LOG10E;
	}
	function neg(a) {
		return -a;
	}
	function positive(a){
		return a;
	}
	function trunc(a) {
		if(Math.trunc) return Math.trunc(a);
		else return a < 0 ? Math.ceil(a) : Math.floor(a);
	}
	function random(a) {
		return Math.random() * (a || 1);
	}
	function fac(a) { //a!
		a = 0 | a;
		if(a === 0) return 1;
		else if(a < 0) return NaN;
		else {
			var b = a;
			while (a > 1) {
				b = b * (--a);
			}
			return b;
		}
	}

	// TODO: use hypot that doesn't overflow
	function hypot() {
		if(Math.hypot) return Math.hypot.apply(this, arguments);
		var y = 0;
		var length = arguments.length;
		for (var i = 0; i < length; i++) {
			if (arguments[i] === Infinity || arguments[i] === -Infinity) {
				return Infinity;
			}
			y += arguments[i] * arguments[i];
		}
		return Math.sqrt(y);
	}

	function condition(cond, yep, nope) {
		return cond ? yep : nope;
	}
	
	function append(a, b) {
		if (Object.prototype.toString.call(a) != "[object Array]") {
			return [a, b];
		}
		a = a.slice();
		a.push(b);
		return a;
	}

	function list(){
		return [].slice.call(arguments);
	}

	function Parser() {
		this.success = false;
		this.errormsg = "";
		this.expression = "";

		this.pos = 0;

		this.tokennumber = 0;
		this.tokenprio = 0;
		this.tokenindex = 0;
		this.tmpprio = 0;

		this.ops1 = {
			"-": neg,
			"+": positive,
			"~!": fac, 			//Suffix operator: begin with ~
			"~?": comma
		};

		this.ops2 = {
			"+": add,
			"-": sub,
			"*": mul,
			"/": div,
			"%": mod,
			"^": Math.pow,
			",": comma,
			"||": concat,
			"==": equal,
			"!=": notEqual,
			">": greaterThan,
			"<": lessThan,
			">=": greaterThanEqual,
			"<=": lessThanEqual,
			"and": andOperator,
			"or": orOperator
		};

		this.overload_ops1 = {
			"~!": fac,
			"~?": comma
		};

		this.overload_ops2 = {
			"^": Math.pow,
			"and": andOperator,
			"or": orOperator
		};

		this.tokenprio_map1 = {
			"-": 4,
			"+": 4,
			"~!": 4,
			"~?": 6
		};

		this.tokenprio_map2 = {
			"," :  0,
			"or":  0,
			"and": 0,
			"||":  1,
			"==":  1,
			"!=":  1,
			">":   1,
			"<":   1,
			">=":  1,
			"<=":  1,
			"+":   2,
			"-":   2,
			"*":   3,
			"/":   4,
			"%":   4,
			"^":   5
		};

		this.functions = {
			"random": random,
			"fac": fac,
			"min": Math.min,
			"max": Math.max,
			"hypot": hypot,
			"pyt": hypot, // backward compat
			"pow": Math.pow,
			"atan2": Math.atan2,
			"cond": condition,

			"sin": Math.sin,
			"cos": Math.cos,
			"tan": Math.tan,
			"asin": Math.asin,
			"acos": Math.acos,
			"atan": Math.atan,
			"sinh": sinh,
			"cosh": cosh,
			"tanh": tanh,
			"asinh": asinh,
			"acosh": acosh,
			"atanh": atanh,
			"sqrt": Math.sqrt,
			"log": Math.log,
			"lg" : log10,
			"log10" : log10,
			"abs": Math.abs,
			"ceil": Math.ceil,
			"floor": Math.floor,
			"round": Math.round,
			"trunc": trunc,
			"exp": Math.exp
		};
		
		this.simplify_exclude_functions = [
			"random"
		];

		this.consts = {
			"E": Math.E,
			"PI": Math.PI
		};
	}

	Parser.parse = function (expr) {
		return new Parser().parse(expr);
	};

	Parser.evaluate = function (expr, variables) {
		return Parser.parse(expr).evaluate(variables);
	};

	Parser.Expression = Expression;

	var PRIMARY      = 1 << 0;
	var OPERATOR     = 1 << 1;
	var FUNCTION     = 1 << 2;
	var LPAREN       = 1 << 3;
	var RPAREN       = 1 << 4;
	var COMMA        = 1 << 5;
	//var SIGN         = 1 << 6;
	var CALL         = 1 << 7;
	var NULLARY_CALL = 1 << 8;

	Parser.prototype = {
		overload: function(key, Class, func){
			if(func.length !== 1 && func.length !== 2){
				throw new Error('Invalid number of arguments, expected 1 or 2.');
			}
			if(!this.ops1[key] && !this.ops2[key]){
				throw new Error('Invalid operator, use addOperator to add one.');
			}
			var type = func.length;
			
			this['overload_map' + type] = this['overload_map' + type] || {};
			this['overload_map_funcs' + type] = this['overload_map_funcs' + type] || {};

			this['overload_map' + type][key]  = this['overload_map' + type][key] || [];
			this['overload_map_funcs' + type][key] = this['overload_map_funcs' + type][key] || [];

			var overload_map = this['overload_map' + type] [key];
			var overload_map_funcs = this['overload_map_funcs' + type][key];
			var self = this;

			function overload(op){
				op = op || function(){
					throw new Error('function ' + op + ' not defined.');
				};
				return function(){
					var args = [].slice.call(arguments);
					var matched = false;

					for(var i = 0; i < args.length; i++){
						var _Class = args[i].constructor;
						var idx = overload_map.indexOf(_Class);

						if(idx >= 0){
							matched = true;
							break;
						}
					}

					if(matched){
						args = args.map(function(o){
							if(!(o instanceof _Class)){
								return new _Class(o);
							}
							return o;
						});
						return overload_map_funcs[idx].apply(this, args);
					}

					return op.apply(this, args);	
				}
			}

			if(overload_map.length <= 0){
				if(key in this.ops1 && func.length === 1){
					this.overload_ops1[key] = this.ops1[key] = overload(this.ops1[key]);
				}else if(key in this.ops2 && func.length === 2){
					this.overload_ops2[key] = this.ops2[key] = overload(this.ops2[key]);
				}
			}
			overload_map.push(Class);
			overload_map_funcs.push(func);
		},

		addOperator: function(name, prio, func){
			if(func.length === 1){
				this.overload_ops1[name] = this.ops1[name] = func;
				this.tokenprio_map1[name] = prio;
			}else if(func.length === 2){
				this.overload_ops2[name] = this.ops2[name] = func;
				this.tokenprio_map2[name] = prio;
			}else{
				throw new Error('Invalid number of arguments, expected 1 or 2.')
			}
		},

		addFunction: function(name, func, can_simplify){
			this.functions[name] = func;
			if(can_simplify === false){
				this.simplify_exclude_functions.push(name);
			}
		},

		parse: function (expr) {
			this.errormsg = "";
			this.success = true;
			var operstack = [];
			var tokenstack = [];
			this.tmpprio = 0;
			var expected = (PRIMARY | LPAREN | FUNCTION);
			var noperators = 0;
			this.expression = expr;
			this.pos = 0;

			while (this.pos < this.expression.length) {
				if (this.isOp1() && (expected & FUNCTION) !== 0) {
					this.tokenprio = this.tokenprio_map1[this.tokenindex];
					noperators++;
					this.pos += this.tokenindex.length;
					this.addfunc(tokenstack, operstack, TOP1);
					expected = (PRIMARY | LPAREN | FUNCTION);
				}
				else if (this.isSuffixOp()){
					this.tokenprio = this.tokenprio_map1[this.tokenindex];
					this.pos += this.tokenindex.length-1;
					noperators++;
					this.addfunc(tokenstack, operstack, TOP1);
					expected = (OPERATOR | RPAREN | COMMA);
				}
				else if (this.isOp2()) {
					this.tokenprio = this.tokenprio_map2[this.tokenindex];
					this.pos += this.tokenindex.length;
					if (this.isComment()) {

					}
					else {
						if ((expected & OPERATOR) === 0) {
							this.error_parsing(this.pos, "unexpected operator");
						}
						noperators += 2;
						this.addfunc(tokenstack, operstack, TOP2);
						expected = (PRIMARY | LPAREN | FUNCTION);
					}
				}
				else if (this.isNumber()) {
					if ((expected & PRIMARY) === 0) {
						this.error_parsing(this.pos, "unexpected number");
					}
					var token = new Token(TNUMBER, 0, 0, this.tokennumber);
					tokenstack.push(token);

					expected = (OPERATOR | RPAREN | COMMA);
				}
				else if (this.isString()) {
					if ((expected & PRIMARY) === 0) {
						this.error_parsing(this.pos, "unexpected string");
					}
					var token = new Token(TNUMBER, 0, 0, this.tokennumber);
					tokenstack.push(token);

					expected = (OPERATOR | RPAREN | COMMA);
				}
				else if (this.isLeftParenth()) {
					this.pos++;
					this.tmpprio += 10;
					
					if ((expected & LPAREN) === 0) {
						this.error_parsing(this.pos, "unexpected \"(\"");
					}

					if (expected & CALL) {
						noperators += 2;
						this.tokenprio = -2;
						this.tokenindex = -1;
						this.addfunc(tokenstack, operstack, TFUNCALL);
					}

					expected = (PRIMARY | LPAREN | FUNCTION | NULLARY_CALL);
				}
				else if (this.isRightParenth()) {
					this.pos++;
					this.tmpprio -= 10;
				  if (expected & NULLARY_CALL) {
						var token = new Token(TNUMBER, 0, 0, []);
						tokenstack.push(token);
					}
					else if ((expected & RPAREN) === 0) {
						this.error_parsing(this.pos, "unexpected \")\"");
					}

					expected = (OPERATOR | RPAREN | COMMA | LPAREN | CALL);
				}
				else if (this.isComma()) {
					this.pos++;
					this.tokenprio = -1;

					if ((expected & COMMA) === 0) {
						this.error_parsing(this.pos, "unexpected \",\"");
					}
					this.addfunc(tokenstack, operstack, TOP2);
					noperators += 2;
					expected = (PRIMARY | LPAREN | FUNCTION);
				}
				else if (this.isConst()) {
					if ((expected & PRIMARY) === 0) {
						this.error_parsing(this.pos, "unexpected constant");
					}
					var consttoken = new Token(TNUMBER, 0, 0, this.tokennumber);
					tokenstack.push(consttoken);
					expected = (OPERATOR | RPAREN | COMMA);
				}
				else if (this.isVar()) {
					if ((expected & PRIMARY) === 0) {
						this.error_parsing(this.pos, "unexpected variable");
					}
					var vartoken = new Token(TVAR, this.tokenindex, 0, 0);
					tokenstack.push(vartoken);

					expected = (OPERATOR | RPAREN | COMMA | LPAREN | CALL);
				}
				else if (this.isWhite()) {
				}
				else {
					if (this.errormsg === "") {
						this.error_parsing(this.pos, "unknown character");
					}
					else {
						this.error_parsing(this.pos, this.errormsg);
					}
				}
			}
			if (this.tmpprio < 0 || this.tmpprio >= 10) {
				this.error_parsing(this.pos, "unmatched \"()\"");
			}
			while (operstack.length > 0) {
				var tmp = operstack.pop();
				tokenstack.push(tmp);
			}

			if (noperators + 1 !== tokenstack.length) {
				//print(noperators + 1);
				//print(tokenstack);
				this.error_parsing(this.pos, "parity");
			}

			return new Expression(
				tokenstack, 
				this.ops1, 
				this.ops2, 
				this.functions,
				this.overload_ops1,
				this.overload_ops2,
				this.simplify_exclude_functions);
		},

		evaluate: function (expr, variables) {
			return this.parse(expr).evaluate(variables);
		},

		error_parsing: function (column, msg) {
			this.success = false;
			this.errormsg = "parse error [column " + (column) + "]: " + msg;
			this.column = column;
			throw new Error(this.errormsg);
		},

//\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\

		addfunc: function (tokenstack, operstack, type_) {
			var operator = new Token(type_, this.tokenindex, this.tokenprio + this.tmpprio, 0);
			while (operstack.length > 0) {
				if (operator.prio_ <= operstack[operstack.length - 1].prio_) {
					tokenstack.push(operstack.pop());
				}
				else {
					break;
				}
			}
			operstack.push(operator);
		},

		// Ported from the yajjl JSON parser at http://code.google.com/p/yajjl/
		unescape: function(v, pos) {
			var buffer = [];
			var escaping = false;

			for (var i = 0; i < v.length; i++) {
				var c = v.charAt(i);

				if (escaping) {
					switch (c) {
					case "'":
						buffer.push("'");
						break;
					case '\\':
						buffer.push('\\');
						break;
					case '/':
						buffer.push('/');
						break;
					case 'b':
						buffer.push('\b');
						break;
					case 'f':
						buffer.push('\f');
						break;
					case 'n':
						buffer.push('\n');
						break;
					case 'r':
						buffer.push('\r');
						break;
					case 't':
						buffer.push('\t');
						break;
					case 'u':
						// interpret the following 4 characters as the hex of the unicode code point
						var codePoint = parseInt(v.substring(i + 1, i + 5), 16);
						buffer.push(String.fromCharCode(codePoint));
						i += 4;
						break;
					default:
						throw this.error_parsing(pos + i, "Illegal escape sequence: '\\" + c + "'");
					}
					escaping = false;
				} else {
					if (c == '\\') {
						escaping = true;
					} else {
						buffer.push(c);
					}
				}
			}

			return buffer.join('');
		},

		isNumber: function () {
			var r = false;
			var str = "";
			while (this.pos < this.expression.length) {
				var code = this.expression.charCodeAt(this.pos);
				if ((code >= 48 && code <= 57) || code === 46) {
					str += this.expression.charAt(this.pos);
					this.pos++;
					this.tokennumber = parseFloat(str);
					r = true;
				}
				else {
					break;
				}
			}
			return r;
		},

		isString: function () {
			var r = false;
			var str = "";
			var startpos = this.pos;
			if (this.pos < this.expression.length && this.expression.charAt(this.pos) == "'") {
				this.pos++;
				while (this.pos < this.expression.length) {
					var code = this.expression.charAt(this.pos);
					if (code != "'" || str.slice(-1) == "\\") {
						str += this.expression.charAt(this.pos);
						this.pos++;
					}
					else {
						this.pos++;
						this.tokennumber = this.unescape(str, startpos);
						r = true;
						break;
					}
				}
			}
			return r;
		},

		isConst: function () {
			var str;
			for (var i in this.consts) {
				if (true) {
					var L = i.length;
					str = this.expression.substr(this.pos, L);
					if (i === str) {
						this.tokennumber = this.consts[i];
						this.pos += L;
						return true;
					}
				}
			}
			return false;
		},

		isLeftParenth: function () {
			var code = this.expression.charCodeAt(this.pos);
			return code === 40;
		},

		isRightParenth: function () {
			var code = this.expression.charCodeAt(this.pos);
			return code === 41;
		},

		isComma: function () {
			var code = this.expression.charCodeAt(this.pos);
			if (code === 44) { // ,
				this.tokenindex = ",";
				return true;
			}
			return false;
		},

		isWhite: function () {
			var code = this.expression.charCodeAt(this.pos);
			if (code === 32 || code === 9 || code === 10 || code === 13) {
				this.pos++;
				return true;
			}
			return false;
		},

		isOp1: function () {
			var rest = this.expression.slice(this.pos);
			var ops = Object.keys(this.ops1).sort(function(a, b){
				return b.length - a.length;
			});
			var self = this;

			var res = ops.some(function(op){
				if(rest.indexOf(op) == 0){
					self.tokenindex = op;
					return true;
				}
			});

			return res;
		},

		isOp2: function () {
			var rest = this.expression.slice(this.pos);
			var ops = Object.keys(this.ops2).sort(function(a, b){
				return b.length - a.length;
			});

			var self = this;

			var res = ops.some(function(op){
				if(rest.indexOf(op) == 0){
					self.tokenindex = op;
					return true;
				}
			});

			return res;
		},

		isSuffixOp: function() {
			var _r = this.expression.slice(this.pos);
			var rest = '~' + _r;
			var ops = Object.keys(this.ops1).sort(function(a, b){
				return b.length - a.length;
			});
			var self = this;

			var res = ops.some(function(op){
				if(op !== '~' && rest.indexOf(op) == 0){
					self.tokenindex = op;
					return true;
				}
			});
			
			if(res){
				var tokenindex = this.tokenindex;
				var len = this.tokenindex.length - 1;
				len += _r.slice(len).length - _r.slice(len).trimLeft().length;

				this.pos += len;

				if(this.pos >= this.expression.length
					|| this.isRightParenth() || this.isOp2() || this.isComma()){
					//look up forward to check if this operator is suffix operator or 2-target operator
					this.tokenindex = tokenindex;
					this.pos -= len;
					return true;
				}else{
					this.pos -= len;
					return false;
				}
			}

			return res;			
		},

		isVar: function () {
			var str = "";
			for (var i = this.pos; i < this.expression.length; i++) {
				var c = this.expression.charAt(i);
				if (c.toUpperCase() === c.toLowerCase()) {
					if (i === this.pos || (c != '_' && (c < '0' || c > '9'))) {
						break;
					}
				}
				str += c;
			}
			if (str.length > 0) {
				this.tokenindex = str;
				this.tokenprio = 4;
				this.pos += str.length;
				return true;
			}
			return false;
		},

		isComment: function () {
			var code = this.expression.charCodeAt(this.pos - 1);
			if (code === 47 && this.expression.charCodeAt(this.pos) === 42) {
				this.pos = this.expression.indexOf("*/", this.pos) + 2;
				if (this.pos === 1) {
					this.pos = this.expression.length;
				}
				return true;
			}
			return false;
		}
	};

	scope.Parser = Parser;
	return Parser
})(typeof exports === 'undefined' ? {} : exports);