Click here to Skip to main content
Click here to Skip to main content

Invent your own Dynamic LINQ parser

, 8 Apr 2012 MIT
Rate this:
Please Sign up or sign in to vote.
This is an alternative for "Dynamically generate a LINQ query with a custom property".
This is an old version of the currently published tip/trick.

Introduction

This is an alternative to the original Tip Dynamically generate a LINQ query with a custom property.

The original post follows the concept of tweaking with the client of of a query to allow dynamic queries. I find that quite intrusive and not re-usable for future use as I commented on the original post.

I outline here how you can re-invent your own Dynamic Linq version. I present some parsing techniques that might be helpful for other simple parser tasks. For "real" parser works, I strongly recommend using a parser generator like Coco/R or like ANTLR.

The functionality:

create from an expression that is given in a string a function that can be used in a LINQ query, e.g.

IEnumerable<MySourceElement> items = ...;
...
string s = GetUserEntry(); // e.g. Name == "x" || Number >= 800
...
var pred = SimpleExpression.PredicateParser<MySourceElement>.Parse(s);
var f = pred.Compile();
var query = from e in items where f(e) select e;
...

Using the code

This is a very dense code that shows how you could write your own Dynamic LINQ parser:

  • the scanner is from line 11 to line 54
  • the code generator is from line 57 to line 108
  • the parser from is line 109 to line 149

