A Tiny Expression Evaluator

• Download source - 78.28 KB

Introduction

@TinyExe stands for "a Tiny Expression Evaluator". It is a small commandline utility that allows you to enter simple and more complex mathematical formulas which will be evaluated and calculated on the spot. Even though there are already a number of expression evaluators around on CodeProject and beyond, this particular project is meant mainly to demonstrate the possibilities of @TinyPG. @TinyPG is a parser generator used to create various types of languages and is described in another article here on CodeProject.

This expression evaluator therefore is based on a typical parser/lexer based compiler theory. The implementation of the sementics is done in pure C# codebehind. Since @TinyPG also generates pure and clearly readable C#, consequently this expression evaluator is a set of fully contained C# source code, without requiring any external dependencies. It can therefore be easily used within your own projects. This project also contains the grammar file used to generate the scanner and the parser, so feel free to modify the grammar for your own needs.

In this article, I will expain mainly:

• Some of the features currently supported by this expression evaluator
• How to use this evaluator engine within your own projects
• How to extend the functionality of this evaluator as to adapt it to your own purposes

Background

Due to a lack of good example grammars and demos on how to use @TinyPG, I decided to build a demonstration project which shows how @TinyPG can be used for more advanced grammars such as expression evaluators. So why create an Expression Evaluator for the purpose of a demo? Because well, runtime Expression Evaluators are cool! Take Excel for example, it's the most widely used runtime Expression Evaluator used today. Wouldn't it be awesome to unleash some of that power of Excel inside your own applications?

So, since a runtime expression evaluator may just come in handy, I thought this would make a nice demo project. Note that this is not just a demo though. This expression evaluator is fully functional and ready to execute!

Even though @TinyPG comes with a small tutorial on how to write a simple expression evaluator, I decided to show that @TinyPG can be used to produce powerful LL(1)-grammars. This project also nicely demonstrates how the grammar and syntax can be cleanly separated from the semantics. The calculation rules are implemented separately from the parser and scanner.

Using the Tool

The functionality of the tool is based on the implementation as used in Excel. Currently the expression evaluator supports the following features:

• It can parse mathematical expressions, including support for the most commonly used functions,e.g.:
  • 4*(24/2-5)+14
  • cos(Pi/4)*sin(Pi/6)^2
  • 1-1/E^(0.5^2)
  • min(5;2;9;10;42;35)
• The following functions are supported:
  • About Abs Acos And Asin Atan Atan2 Avg Ceiling Clear Cos Cosh Exp Fact Floor Format Help Hex If Floor Left Len Ln Log Lower Max Min Mid Min Not Or Pow Right Round Sign Sin Sinh Sqr Sqrt StDev Trunc Upper Val Var
• Basic string functions:
  • "Hello " & "world"
  • "Pi = " & Pi
  • Len("hello world")
• Boolean operators:
  • true != false
  • 5 > 6 ? "hello" : "world"
  • If(5 > 6;"hello";"world")
• Function and variable declaration
  • x := 42
  • f(x) := x^2
  • f(x) := sin(x) / cos(x)    // declare new dynamic functions using built-in functions
  • Pi
  • E
• Recursion and scope
  • fac(n) := (n = 0) ? 1 : fac(n-1)*n     // fac calls itself with different parameters
  • f(x) = x*Y       // x is in function scope, Y is global scope
• Helper functions
  • Help() - lists all built-in functions
  • About() - displays information about the utility
  • Clear() - clears the display

Basically when starting the tool, simply type the expression you want to calculate directly on the commandline. Use up and down buttons for autocompletion of previously entered expressions and formulas. Isn't this just so much easier than using the windows calculator? Anyway, currently only 5 datatypes are supported: double, hexidecimal, int, string and boolean. Note that integers (and hexadecimals also) are always converted to doubles when used in a calculation by default. Use the int() function to convert to integer explicitly.

The tool uses the following precedence rules for its operators:

