An expression evaluator written in VB.NET


There is a new version (still very simple), at the address below: 
http://www.codeproject.com/Articles/13779/The-expression-evaluator-revisited-Eval-function-i

Introduction

My company needed a small expression evaluator to use in our .NET application. Using the .NET framework compilation capabilities seem to be the most obvious way to make an evaluator. However, in practice this technique has a nasty side effect, it looks like it creates a new DLL in memory each time you evaluate your function and it seems nearly impossible to unload the DLL. You can refer to remarks at the end of the article Evaluating Mathematical Expressions by Compiling C# Code at Runtime for more details.

This evaluator is neither using CodeDOM nor trying to compile VB source. On the contrary, it parses your expression and evaluates its value.

Compared to other projects that I have seen, this evaluator can do the following:

access and process string expressions.
You can evaluate "Hello" + " " + "world"
access and process objects.
You can evaluate ThisForm.Left.
it also offers easy extensibility.

You can add any number of custom functions without having to change the evaluator code.

Using the code

The evaluator can be run with just two lines of code:

Dim mEvaluator As New Evaluator 
Dim res As integer = CInt(mEvaluator.Eval("1+1"))

How to provide variables for the evaluator

The evaluator raises an event GetVariable when a keyword is not detected. There is no need for you to publish all the variables and then run the eval. On the contrary, you can provide an on demand function which provides only the needed variables:

 Private Sub Evaluator1_GetVariable(ByVal name As String, _
            ByRef value As Object) Handles Evaluator1.GetVariable
    Select Case name
      Case "anumber"
        value = 5.0
      Case "theForm"
        value = Me
      Case "adate"
        value = #1/1/2005#
    End Select
End Sub

How to extend the evaluator with custom functions

The member functions found in the class EvalFunctions are automatically used by the evaluator. In this example, you can see how we can make the evaluator implement the sin and now functions:

Public Class EvalFunctions 
   Function sin(ByVal v As Double) As Double
     Return Math.Sin(v)
   End Function

   Function now() As DateTime
     Return Microsoft.VisualBasic.Now
   End Function

As you can see you don't need much wrapping, the function can be written and used straightaway in this class. Note however that the evaluator does not make any distinction between the Integers and Doubles. Therefore, remember to use Doubles and not Integers for your function parameters.

How does this work?

The evaluator is made of a classic Tokenizer followed by a classic Parser. I wrote both of them in VB, without using any Lex or Bisons tools. The aim was readability over speed. Tokenizing, parsing and execution is done in one pass. This is elegant and at the same time quite efficient because the evaluator never looks ahead or back, more than one character.

The tokenizer

It reads the characters one by one and changes its state according to the characters it encounters. When it recognizes one of the recognized Token types, it returns it to the parser. If it does not recognize a character, it will raise a syntax error exception.

' Recognized token types :
Private Enum eTokenType
 none                   ' temporary state
 end_of_formula         ' when the tokenizer reach the end
 operator_plus          ' +
 operator_minus         ' -
 operator_mul           ' *
 operator_div           ' /
 operator_percent       ' %
 open_parenthesis       ' (
 comma                  ' ,
 dot                    ' .
 close_parenthesis      ' )
 operator_ne            ' <>
 operator_gt            ' <=
 operator_ge            ' >=
 operator_eq            ' =
 operator_le            ' <=
 operator_lt            ' <
 operator_and           ' AND
 operator_or            ' OR
 operator_not           ' NOT
 operator_concat        ' & 
 value_identifier       ' any word starting with a letter or _ 
 value_true             ' TRUE 
 value_false            ' FALSE 
 value_number           ' any number starting 0-9 or . 
 value_string           ' any string starting ' or " 
 open_bracket           ' [ 
 close_bracket          ' ] 
End Enum

The Tokenizer is fairly simple, it accepts a loose VB/Excel syntax. The evaluator is split into two classes, one does the tokenization and the second processes the tokens. This is the standard way of doing it. This is quite flexible also. This way, if you wish you could amend it to accept a C++ syntax by changing the way the parser detects the operators eq, ne, and, or, not... Changing the Tokenizer will not force you to reprogram the rest of the evaluator.

The Parser

The Parser is a bit more complicated than a Tokenizer. It is like the Tokenizer with a sort of flow machine, a bit like a pipe. It will process the token one by one without looking ahead or back.

In this article, I speak about operators, left parts and right parts. In the expression 1 + 2, I call + the operator, 1 is the left part and 2 is the right part.

One of the complicated concepts of the Parser is priorities. For example, the expression:

1 + 2 * 3

is not treated the same way as the expression:

1 * 2 + 3

The evaluator operates using a standard set of priorities. The multiplication has more priority than addition. Therefore:

1 + 2 * 3 = 1 + 6 = 7

1 * 2 + 3 = 2 + 3 = 5

In the above cases, we need to do the multiplication first.

So how can this be done in one pass?

At any time, the parser knows what is its level of priority.

Private Enum ePriority
  none = 0
  [concat] = 1
  [or] = 2
  [and] = 3
  [not] = 4
  equality = 5
  plusminus = 6
  muldiv = 7
  percent = 8
  unaryminus = 9
End Enum

When the parser encounters an operator, it will recursively call the parser to get the right part. When the parser returns the right part, the operator can apply its operation (for example +) and the parsing continues.

The interesting part is that while calculating the right part, the Tokenizer already knows its current level of priority. Therefore, while parsing the right part, if it detects an operator with more priority, it will continue its parsing and return only the resulting value.

You said it supports object?

Yes, the evaluator supports the . operator. If you enter the expression theForm.text then the evaluator will return the title of the form. If you enter the expression theForm.left, it will return its runtime left position. This feature is only experimental and has not been tested yet. That is why I have put this code here, hoping others will find its features valuable and submit their improvements.

How does this work?

In fact the object came free. I used System.Reflection to evaluate the custom functions. And the same code is used to access the object's methods and properties. When the parser encounters an identifier that is a keyword without any meaning for it, it will try to reflect the CurrentObject to see if it can find a method or a property with the same name.

 mi = CurrentObject.GetType().GetMethod(func, _
  _Reflection.BindingFlags.IgnoreCase _ 
  Or Reflection.BindingFlags.Public _ Or Reflection.BindingFlags.Instance)

If a method or a property is found, it will feed its parameters.

valueleft = mi.Invoke(CurrentObject, _
  _ System.Reflection.BindingFlags.Default, Nothing, 
  _ DirectCast(parameters.ToArray(GetType(Object)), Object()), Nothing)

Points of Interest

This is the only formula evaluator available on CodeProject with a separate Tokenizer and Parser (I believe). The extensibility can be pushed to the maximum due to the use of System.Reflection.