The implemented features:

  • names as properties or fields of the lambda parameter
  • double or int numbers
  • strings
  • nested expressions
  • numeric, string, boolean type system with numeric type promotion
  • operators ||, &&, ==, !=, <, <=, >=, >, !
  1  using System;
  2  using System.Collections.Generic;
  3  using System.Linq;
  4  using System.Linq.Expressions;
  5  using System.Text.RegularExpressions;
  6   
  7  namespace SimpleExpression
  8  {
  9      public abstract class PredicateParser
 10      {
 11          #region scanner
 12          /// <summary>tokenizer pattern: Optional-SpaceS...Token...Optional-Spaces</summary>
 13          private static readonly string _pattern = @"\s*(" + string.Join("|", new string[]
 14          {
 15              // operators and punctuation that are longer than one char: longest first
 16              string.Join("|", new string[] { "||", "&&", "==", "!=", "<=", ">=" }.Select(e => Regex.Escape(e))),
 17              @"""(?:\\.|[^""])*""",  // string
 18              @"\d+(?:\.\d+)?",       // number with optional decimal part
 19              @"\w+",                 // word
 20              @"\S",                  // other 1-char tokens (or eat up one character in case of an error)
 21          }) + @")\s*";
 22          /// <summary>get 1st char of current token (or a Space if no 1st char is obtained)</summary>
 23          private char Ch { get { return string.IsNullOrEmpty(Curr) ? ' ' : Curr[0]; } }
 24          /// <summary>move one token ahead</summary><returns>true = moved ahead, false = end of stream</returns>
 25          private bool Move() { return _tokens.MoveNext(); }
 26          /// <summary>the token stream implemented as IEnumerator&lt;string&gt;</summary>
 27          private IEnumerator<string> _tokens;
 28          /// <summary>constructs the scanner for the given input string</summary>
 29          protected PredicateParser(string s)
 30          {
 31              _tokens = Regex.Matches(s, _pattern, RegexOptions.Compiled).Cast<Match>()
 32                        .Select(m => m.Groups[1].Value).GetEnumerator();
 33              Move();
 34          }
 35          protected bool IsNumber { get { return char.IsNumber(Ch); } }
 36          protected bool IsDouble { get { return IsNumber && Curr.Contains('.'); } }
 37          protected bool IsString { get { return Ch == '"'; } }
 38          protected bool IsIdent { get { char c = Ch; return char.IsLower(c) || char.IsUpper(c) || c == '_'; } }
 39          /// <summary>throw an argument exception</summary>
 40          protected void Abort(string msg) { throw new ArgumentException("Error: " + (msg ?? "unknown error")); }
 41          /// <summary>get the current item of the stream or an empty string after the end</summary>
 42          protected string Curr { get { return _tokens.Current ?? string.Empty; }}
 43          /// <summary>get current and move to the next token (error if at end of stream)</summary>
 44          protected string CurrAndNext { get { string s = Curr; if (!Move()) Abort("data expected"); return s; } }
 45          /// <summary>get current and move to the next token if available</summary>
 46          protected string CurrOptNext { get { string s = Curr; Move(); return s; } }
 47          /// <summary>moves forward if current token matches and returns that (next token must exist)</summary>
 48          protected string CurrOpAndNext(params string[] ops)
 49          {
 50              string s = ops.Contains(Curr) ? Curr : null;
 51              if (s != null && !Move()) Abort("data expected");
 52              return s;
 53          }
 54          #endregion
 55      }
 56      public class PredicateParser<TData>: PredicateParser
 57      {
 58          #region code generator
 59          private static readonly Type _bool = typeof(bool);
 60          private static readonly Type[] _prom = new Type[]
 61          { typeof(decimal), typeof(double), typeof(float), typeof(ulong), typeof(long), typeof(uint),
 62            typeof(int), typeof(ushort), typeof(char), typeof(short), typeof(byte), typeof(sbyte) };
 63          /// <summary>enforce the type on the expression (by a cast) if not already of that type</summary>
 64          private static Expression Coerce(Expression expr, Type type)
 65          {
 66              return expr.Type == type ? expr : Expression.Convert(expr, type);
 67          }
 68          /// <summary>casts if needed the expr to the "largest" type of both arguments</summary>
 69          private static Expression Coerce(Expression expr, Expression sibling)
 70          {
 71              if (expr.Type != sibling.Type)
 72              {
 73                  Type maxType = MaxType(expr.Type, sibling.Type);
 74                  if (maxType != expr.Type) expr = Expression.Convert(expr, maxType);
 75              }
 76              return expr;
 77          }
 78          /// <summary>returns the first if both are same, or the largest type of both (or the first)</summary>
 79          private static Type MaxType(Type a, Type b) { return a==b?a:(_prom.FirstOrDefault(t=>t==a||t==b)??a); }
 80          /// <summary>
 81          /// Code generation of binary and unary epressions, utilizing type coercion where needed
 82          /// </summary>
 83          private static readonly Dictionary<string, Func<Expression, Expression, Expression>> _binOp =
 84              new Dictionary<string,Func<Expression,Expression,Expression>>()
 85          {
 86              { "||", (a,b)=>Expression.OrElse(Coerce(a, _bool), Coerce(b, _bool)) },
 87              { "&&", (a,b)=>Expression.AndAlso(Coerce(a, _bool), Coerce(b, _bool)) },
 88              { "==", (a,b)=>Expression.Equal(Coerce(a,b), Coerce(b,a)) },
 89              { "!=", (a,b)=>Expression.NotEqual(Coerce(a,b), Coerce(b,a)) },
 90              { "<", (a,b)=>Expression.LessThan(Coerce(a,b), Coerce(b,a)) },
 91              { "<=", (a,b)=>Expression.LessThanOrEqual(Coerce(a,b), Coerce(b,a)) },
 92              { ">=", (a,b)=>Expression.GreaterThanOrEqual(Coerce(a,b), Coerce(b,a)) },
 93              { ">", (a,b)=>Expression.GreaterThan(Coerce(a,b), Coerce(b,a)) },
 94          };
 95          private static readonly Dictionary<string, Func<Expression, Expression>> _unOp =
 96              new Dictionary<string, Func<Expression, Expression>>()
 97          {
 98              { "!", a=>Expression.Not(Coerce(a, _bool)) },
 99          };
100          /// <summary>create a constant of a value</summary>
101          private static ConstantExpression Const(object v) { return Expression.Constant(v); }
102          /// <summary>create lambda parameter field or property access</summary>
103          private MemberExpression ParameterMember(string s) { return Expression.PropertyOrField(_param, s); }
104          /// <summary>create lambda expression</summary>
105          private Expression<Func<TData, bool>> Lambda(Expression expr) { return Expression.Lambda<Func<TData, bool>>(expr, _param); }
106          /// <summary>the lambda's parameter (all names are members of this)</summary>
107          private readonly ParameterExpression _param = Expression.Parameter(typeof(TData), "_p_");
108          #endregion
109          #region parser
110          /// <summary>initialize the parser (and thus, the scanner)</summary>
111          private PredicateParser(string s): base(s) { }
112          /// <summary>main entry point</summary>
113          public static Expression<Func<TData, bool>> Parse(string s) { return new PredicateParser<TData>(s).Parse(); }
114          private Expression<Func<TData, bool>> Parse() { return Lambda(ParseExpression()); }
115          private Expression ParseExpression() { return ParseOr(); }
116          private Expression ParseOr()         { return ParseBinary(ParseAnd, "||"); }
117          private Expression ParseAnd()        { return ParseBinary(ParseEquality, "&&"); }
118          private Expression ParseEquality()   { return ParseBinary(ParseRelation, "==", "!="); }
119          private Expression ParseRelation()   { return ParseBinary(ParseUnary, "<", "<=", ">=", ">"); }
120          private Expression ParseUnary()      { return CurrOpAndNext("!") != null ? _unOp["!"](ParseUnary())
121                                                 : ParsePrimary(); }
122          private Expression ParseIdent()      { return ParameterMember(CurrOptNext); }
123          private Expression ParseString()     { return Const(Regex.Replace(CurrOptNext, "^\"(.*)\"$",
124                                                 m => m.Groups[1].Value)); }
125          private Expression ParseNumber()     { if (IsDouble) return Const(double.Parse(CurrOptNext));
126                                                 return Const(int.Parse(CurrOptNext)); }
127          private Expression ParsePrimary()
128          {
129              if (IsIdent) return ParseIdent();
130              if (IsString) return ParseString();
131              if (IsNumber) return ParseNumber();
132              return ParseNested();
133          }
134          private Expression ParseNested()
135          {
136              if (CurrAndNext != "(") Abort("(...) expected");
137              Expression expr = ParseExpression();
138              if (CurrOptNext != ")") Abort("')' expected");
139              return expr;
140          }
141          /// <summary>generic parsing of binary expressions</summary>
142          private Expression ParseBinary(Func<Expression> parse, params string[] ops)
143          {
144              Expression expr = parse();
145              string op;
146              while ((op = CurrOpAndNext(ops)) != null) expr = _binOp[op](expr, parse());
147              return expr;
148          }
149          #endregion
150      }
151  }
152  
153  

