I need a fast runtime expression parser

Question

I need to locate a fast, lightweight expression parser.

Ideally I want to pass it a list of name/value pairs (e.g. variables) and a string containing the expression to evaluate. All I need back from it is a true/false value.

The types of expressions should be along the lines of:

varA == "xyz" and varB==123

Basically, just a simple logic engine whose expression is provided at runtime.

UPDATE
At minimum it needs to support ==, !=, >, >=, <, <=

Regarding speed, I expect roughly 5 expressions to be executed per request. We'll see somewhere in the vicinity of 100/requests a second. Our current pages tend to execute in under 50ms. Usually there will only be 2 or 3 variables involved in any expression. However, I'll need to load approximately 30 into the parser prior to execution.

UPDATE 2012/11/5
Update about performance. We implemented nCalc nearly 2 years ago. Since then we've expanded it's use such that we average 40+ expressions covering 300+ variables on post backs. There are now thousands of post backs occurring per second with absolutely zero performance degradation.

We've also extended it to include a handful of additional functions, again with no performance loss. In short, nCalc met all of our needs and exceeded our expectations.

Comeuppance

don't know anything off-the-shelf, but doesn't seem too hard to write yourself (depending on requirements). Is == the only comparator? vars are case-sensitive as in C# or not case-sensitive as in vb.net? boolean operators allowed (and or not). Trying to figure out if this can really be any expression that you could write in code or users are limited to A=B – Godfearing

@Chris Lively, there are several good ways here #1438464 – Hydro

Does the parser need to be fast, or just the evaluation? – Veronica

@CodeInChaos: I'm not sure I understand the question. – Comeuppance

Quite often you parse the string only once and evaluate it ofter afterwards. For example compiling it into a dynamic method might take a bit, but afterwards the performance of evaluating it is the same as a function written in C#. – Veronica

> Quite often you parse the string only once and evaluate it often afterwards (eg with different arguments) NCalc mentioned below acheives this via a cache which works from multiple threads – Hoffarth

Also see #54344 – Prosy

I used ncalc in the past, but while nCalc is quite old. Jace is new and faster :) Github repo of Jace – Adopt

Answer 1

Have you seen https://ncalc.codeplex.com/ and https://github.com/sheetsync/NCalc ?

It's extensible, fast (e.g. has its own cache) enables you to provide custom functions and varaibles at run time by handling EvaluateFunction/EvaluateParameter events. Example expressions it can parse:

Expression e = new Expression("Round(Pow(Pi, 2) + Pow([Pi2], 2) + X, 2)");

  e.Parameters["Pi2"] = new Expression("Pi * Pi");
  e.Parameters["X"] = 10;

  e.EvaluateParameter += delegate(string name, ParameterArgs args)
    {
      if (name == "Pi")
      args.Result = 3.14;
    };

  Debug.Assert(117.07 == e.Evaluate());

It also handles unicode & many data type natively. It comes with an antler file if you want to change the grammer. There is also a fork which supports MEF to load new functions.

It also supports logical operators, date/time's strings and if statements.

Hoffarth

Just tested. Looks great. Still need to load test it, but the project was extremely easy to implement. – Comeuppance

ace, feel free to post in the Ncalc discussions page if you have any problems – Hoffarth

Just wanted to post an update after 7 months of usage. Simply put, it rocks. It is fast, very easy to implement, and even easier to extend with our own custom functions. I highly recommend nCalc. – Comeuppance

Thanks Chris, Great to hear :) I really enjoy working with the framework – Hoffarth

Does anyone know if this evaluator uses lazy ordering? e.g.: (eval(a) || eval(b)) => eval(b) never executes because eval(a) returned true. BTW, there's a clone of it here that's still being maintained: github.com/pitermarx/NCalc-Edge. – Mundford

I can see in the unit tests of the code, that there's a test there to see if boolean expressions get short-circuited, so I guess the answer is yes. – Mundford

Note: NCalc moved to Github: github.com/sheetsync/NCalc and will not be maintained any more. The (archive) link in the answer suggests to look into github.com/sebastienros/jint which is continued to be developed. – Cerated

Answer 2

How about the Fast Lightweight Expression Evaluator? It lets you set variables and supports logical operators.

If you need something beefier and have the time, you could also design your own expression language with Irony.

Beggs

I saw this but wasn't sure if anyone has actually used it. Do you have real world experience with it? – Comeuppance

@Chris - I ran across it while tinkering with my own expression parser. It works as advertised but my requirements don't include fast so you may want to benchmark. Also, it may or may not be lightweight depending on how you define it ;). – Beggs

I upvoted you, but ultimately decided against this. After downloading it I saw it was all vb code; which I am sure is just fine but something in me (probably 20+ years of development) refuses to work with anything vb related if I have a choice. ;) – Comeuppance

For me. it faster than NCalc – Goulden

Or try this old chestnut. I still use it today and it works great. codeproject.com/Articles/19768/… – Oversubtlety

Answer 3

Hisystems' Interpreter supports custom functions, operators and literals, is lightweight pure c# portable code. Currently runs on iOS via MonoTouch and should run on any other Mono environment as well as windows. Free for commercial use. Available on GitHub at https://github.com/hisystems/Interpreter.

Banlieue

Answer 4

I fully appreciate how late this answer is however I would like to throw in my solution because I believe it can add more above the accepted answer of using NCalc should someone wish to use the expressions across multiple platforms.

-- Update --

I have created a parser for C# with plans to also implement it for Java and Swift over the next few months. This would mean that you can evaluate the expressions on multi-platforms without the need for tweaking per platform.

While Java and Swift was planned it never made it in to a fully fledge release. Instead there is now support for .NET Standard enabling support for Xamarin apps.

-- End update --

Expressive is the tool and it is available at: GitHub or Nuget.

The site has a fair amount of documentation on it but to prevent link rot here is an example on how to use it:

Variable support

var expression = new Expression("1 * [variable]");
var result = expression.Evaluate(new Dictionary<string, object> { ["variable"] = 2);

Functions

var expression = new Expression("sum(1,2,3,4)");
var result = expression.Evaluate();

It was designed to match NCalc as best as possible however it has added support for things like a 'null' keyword.

Reptilian

Answer 5

self promotion here i wrote aa generic parser generator for c# https://github.com/b3b00/csly you can find an expression parseras example on my github. you may need to customize it to fit your needs

Equity