package { /******************************************************************************* * Copyright (c) 2009 Andreas Rozek * * * * Permission is hereby granted, free of charge, to any person obtaining a copy * * of this software and associated documentation files (the "Software"),to deal * * in the Software without restriction, including without limitation the rights * * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell * * copies of the Software, and to permit persons to whom the Software is fur- * * nished to do so, subject to the following conditions: * * * * The above copyright notice and this permission notice shall be included in * * all copies or substantial portions of the Software. * * * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR * * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, * * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE * * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIA- * * BILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, * * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN * * THE SOFTWARE. * * * * Additionally, any modifications to the original Software must be clearly * * marked in a way, that the original author will never be considered as the * * author of these modifications! * *******************************************************************************/ public class ExpressionParser { public function ExpressionParser () { /* nop */ }; protected static var SourceCode:String; protected static var SourceLength:int; protected static var SourcePosition:int; protected static var curChar:String; protected static var TokenStack:Array; public static function ValueOf (newSourceCode:String):Number { SourceCode = newSourceCode; SourceLength = SourceCode.length; /**** initialize scanner ****/ SourcePosition = 0; curChar = SourceCode.charAt(0); /**** initialize tokenizer ****/ TokenStack = new Array(); /**** parse expression ****/ var curToken:Object = nextToken() if (curToken.Type === "eof") { return NaN; } else { deferToken(curToken); }; var firstNode:Object = parsedExpression(); curToken = nextToken(); if (curToken.Type !== "eof") { throw "unexpected characters after expression at position " + (curToken.Position+1); }; return ValueOfNode(firstNode); }; /******************************************************************************* * * * Scanner * * * *******************************************************************************/ //------------------------------------------------------------------------------ // atEOF has the end of the source code been reached? //------------------------------------------------------------------------------ protected static function atEOF ():Boolean { return (SourcePosition >= SourceLength); }; //------------------------------------------------------------------------------ // proceed proceeds to the next character in the source code //------------------------------------------------------------------------------ protected static function proceed ():void { if (atEOF()) return; SourcePosition++; if (atEOF()) { curChar = ""; } else { curChar = SourceCode.charAt(SourcePosition); }; }; //------------------------------------------------------------------------------ // skipWhitespace skips all whitespace char.s from the current position on //------------------------------------------------------------------------------ protected static function skipWhitespace ():void { while ( (curChar === " ") || (curChar === "\n") || (curChar === "\r") || (curChar === "\t") ) { // handles EOF properly proceed(); }; }; /******************************************************************************* * * * Tokenizer * * * *******************************************************************************/ //------------------------------------------------------------------------------ // deferToken defers a given token for later delivery //------------------------------------------------------------------------------ protected static function deferToken (newToken:Object):void { TokenStack.push(newToken); }; //------------------------------------------------------------------------------ // newIdentifierToken creates (and delivers) a new identifier token //------------------------------------------------------------------------------ protected static function newIdentifierToken (TokenPosition:int):Object { do { proceed(); } while (curChar.search(/^[a-zA-Z0-9]$/) === 0); return { Type: "identifier", Position: TokenPosition, Value: SourceCode.slice(TokenPosition,SourcePosition) }; }; //------------------------------------------------------------------------------ // newNumberToken creates (and delivers) a new number token //------------------------------------------------------------------------------ protected static function newNumberToken (TokenPosition:int):Object { do { // skip integral part proceed(); } while (curChar.search(/^[0-9]$/) === 0); if (curChar === ".") { // skip fractional part proceed() if (curChar.search(/^[0-9]$/) !== 0) { throw "invalid number literal at position " + (SourcePosition+1); }; do { proceed(); } while (curChar.search(/^[0-9]$/) === 0); }; if ((curChar === "e") || (curChar === "E")) { // skip exponential part proceed(); if ((curChar === "+") || (curChar === "-")) { proceed(); }; if (curChar.search(/^[0-9]$/) !== 0) { throw "invalid number literal at position " + (SourcePosition+1); }; do { proceed(); } while (curChar.search(/^[0-9]$/) === 0); }; return { Type: "number", Position: TokenPosition, Value: SourceCode.slice(TokenPosition,SourcePosition) }; }; //------------------------------------------------------------------------------ // nextToken yields the next pending token from the source code //------------------------------------------------------------------------------ protected static function nextToken ():Object { if (TokenStack.length > 0) { return TokenStack.pop(); }; // **** no pending tokens, create a new one **** skipWhitespace(); var auxChar:String = curChar; if (atEOF()) { return {Type:"eof", Position:SourcePosition, Value:""}; } else if ("0123456789".indexOf(curChar) >= 0) { return newNumberToken(SourcePosition); } else if ("(),".indexOf(curChar) >= 0) { proceed(); return {Type:auxChar, Position:SourcePosition-1, Value:auxChar}; } else if ("+-*/%\\".indexOf(curChar) >= 0) { proceed(); return {Type:"operator", Position:SourcePosition-1, Value:auxChar}; } else if (curChar.search(/^[a-zA-Z]$/) === 0) { return newIdentifierToken(SourcePosition); } else { throw "unrecognized character at position " + (SourcePosition+1); }; }; /******************************************************************************* * * * Parser * * * *******************************************************************************/ //------------------------------------------------------------------------------ // newConstantNode creates a ParseNode for constants //------------------------------------------------------------------------------ protected static function newConstantNode ( Position:int, ConstantName:String ):Object { return { Type: "constant", Position: Position, Name: ConstantName.toLowerCase() }; }; //------------------------------------------------------------------------------ // newFunctionNode creates a ParseNode for function invocations //------------------------------------------------------------------------------ protected static function newFunctionNode ( Position:int, FunctionName:String, ArgumentList:Array ):Object { return { Type: "function", Position: Position, Name: FunctionName.toLowerCase(), ArgumentList: ArgumentList }; }; //------------------------------------------------------------------------------ // newGroupNode creates a ParseNode for grouped expressions //------------------------------------------------------------------------------ protected static function newGroupNode ( Position:int, Expression:Object ):Object { return { Type: "group", Position: Position, Expression: Expression }; }; //------------------------------------------------------------------------------ // newInfixNode creates a ParseNode for infix operator expressions //------------------------------------------------------------------------------ protected static function newInfixNode ( Position:int, Operator:String, leftOperand:Object, rightOperand:Object ):Object { return { Type: "infix", Position: Position, Operator: Operator, leftOperand: leftOperand, rightOperand: rightOperand }; }; //------------------------------------------------------------------------------ // newLiteralNode creates a ParseNode for literal values //------------------------------------------------------------------------------ protected static function newLiteralNode ( Position:int, LiteralValue:String ):Object { return { Type: "literal", Position: Position, Value: Number(LiteralValue) }; }; //------------------------------------------------------------------------------ // newPrefixNode creates a ParseNode for prefix operator expressions //------------------------------------------------------------------------------ protected static function newPrefixNode( Position:int, Operator:String, Operand:Object ):Object { return { Type: "prefix", Position: Position, Operator: Operator, Operand: Operand }; }; //------------------------------------------------------------------------------ // OperatorPriority determines the priority of a given operator //------------------------------------------------------------------------------ protected static function OperatorPriority (Operator:String):int { switch (Operator) { case "+": case "-": return 1; case "*": case "/": case "%": case "\\": return 2; default: return 0; }; }; //------------------------------------------------------------------------------ // parsedExpression parses (and yields) a given (sub-)expression //------------------------------------------------------------------------------ protected static function parsedExpression ( leftOperand:Object = null, Operator:String = "", OperatorPosition:int = 0 ):Object { var minPriority:int, curPriority:int; if (leftOperand === null) { leftOperand = parsedOperand(); var curToken:Object = nextToken(); if (curToken.Type != "operator") { deferToken(curToken); return leftOperand; }; Operator = curToken.Value; OperatorPosition = curToken.Position; minPriority = 0; curPriority = OperatorPriority(Operator); } else { curPriority = OperatorPriority(Operator); minPriority = curPriority; }; var rightOperand:Object = parsedOperand(); while (true) { curToken = nextToken(); if (curToken.Type != "operator") { deferToken(curToken); return newInfixNode(OperatorPosition, Operator, leftOperand, rightOperand); }; var newPriority:int = OperatorPriority(curToken.Value); if (newPriority < minPriority) { deferToken(curToken); return newInfixNode(OperatorPosition, Operator, leftOperand, rightOperand); }; if (newPriority <= curPriority) { leftOperand = newInfixNode( OperatorPosition, Operator, leftOperand, rightOperand ); Operator = curToken.Value; OperatorPosition = curToken.Position; curPriority = OperatorPriority(Operator); rightOperand = parsedOperand(); } else { // newPriority > curPriority rightOperand = parsedExpression( rightOperand, curToken.Value, curToken.Position ); }; }; return null; // just to satisfy the compiler! }; //------------------------------------------------------------------------------ // parsedOperand parses (and yields) a single operand //------------------------------------------------------------------------------ protected static function parsedOperand ():Object { var curToken:Object = nextToken(); switch (curToken.Type) { case "eof": throw "unexpected end-of-input"; case "number": return newLiteralNode(curToken.Position, curToken.Value); case "(": var SubExpression:Object = parsedExpression(); var futureToken:Object = nextToken(); if (futureToken.Type != ")") { throw "')' expected (to end a grouped expression at position " + (curToken.Position+1) + ")"; }; return newGroupNode(curToken.Position, SubExpression); case "operator": if ((curToken.Value === "+") || (curToken.Value === "-")) { futureToken = nextToken(); if (futureToken.Type === "number") { // apply sign to numbers if (curToken.Value === "-") { futureToken.Value = -futureToken.Value; }; return newLiteralNode(curToken.Position, futureToken.Value); }; deferToken(futureToken); if (curToken.Value === "+") { return parsedOperand(); } else { return newPrefixNode(curToken.Position, "-", parsedOperand()); }; } else { throw "prefix operator expected at position " + (curToken.Position+1); }; case "identifier": futureToken = nextToken(); if (futureToken.Type === "(") { return newFunctionNode( curToken.Position, curToken.Value, parsedArgumentList() ); } else { deferToken(futureToken) return newConstantNode(curToken.Position, curToken.Value); }; default: throw "operand expected at position " + (curToken.Position+1); }; }; //------------------------------------------------------------------------------ // parsedArgumentList parses the argument list for a function invocation //------------------------------------------------------------------------------ protected static function parsedArgumentList ():Array { var ArgumentList:Array = new Array(); var curToken:Object = nextToken(); if (curToken.Type === ")") return ArgumentList; deferToken(curToken); while (true) { ArgumentList.push(parsedExpression()); curToken = nextToken(); switch (curToken.Type) { case "eof": throw "unexpected end-of-input within function invocation"; case ")": return ArgumentList; case ",": break; default: throw "',' or ')' expected at position " + (curToken.Position+1); }; }; return null; // just to satisfy the compiler! }; /******************************************************************************* * * * Evaluator * * * *******************************************************************************/ //------------------------------------------------------------------------------ // ConstantValue delivers the value of a given constant //------------------------------------------------------------------------------ protected static function ConstantValue (ConstantName:String):Number { switch (ConstantName) { case "pi": return Math.PI; case "e": return Math.E; case "infinity": return 1/0; // // <<<< additional constants may be added here <<<< // default: throw "unknown constant '" + ConstantName + "'"; }; }; //------------------------------------------------------------------------------ // expectNArguments verifies the presence of all required arguments //------------------------------------------------------------------------------ protected static function expectNArguments ( ArgumentList:Array, nMin:int, nMax:int, Position:int ):void { if (ArgumentList == null) { if (nMin !== 0) { throw "no arguments given (in function call at position " + (Position+1) + ")"; }; } else { var ArgumentCount:int = ArgumentList.length; if (ArgumentCount < nMin) { throw "insufficient arguments given (in function call at position " + (Position+1) + ")"; } else if ((nMax >= 0) && (ArgumentCount > nMax)) { throw "too many arguments given (in function call at position " + (Position+1) + ")"; }; }; }; //------------------------------------------------------------------------------ // FunctionValue invokes a given function and delivers the result //------------------------------------------------------------------------------ protected static function FunctionValue ( FunctionName:String, Position:int, ArgumentList:Array = null ):Number { switch (FunctionName) { case "sin": expectNArguments(ArgumentList, 1,1, Position); return Math.sin(ValueOfNode(ArgumentList[0])); case "cos": expectNArguments(ArgumentList, 1,1, Position); return Math.cos(ValueOfNode(ArgumentList[0])); case "tan": expectNArguments(ArgumentList, 1,1, Position); return Math.tan(ValueOfNode(ArgumentList[0])); case "deg2rad": expectNArguments(ArgumentList, 1,1, Position); return ValueOfNode(ArgumentList[0])*Math.PI/180; case "rad2deg": expectNArguments(ArgumentList, 1,1, Position); return ValueOfNode(ArgumentList[0])*180/Math.PI; case "asin": expectNArguments(ArgumentList, 1,1, Position); return Math.asin(ValueOfNode(ArgumentList[0])); case "acos": expectNArguments(ArgumentList, 1,1, Position); return Math.acos(ValueOfNode(ArgumentList[0])); case "atan": expectNArguments(ArgumentList, 1,1, Position); return Math.atan(ValueOfNode(ArgumentList[0])); case "exp": expectNArguments(ArgumentList, 1,1, Position); return Math.exp(ValueOfNode(ArgumentList[0])); case "exp2": expectNArguments(ArgumentList, 1,1, Position); return Math.pow(2,ValueOfNode(ArgumentList[0])); case "exp10": expectNArguments(ArgumentList, 1,1, Position); return Math.pow(10,ValueOfNode(ArgumentList[0])); case "ln": expectNArguments(ArgumentList, 1,1, Position); return Math.log(ValueOfNode(ArgumentList[0])); case "log2": expectNArguments(ArgumentList, 1,1, Position); return Math.log(ValueOfNode(ArgumentList[0]))/Math.log(2); case "log10": expectNArguments(ArgumentList, 1,1, Position); return Math.log(ValueOfNode(ArgumentList[0]))/Math.log(10); case "ceil": expectNArguments(ArgumentList, 1,1, Position); return Math.ceil(ValueOfNode(ArgumentList[0])); case "floor": expectNArguments(ArgumentList, 1,1, Position); return Math.floor(ValueOfNode(ArgumentList[0])); case "round": expectNArguments(ArgumentList, 1,1, Position); return Math.round(ValueOfNode(ArgumentList[0])); case "random": expectNArguments(ArgumentList, 0,0, Position); return Math.random(); case "sum": expectNArguments(ArgumentList, 1,-1, Position); var Outcome:Number = ValueOfNode(ArgumentList[0]); for (var i:int = 1; i < ArgumentList.length; i++) { Outcome += ValueOfNode(ArgumentList[i]); }; return Outcome; case "min": expectNArguments(ArgumentList, 1,-1, Position); Outcome = ValueOfNode(ArgumentList[0]); for (i = 1; i < ArgumentList.length; i++) { var newValue:Number = ValueOfNode(ArgumentList[i]); if (newValue < Outcome) Outcome = newValue; }; return Outcome; case "max": expectNArguments(ArgumentList, 1,-1, Position); Outcome = ValueOfNode(ArgumentList[0]); for (i = 1; i < ArgumentList.length; i++) { newValue = ValueOfNode(ArgumentList[i]); if (newValue > Outcome) Outcome = newValue; }; return Outcome; // // <<<< additional functions may be added here <<<< // default: throw "unknown function '" + FunctionName + "'"; }; }; //------------------------------------------------------------------------------ // ValueOfNode evaluates a given node and yields the result //------------------------------------------------------------------------------ protected static function ValueOfNode (ParseNode:Object):Number { switch (ParseNode.Type) { case "literal": return ParseNode.Value; case "constant": return ConstantValue(ParseNode.Name); case "function": return FunctionValue( ParseNode.Name, ParseNode.Position, ParseNode.ArgumentList ); case "group": return ValueOfNode(ParseNode.Expression); case "prefix": if (ParseNode.Operator === "+") { // not really necessary return ValueOfNode(ParseNode.Operand); } else { return -ValueOfNode(ParseNode.Operand); }; case "infix": var leftOperand:Number = ValueOfNode(ParseNode.leftOperand); var rightOperand:Number = ValueOfNode(ParseNode.rightOperand); switch (ParseNode.Operator) { case "+": return leftOperand + rightOperand; case "-": return leftOperand - rightOperand; case "*": return leftOperand * rightOperand; case "/": return leftOperand / rightOperand; // may throw an error case "%": return leftOperand % rightOperand; // may throw an error case "\\": var Outcome:Number = leftOperand / rightOperand; // may throw an error return (Outcome < 0 ? Math.ceil(Outcome) : Math.floor(Outcome)); default: throw "internal error: unknown infix operator '" + ParseNode.Operator + "'"; }; default: throw "internal error: unknown node type '" + ParseNode.Type + "'"; }; }; } }