This program calls the entry point of the parser above and runs various queries employing the calculated expression:

  1          static void Main(string[] args)
  2          {
  3              var items = new List<Element>()
  4              {
  5                  new Element("a", 1000),
  6                  new Element("b", 900),
  7                  new Element("c", 800),
  8                  new Element("d", 700),
  9                  new Element("e", 600),
 10                  new Element("x", 500),
 11                  new Element("y", 400),
 12                  new Element("z", 300),
 13              };
 14   
 15              string s = "Name == \"x\" || Number >= 800";
 16              var pred = SimpleExpression.PredicateParser<Element>.Parse(s);
 17              Console.WriteLine("User Entry: {0}", s);
 18              Console.WriteLine("Expr Tree:  {0}", pred.ToString());
 19              var f = pred.Compile();
 20              Console.WriteLine("### mark affectd items ###");
 21              foreach (var item in items)
 22              {
 23                  Console.WriteLine("{2} Name = {0}, Number = {1}", item.Name, item.Number, f(item) ? "x" : " ");
 24              }
 25              Console.WriteLine("### where-select ###");
 26              var q = from e in items where f(e) select e;
 27              foreach (var item in q)
 28              {
 29                  Console.WriteLine("  Name = {0}, Number = {1}", item.Name, item.Number);
 30              }
 31          }
The output is:
User Entry: Name == "x" || Number >= 800
Expr Tree:  _p_ => ((_p_.Name == "x") OrElse (Convert(_p_.Number) >= 800))
### mark affectd items ###
x Name = a, Number = 1000
x Name = b, Number = 900
x Name = c, Number = 800
  Name = d, Number = 700
  Name = e, Number = 600
x Name = x, Number = 500
  Name = y, Number = 400
  Name = z, Number = 300
### where-select ###
  Name = a, Number = 1000
  Name = b, Number = 900
  Name = c, Number = 800
  Name = x, Number = 500

Points of Interest

As mentioned, check out the available parser generators to do real work with parsers.

LINQ Expression Tree

Dynamic LINQ

To extend the parser: You may easily add more to the expressions, especially new operators is a simple thing:

  • to add + and - binary operators, add them to the _binOp dictionary (similar to ==, e.g. , ("+": Expression.Add(...), "-": Expression.Subtract(...)) create ParseSum() as a copy of ParseRelation, pass "+", "-" as ops, pass ParseSum to ParseRelation (in place of the ParseUnary), pass ParseUnary to ParseSum. That's it.
  • likewise for "*", "/", "%": make ParseMul as copy of the above mentioned ParseSum, pass the right ParseXXX actions, add the respective Expression factories to the _binOps dictionary. Done.
  • An unary "-" is to be added in the _unOps dictionary (no coercion needed). The parsing is done in the ParseUnary() function, e.g.
...
 93      { ">", (a,b)=>Expression.GreaterThan(Coerce(a,b), Coerce(b,a)) },
 94      { "+", (a,b)=>Expression.Add(Coerce(a,b), Coerce(b,a)) },
 95      { "-", (a,b)=>Expression.Subtract(Coerce(a,b), Coerce(b,a)) },
 96      { "*", (a,b)=>Expression.Multiply(Coerce(a,b), Coerce(b,a)) },
 97      { "/", (a,b)=>Expression.Divide(Coerce(a,b), Coerce(b,a)) },
 98      { "%", (a,b)=>Expression.Modulo(Coerce(a,b), Coerce(b,a)) },
 99  };
