Parser for query filter expression tree

c# expression-trees parsing tsql

Question

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

Popular Answer

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!




Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow
Is this KB legal? Yes, learn why
Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow
Is this KB legal? Yes, learn why