The Freak Parade

Evaluating dynamic, ad hoc or user provided expressions at runtime, usually in the context of an application’s current state, has been a valuable tool in the programmers tool-belt since the days when Cro-Magnon man was beating the brains out of Saber-toothed tigers to feed his hungry, hairy family.

In an interpreted language, like JavaScript, this is no problem, there is almost always some kind of Eval(string) command that will allow you to pass in and execute some arbitrary piece of code, such as an expression, as capriciously as you like.

With compiled languages, though, by the time your program actually executes, the compiler has completed its work and gone home to have a glass of Wild Turkey and watch football. If you want to evaluate some arbitrary expression (like this one that you might use in a reporting tool)

if (Amount < 0) then 'Red' else 'Black'

You either need to call the compiler back into the office or roll up your sleeves and do the job yourself. Some people would call this a DSL, or Domain Specific Language, at this point, although personally I feel like calling a simple expression language a DSL, especially if it doesn’t have any elements that relate to your specific domain but just operate on the objects you have in memory, whatever they are, is a bit of a stretch. But that’s an abstract distinction, DSL or not, the options are the same.

Compile Code on the Fly

In .NET you can use the System.CodeDom.Compiler classes to compile some arbitrary piece of source code into an in-memory class inside an in-memory assembly, and then execute the code. This is the approach you would take if you were going to use Boo (or some expression language based on Boo), but really there is a lot of baggage that comes with that approach that I think makes it inappropriate for most scenarios where you want to evaluate ad hoc expressions. Namely, if you are dealing with a large number of potential expressions that aren’t mostly known at the start of your application, you will be creating lots of dynamic assemblies, which isn’t blazing fast (although executing the expressions will be), and keeping them around in memory. If you allow end users or developers to modify expressions at runtime, the old assembly holding the previous version of the expression can’t be unloaded from memory, and you generally have a mess. However, there is a huge design-time upside to this approach, which is that you don’t have to define an expression language yourself, you can re-use the expression syntax of the language you are using, and you don’t have to think much about parsing or compiling anything. But the runtime story in many scenario often makes the approach untenable.

Reflection Emit - the lightweight, high performance approach

If you’re very clever, there is a middle way in .NET, which is to use black magic and Reflection.Emit to generate methods straight to IL (basically a custom parser/compiler just for expressions), which bypasses most of the ugliness of the previous approach. Expressions are still compiled and use early binding (not reflection) to evaluate your expressions. I think in many, many scenarios this is a great option. Plus, you don’t need to collect all the frogs tongues and newts eyes to whip up this voodoo yourself, some kind, intelligent soul has done this for us.

The Old-Fashioned Way

If you want complete control of your expression language, though, perhaps to make it more end user friendly than C#, or you need late bound semantics when evaluating your expressions, or you just like to take things apart and get dirty, there’s always the old fashioned way. The old fashioned way is a three part approach, both a bit tedious, but not particularly difficult, especially with modern tools.

1. Define the syntax and grammar of your expression language

2. Parse your expression into an Abstract Syntax Tree (AST) based on your grammar

3. Compile your expression into an object model (or, alternatively, directly interpret from the AST)

Step one involves taking a string like “(10 - 2) + x ^ y” and splitting it up into something a computer can make use of. AST’s are all the rage now-a-days along with DSL’s, so won’t go into too much detail here, ask Google all about them. The point is, the string needs to be parsed. This task itself can be accomplished in one of three ways:

A. Hand roll parsing logic, possibly using Regular Expressions. Yuck. Error prone and tedious.

B. Use a modern parser-generator, like ANTLR, to define the grammar of your expression language in a clean, easily understood manner and let the tool code generate the classes required to parse expression strings according to your grammar. This is a straightforward, robust approach that offers the most flexibility. However, it also requires a few steps to create a grammar, generate a parser, test, modify, repeat. It isn’t without some tedium.

C. Use a parser that doesn’t use code generation, but allows your grammar to be directly defined in your target language and fed directly to a parser for parsing your strings. The only example of this I am aware of is a very cool tool on CodePlex called Irony. There may be others like it, but this is the only one I’m aware of personally, and it is quite nice.

(D. Of course, you could use an existing expression evaluator library - there are several - one of them is certain to suit your needs - I list the ones I’ve found below)

Once your expressions are parsed into a nice Abstract Syntax Tree, you need to do something with that tree. You can interpret the tree directly, or you can “compile” the AST into an object model that can be used to quickly evaluate the expression in many different contexts, with many different values for variables, etc. This is it’s own exercise in tedium, but once done can be relatively easily enhanced and modified as your expression language evolves.

[UPDATE:] A CodeProject article just popped up with another Parser Generator for .NET that looks pretty cool. This is a stand alone tool that takes your grammar and generates a parser <GASP!> No…really? Um…like all other parser generators in the world? Yes, BUT, it generates the parser completely, i.e. it does NOT generate some source code that derives from or must be consumed by the parent library (like most other parser generators). This means that the parser this tool generates is entirely standalone, it adds no dependencies to your project, and if you feel like it you could tweak it or study it or do whatever you like, it’s all there. I haven’t evaluated this one yet, but I definitely will in the near future. Here is a blurb from the intro to the CodeProject article:

“TinyGP stands for “Tiny Parser Generator”. This particular generator is an LL(1) recursive descent parser generator. This means that instead of generating a state machine out of a grammar like most compiler compilers, instead it will generate source code directly; basically generating a method for each non-terminal in the grammar. Terminals are expressed using .Net’s powerful regular expressions. To help the programmer create .Net regular expressions a Regex tool is embedded in TinyPG. Grammars can be written using the extended BNF notation. TinyGP will generate a scanner, parser and parsetree file in c# code from this which can be compiled directly into your own projects.”

[UPDATE 2] Using the recipe above, and Irony.net, I have posted a reference implementation an object-model based expression evaluator on Codeplex and called it Simple Expression Evaluator. Check it out. I used Irony.net as the default compiler, but structured the project so that by implementing a simple interface you could easily plug in any parser you like.

And that’s it, then you’re done. For those too busy or not geeky enough to want to build your own expression evaluating machines, I’ll list the libraries I have identified that looked good enough (to me) to use in a professional project.

Resources

1. Flee - Fast Lightweight Expression Evaluator - uses IL generation to produce a high performance expression evaluator based on C#.

2. LazyParser.NET - a late bound expression evaluator that does the whole bit manually. Uses reflection to resolve context variables, so it is slower than flee, but has the advantage of being late bound and so a little more flexible in certain circumstances.

3. The Spring.NET framework has a pretty intense expression evaluator library as well

4. Script.NET - A fully featured, interpreted scripting language based on C# and using Irony.NET. It can do a lot more than evaluate expressions, but it can evaluate expressions, too.

5. CodeProject article on using the ANTLR + Grammar approach to rolling your own expression evaluator. Article has a pretty professional library included in the code download.

6. Irony.NET compiler construction kit on Code Plex - a code gen-less parser tool. Create your grammars directly in C#.

7. A blog post on how Irony works

8. CodeProject article on getting started with Irony.NET

9. CodeProject article on writing a DSL using Irony.NET

10. Several approaches to evaluating expressions, ignoring the parsing aspect. Basically, various ways you could transform your AST into an object model.

11. TinyParser Generator is a utility that will generate the source code for a complete compiler from your grammar, without any intermediate libraries needed to be referenced by your code.

12. Simple Expression Evaluator - Irony.NET based Expression Evaluator