Разбор рекурсивного выражения в 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# с проверкой типов во время фазы анализа и отдельными анализаторами строк и чисел.