General Expression Parser and Evaluator

• Download GenExpParser - 25.43 KB Source code and sample application

Introduction

Most of the expression parsers I have seen are designed to parse and evaluate mathematical expressions.
While I to want to parse math expressions I also wanted the ability handle different types of expressions.
I wanted a parser that would return a list of the base elements in a expression and let me apply my
own evaluator to that list.

Using the code

In order to parse an expression a user supplied tokenizer is required. The tokenizer provides two functions:

1. It parses the expression into its base elements. These elements are of one of the following types
   • Literal - A string encoded in double or single quote marks
   • Identifier - A variable name to resolved by the evaluator
   • Constant - An numeric or hex constant
   • Function - The name of a function to be invoked by the evaluator
   • Argument - The function argument delimiter, ie a comma
   • GroupStart - IE a left perenethesis
   • GroupEnd - IE a closing right perenethesis
   • Operator - An expression operator
   • CondTrue - Marks the start of elements to be evaluated when a condition is true.
     The CondTrue and CondFalse operators come form conditional expressions IE (a>b ? a : b)
   • CondFalse - Marks the start of elements to be evaluated when a condition is false
   • Assignment - An assignment operator

   The tokenizer is free to determine which type an element belongs to. The tokenizer also
   assigns the precedence to the operators. It also assigns the association of the operator. A operator is either Left or Right associative. Most operators are Left associative but the exponent, "**", and conditional, "?", operators are right associative.

2. It provides a function to create an operator from a token element. An operator falls into one of the following groups:
   • Arithmetic - A mathematical operator IE +, - or *
   • Comparison - A comparison operator IE ==, > or <
   • Logical - A logical operator IE && (AND) or || (OR)
   • Bitwise - A bitwise operator IE & (AND), | (OR) or ^ (XOR)
   • Conditional - True or False element of a conditional expression IE (a>b ? ... : ...)
   • Assignment - Assign result to a variable IE =, +=, or -+

Once the expression has been tokenized an RPN list elements is created using the "Shunting Yard" algorithm.

Below are some examples of expressions and the parsing results using the supplied "MathParser" as the tokenizer.

   x = a+b*c         -a+(b+c)*2       a>b ? a-b : a+b    a+min(x, y)
   0: Identifier x   0: Identifier a  0: Identifier a    0: Identifier a
   1: Identifier a   1: Operator -    1: Identifier b    1: Identifier x
   2: Identifier b   2: Identifier b  2: Operator >      2: Identifier y
   3: Identifier c   3: Identifier c  3: CondTrue ? 8    3: Function min 2
   4: Operator *     4: Operator +    4: Identifier a    4: Operator +
   5: Operator +     5: Constant 2    5: Identifier b   
   6: Assignment =   6: Operator *    6: Operator -  
                     7: Operator +    7: CondFalse : 11
                                      8: Identifier a
                                      9: Identifier b
                                     10: Operator +

What is shown above is the result of applying the "ToString" method to the elements returned by the parser. The "Identifier", "Constant" and "Operator" items are self explanatory. The "CondTrue" and CondFalse" elements act as a "If, Else" construct. The number on the "CondTrue" element is the index of the first element to be evaluated if the condition is false. The number of the "CondFalse" element is the index of the first element following the conditional expression. The "CondFalse" element in effect acts as a "GoTo" the element specified. The number on the "Function" element is the number of arguments to be passed to the named function.

The list of elements in an expression is generated by calling the parser. For example from the test application:

 . . . 
 ITokeniser parser = new MathParser();
 List<RpnElement> tokens = Parser.ParseExpression(parser,rpnExpression.Text);
 . . .

Evaluating the Expression

The act of evaluating an expression involves the following steps:

1. If the next element on the expression list is a "Literal" or "Constant" then push its value onto the operand stack.
2. If the next element is an "Identifier" then get the current value of the identifier and push it on to the stack.
3. If the next element is a function or an operator then pop the required function arguments or the Left and Right sides of the operator from the stack. Then evaluate the function or the operator. Push the result onto the operand stack.
4. Repeat until all elements in the expression list have been processed.
5. When all elements have been processed there should be one operand left on the operand stack, this is the result of the expression.

