title: Parser for query filter expression tree
body: <p>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.</p>
  
  <p>Ideally, I am looking for .NET code (C#) but also a similar parser that works in T-SQL.</p>
  
  <p>What I want is for something to parse e.g.:</p>
  
  <p>((a=b)|(e=1))&amp;(c&lt;=d)</p>
  
  <p>Ideally, the operators can be definable (e.g. '&lt;' 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.</p>
  
  <p>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&lt;=d' should be assumed to be quicker and thus evaluated first.</p>
  
  <p>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?</p>
  
  <p>Many Thanks</p>
  
  <p>Lee</p>