100  private static readonly Dictionary<string, Func<Expression, Expression>> _unOp =
101                 new Dictionary<string, Func<Expression, Expression>>()
102  {
103      { "!", a=>Expression.Not(Coerce(a, _bool)) },
104      { "-", a=>Expression.Negate(a) },
105  };
...
119  private Expression ParseRelation() { return ParseBinary(ParseSum, "<", "<=", ">=", ">"); }
120  private Expression ParseSum()      { return ParseBinary(ParseMul, "+", "-"); }
121  private Expression ParseMul()      { return ParseBinary(ParseUnary, "*", "/", "%"); }
122  private Expression ParseUnary()
123  {
124      if (CurrOpAndNext("!") != null) return _unOp["!"](ParseUnary());
125      if (CurrOpAndNext("-") != null) return _unOp["-"](ParseUnary());
126      return ParsePrimary();
127  }

If you like this alternative to the tip, please rate it Wink | ;-)

Any feedback is very much appreciated.

Please note: this is meant as alternative to the given tip. This alternative does not require the data provider to use special kind of properties or fields. For real work on this, checkout the available Dynamic LINQ implementaiton.

Have fun!

Andi

History

V1.02012-03-28
First version
V1.12012-03-29
fix typo on line 107, simplified ParsePrimary, fixed ParseNumber to correctly distinguish between int and double, some minor code formatting adjustments, add sources download link, update tags (.NET4)
V1.22012-03-29
added sample code for showing how easily extending the expression parser
early adopter of the brand new code rendering feature:
<pre ... countlines="true" countstart="93">...
(thanks Chris Maunder[^] for adding this feature[^] so quickly!)
V1.32012-04-06
Fix Regex for string (properly handles embedded double quotes) and number (decimal part is optional)

License

This article, along with any associated source code and files, is licensed under The MIT License

Share

About the Author

Andreas Gieriet
Founder eXternSoft GmbH
Switzerland Switzerland
I feel comfortable on a variety of systems (UNIX, Windows, cross-compiled embedded systems, etc.) in a variety of languages, environments, and tools.
I have a particular affinity to computer language analysis, testing, as well as quality management.
 
More information about what I do for a living can be found at my LinkedIn Profile and on my company's web page (German only).
Follow on   LinkedIn

Comments and Discussions


Discussions posted for the Published version of this article. Posting a message here will take you to the publicly available article in order to continue your conversation in public.
 
SuggestionSmall improvment for supporting nested properties [modified] Pinmembermetbone13-Oct-14 19:20 
GeneralRe: Small improvment for supporting nested properties PinprofessionalAndreas Gieriet14-Oct-14 9:57 
GeneralRe: Small improvment for supporting nested properties Pinmembermetbone29-Oct-14 23:13 
GeneralRe: Small improvment for supporting nested properties PinprofessionalAndreas Gieriet30-Oct-14 9:59 
GeneralMy vote of 5 PinmemberMember 100601257-Mar-14 10:27 
GeneralRe: My vote of 5 PinprofessionalAndreas Gieriet7-Mar-14 22:39 
QuestionFailure analyzing string attributes using greather than, etc PinmemberMember 1006012517-May-13 8:26 
AnswerRe: Failure analyzing string attributes using greather than, etc PinmemberAndreas Gieriet17-May-13 11:42 
GeneralRe: Failure analyzing string attributes using greather than, etc PinmemberMember 1006012517-May-13 18:13 
GeneralRe: Failure analyzing string attributes using greather than, etc PinmemberAndreas Gieriet18-May-13 19:58 
GeneralRe: Failure analyzing string attributes using greather than, etc PinmemberMember 1006012519-May-13 12:41 
GeneralRe: Failure analyzing string attributes using greather than, etc [modified] PinmemberAndreas Gieriet20-May-13 0:28 
GeneralRe: Failure analyzing string attributes using greather than, etc PinmemberMember 1006012520-May-13 5:00 
GeneralRe: Failure analyzing string attributes using greather than, etc PinmemberAndreas Gieriet20-May-13 5:21 
GeneralRe: Failure analyzing string attributes using greather than, etc PinmemberMember 1006012520-May-13 6:42 
GeneralMy vote of 5 PinmemberClifford Nelson30-May-12 19:15 
GeneralRe: My vote of 5 PinmemberAndreas Gieriet30-May-12 22:04 
SuggestionTypo error on line 107 for parameter expression declaration PinmemberMatthew YC So28-Mar-12 18:57 
GeneralRe: Typo error on line 107 for parameter expression declaration PinmemberAndreas Gieriet28-Mar-12 20:12 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.141223.1 | Last Updated 8 Apr 2012
Article Copyright 2012 by Andreas Gieriet
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid