Parser for query filter expression tree
I'm looking for a parser that can work with a query filter. However, I'm not entirely sure about the terminology, so this proves the hard work. I hope someone can help me. I've read about "recursive descent parsers", but I'm wondering if they are needed for full-sized parsers and not the logical expression evaluation I'm looking for.
Ideally, I'm looking for .NET code (C #), but also a similar parser that works in T-SQL.
I want something to parse something like:
((a = b) | (e = 1)) & (c <= z)
Ideally, operators can be defined (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 the order of precedence (and ideally handles the absence of any parentheses), and then calls my code with expressions to compute a boolean result - eg. 'A = b'?). I would not expect the parser to understand UDFs in an expression (although some basic ones would be useful, like splitting strings). Splitting the expression (left and right) would be nice.
It is preferable that the parser asks the minimum number of questions to get the final result - for example, if one side of the AND is false, then there is no point evaluating the other side, and evaluate the lightest side first (i.e., in the above expression "c < = d "should be considered faster and therefore evaluated first.
I can imagine that this is a lot of work, however, quite common. Can anyone give me any guidance? If there are no parsers that are as flexible as above, are there any basic parsers that I can use as a start?
Many thanks
Lee
source to share
You can check out Irony . With it, you define your grammar in C # code using syntax that shouldn't be far from bnf. They even have a simple example on their site (expression evaluator) that seems to be very close to what you want to achieve.
Edit: This year's Lang.Net symposium did a story about irony .
Hope this helps!
source to share
Try Vici.Parser: Download it here (free) , it's the most flexible parser / evaluator I've found so far.
source to share
NET expression trees can be used 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 the "test" in the debugger. Everything has already been analyzed for you, you can just use it.
The only problem is that in .NET 3.5, you can have up to 4 arguments in Func. So, I changed "e" to "c" in one place. At 4.0, this limit changes to 16.
source to share