Parser for query filter expression tree

Question

Hi

I am looking for a parser that can operate on a query filter. However, I'm not quite sure of the terminology so it's proving hard work. I hope that someone can help me. I've read about 'Recursive descent parsers' but I wonder if these are for full-blown language parsers rather than the logical expression evaluation that I'm looking for.

Ideally, I am looking for .NET code (C#) but also a similar parser that works in T-SQL.

What I want is for something to parse e.g.:

((a=b)|(e=1))&(c<=d)

Ideally, the operators can be definable (e.g. '<' vs 'lt', '=' vs '==' vs 'eq', etc) and we can specify function-type labels (e.g. (left(x,1)='e')). The parser loads this, obeys order precedence (and ideally handles the lack of any brackets) and then calls-back to my code with expressions to evaluate to a boolean result - e.g. 'a=b'?). I wouldn't expect the parser to understand the custom functions in the expression (though some basic ones would be useful, like string splitting). Splitting the expression (into left- and right-hand parts) would be nice.

It is preferable that the parser asks the minimum number of questions to have to work out the final result - e.g. if one side of an AND is false, there is no point evaluating the other side, and to evaluate the easiest side first (i.e. in the above expression, 'c<=d' should be assumed to be quicker and thus evaluated first.

I can imagine that this is a lot of work to do, however, fairly common. Can anyone give me any pointers? If there aren't parsers that are as flexible as above, are there any basic parsers that I can use as a start?

Many Thanks

Lee

Answer 1

Take a look at this. ANTLR is a good parser generator and the linked-to article has working code which you may be able to adapt to your needs.

Answer 2

Try Vici.Parser: download it here (free) , it's the most flexible expression parser/evaluator I've found so far.

Answer 3

If it's possible for you, use .Net 3.5 expressions.

Compiler parses your expression for you and gives you expression tree that you can analyze and use as you need. Not very simple but doable (actually all implementations of IQueryable interface do exactly this).

Answer 4

You could check out Irony. With it you define your grammar in C# code using a syntax which is not to far from bnf. They even have a simple example on their site (expression evaluator) which seems to be quite close to what you want to achieve.

Edit: There's been a talk about Irony at this year's Lang.Net symposium.

Hope this helps!

Answer 5

You can use .NET expression trees for this. And the example is actually pretty simple.

Expression<Func<int, int, int, int, bool>> test = (int a, int b, int c, int d) => ((a == b) | (c == 1)) & (c <= d);

And then just look at "test" in the debugger. Everything is already parsed for you, you can just use it.

The only problem is that in .NET 3.5 you can have only up to 4 arguments in Func. So, I changed "e" to "c" in one place. In 4.0 this limit is changed to 16.