From a2d7b6445f2287bd74e09ad4ec530ea2c2449239 Mon Sep 17 00:00:00 2001 From: goodale Date: Sun, 4 Nov 2001 23:01:58 +0000 Subject: New improved, or at least more functional, expression parser and evaluator. Now can deal with both floating point and integer values. You can use the functions from the standard C maths library which take one argument. Evaluation should be faster, 'though parsing is probably a bit slower. Now the user-supplied evaluation routine is called just once at the beginning of the evaluation, so if any of the evaluations need a global operation, these can all be done at once. The routines have now been renamed as Util_ functions and the header file cctki_Expression.h has been renamed as util_Expression.h. IMPORTANT NOTE: The above means you will need to rm configs/*/build/Cactus/util/Expression.c.d rm configs/*/build/Cactus/main/Groups.c.d after updating to get rid of stale dependency files. Tom git-svn-id: http://svn.cactuscode.org/flesh/trunk@2449 17b73243-c579-4c4c-a9d2-2d5706c11dac --- src/util/Expression.c | 1108 ++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 869 insertions(+), 239 deletions(-) (limited to 'src/util/Expression.c') diff --git a/src/util/Expression.c b/src/util/Expression.c index 6c9e2888..0233a4fe 100644 --- a/src/util/Expression.c +++ b/src/util/Expression.c @@ -4,11 +4,13 @@ @author Tom Goodale @desc Expression evaluator. + Can cope with arithmetic expressions and ones involving the standard + C library mathematical functions (or those taking only one argument). @enddesc @version $Header$ @@*/ -#ifndef TEST_CCTKI_EVALUATE +#ifndef TEST_EXPRESSION_PARSER #include "cctk.h" #endif @@ -16,11 +18,17 @@ #include #include -#include "cctki_Expression.h" +#include + +#include "util_Expression.h" static const char *rcsid = "$Header$"; +#ifndef TEST_EXPRESSION_PARSER +#include "util_String.h" CCTK_FILEVERSION(util_Expression_c) +#define strdup(a) Util_Strdup(a) +#endif /******************************************************************** ********************* Local Data Types *********************** @@ -38,24 +46,31 @@ typedef struct PToken ********************************************************************/ static pToken *Tokenise(const char *expression); -static char *RPParse(pToken **current, char *stack, int *stacklength); -static int Evaluate(int val1, const char *operator, int val2); +int RPParse(pToken **current,uExpressionInternals *buffer); +static int EvaluateBinary(uExpressionValue *retval, + const uExpressionValue *val1, + uExpressionOpcode opcode, + const uExpressionValue *val2); + +static int EvaluateUnary(uExpressionValue *retval, + uExpressionOpcode opcode, + const uExpressionValue *value); static int isoperator(const char *token); static int cmpprecendence(const char *op1, const char *op2); +static int opencode(const char *operator, uExpressionType *type, uExpressionOpcode *opcode); -static pToken *newtoken(const char *tokenstart, const char *tokenend); +static int StoreVar(uExpressionInternals *buffer, const char *var); -#if 0 -static void insertbefore(pToken *base, pToken *this); -#endif +static pToken *newtoken(const char *tokenstart, const char *tokenend); +static void FreeTokens(pToken *list); +static void insertafter(pToken *base, pToken *this); -#ifdef TEST_CCTKI_EVALUATE +#ifdef TEST_EXPRESSION_PARSER +static const char *opname(uExpressionOpcode opcode); static void printtokens(pToken *start); #endif -static void insertafter(pToken *base, pToken *this); -static void FreeTokens(pToken *list); /******************************************************************** ********************* Other Routine Prototypes ********************* @@ -65,57 +80,112 @@ static void FreeTokens(pToken *list); ********************* Local Data ***************************** ********************************************************************/ -#define INITIAL_BUFFER_LENGTH 1000 -#define MAX_STACK_SIZE 256 #define MAX_OPS 100 +#define MAX_STACK_SIZE 256 + +static struct +{ + const char *operator; + uExpressionType type; + int precedence; + uExpressionOpcode opcode; +} operators[] = { + /* Binary operators. */ + {"=", binary, 1,OP_EQUALS}, + {"<", binary, 1,OP_LESS_THAN}, + {">", binary, 1,OP_GREATER_THAN}, + {"<=", binary, 1,OP_LEQUALS}, + {">=", binary, 1,OP_GEQUALS}, + {"&&", binary, 2,OP_AND}, + {"||", binary, 2,OP_OR}, + {"+", binary, 3,OP_PLUS}, + {"-", binary, 3,OP_MINUS}, + {"/", binary, 4,OP_DIV}, + {"*", binary, 4,OP_TIMES}, + {"^", binary, 5,OP_POWER}, + /* Unary Operators - these must have the highest precedence. */ + {"acos", unary, 6, OP_ACOS}, + {"asin", unary, 6, OP_ASIN}, + {"atan", unary, 6, OP_ATAN}, + {"ceil", unary, 6, OP_CEIL}, + {"cos" , unary, 6, OP_COS}, + {"cosh", unary, 6, OP_COSH}, + {"exp", unary, 6, OP_EXP}, + {"fabs", unary, 6, OP_FABS}, + {"floor", unary, 6, OP_FLOOR}, + {"log", unary, 6, OP_LOG}, + {"log10", unary, 6, OP_LOG10}, + {"sin", unary, 6, OP_SIN}, + {"sinh", unary, 6, OP_SINH}, + {"sqrt", unary, 6, OP_SQRT}, + {"tan", unary, 6, OP_TAN}, + {"tanh", unary, 6, OP_TANH}, + {NULL, binary, -1,OP_NONE} +}; + /******************************************************************** ********************* External Routines ********************** ********************************************************************/ /*@@ - @routine CCTKi_ExpressionParse + @routine Util_ExpressionParse @date Tue Sep 19 21:23:08 2000 @author Tom Goodale @desc - Parses an expression returning a predigested string in RPN. + Parses an expression returning a predigested representation + suitable for passing to ExpressionEvaluate. @enddesc @calls @calledby @history @endhistory + @var expression + @vdesc Expression to parse + @vtype const char * + @vio in + @vcomment + + @endvar + @returntype uExpression + @returndesc + The parsed form of the expression or NULL on error. + @endreturndesc @@*/ -char *CCTKi_ExpressionParse(const char *expression) +uExpression Util_ExpressionParse(const char *expression) { pToken *list; pToken *temp; - char *buffer; - int buffer_length; + uExpressionInternals *buffer; - buffer_length = INITIAL_BUFFER_LENGTH; - - buffer = (char *)malloc(buffer_length); + buffer = (uExpressionInternals *)malloc(sizeof(uExpressionInternals)); if(buffer) { + /* Initialise the buffer */ + buffer->ntokens = 0; + buffer->tokens = NULL; + buffer->nvars = 0; + buffer->vars = NULL; + /* FIXME: Don't really need a two pass algorithm here - * it can all be done in one step. */ - + /* Split the list into tokens */ list = Tokenise(expression); - -#ifdef TEST_CCTKI_EVALUATE + +#ifdef TEST_EXPRESSION_PARSER printtokens(list); #endif temp = list; /* Convert the list into a string in RPN order */ - buffer = RPParse(&temp, buffer, &buffer_length); + RPParse(&temp, buffer); FreeTokens(list); } @@ -124,11 +194,11 @@ char *CCTKi_ExpressionParse(const char *expression) } /*@@ - @routine CCTKi_ExpressionEvaluate + @routine Util_ExpressionEvaluate @date Tue Sep 19 21:23:40 2000 @author Tom Goodale @desc - Evaluates an parsed expression string created by CCTKI_ExpressionParse. + Evaluates a parsed expression created by Util_ExpressionParse. The user passes in a function which is used to evaluate all operands. @enddesc @calls @@ -136,48 +206,219 @@ char *CCTKi_ExpressionParse(const char *expression) @history @endhistory + @var buffer + @vdesc The parsed expression + @vtype const uExpression + @vio in + @vcomment + This expression should have been created by Util_ExpressionParse + @endvar + @var retval + @vdesc The return value + @vtype uExpressionValue * + @vio out + @vcomment + On exit contains the answer if there were no errors + @endvar + @var eval + @vdesc Variable evaluation function + @vtype int (*eval)(int, const char * const *, uExpressionValue *, void *), + @vio in + @vcomment + This function is called with an array of variables to determine the values of + and should return the corresponding values. + @endvar + @var data + @vdesc Arbitrary data to be passed to user supplied function. + @vtype void * + @vio in + @vcomment + This cna be anything the user needs to evaluate things. + @endvar + + @returntype int + @returndesc + +ve - success but there were this number of remaining operation on the stack. + 0 - success + -ve - the number of remaining items on the expression stack when an error was + encountered + @endreturndesc @@*/ -int CCTKi_ExpressionEvaluate(char *buffer, - int (*eval)(const char *, void *), - void *data) +int Util_ExpressionEvaluate(const uExpression buffer, + uExpressionValue *retval, + int (*eval)(int, const char * const *, uExpressionValue *, void *), + void *data) { - char *first; - char *token; - int stack[MAX_STACK_SIZE]; + int retcode; + uExpressionValue stack[MAX_STACK_SIZE]; int stackpointer; + int position; + uExpressionValue *varvals; - first = buffer; + retcode = 0; stackpointer = 0; - /* Tokens are seperated by @ signs */ - while((token = strtok(first,"@"))) + /* Assign memory for array to contain all variable values */ + varvals = (uExpressionValue *)malloc(buffer->nvars*sizeof(uExpressionValue)); + + if(varvals) { - first = NULL; + /* Evaluate the variables in one go to help people doing parallel ops. */ + eval(buffer->nvars, buffer->vars, varvals, data); + } - if(!isoperator(token)) + /* Tokens are seperated by @ signs */ + for(position = 0; position < buffer->ntokens; position++) + { + if(buffer->tokens[position].type == val) { - /* Evaluate and put on stack */ - stack[stackpointer] = eval(token, data); + /* Put value on stack */ + stack[stackpointer] = varvals[buffer->tokens[position].token.varnum]; + stackpointer++; } else { -#ifdef TEST_CCTKI_EVALUATE - printf("Stackpointer is %d, %f %s %f = ", - stackpointer, stack[stackpointer-2], token, stack[stackpointer-1]); +#ifdef TEST_EXPRESSION_PARSER + + printf("Stackpointer is %d, ", stackpointer); + if(buffer->tokens[position].type == binary) + { + switch(stack[stackpointer-2].type) + { + case ival: + printf("%d " ,stack[stackpointer-2].value.ival); break; + case rval: + printf("%f " ,stack[stackpointer-2].value.rval); break; + default: + ; + } + } + + printf("%s ", opname(buffer->tokens[position].token.opcode)); + switch(stack[stackpointer-1].type) + { + case ival: + printf("%d " ,stack[stackpointer-1].value.ival); break; + case rval: + printf("%f " ,stack[stackpointer-1].value.rval); break; + default: + ; + } + printf(" = "); + fflush(stdout); #endif /* Evaluate operation, clear operands from stack and add the result to the stack. */ - stack[stackpointer-2] = Evaluate(stack[stackpointer-2],token,stack[stackpointer-1]); - stackpointer--; -#ifdef TEST_CCTKI_EVALUATE - printf("%f\n", stack[stackpointer-1]); + switch(buffer->tokens[position].type) + { + case binary: + if(stackpointer > 1) + { + EvaluateBinary(&(stack[stackpointer-2]), + &(stack[stackpointer-2]), + buffer->tokens[position].token.opcode, + &(stack[stackpointer-1])); + stackpointer--; + } + else + { + retcode = -1; + } + break; + case unary: + if(stackpointer > 0) + { + EvaluateUnary(&(stack[stackpointer-1]), + buffer->tokens[position].token.opcode, + &(stack[stackpointer-1])); + } + else + { + retcode = -1; + } + break; + default : + ; + } + +#ifdef TEST_EXPRESSION_PARSER + if(!retcode) + { + switch(stack[stackpointer-1].type) + { + case ival: + printf("%d\n" ,stack[stackpointer-1].value.ival); break; + case rval: + printf("%f\n" ,stack[stackpointer-1].value.rval); break; + default: + ; + } + } #endif } + if(stackpointer < 0 || stackpointer > MAX_STACK_SIZE || retcode ) + { + retcode = -1; + break; + } } - return stack[stackpointer-1]; + if(varvals) + { + free(varvals); + } + + if(retcode) + { + retcode = -1-stackpointer; + } + else + { + *retval=stack[stackpointer-1]; + retcode = stackpointer-1; + } + + return retcode; +} + + /*@@ + @routine Util_ExpressionFree + @date Sat Nov 3 11:56:04 2001 + @author Tom Goodale + @desc + Frees an expression buffer + @enddesc + @calls + @calledby + @history + + @endhistory + @var buffer + @vdesc Expression buffer to be freed. + @vtype uExpression + @vio inout + @vcomment + + @endvar + +@@*/ +void Util_ExpressionFree(uExpression buffer) +{ + int i; + + if(buffer) + { + free(buffer->tokens); + + for(i = 0; i < buffer->nvars; i++) + { + free((char *)(buffer->vars[i])); + } + free(buffer->vars); + } + free(buffer); } @@ -197,6 +438,18 @@ int CCTKi_ExpressionEvaluate(char *buffer, @history @endhistory + @var expression + @vdesc Expression to be tokenised. + @vtype const char * + @vio in + @vcomment + + @endvar + + @returntype pToken * + @returndesc + Linked list of tokens. + @endreturndesc @@*/ static pToken *Tokenise(const char *expression) @@ -231,6 +484,7 @@ static pToken *Tokenise(const char *expression) case '-' : case '/' : case '*' : + case '^' : case '(' : case ')' : case '<' : @@ -261,6 +515,7 @@ static pToken *Tokenise(const char *expression) case '-' : case '/' : case '*' : + case '^' : case '(' : case ')' : case '=' : @@ -319,65 +574,85 @@ static pToken *Tokenise(const char *expression) return start; } + /*@@ @routine RPParse @date Tue Sep 19 21:28:36 2000 @author Tom Goodale @desc - Parses an toke list into Reverse Polish Notation (RPN). + Parses a token list into Reverse Polish Notation (RPN). @enddesc @calls @calledby @history @endhistory - + @var current + @vdesc Current token + @vtype pToken ** + @vio inout + @vcomment + This is the current token on input, and the new current token on output. + @endvar + @var buffer + @vdesc Expression buffer + @vtype uExpressionInternals * + @vio inout + @vcomment + This is the buffer in which to store the parse results. + @endvar + + @returntype int + @returndesc + 0 - success + @endreturndesc @@*/ -#define PUSH(stack, stacklength, value) do \ -{ \ - int len = strlen(stack)+strlen(value)+3; \ - \ - if(len > stacklength) \ - { \ - stack = (char *)realloc(stack, len); \ - } \ - sprintf(stack,"%s@%s",stack,value); \ + +#define RESIZE_STACK(stack) \ + (stack)->ntokens++; \ + (stack)->tokens = (uExpressionToken *)realloc((stack)->tokens, \ + (stack)->ntokens*sizeof(uExpressionToken));\ + +#define PUSHOP(stack, xtype, value) do \ +{ \ + RESIZE_STACK(stack) \ + (stack)->tokens[(stack)->ntokens-1].type = xtype; \ + (stack)->tokens[(stack)->ntokens-1].token.opcode = value; \ } while(0) +#define PUSHTOK(stack, xtype, value) do \ +{ \ + RESIZE_STACK(stack) \ + (stack)->tokens[(stack)->ntokens-1].type = xtype; \ + (stack)->tokens[(stack)->ntokens-1].token.varnum = value; break; \ +} while(0) -static char *RPParse(pToken **current, char *stack, int *stacklength) +int RPParse(pToken **current, uExpressionInternals *buffer) { - char *retval; + int retcode; pToken *this; char *operator; char *opstack[MAX_OPS]; int numops; int precedence; + int varnum; + uExpressionType optype; + uExpressionOpcode opcode; numops = 0; this = *current; - retval = stack; + retcode = 0; operator = NULL; - if(*stacklength > 0) - { - stack[0] = 0; - } - else - { - stack = (char *)malloc(sizeof(char)); - *stacklength = 1; - } - for(this = *current; this && strcmp(this->token,")"); this = this->next) { if(!strcmp(this->token, "(") && this->next) { /* This is a sub-group, so parse recursively */ this = this->next; - retval = RPParse(&this, retval, stacklength); + retcode = RPParse(&this, buffer); if(! this) { break; @@ -385,7 +660,8 @@ static char *RPParse(pToken **current, char *stack, int *stacklength) } else if(!isoperator(this->token)) { - PUSH(retval, *stacklength, this->token); + varnum = StoreVar(buffer, this->token); + PUSHTOK(buffer, val, varnum); } else { @@ -405,14 +681,16 @@ static char *RPParse(pToken **current, char *stack, int *stacklength) else { /* Lower or equal precedence */ - PUSH(retval, *stacklength, operator); + opencode(operator, &optype, &opcode); + PUSHOP(buffer, optype, opcode); operator = this->token; while(numops > 0) { if(cmpprecendence(opstack[numops-1], operator) <=0) { numops--; - PUSH(retval, *stacklength, opstack[numops]); + opencode(opstack[numops], &optype, &opcode); + PUSHOP(buffer, optype, opcode); } else { @@ -430,119 +708,267 @@ static char *RPParse(pToken **current, char *stack, int *stacklength) if(operator) { - PUSH(retval, *stacklength, operator); + opencode(operator, &optype, &opcode); + PUSHOP(buffer, optype, opcode); while(numops > 0) { numops--; - PUSH(retval, *stacklength, opstack[numops]); + opencode(opstack[numops], &optype, &opcode); + PUSHOP(buffer, optype, opcode); } } *current=this; - return retval; + return retcode; } /*@@ - @routine Evaluate + @routine EvaluateBinary @date Tue Sep 19 21:35:34 2000 @author Tom Goodale @desc - Evaluates val1 op val2 + Evaluates the binary operation val1 op val2 @enddesc @calls @calledby @history @endhistory + @var retval + @vdesc The result + @vtype uExpressionValue * + @vio out + @vcomment + + @endvar + @var val1 + @vdesc The first operand + @vtype const uExpressionValue * + @vio in + @vcomment + + @endvar + @var opcode + @vdesc The opcode of the operator. + @vtype uExpressionOpcode + @vio in + @vcomment + + @endvar + @var val2 + @vdesc The second operand + @vtype const uExpressionValue * + @vio in + @vcomment + + @endvar + @returntype int + @returndesc + 0 - success + @endreturndesc @@*/ -static int Evaluate(int val1, const char *operator, int val2) +static int EvaluateBinary(uExpressionValue *retval, + const uExpressionValue *val1, + uExpressionOpcode opcode, + const uExpressionValue *val2) { - int retval; - - if(!strcmp(operator, "+")) - { - retval = (val1+val2); - } - else if(!strcmp(operator, "-")) - { - retval = (val1-val2); - } - else if(!strcmp(operator, "/")) - { - retval = (val1/val2); - } - else if(!strcmp(operator, "*")) - { - retval = (val1*val2); - } - else if(!strcmp(operator, "&&")) - { - retval = (val1 && val2); - } - else if(!strcmp(operator, "||")) - { - retval = (val1 || val2); - } - else if(!strcmp(operator, "=")) - { - retval = ( val1 == val2); - } - else if(!strcmp(operator, "<")) - { - retval = (val1 < val2); + + /* Define a macro so only have to do this once + * irrespective of operand types. + */ + #define EVALUATEBINARY(retval,val1,val2) \ + switch(opcode) \ + { \ + case OP_PLUS : \ + (retval) = ((val1)+(val2)); \ + break; \ + case OP_MINUS : \ + (retval) = ((val1)-(val2)); \ + break; \ + case OP_DIV : \ + (retval) = ((val1)/(val2)); \ + break; \ + case OP_TIMES : \ + (retval) = ((val1)*(val2)); \ + break; \ + case OP_POWER : \ + (retval) = pow(val1,val2); \ + break; \ + case OP_AND : \ + (retval) = ((val1) && (val2)); \ + break; \ + case OP_OR : \ + (retval) = ((val1) || (val2)); \ + break; \ + case OP_EQUALS : \ + (retval) = ( (val1) == (val2)); \ + break; \ + case OP_LESS_THAN : \ + (retval) = ((val1) < (val2)); \ + break; \ + case OP_LEQUALS : \ + (retval) = ((val1) <= (val2)); \ + break; \ + case OP_GREATER_THAN : \ + (retval) = ((val1) > (val2)); \ + break; \ + case OP_GEQUALS : \ + (retval) = ((val1) >= (val2)); \ + break; \ + default : \ + fprintf(stderr, "Unknown operation %d", opcode); \ + (retval) = 0; \ } - else if(!strcmp(operator, "<=")) + + /* Need to decide where to get operands from and where to put them. */ + if(val1->type==ival && val2->type==ival) { - retval = (val1 <= val2); + retval->type=ival; + EVALUATEBINARY(retval->value.ival,val1->value.ival,val2->value.ival); } - else if(!strcmp(operator, ">")) + else if(val1->type==rval && val2->type==ival) { - retval = (val1 > val2); + retval->type=rval; + EVALUATEBINARY(retval->value.rval,val1->value.rval,val2->value.ival); } - else if(!strcmp(operator, ">=")) + else if(val1->type==ival && val2->type==rval) { - retval = (val1 >= val2); + retval->type=rval; + EVALUATEBINARY(retval->value.rval,val1->value.ival,val2->value.rval); } - else + else /* if(val1->type==rval && val2->type==rval) */ { - fprintf(stderr, "Unknown operation %s", operator); - retval = 0; + retval->type=rval; + EVALUATEBINARY(retval->value.rval,val1->value.rval,val2->value.rval); } - return retval; + return 0; } - + /*@@ - @routine FreeTokens - @date Tue Sep 19 21:39:07 2000 + @routine EvaluateUnary + @date Sun Nov 4 22:18:50 2001 @author Tom Goodale @desc - Frees a list of tokens. + Evaluates a unary operation on value @enddesc @calls @calledby @history @endhistory - + @var retval + @vdesc The result + @vtype uExpressionValue * + @vio out + @vcomment + + @endvar + + @endvar + @var opcode + @vdesc The opcode of the operator. + @vtype uExpressionOpcode + @vio in + @vcomment + + @endvar + @var value + @vdesc The operand + @vtype const uExpressionValue * + @vio in + @vcomment + + @returntype int + @returndesc + 0 - success + @endreturndesc @@*/ -void FreeTokens(pToken *list) +static int EvaluateUnary(uExpressionValue *retval, + uExpressionOpcode opcode, + const uExpressionValue *value) { - pToken *token; - pToken *next; + + #define UNARYMATHOPERATE(a) \ + case OP_##a : \ + (retval) = a(val); \ + break; - for(token = list; token; token = next) + #define EVALUATEUNARY(retval, val) \ + switch(opcode) \ + { \ + case OP_ACOS : \ + (retval) = acos(val); \ + break; \ + case OP_ASIN : \ + (retval) = asin(val); \ + break; \ + case OP_ATAN : \ + (retval) = atan(val); \ + break; \ + case OP_CEIL : \ + (retval) = ceil(val); \ + break; \ + case OP_COS : \ + (retval) = cos(val); \ + break; \ + case OP_COSH : \ + (retval) = cosh(val); \ + break; \ + case OP_EXP : \ + (retval) = exp(val); \ + break; \ + case OP_FABS : \ + (retval) = fabs(val); \ + break; \ + case OP_FLOOR : \ + (retval) = floor(val); \ + break; \ + case OP_LOG : \ + (retval) = log(val); \ + break; \ + case OP_LOG10 : \ + (retval) = log10(val); \ + break; \ + case OP_SIN : \ + (retval) = sin(val); \ + break; \ + case OP_SINH : \ + (retval) = sinh(val); \ + break; \ + case OP_SQRT : \ + (retval) = sqrt(val); \ + break; \ + case OP_TAN : \ + (retval) = tan(val); \ + break; \ + case OP_TANH : \ + (retval) = tanh(val); \ + break; \ + default : \ + fprintf(stderr, "Unknown operation %d", opcode); \ + (retval) = 0; \ + } + + if(value->type==ival) { - next = token->next; - free(token->token); - free(token); + retval->type=rval; + EVALUATEUNARY(retval->value.rval,value->value.ival); } + else /* if(val->type==rval) */ + { + retval->type=rval; + EVALUATEUNARY(retval->value.rval,value->value.rval); + } + + return 0; } + /*@@ @routine isoperator @date Tue Sep 19 21:30:20 2000 @@ -555,29 +981,35 @@ void FreeTokens(pToken *list) @history @endhistory + @var token + @vdesc Token to test. + @vtype const char * + @vio in + @vcomment + + @endvar + @returntype int + @returndesc + 1 - is an operator + 0 - is not an operator + @endreturndesc @@*/ static int isoperator(const char *token) { int retval; - if(!strcmp(token, "+") || - !strcmp(token, "-") || - !strcmp(token, "/") || - !strcmp(token, "*") || - !strcmp(token, "&&") || - !strcmp(token, "||") || - !strcmp(token, "=") || - !strcmp(token, "<") || - !strcmp(token, "<=") || - !strcmp(token, ">") || - !strcmp(token, ">=")) - { - retval = 1; - } - else + int i; + + retval = 0; + + for(i=0; operators[i].operator; i++) { - retval = 0; + if(!strcmp(operators[i].operator,token)) + { + retval = 1; + break; + } } return retval; @@ -595,54 +1027,183 @@ static int isoperator(const char *token) @history @endhistory - + @var op1 + @vdesc First operator + @vtype const char * + @vio in + @vcomment + + @endvar + @var op2 + @vdesc Second operator + @vtype const char * + @vio in + @vcomment + + @endvar + + @returntype int + @returndesc + +ve - op1 is higher precedence than op2 + 0 - op1 and op2 are of equal precedence + -ve - op2 is higher precedence than op1 + @endreturndesc @@*/ static int cmpprecendence(const char *op1, const char *op2) { int retval; - const char *op; + int i; int op1prec; int op2prec; - int *prec; - /* Work out the precedence level for each operator */ - for(op = op1, prec = &op1prec; - op ; - op = (op == op1 ) ? op2 : NULL, - prec = (op == op1) ? &op1prec : &op2prec) + op1prec = -1; + op2prec = -1; + + for(i=0; operators[i].operator; i++) { - if(!strcmp(op, "=") || - !strcmp(op, "<") || - !strcmp(op, "<=") || - !strcmp(op, ">") || - !strcmp(op, ">=")) + if(!strcmp(operators[i].operator,op1)) { - *prec = 1; + op1prec = operators[i].precedence; } - else if(!strcmp(op, "&&") || - !strcmp(op, "||")) + if(!strcmp(operators[i].operator,op2)) { - *prec = 2; + op2prec = operators[i].precedence; } - else if(!strcmp(op, "+") || - !strcmp(op, "-")) + + if(op1prec != -1 && op2prec != -1) { - *prec = 3; + break; } - else if(!strcmp(op, "/") || - !strcmp(op, "*")) + } + + /* Now see which has the higher precedence */ + retval = op2prec-op1prec; + + return retval; +} + + /*@@ + @routine opencode + @date Sun Nov 4 22:05:36 2001 + @author Tom Goodale + @desc + Finds the encoding for a given operator. + @enddesc + @calls + @calledby + @history + + @endhistory + @var operator + @vdesc The operator to get info on. + @vtype const char * + @vio in + @vcomment + + @endvar + @var type + @vdesc Operator type + @vtype uExpressionType * + @vio out + @vcomment + + @endvar + @var opcode + @vdesc The operator's opcode + @vtype uExpressionOpcode + @vio out + @vcomment + + @endvar + + @returntype int + @returndesc + 0 - success + -1 - operator doesn't exist + @endreturndesc +@@*/ +static int opencode(const char *operator, uExpressionType *type, uExpressionOpcode *opcode) +{ + int retcode; + int i; + + retcode = -1; + for(i=0; operators[i].operator; i++) + { + if(!strcmp(operators[i].operator,operator)) { - *prec = 4; + retcode = 0; + *type = operators[i].type; + *opcode = operators[i].opcode; + break; } - else + } + return retcode; +} + + + /*@@ + @routine StoreVar + @date Sun Nov 4 22:09:34 2001 + @author Tom Goodale + @desc + Stores a variable name in an expression buffer. + If the variable already exists, it returns the + old number, otherwise it saves the variable and + returns its new number. + @enddesc + @calls + @calledby + @history + + @endhistory + @var buffer + @vdesc Buffer in which to store the name + @vtype uExpressionInternals * + @vio inout + @vcomment + + @endvar + @var var + @vdesc The variable to be stored. + @vtype const char * + @vio in + @vcomment + + @endvar + + @returntype int + @returndesc + The assigned variable number + @endreturndesc +@@*/ +static int StoreVar(uExpressionInternals *buffer, const char *var) +{ + int retval; + int i; + + retval = -1; + + /* Look for old value. */ + for(i = 0; i < buffer->nvars; i++) + { + if(!strcmp(buffer->vars[i],var)) { - fprintf(stderr, "Unknown operator '%s'\n", op); - *prec = 0; + retval = i; + break; } } - /* Now see which has the higher precedence */ - retval = op2prec-op1prec; + /* If the variable is new, resize list and add it. */ + if(retval == -1) + { + buffer->nvars++; + buffer->vars = (const char **)realloc(buffer->vars,sizeof(const char *)*buffer->nvars); + + buffer->vars[buffer->nvars-1] = strdup(var); + + retval = buffer->nvars-1; + } return retval; } @@ -652,14 +1213,33 @@ static int cmpprecendence(const char *op1, const char *op2) @date Tue Sep 19 21:30:42 2000 @author Tom Goodale @desc - Creates a new token item. + Creates a new token item given the beginning and end of + the string containing the token. @enddesc @calls @calledby @history @endhistory + @var tokenstart + @vdesc pointer to first charater in token + @vtype const char * + @vio in + @vcomment + + @endvar + @var tokenend + @vdesc pointer to last charater in token + @vtype const char * + @vio in + @vcomment + + @endvar + @returntype pToken * + @returndesc + The new token object + @endreturndesc @@*/ static pToken *newtoken(const char *tokenstart, const char *tokenend) { @@ -699,11 +1279,11 @@ static pToken *newtoken(const char *tokenstart, const char *tokenend) } /*@@ - @routine insertbefore - @date Tue Sep 19 21:33:39 2000 + @routine FreeTokens + @date Tue Sep 19 21:39:07 2000 @author Tom Goodale @desc - Inserts a token before another one in a list. + Frees a list of tokens. @enddesc @calls @calledby @@ -712,23 +1292,19 @@ static pToken *newtoken(const char *tokenstart, const char *tokenend) @endhistory @@*/ -#if 0 -static void insertbefore(pToken *base, pToken *this) +void FreeTokens(pToken *list) { - if(base && this) - { - this->next = base; - this->last = base->last; - base->last = this; + pToken *token; + pToken *next; - if(this->last) - { - this->last->next = this; - } + for(token = list; token; token = next) + { + next = token->next; + free(token->token); + free(token); } -} -#endif - +} + /*@@ @routine insertafter @date Tue Sep 19 21:34:02 2000 @@ -741,6 +1317,20 @@ static void insertbefore(pToken *base, pToken *this) @history @endhistory + @var base + @vdesc The base of the list + @vtype pToken * + @vio inout + @vcomment + + @endvar + @var this + @vdesc Token to add to list. + @vtype pToken * + @vio inout + @vcomment + + @endvar @@*/ static void insertafter(pToken *base, pToken *this) @@ -758,102 +1348,142 @@ static void insertafter(pToken *base, pToken *this) } } +#if TEST_EXPRESSION_PARSER + /*@@ - @routine printtokens - @date Tue Sep 19 21:34:24 2000 + @routine opname + @date Sun Nov 4 22:08:10 2001 @author Tom Goodale @desc - Debugging function to print out the tokens. + Finds the name of an operator. @enddesc @calls @calledby @history @endhistory + @var opcode + @vdesc The operator's opcode + @vtype uExpressionOpcode + @vio in + @vcomment + + @endvar + @returntype const char * + @returndesc + The operator's name or NULL if it doesn't exist. + @endreturndesc @@*/ -#if TEST_CCTKI_EVALUATE -static void printtokens(pToken *start) +static const char *opname(uExpressionOpcode opcode) { - pToken *token; + const char *retval; + int i; - for(token = start; token; token = token->next) + retval = NULL; + + for(i=0; operators[i].operator; i++) { - printf("->%s", token->token); + if(operators[i].opcode == opcode) + { + retval = operators[i].operator; + break; + } } - - printf("\n"); + return retval; } -#endif /* TEST_CCTKI_EVALUATE */ - /*@@ - @routine printstack - @date Tue Sep 19 21:34:48 2000 + @routine printtokens + @date Tue Sep 19 21:34:24 2000 @author Tom Goodale @desc - Debugging function to print out a predigested string. - Note that is modifies the string, so it should be passed - a copy. + Debugging function to print out the tokens. @enddesc @calls @calledby @history @endhistory + @var start + @vdesc First token in list + @vtype pToken * + @vio in + @vcomment + + @endvar @@*/ -#if 0 -static void printstack(char *stack) +static void printtokens(pToken *start) { - char *first; - char *token; - - first = stack; + pToken *token; - while((token = strtok(first,"@"))) + for(token = start; token; token = token->next) { - first = NULL; - printf("Token is %s\n", token); + printf("->%s", token->token); } + + printf("\n"); } -#endif +#endif /* TEST_EXPRESSION_PARSER */ /******************************************************************** ********************* TEST FUNCTIONS ************************* ********************************************************************/ -#ifdef TEST_CCTKI_EVALUATE +#ifdef TEST_EXPRESSION_PARSER -int evaluator(const char *token, void *data) +int evaluator(int nvars, const char * const *vars, uExpressionValue *vals, void *data) { - int retval; - - retval = strtod(token, NULL); + int i; - /* fprintf(stderr, "Evaluated '%s' to %f\n", token,retval); */ + for(i = 0; i < nvars; i++) + { + if(strchr(vars[i],'.')) + { + vals[i].type = rval; + vals[i].value.rval = strtod(vars[i], NULL); + } + else + { + vals[i].type = ival; + vals[i].value.ival = strtol(vars[i], NULL,0); + } + } - return retval; + return 0; } int main(int argc, char *argv[]) { - char *buffer; + uExpression buffer; + uExpressionValue value; + value.type = ival; + if(argc < 2) { printf("Usage: %s \"string\"\n", argv[0]); exit(0); } - buffer = CCTKi_ExpressionParse(argv[1]); + buffer = Util_ExpressionParse(argv[1]); - printf("Value is %f\n", CCTKi_ExpressionEvaluate(buffer, evaluator,NULL)); - - free(buffer); + Util_ExpressionEvaluate(buffer, &value,evaluator,NULL); + + if(value.type==ival) + { + printf("Value is %d\n", value.value.ival); + } + else + { + printf("Value is %f\n", value.value.rval); + } + + Util_ExpressionFree(buffer); return 0; } -#endif /* TEST_CCTKI_EVALUATE */ +#endif /* TEST_EXPRESSION_PARSER */ -- cgit v1.2.3