Sprache中的递归表达式解析 [英] Recursive expression parsing in Sprache

问题描述

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

I am building a Sprache parser to parse expressions similar to SQL search conditions. e.g Property = 123 or Property > AnotherProperty

到目前为止，这两个示例均有效，但是我正在努力弄清楚我需要做些什么才能允许ANDing/ORing条件和括号.

So far both of those examples work, however I am struggling to figure out what I need to do to allow ANDing/ORing conditions and parenthesis.

到目前为止，基本上我是这样的:

Basically I have this so far:

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};

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

This works for the simple cases above, but now I need a pointer on how to implement conditions like:

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

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

任何人都可以给我一个关于如何构造这种事情的解析器的想法吗?

Can anyone give me an idea on how to structure the parsers for this sort of thing?

推荐答案

到目前为止，您所拥有的是一个基本的比较表达式解析器.看来您想将其包装在具有子表达式支持的处理逻辑表达式(and，or等)的解析器中.

What you have so far is a basic comparison expression parser. It looks like you want to wrap that in a parser that handles logical expressions (and, or, etc.) with sub-expression support.

我最初发布的代码是从我仍在使用的未经测试的代码中删除的，该代码无法处理具有多个术语的语句.我对ChainOperator方法的理解显然不完整.

The code I posted at first was ripped from poorly-tested code I was still working on, which didn't handle statements with multiple terms. My understanding of the ChainOperator method was clearly incomplete.

Parse.ChainOperator是使您可以指定运算符并使它们在表达式中出现0到很多次的方法.我对它的工作原理进行了假设，结果证明这是错误的.

Parse.ChainOperator is the method that lets you specify your operators and have them appear 0-to-many times in the expression. I was making assumptions about how it worked that turned out to be just wrong.

我已经重写了代码，并添加了一些代码使其更易于使用:

I've rewritten the code and added a few bits to make it easier to use:

// 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解析器中:

---

You will still need to add your own parsers for handling comparison expressions and so on. Plug those into the BooleanValue parser after the existing terms:

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

我正在使用更C#样式的过滤器规范执行类似的操作，在解析阶段进行类型检查，并为字符串和数字分别使用解析器.

I'm doing something similar with a more C#-style filter specification with type checking during the parse phase and separate parsers for strings vs numbers.

这篇关于Sprache中的递归表达式解析的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！