REVO2700ExpressionParser#H@qwhitera/******************************************************************************* * 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! * *******************************************************************************/ -------------------------------------------------------------------------------- -- ValueOf parses and evaluates a given expression and delivers its result -- -------------------------------------------------------------------------------- local SourceCode, SourceLength, SourcePosition, curChar local pendingToken, pendingTokens function ValueOf newSourceCode put newSourceCode into SourceCode put the number of chars of SourceCode into SourceLength # **** initialize scanner **** put 1 into SourcePosition put char SourcePosition of SourceCode into curChar # **** initialize tokenizer **** put empty into pendingToken put 0 into pendingTokens # **** parse expression **** local curToken; put nextToken() into curToken if (curToken["Type"] = "eof") then return empty else deferToken(curToken) end if local firstNode; put parsedExpression() into firstNode put nextToken() into curToken if (curToken["Type"] <> "eof") then throw "unexpected characters after expression at position " & \ curToken["Position"] end if return ValueOfNode(firstNode) end ValueOf /******************************************************************************* * * * Scanner * * * *******************************************************************************/ -------------------------------------------------------------------------------- -- atEOF has the end of the source code been reached? -- -------------------------------------------------------------------------------- private function atEOF return (SourcePosition > SourceLength) end atEOF -------------------------------------------------------------------------------- -- proceed proceeds to the next character in the source code -- -------------------------------------------------------------------------------- private command proceed if (atEOF()) then exit proceed add 1 to SourcePosition if (atEOF()) then put "" into curChar else put char SourcePosition of SourceCode into curChar end if end proceed -------------------------------------------------------------------------------- -- skipWhitespace skips all whitespace char.s from the current position on -- -------------------------------------------------------------------------------- private command skipWhitespace repeat while ( \ (curChar = " ") or (curChar = return) or (curChar = tab) \ ) # handles EOF properly proceed end repeat end skipWhitespace /******************************************************************************* * * * Tokenizer * * * *******************************************************************************/ -------------------------------------------------------------------------------- -- deferToken defers a given token for later delivery -- -------------------------------------------------------------------------------- private command deferToken newToken add 1 to pendingTokens put newToken into pendingToken[pendingTokens] end deferToken -------------------------------------------------------------------------------- -- newIdentifierToken creates (and delivers) a new identifier token -- -------------------------------------------------------------------------------- private function newIdentifierToken TokenPosition repeat until not matchText(curChar,"[a-zA-Z0-9]") proceed end repeat return newToken( \ "identifier", TokenPosition, \ char TokenPosition to SourcePosition-1 of SourceCode \ ) end newIdentifierToken -------------------------------------------------------------------------------- -- newNumberToken creates (and delivers) a new number token -- -------------------------------------------------------------------------------- private function newNumberToken TokenPosition repeat until (not matchText(curChar,"[0-9]")) # skip integral part proceed end repeat if (curChar = ".") then # skip fractional part proceed if (not matchText(curChar,"[0-9]")) then throw "invalid number literal at position " & SourcePosition end if repeat until (not matchText(curChar,"[0-9]")) proceed end repeat end if if ((curChar = "e") or (curChar = "E")) then # skip exponential part proceed if ((curChar = "+") or (curChar = "-")) then proceed end if if (not matchText(curChar,"[0-9]")) then throw "invalid number literal at position " & SourcePosition end if repeat until (not matchText(curChar,"[0-9]")) proceed end repeat end if return newToken( \ "number", TokenPosition, \ char TokenPosition to SourcePosition-1 of SourceCode \ ) end newNumberToken -------------------------------------------------------------------------------- -- newToken creates (and delivers) a new token "structure" -- -------------------------------------------------------------------------------- private function newToken TokenType, TokenPosition, TokenValue local freshToken put TokenType into freshToken["Type"] put TokenPosition into freshToken["Position"] put TokenValue into freshToken["Value"] return freshToken end newToken -------------------------------------------------------------------------------- -- nextToken yields the next pending token from the source code -- -------------------------------------------------------------------------------- private function nextToken TokenOffset if (pendingTokens > 0) then local firstToken; put pendingToken[1] into firstToken repeat with i = 2 to pendingTokens put pendingToken[i] into pendingToken[i-1] end repeat put empty into pendingToken[pendingTokens] subtract 1 from pendingTokens return firstToken end if # **** no pending tokens, create a new one **** skipWhitespace local auxChar; put curChar into auxChar switch case atEOF() return newToken("eof", SourcePosition, "") case (curChar is an integer) return newNumberToken(SourcePosition) case (curChar = "(") case (curChar = ")") case (curChar = ",") proceed return newToken(auxChar, SourcePosition-1, auxChar) case (curChar is among the items of "+,-,*,/,%,\") proceed return newToken("operator", SourcePosition-1, auxChar) case matchText(curChar,"[a-zA-Z]") return newIdentifierToken(SourcePosition) default throw "unrecognized character at position " & SourcePosition end switch end nextToken /******************************************************************************* * * * Parser * * * *******************************************************************************/ -------------------------------------------------------------------------------- -- newConstantNode creates a ParseNode for constants -- -------------------------------------------------------------------------------- private function newConstantNode Position, ConstantName local ParseNode put "constant" into ParseNode["Type"] put Position into ParseNode["Position"] put ConstantName into ParseNode["Name"] return ParseNode end newConstantNode -------------------------------------------------------------------------------- -- newFunctionNode creates a ParseNode for function invocations -- -------------------------------------------------------------------------------- private function newFunctionNode Position, FunctionName, ArgumentList local ParseNode put "function" into ParseNode["Type"] put Position into ParseNode["Position"] put FunctionName into ParseNode["Name"] put ArgumentList into ParseNode["ArgumentList"] return ParseNode end newFunctionNode -------------------------------------------------------------------------------- -- newGroupNode creates a ParseNode for grouped expressions -- -------------------------------------------------------------------------------- private function newGroupNode Position, Expression local ParseNode put "group" into ParseNode["Type"] put Position into ParseNode["Position"] put Expression into ParseNode["Expression"] return ParseNode end newGroupNode -------------------------------------------------------------------------------- -- newInfixNode creates a ParseNode for infix operator expressions -- -------------------------------------------------------------------------------- private function newInfixNode Position, Operator, leftOperand, rightOperand local ParseNode put "infix" into ParseNode["Type"] put Position into ParseNode["Position"] put Operator into ParseNode["Operator"] put leftOperand into ParseNode["leftOperand"] put rightOperand into ParseNode["rightOperand"] return ParseNode end newInfixNode -------------------------------------------------------------------------------- -- newLiteralNode creates a ParseNode for literal values -- -------------------------------------------------------------------------------- private function newLiteralNode Position, LiteralValue local ParseNode put "literal" into ParseNode["Type"] put Position into ParseNode["Position"] put LiteralValue into ParseNode["Value"] return ParseNode end newLiteralNode -------------------------------------------------------------------------------- -- newPrefixNode creates a ParseNode for prefix operator expressions -- -------------------------------------------------------------------------------- private function newPrefixNode Position, Operator, Operand local ParseNode put "prefix" into ParseNode["Type"] put Position into ParseNode["Position"] put Operator into ParseNode["Operator"] put Operand into ParseNode["Operand"] return ParseNode end newPrefixNode -------------------------------------------------------------------------------- -- OperatorPriority determines the priority of a given operator -- -------------------------------------------------------------------------------- private function OperatorPriority Operator switch Operator case "+"; case "-" return 1 case "*"; case "/"; case "%"; case "\" return 2 default return 0 end switch end OperatorPriority -------------------------------------------------------------------------------- -- parsedExpression parses (and yields) a given (sub-)expression -- -------------------------------------------------------------------------------- private function parsedExpression leftOperand, Operator, OperatorPosition local minPriority, curPriority if (leftOperand is not an array) then put parsedOperand() into leftOperand local curToken; put nextToken() into curToken if (curToken["Type"] <> "operator") then deferToken(curToken) return leftOperand end if put curToken["Value"] into Operator put curToken["Position"] into OperatorPosition put 0 into minPriority put OperatorPriority(Operator) into curPriority else put OperatorPriority(Operator) into curPriority put curPriority into minPriority end if local rightOperand; put parsedOperand() into rightOperand repeat forever put nextToken() into curToken if (curToken["Type"] <> "operator") then deferToken(curToken) return newInfixNode(OperatorPosition, Operator, leftOperand, rightOperand) end if local newPriority; put OperatorPriority(curToken["Value"]) into newPriority if (newPriority < minPriority) then deferToken(curToken) return newInfixNode(OperatorPosition, Operator, leftOperand, rightOperand) end if if (newPriority <= curPriority) then put newInfixNode(OperatorPosition, Operator, leftOperand, rightOperand) \ into leftOperand put curToken["Value"] into Operator put curToken["Position"] into OperatorPosition put OperatorPriority(Operator) into curPriority put parsedOperand() into rightOperand else # newPriority > curPriority put parsedExpression(rightOperand, curToken["Value"], curToken["Position"]) \ into rightOperand end if end repeat end parsedExpression -------------------------------------------------------------------------------- -- parsedOperand parses (and yields) a single operand -- -------------------------------------------------------------------------------- private function parsedOperand local curToken; put nextToken() into curToken switch curToken["Type"] case "eof" throw "unexpected end-of-input" case "number" return newLiteralNode(curToken["Position"],curToken["Value"]) case "(" local SubExpression; put parsedExpression() into SubExpression local futureToken; put nextToken() into futureToken if (futureToken["Type"] <> ")") then throw "')' expected (to end a grouped expression at position " & \ curToken["Position"] & ")" end if return newGroupNode(curToken["Position"],SubExpression) case "operator" if (curToken["Value"] = "+") or (curToken["Value"] = "-") then put nextToken() into futureToken if (futureToken["Type"] = "number") then # apply sign to numbers if (curToken["Value"] = "-") then put -futureToken["Value"] into futureToken["Value"] end if return newLiteralNode(curToken["Position"],futureToken["Value"]) end if deferToken futureToken if (curToken["Value"] = "+") then return parsedOperand() else return newPrefixNode(curToken["Position"],"-",parsedOperand()) end if else throw "prefix operator expected at position " & curToken["Position"] end if case "identifier" put nextToken() into futureToken if (futureToken["Type"] = "(") then return newFunctionNode( \ curToken["Position"], curToken["Value"], \ parsedArgumentList() \ ) else deferToken futureToken return newConstantNode(curToken["Position"],curToken["Value"]) end if default throw "operand expected at position " & curToken["Position"] end switch end parsedOperand -------------------------------------------------------------------------------- -- parsedArgumentList parses the argument list for a function invocation -- -------------------------------------------------------------------------------- private function parsedArgumentList local ArgumentList, ArgumentCount; put 0 into ArgumentCount local curToken; put nextToken() into curToken if (curToken["Type"] = ")") then return ArgumentList deferToken(curToken) repeat forever add 1 to ArgumentCount put parsedExpression() into ArgumentList[ArgumentCount] put nextToken() into curToken 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"] end switch end repeat # return ArgumentList end parsedArgumentList /******************************************************************************* * * * Evaluator * * * *******************************************************************************/ -------------------------------------------------------------------------------- -- ConstantValue delivers the value of a given constant -- -------------------------------------------------------------------------------- private function ConstantValue ConstantName switch ConstantName case "pi" return pi case "e" return exp(1) # # <<<< additional constants may be added here <<<< # default throw "unknown constant '" & ConstantName & "'" end switch end ConstantValue -------------------------------------------------------------------------------- -- expectNArguments verifies the presence of all required arguments -- -------------------------------------------------------------------------------- private command expectNArguments ArgumentList, nMin, nMax, Position if (ArgumentList is not an array) then if (nMin <> 0) then throw "no arguments given (in function call at position " & Position & ")" end if else local ArgumentCount; put the number of elements of ArgumentList into ArgumentCount switch case (ArgumentCount < nMin) throw "insufficient arguments given (in function call at position " & \ Position & ")" case (nMax is not empty) and (ArgumentCount > nMax) throw "too many arguments given (in function call at position " & \ Position & ")" end switch end if end expectNArguments -------------------------------------------------------------------------------- -- FunctionValue invokes a given function and delivers the result -- -------------------------------------------------------------------------------- private function FunctionValue FunctionName, Position, ArgumentList switch FunctionName case "sin" expectNArguments ArgumentList, 1,1, Position return sin(ValueOfNode(ArgumentList[1])) case "cos" expectNArguments ArgumentList, 1,1, Position return cos(ValueOfNode(ArgumentList[1])) case "tan" expectNArguments ArgumentList, 1,1, Position return tan(ValueOfNode(ArgumentList[1])) case "deg2rad" expectNArguments ArgumentList, 1,1, Position return ValueOfNode(ArgumentList[1])*pi/180 case "rad2deg" expectNArguments ArgumentList, 1,1, Position return ValueOfNode(ArgumentList[1])*180/pi case "asin" expectNArguments ArgumentList, 1,1, Position return asin(ValueOfNode(ArgumentList[1])) case "acos" expectNArguments ArgumentList, 1,1, Position return acos(ValueOfNode(ArgumentList[1])) case "atan" expectNArguments ArgumentList, 1,1, Position return atan(ValueOfNode(ArgumentList[1])) case "exp" expectNArguments ArgumentList, 1,1, Position return exp(ValueOfNode(ArgumentList[1])) case "exp2" expectNArguments ArgumentList, 1,1, Position return exp2(ValueOfNode(ArgumentList[1])) case "exp10" expectNArguments ArgumentList, 1,1, Position return exp10(ValueOfNode(ArgumentList[1])) case "ln" expectNArguments ArgumentList, 1,1, Position return ln(ValueOfNode(ArgumentList[1])) case "log2" expectNArguments ArgumentList, 1,1, Position return log2(ValueOfNode(ArgumentList[1])) case "log10" expectNArguments ArgumentList, 1,1, Position return log10(ValueOfNode(ArgumentList[1])) case "sum" expectNArguments ArgumentList, 1,, Position local Outcome; put ValueOfNode(ArgumentList[1]) into Outcome repeat with i = 2 to the number of elements of ArgumentList add ValueOfNode(ArgumentList[i]) to Outcome end repeat return Outcome case "min" expectNArguments ArgumentList, 1,, Position put ValueOfNode(ArgumentList[1]) into Outcome repeat with i = 2 to the number of elements of ArgumentList local newValue; put ValueOfNode(ArgumentList[i]) into newValue if (newValue < Outcome) then put newValue into Outcome end repeat return Outcome case "max" expectNArguments ArgumentList, 1,, Position put ValueOfNode(ArgumentList[1]) into Outcome repeat with i = 2 to the number of elements of ArgumentList put ValueOfNode(ArgumentList[i]) into newValue if (newValue > Outcome) then put newValue into Outcome end repeat return Outcome # # <<<< additional functions may be added here <<<< # default throw "unknown function '" & FunctionName & "'" end switch end FunctionValue -------------------------------------------------------------------------------- -- ValueOfNode evaluates a given node and yields the result -- -------------------------------------------------------------------------------- private function ValueOfNode ParseNode 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"] = "+") then # not really necessary return ValueOfNode(ParseNode["operand"]) else return -ValueOfNode(ParseNode["operand"]) end if case "infix" local leftOperand; put ValueOfNode(ParseNode["leftOperand"]) into leftOperand local rightOperand; put ValueOfNode(ParseNode["rightOperand"]) into 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 mod rightOperand # may throw an error case "\" return leftOperand div rightOperand # may throw an error default throw "internal error: unknown infix operator '" & ParseNode["Operator"] & "'" end switch default throw "internal error: unknown node type '" & ParseNode["Type"] & "'" end switch end ValueOfNode 4ExpressionParser Library Stack cREVTempMaster-windowManagerPlacefalsemenubarlinkHiliteColor blendLevel0 cantAbortfalse maxWidth65535rect194,114,594,514 patterns colors decorationsdefaulticonicfalselinkVisitedColorshadowtrue cantDeletetrueid1002altId0 hcAddressingfalsestartUpIconicfalse windowShape0titleExpressionParser Library Stack linkColor cantModifyfalse textStyle maxHeight65535underlineLinksstyletopleveldestroyWindowfalse liveresizingfalse passwordscroll0 behaviorpasskeyicon0nameExpressionParser resizabletrue alwaysBufferfalseformatForPrintingfalsevisibletruemetalfalse minWidth32 destroyStacktrue textSize textFont dynamicPathsfalse minHeight32cREVGeometryCachestackID1002 cREVGeneralbreakpointconditionsscripteditorvscroll8655 breakpointsbreakpointstates @cREVTempMasterinksrcCopy dontSearchfalsemarkfalsethreeDtrue blendLevel0rect 0,0,400,400defaultButton patterns colors cantDeletefalseid1002altId0 textStyle behaviorname card id 1002layer1 borderWidth2 showBorderfalse textSize textFontcREVGeometryCachetotal0order