Below is the main loop of the sample evaluator included with the test application.

    private RpnParser.RpnOperand RpnEval(List<RpnElement> tokens) {
      Stack<RpnOperand> oprndStack = new Stack<RpnOperand>();
      RpnOperand oprnd = null;
      for (int nextElem = 0; nextElem < tokens.Count; ++nextElem) {
        RpnElement token = tokens[nextElem];
        switch (token.ElementType) {
          // create an operand from the token and push onto the operand stack
          case ElementType.Literal:
          case ElementType.Constant:
            oprnd = new RpnOperand((RpnToken)token);
            break;
          // Get the current value of the identifier and
          // push it onto the operand stack
          case ElementType.Identifier:
            oprnd = EvalIdentifier((RpnToken)token);
            break;
          // Pop the left and right sides of the operator from operand stack
          // Perform the operation and push the results onto the operand stack
          case ElementType.Operator:
            RpnOperator oper = (RpnOperator)token;
            RpnOperand lhs, rhs;
            lhs = rhs = null;
            if (oper.IsMonadic && oprndStack.Count >= 1) {
              lhs = new RpnOperand(0);
              rhs = oprndStack.Pop();
            } else
              if (oprndStack.Count >= 2) {
                rhs = oprndStack.Pop();
                lhs = oprndStack.Pop();
              }
            if (lhs == null)
              StackError("operator", token.StrValue);
            else
              oprnd = EvalOperator(oper, lhs, rhs);
            break;
          // Determine if True or False condition has be met
          // Set element index to the next element to be processed
          case ElementType.CondTrue:
          case ElementType.CondFalse:
            oper = (RpnOperator)token;
            if (oprndStack.Count < 1)
              StackError("operator", token.StrValue);
            if (oper.OpType == OperatorType.CondTrue) {
              lhs = oprndStack.Pop();
              if (lhs.NumValue == 0)
                nextElem = oper.CondGoto - 1;  // for loop will add one
            } else
              nextElem = oper.CondGoto - 1; // for loop will add one
            continue;
          // Pop the function arguments from the operand stack 
          // and place into an array
          // Evalualate the function and push the result onto operand stack
          case ElementType.Function:
            RpnFunction func = (RpnFunction)token;
            if (oprndStack.Count >= func.ArgCount) {
              RpnOperand[] args = new RpnOperand[func.ArgCount];
              for (int i = func.ArgCount - 1; i >= 0; --i)
                args[i] = oprndStack.Pop();
              if (evalCBox.Checked)
                oprnd = EvalFunction(func, args);
            } else
              StackError("function", token.StrValue);
            break;
          // Pop Identifier and value to be assigned fron the stack
          // Push the resulting operand onto the operand stack
          case RpnParser.ElementType.Assignment:
            if (oprndStack.Count > 1) {
              rhs = oprndStack.Pop();   // value to be assigned
              lhs = oprndStack.Pop();   // identifier to be assigned to
              oprnd = AssignOperator((RpnOperator)token, lhs, rhs);
            } else
              StackError("assignment", token.StrValue);
            break;

        }
        oprndStack.Push(oprnd);
      }
      if (oprndStack.Count != 1)
        StackError("result", "");
      return oprndStack.Pop();
    }

    private void StackError(string token, string value) {
      string text = String.Format("Insufficiant operands on stack for {0}: {1}",
         token, value);
      throw new ApplicationException(text);
    }
  

Summary

Hopefully this article demonstrates a generalized expression parser. Where the elements that make up an expression and the evaluation of that expression are controlled by the user. The only job of the parser is to present the elements in a standard, consistent manner.

References

C# Expression Parser using RPN
"Shunting Yard" algorithm

History

July 9, 2008 - Version 1 released.

July 11, 2008 - Removed signing requirement from project.

You must Sign In to use this message board.

FAQ  Noise Tolerance Very HighHighMediumLowVery Low  Search Messages    Layout Expand All MessagesThread ViewNo Javascript (slow)No Javascript Preview    Per page 102550

Msgs 1 to 7 of 7 (Total in Forum: 7) (Refresh) FirstPrevNext

trouble with point in float numbers pasha-e 22:22 22 Jul '08   Thanks a lot for your urgent responce and corrections! But I've found couple more bugs: 1. expression like 0.5*a gives the error "Unsupported operator found". Is it planned to support float constants? 2. a*b at a=1, b=1 works fine, but at а=1, b=1.0 (or 0.5) gives the error "Invalid string operation *". But expressiom like a+b works fine at all a and b Sign In·View Thread·PermaLink Re: trouble with point in float numbers WBurgMo 7:25 23 Jul '08   Case 1: expression like 0.5*a gives the error "Unsupported operator found" I am unable to reproduce this error Case 2: a*b at a=1, b=1 works fine, but at а=1, b=1.0 (or 0.5) gives the error "Invalid string operation *" I am unable to reproduce this error using given examples. I can reproduce it if I use a='1' and/or b='0.5'. But in that case, the program is working as designed. Sign In·View Thread·PermaLink Re: trouble with point in float numbers pasha-e 21:52 23 Jul '08   ok.. I think this library contain the block of regional depending code. When I changed decimal delimeter "," to "." in system regional setting, the program began to work correctly Sign In·View Thread·PermaLink trouble with sign pasha-e 1:22 22 Jul '08   expression like 3*(-5) causes an error "Insufficiant operands on stack for operator: *" while 3*a, at a=-5, works fine also a<-5 at a=-5 causes an error "Insufficiant operands on stack for operator: <" thanks for the library! Sign In·View Thread·PermaLink Re: trouble with sign WBurgMo 11:40 22 Jul '08   The source has been updated to correct this error. If an operator ends with a plus or minus sign, the sign will be treated as a separate operator. IE <- is treated as a < operator and a - operator. a + or - sign in front of any operator other that an equal sign is an error. An error will be raised if an unsupported operator is found Sign In·View Thread·PermaLink Sign for library Alexey Prosyankin 22:26 10 Jul '08   If it would be possible disable signing for your library, because your key absent in project. Sign In·View Thread·PermaLink Re: Sign for library WBurgMo 11:37 11 Jul '08   The download has been updated to remove the signing requirement. Sign In·View Thread·PermaLink 5.00/5 (1 vote)

Last Visit: Monday, December 1, 2008 8:47 PM     Last Update:Monday, December 1, 2008 8:47 PM