1.	( ), f(x)	Grouping, functions
2.	!   ~   -   +	(most) unary operations
3.	^	Power to (Excel rule: that is a^b^c -> (a^b)^c
3.	*   /   %	Multiplication, division, modulo
4.	+   -	Addition and subtraction
4.	&	concatenation of strings
5.	<   <=   >   >=	Comparisons: less-than, ...
6.	=   !=   <>	Comparisons: equal and not equal
7.	&&	Logical AND
8.	||	Logical OR
9.	?:	Conditional expression
10	:=	Assignment

Embedding the Evaluator Engine

If you would like to embed this Tiny Expression Evaluator inside your own projects, there are only a few simple steps involved.

1. Copy the Evaluator folder including all classes inside it into your own C# project. In short, we have the following classes:
   1. Context - The context holds all available declared functions and variables and the scope stack.
   2. Expression - Wrapper class that holds and evaluates the expression.
   3. Function - Defines the prototype for a function. A function must have a name, a pointer (delegate) to an actual implementation of a function and it must have the minimum and maximum allowed number of paramters set.
   4. Functions - This class defines the list of default available functions. Feel free to add your own to the list.
   5. Parser - The parser for the expression. This code is generated by TinyPG.
   6. ParseTree - the resulting parse tree after parsing the expression. This code is generated by TinyPG.
   7. ParseTreeEvaluator - This is a subclass of ParseTree and implements the core semantics of the operators. The code should be pretty easy to understand, since the methods of the class correspond directly with the defined grammar (see TinyExe.tpg).
   8. Scanner - This is the scanner used by the parser to match against terminals inside the expression. This class is also generated by TinyPG.
   9. Variables - This is currently implemented as a (case-sensitive) dictionary. A variable is simply a <name, value> pair.
2. Add the namespace (in this case TinyExe, but feel free to change it) to your classes.
3. Then, insert the following code to execute an evaluation:

string expr = "1*3/4"; // define the expression as a string
...
// create the Expression object providing the string
Expression exp = new Expression(expr);

// check for parse errors
 if (exp.Errors.Count > 0)
 {
     Console.WriteLine(exp.Errors[0].Message);
     return;
 }

 // No parse error, go ahead and evaluate the expression
 // Note that Eval() always returns an object that can be of various types
 // you will need to check for the type yourself
 object val = exp.Eval();

 // check for interpretation errors (e.g. is the function defined?)
 if (exp.Errors.Count > 0)
 {
     Console.WriteLine(exp.Errors[0].Message);
     return;
 }
 // nothing returned, nothing to evaluate or some kind of error occured?
 if (val == null)
     return;

 //print the result to output as a string
 Console.WriteLine(string.Format(CultureInfo.InvariantCulture, "{0}", val));

The code above handles any expression gracefully. But just to be absolutely sure, you might want to trap any exception in a try...catch statement.

Extending the Evaluator Engine

Basically, there are 2 kinds of extensions you can make:

1. Add your own built-in functions within the allowed syntax of the evaluator
2. Enhance or change the syntax, therefore changing the grammar

Adding a Static Function

The easiest way to add a new function is to open up the Functions class, and add your implementation in the InitDefaults() method. If you prefer to externalize your function, then you should add your function to the Context.Default.Functions.

For example:

Context.Default.Functions.Add("myfunc", new StaticFunction("MyFunc", MyFunc, 2, 3));

where the MyFunc function is declared as:

private static object MyFunc(object[] parameters) { ... }

Parameters are passed as a list of objects. The number of objects will always be the same as specified in the declaration, in this case a minumum of 2 parameters and a mixumum of 3. The function will need to check the number of parameters and check for the correct type being passed.

In a more advanced setting, e.g., if you need access to the Context object, or to other classes in your project, you can implement your own version of the Function class. You  will need to create a subclass derived from the Function class and implement the Eval() method. Also, you will need to take care of the initialization of arguments, Parametersettings and handle the scope. As an example, take a look at the ClearFunction class.

Changing the Syntax

In order to change the syntax and add new features to the expression language, e.g. add support for extra datatypes (i.e., Date/Time, Money) or allow custom datatypes (i.e., structs), or maybe even more exotic: allow evaluaton of JavaScript, you will need to have a fundamental understanding of parsers and compiler theory. Please have a look at the @TinyPG parser generator article, it explains the basics on how to create a parser for your language.

Just changing the syntax will not be sufficient. It's quite easy to change the grammar used to parse the input, but the semantics (code behind) will also need to be updated accordingly. Luckily the ParseTree that is generated is quite straightforward in use. Suppose for example that we would like to support an new rule, e.g. an IF-THEN-ELSE statement. We could add a new statement in the grammer file (see the included TinyExe.tpg):

IfThenElseStatement	-> IF RelationalExpression THEN Expression (ELSE Expression)?;

When generating the code with @TinyPG for the Scanner, Parser and ParseTree, typically the ParseTree will now contain an addition method called:

protected virtual object EvalIfThenElseStatement
		(ParseTree tree, params object[] paramlist)

As you can see, the method is declared as virtual, meaning you can override this method in a subclass. This is exactly what I did in TinyExe. The ParseTreeEvaluator is a subclass of ParseTree and contains all necessary overrides. The main reason for putting this in a subclass, is that I can now change the grammar of the parser over and over again, and generate a new ParseTree, without the subclass being overwritten.

So what you need to do is override the function in the ParseTreeEvaluator class. You need to understand that this method is called just-in-time, while evaluating the parsetree. At some point during parsing the input, the Parser created a new ParseNode of type IfThenElseStatement. During evaluation of this node, the corresponding EvalIfThenElseStatement (your overriden method!) is called.

At the point of entry in this method, you need to understand that the current ParseNode (of type IfThenElseStatement) is actually this. Because the statement contains 6 parts (of which the last 2 of the ELSE part are optional), this will contain 4 or 6 Nodes:

1. this.Nodes[0] corresponds to the ParseNode of type IF
2. this.Nodes[1] corresponds to the RelationalExpression
3. this.Nodes[2] corresponds to the ParseNode of type THEN
4. this.Nodes[3] corresponds to the Expression Node
5. If this.Nodes[4] exists, it will correspond to the ELSE node
6. if this.Nodes[5] exists, it will correspond to the Expression Node.

So again, I hope this makes clear that the structure of the ParseTree is straightforward and can be quickly resolved back to the original grammar.

Now, the nodes that are of real interest are nodes 1, 3 and 5 of course. So first, we evaluate Nodes[1]. Because Nodes[1] is a non-terminal, it means it can contains a complete subtree. This subtree needs to be evaluated. To make this easier, you can make use of the helper function this.GetValue().

object result = this.GetValue(tree, TokenType.RelationalExpression, 0);

Note that we expect the result of the evaluation to be a boolean value (true or false), however we cannot be certain. So make sure to first check the type of the return value. If this turns out not to be boolean, raise an error.

If result is true, then we can repeat the procedure and evaluate Nodes[3] and return this value. Otherwise we evaluate Nodes[5] (if it exists) and return that.

This is basically in a nutshell 2 ways how extensions are supported. If you have additional questions, just drop me a line.

Points of Interest

Apart from writing a fully functional-handy-comprehensive-easy-to-use-tiny-formula-calculation-utility that by far outperforms your default windows calculator, I also hope that this project will serve as a good demonstration on how @TinyPG can be used in a real-world-scenario.

Of course, there are always new features that could be added, however for now I think this demontration shows nicely how you can create a quite powerful language with some basic knowledge of grammars, parsers and of course a bit of c#.

So that's it. If you have any ideas for new features, comments or remarks, please drop a note!

HistoryHistory

@TinyExe v1.0

Tiny Expression Evaluator Version 1.0 was released on 16^st of August 2011. This version includes the following features:

• Evaluation of mathematical functions and expressions
• Default built-in functions
• Runtime function and variable declarations
• Function-scoped and global variables
• Recursive function calls
• Multiple datatype support (double, int, hex, bool and string)
• Recursive function calls
• Predefined constants Pi en E
• Boolean operators and assignments