递归表达式解析在Sprache中的应用

Question

我正在构建一个Sprache解析器来解析类似于SQL搜索条件的表达式。例如Property = 123或Property > AnotherProperty

到目前为止，这两个例子都起作用了，但是我很难弄清楚我需要做什么才能允许ANDing/ORing条件和括号。

基本上到目前为止我有这样的想法：

private static readonly Parser<string> Operators =
    Parse.String("+").Or(Parse.String("-")).Or(Parse.String("="))
        .Or(Parse.String("<")).Or(Parse.String(">"))
        .Or(Parse.String("<=")).Or(Parse.String(">=")).Or(Parse.String("<>"))
        .Text();

private static readonly Parser<IdentifierExpression> Identifier = 
    from first in Parse.Letter.Once()
    from rest in Parse.LetterOrDigit.Many()
    select new IdentifierExpression(first.Concat(rest).ToArray());

public static readonly Parser<Expression> Integer =
    Parse.Number.Select(n => new IntegerExpression {Value = int.Parse(n)});

public static readonly Parser<SearchCondition> SearchCondition = 
    from left in Identifier.Or(Number)
    from op in Operators.Token()
    from right in Identifier.Or(Number)
    select new SearchCondition { Left = left, Right = right, Operator = op};

这适用于上面的简单情况，但现在我需要一个如何实现如下条件的指针：

• PropertyX = PropertyY OR PropertyX = PropertyZ
• PropertyA > PropertyB AND (OtherAnotherProperty = 72 OR OtherAnotherProperty = 150)

有人能给我一个关于如何构造这类事情的解析器的想法吗？

Answer 1

到目前为止，您拥有的是一个基本的比较表达式解析器。看起来，您希望将其封装到一个处理逻辑表达式(and、or等)的解析器中。有子表达式支持。

我最初发布的代码是从我仍然在处理的测试不佳的代码中提取出来的，它没有处理带有多个术语的语句。我对ChainOperator方法的理解显然是不完整的。

Parse.ChainOperator是一种方法，允许您指定运算符，并使它们在表达式中出现0到多次。我对它的工作方式做了一些假设，结果证明这是错误的。

我重写了代码，并添加了一些代码以使其更易于使用：

// Helpers to make access simpler
public static class Condition
{
    // For testing, will fail all variable references
    public static Expression<Func<object, bool>> Parse(string text)
        => ConditionParser<object>.ParseCondition(text);

    public static Expression<Func<T, bool>> Parse<T>(string text)
        => ConditionParser<T>.ParseCondition(text);

    public static Expression<Func<T, bool>> Parse<T>(string text, T instance)
        => ConditionParser<T>.ParseCondition(text);
}

public static class ConditionParser<T>
{
    static ParameterExpression Parm = Expression.Parameter(typeof(T), "_");

    public static Expression<Func<T, bool>> ParseCondition(string text)
        => Lambda.Parse(text);

    static Parser<Expression<Func<T, bool>>> Lambda =>
        OrTerm.End().Select(body => Expression.Lambda<Func<T, bool>>(body, Parm));

    // lowest priority first
    static Parser<Expression> OrTerm =>
        Parse.ChainOperator(OpOr, AndTerm, Expression.MakeBinary);

    static Parser<ExpressionType> OpOr = MakeOperator("or", ExpressionType.OrElse);

    static Parser<Expression> AndTerm =>
        Parse.ChainOperator(OpAnd, NegateTerm, Expression.MakeBinary);

    static Parser<ExpressionType> OpAnd = MakeOperator("and", ExpressionType.AndAlso);

    static Parser<Expression> NegateTerm =>
        NegatedFactor
        .Or(Factor);

    static Parser<Expression> NegatedFactor =>
        from negate in Parse.IgnoreCase("not").Token()
        from expr in Factor
        select Expression.Not(expr);

    static Parser<Expression> Factor =>
        SubExpression
        .Or(BooleanLiteral)
        .Or(BooleanVariable);

    static Parser<Expression> SubExpression =>
        from lparen in Parse.Char('(').Token()
        from expr in OrTerm
        from rparen in Parse.Char(')').Token()
        select expr;

    static Parser<Expression> BooleanValue =>
        BooleanLiteral
        .Or(BooleanVariable);

    static Parser<Expression> BooleanLiteral =>
        Parse.IgnoreCase("true").Or(Parse.IgnoreCase("false"))
        .Text().Token()
        .Select(value => Expression.Constant(bool.Parse(value)));

    static Parser<Expression> BooleanVariable =>
        Parse.Regex(@"[A-Za-z_][A-Za-z_\d]*").Token()
        .Select(name => VariableAccess<bool>(name));

    static Expression VariableAccess<TTarget>(string name)
    {
        MemberInfo mi = typeof(T).GetMember(name, MemberTypes.Field | MemberTypes.Property, BindingFlags.Instance | BindingFlags.Public).FirstOrDefault();
        var targetType = typeof(TTarget);
        var type = 
            (mi is FieldInfo fi) ? fi.FieldType : 
            (mi is PropertyInfo pi) ? pi.PropertyType : 
            throw new ParseException($"Variable '{name}' not found.");

        if (type != targetType)
            throw new ParseException($"Variable '{name}' is type '{type.Name}', expected '{targetType.Name}'");

        return Expression.MakeMemberAccess(Parm, mi);
    }

    // Helper: define an operator parser
    static Parser<ExpressionType> MakeOperator(string token, ExpressionType type)
        => Parse.IgnoreCase(token).Token().Return(type);
}

还有一些例子：

static class Program
{
    static void Main()
    {
        // Parser with no input
        var condition1 = Condition.Parse("true and false or true");
        Console.WriteLine(condition1.ToString());
        var fn1 = condition1.Compile();
        Console.WriteLine("\t={0}", fn1(null));

        // Parser with record input
        var record1 = new { a = true, b = false };
        var record2 = new { a = false, b = true };
        var condition2 = Condition.Parse("a and b or not a", record);
        Console.WriteLine(condition2.ToString());
        var fn2 = condition2.Compile();
        Console.WriteLine("\t{0} => {1}", record1.ToString(), fn2(record1));
        Console.WriteLine("\t{0} => {1}", record2.ToString(), fn2(record2));
    }
}

您仍然需要添加自己的解析器来处理比较表达式等等。将它们插入到现有术语之后的BooleanValue解析器中：

static Parser<Expression> BooleanValue => 
    BooleanLiteral
    .Or(BooleanVariable)
    .Or(SearchCondition);

我正在使用更多C#风格的过滤器规范进行类似的操作，在解析阶段进行类型检查，并对字符串和数字进行单独的解析。