LightParser plugin #417

Bykiev · 2025-05-15T17:15:37Z

Bykiev
May 15, 2025
Collaborator

Now parser handles many things, like guids, dates/times, hex numbers, but in many use cases it's not needed. I think creating a new NCalc.LightParser plugin can be a good idea. I did some benchmark and light parser is 2 times faster:

// * Summary *

BenchmarkDotNet v0.14.0, Windows 10 (10.0.19045.5737/22H2/2022Update)
Intel Core i3-6100U CPU 2.30GHz (Skylake), 1 CPU, 4 logical and 2 physical cores
.NET SDK 9.0.100
  [Host]     : .NET 8.0.11 (8.0.1124.51707), X64 RyuJIT AVX2
  DefaultJob : .NET 8.0.11 (8.0.1124.51707), X64 RyuJIT AVX2

Method	Mean	Error	StdDev	Median	Rank	Gen0	Allocated
LightParserSimpleExpression	6.618 us	0.1311 us	0.1705 us	6.588 us	1	0.6790	1.05 KB
SimpleParlotExpression	9.941 us	0.2080 us	0.5934 us	9.964 us	2	0.6714	1.05 KB
LightParserAdvancedPExpression	18.935 us	0.4325 us	1.2477 us	18.491 us	3	1.9226	2.97 KB
SimpleAntlrExpression	20.740 us	1.1015 us	3.2477 us	19.407 us	4	8.7280	13.38 KB
AdvancedParlotExpression	47.157 us	0.9273 us	1.8304 us	46.967 us	5	1.8921	2.97 KB
AdvancedAntlrExpression	71.961 us	5.1478 us	15.1785 us	71.520 us	6	25.1465	38.58 KB

// * Warnings *
MultimodalDistribution
LogicalExpressionFactoryBenchmark.SimpleAntlrExpression: Default -> It seems that the distribution can have several modes (mValue = 2.94)
LogicalExpressionFactoryBenchmark.AdvancedAntlrExpression: Default -> It seems that the distribution is bimodal (mValue = 3.79)
LogicalExpressionFactoryBenchmark.LightParserAdvancedExpression: Default -> It seems that the distribution can have several modes (mValue = 2.89)

@gumbarros, what do you think?

Bykiev · 2025-05-15T17:28:40Z

Bykiev
May 15, 2025
Collaborator Author

Parser code:

using NCalc.Domain;
using NCalc.Exceptions;
using Parlot.Fluent;
using static Parlot.Fluent.Parsers;
using Identifier = NCalc.Domain.Identifier;

namespace NCalc.Parser;

/// <summary>
/// Class responsible for parsing strings into <see cref="LogicalExpression"/> objects.
/// </summary>
public static class LogicalExpressionParser
{
    private static readonly Parser<LogicalExpression> Parser;

    private static readonly ValueExpression True = new(true);
    private static readonly ValueExpression False = new(false);

    private static readonly double MinDecDouble = (double)decimal.MinValue;
    private static readonly double MaxDecDouble = (double)decimal.MaxValue;

    private const string InvalidTokenMessage = "Invalid token in expression";

    static LogicalExpressionParser()
    {
        /*
         * Grammar:
         * expression     => ternary ( ( "-" | "+" ) ternary )* ;
         * ternary        => logical ( "?" logical ":" logical)?
         * logical        => equality ( ( "and" | "or" ) equality )* ;
         * equality       => relational ( ( "=" | "!=" | ... ) relational )* ;
         * relational     => shift ( ( ">=" | ">" | ... ) shift )* ;
         * shift          => additive ( ( "<<" | ">>" ) additive )* ;
         * additive       => multiplicative ( ( "-" | "+" ) multiplicative )* ;
         * multiplicative => exponential ( "/" | "*" | "%") exponential )* ;
         * exponential    => unary ( "**" ) unary )* ;
         * unary          => ( "-" | "not" | "!" ) primary
         *
         * primary        => NUMBER
         *                  | STRING
         *                  | "true"
         *                  | "false"
         *                  | ("[" | "{") anything ("]" | "}")
         *                  | function
         *                  | list
         *                  | "(" expression ")" ;
         *
         * function       => Identifier "(" arguments ")"
         * arguments      => expression ( ("," | ";") expression )*
         */
        // The Deferred helper creates a parser that can be referenced by others before it is defined
        var expression = Deferred<LogicalExpression>();

        var comma = Terms.Char(',');
        var divided = Terms.Text("/");
        var times = Terms.Text("*");
        var modulo = Terms.Text("%");
        var minus = Terms.Text("-");
        var plus = Terms.Text("+");

        var equal = OneOf(Terms.Text("=="), Terms.Text("="));
        var notEqual = OneOf(Terms.Text("<>"), Terms.Text("!="));
        var @in = Terms.Text("in", true);
        var notIn = Terms.Text("not in", true);

        var like = Terms.Text("like", true);
        var notLike = Terms.Text("not like", true);

        var greater = Terms.Text(">");
        var greaterOrEqual = Terms.Text(">=");
        var lesser = Terms.Text("<");
        var lesserOrEqual = Terms.Text("<=");

        var leftShift = Terms.Text("<<");
        var rightShift = Terms.Text(">>");

        var exponent = Terms.Text("**");
        var openParen = Terms.Char('(');
        var closeParen = Terms.Char(')');
        var openBrace = Terms.Char('[');
        var closeBrace = Terms.Char(']');
        var openCurlyBrace = Terms.Char('{');
        var closeCurlyBrace = Terms.Char('}');
        var questionMark = Terms.Char('?');
        var colon = Terms.Char(':');
        var semicolon = Terms.Char(';');

        var identifier = Terms.Identifier();

        var not = OneOf(
            Terms.Text("NOT", true).AndSkip(OneOf(Literals.WhiteSpace().Or(Not(AnyCharBefore(openParen))))),
            Terms.Text("!"));
        var and = OneOf(Terms.Text("AND", true), Terms.Text("&&"));
        var or = OneOf(Terms.Text("OR", true), Terms.Text("||"));

        var bitwiseAnd = Terms.Text("&");
        var bitwiseOr = Terms.Text("|");
        var bitwiseXOr = Terms.Text("^");
        var bitwiseNot = Terms.Text("~");

        // "(" expression ")"
        var groupExpression = Between(openParen, expression, closeParen);

        var braceIdentifier = openBrace
            .SkipAnd(AnyCharBefore(closeBrace, consumeDelimiter: true, failOnEof: true).ElseError("Brace not closed."));

        var curlyBraceIdentifier =
            openCurlyBrace.SkipAnd(AnyCharBefore(closeCurlyBrace, consumeDelimiter: true, failOnEof: true)
                .ElseError("Brace not closed."));

        // ("[" | "{") identifier ("]" | "}")
        var identifierExpression = OneOf(
                braceIdentifier,
                curlyBraceIdentifier,
                identifier)
            .Then<LogicalExpression>(x => new Identifier(x.ToString()!));

        // list => "(" (expression ("," expression)*)? ")"
        var populatedList =
            Between(openParen, Separated(comma.Or(semicolon), expression),
                    closeParen.ElseError("Parenthesis not closed."))
                .Then<LogicalExpression>(values => new LogicalExpressionList(values));

        var emptyList = openParen.AndSkip(closeParen).Then<LogicalExpression>(_ => new LogicalExpressionList());

        var list = OneOf(emptyList, populatedList);

        var function = identifier
            .And(list)
            .Then<LogicalExpression>(static x =>
                new Function(new Identifier(x.Item1.ToString()!), (LogicalExpressionList)x.Item2));

        var booleanTrue = Terms.Text("true", true)
            .Then<LogicalExpression>(True);
        var booleanFalse = Terms.Text("false", true)
            .Then<LogicalExpression>(False);

        var singleQuotesStringValue =
            Terms.String(quotes: StringLiteralQuotes.Single)
                .Then<LogicalExpression>(static (ctx, value) =>
                {
                    if (value.Length == 1 &&
                        ((LogicalExpressionParserContext)ctx).Options.HasFlag(ExpressionOptions.AllowCharValues))
                    {
                        return new ValueExpression(value.Span[0]);
                    }

                    return new ValueExpression(value.ToString());
                });

        var doubleQuotesStringValue =
            Terms
                .String(quotes: StringLiteralQuotes.Double)
                .Then<LogicalExpression>(value => new ValueExpression(value.ToString()!));

        var stringValue = OneOf(singleQuotesStringValue, doubleQuotesStringValue);

        var charIsNumber = Literals.Pattern(char.IsNumber);

        var longNumber = Terms.Number<long>(NumberOptions.Integer)
            .AndSkip(Not(
                OneOf(Terms.Text("."), Terms.Text("E", true), Terms.Text("x"), Terms.Text("b"), Terms.Text("o"))))
            .Then<LogicalExpression>(d => new ValueExpression(d));

        var decimalNumber = Terms.Number<decimal>(NumberOptions.Float)
            .AndSkip(Not(OneOf(Terms.Text("x"), Terms.Text("b"), Terms.Text("o"))))
            .Then<LogicalExpression>(static (ctx, val) => {
                bool useDecimal = ((LogicalExpressionParserContext)ctx).Options.HasFlag(ExpressionOptions.DecimalAsDefault);
                if (useDecimal)
                    return new ValueExpression(val);

                return new ValueExpression((double)val);
            });

        var doubleNumber = Terms.Number<double>(NumberOptions.Float)
            .AndSkip(Not(OneOf(Terms.Text("x"), Terms.Text("b"), Terms.Text("o"))))
            .Then<LogicalExpression>(static (ctx, val) => {
                bool useDecimal = ((LogicalExpressionParserContext)ctx).Options.HasFlag(ExpressionOptions.DecimalAsDefault);
                if (useDecimal)
                {
                    if (val > MaxDecDouble)
                        return new ValueExpression(double.PositiveInfinity);

                    if (val < MinDecDouble)
                        return new ValueExpression(double.NegativeInfinity);

                    return new ValueExpression((decimal)val);
                }

                return new ValueExpression(val);
            });

         var decimalOrDoubleNumber = OneOf(decimalNumber, doubleNumber);

        // primary => GUID | NUMBER | identifier| DateTime | string | function | boolean | groupExpression | list ;
        var primary = OneOf(
            longNumber,
            decimalOrDoubleNumber,
            booleanTrue,
            booleanFalse,
            stringValue,
            function,
            groupExpression,
            identifierExpression,
            list);

        // exponential => unary ( "**" unary )* ;
        var exponential = primary.And(ZeroOrMany(exponent.And(primary)))
            .Then(static x =>
            {
                LogicalExpression result = null!;

                switch (x.Item2.Count)
                {
                    case 0:
                        result = x.Item1;
                        break;
                    case 1:
                        result = new BinaryExpression(BinaryExpressionType.Exponentiation, x.Item1, x.Item2[0].Item2);
                        break;
                    default:
                    {
                        for (int i = x.Item2.Count - 1; i > 0; i--)
                        {
                            result = new BinaryExpression(BinaryExpressionType.Exponentiation, x.Item2[i - 1].Item2,
                                x.Item2[i].Item2);
                        }

                        result = new BinaryExpression(BinaryExpressionType.Exponentiation, x.Item1, result);
                        break;
                    }
                }

                return result;
            });

        // ( "-" | "not" ) unary | primary;
        var unary = exponential.Unary(
            (not, static value => new UnaryExpression(UnaryExpressionType.Not, value)),
            (minus, static value => new UnaryExpression(UnaryExpressionType.Negate, value)),
            (bitwiseNot, static value => new UnaryExpression(UnaryExpressionType.BitwiseNot, value))
        );

        // multiplicative => unary ( ( "/" | "*" | "%" ) unary )* ;
        var multiplicative = unary.LeftAssociative(
            (divided, static (a, b) => new BinaryExpression(BinaryExpressionType.Div, a, b)),
            (times, static (a, b) => new BinaryExpression(BinaryExpressionType.Times, a, b)),
            (modulo, static (a, b) => new BinaryExpression(BinaryExpressionType.Modulo, a, b))
        );

        // additive => multiplicative ( ( "-" | "+" ) multiplicative )* ;
        var additive = multiplicative.LeftAssociative(
            (plus, static (a, b) => new BinaryExpression(BinaryExpressionType.Plus, a, b)),
            (minus, static (a, b) => new BinaryExpression(BinaryExpressionType.Minus, a, b))
        );

        // shift => additive ( ( "<<" | ">>" ) additive )* ;
        var shift = additive.LeftAssociative(
            (leftShift, static (a, b) => new BinaryExpression(BinaryExpressionType.LeftShift, a, b)),
            (rightShift, static (a, b) => new BinaryExpression(BinaryExpressionType.RightShift, a, b))
        );

        // relational => shift ( ( ">=" | "<=" | "<" | ">" | "in" | "not in" ) shift )* ;
        var relational = shift.And(ZeroOrMany(OneOf(
                    greaterOrEqual.Then(BinaryExpressionType.GreaterOrEqual),
                    lesserOrEqual.Then(BinaryExpressionType.LesserOrEqual),
                    lesser.Then(BinaryExpressionType.Lesser),
                    greater.Then(BinaryExpressionType.Greater),
                    @in.Then(BinaryExpressionType.In),
                    notIn.Then(BinaryExpressionType.NotIn),
                    like.Then(BinaryExpressionType.Like),
                    notLike.Then(BinaryExpressionType.NotLike)
                )
                .And(shift)))
            .Then(ParseBinaryExpression);

        var equality = relational.And(ZeroOrMany(OneOf(
                    equal.Then(BinaryExpressionType.Equal),
                    notEqual.Then(BinaryExpressionType.NotEqual))
                .And(relational)))
            .Then(ParseBinaryExpression);

        var andTypeParser = and.Then(BinaryExpressionType.And)
            .Or(bitwiseAnd.Then(BinaryExpressionType.BitwiseAnd));

        var orTypeParser = or.Then(BinaryExpressionType.Or)
            .Or(bitwiseOr.Then(BinaryExpressionType.BitwiseOr));

        var xorTypeParser = bitwiseXOr.Then(BinaryExpressionType.BitwiseXOr);

        // "and" has higher precedence than "or"
        var andParser = equality.And(ZeroOrMany(andTypeParser.And(equality)))
            .Then(ParseBinaryExpression);

        var orParser = andParser.And(ZeroOrMany(orTypeParser.And(andParser)))
            .Then(ParseBinaryExpression);

        // logical => equality ( ( "and" | "or" | "xor" ) equality )* ;
        var logical = orParser.And(ZeroOrMany(xorTypeParser.And(orParser)))
            .Then(ParseBinaryExpression);

        // ternary => logical("?" logical ":" logical) ?
        var ternary = logical.And(ZeroOrOne(questionMark.SkipAnd(logical).AndSkip(colon).And(logical)))
            .Then(static x => x.Item2.Item1 == null
                ? x.Item1
                : new TernaryExpression(x.Item1, x.Item2.Item1, x.Item2.Item2))
            .Or(logical);

        var operatorSequence = ternary.LeftAssociative(
            (OneOrMany(OneOf(
                    divided, times, modulo, plus,
                    minus, leftShift, rightShift, greaterOrEqual,
                    lesserOrEqual, greater, lesser, equal,
                    notEqual)),
                static (_, _) => throw new InvalidOperationException("Unknown operator sequence.")));

        expression.Parser = operatorSequence;
        var expressionParser = expression.AndSkip(ZeroOrMany(Literals.WhiteSpace(true))).Eof()
            .ElseError(InvalidTokenMessage);

        AppContext.TryGetSwitch("NCalc.EnableParlotParserCompilation", out var enableParserCompilation);

        Parser = enableParserCompilation ? expressionParser.Compile() : expressionParser;
    }

    private static LogicalExpression ParseBinaryExpression((LogicalExpression, IReadOnlyList<(BinaryExpressionType, LogicalExpression)>) x)
    {
        var result = x.Item1;

        foreach (var op in x.Item2)
        {
            result = new BinaryExpression(op.Item1, result, op.Item2);
        }

        return result;
    }

    public static LogicalExpression Parse(LogicalExpressionParserContext context)
    {
        if (Parser.TryParse(context, out var result, out var error))
            return result;

        string message;
        if (error != null)
            message = $"{error.Message} at position {error.Position}";
        else
            message = $"Error parsing the expression at position {context.Scanner.Cursor.Position}";

        throw new NCalcParserException(message);
    }
}

0 replies

Bykiev · 2025-05-20T06:50:28Z

Bykiev
May 20, 2025
Collaborator Author

@gumbarros, @yallie, any feedback on this?

0 replies

Bykiev · 2025-05-21T16:16:30Z

Bykiev
May 21, 2025
Collaborator Author

Or even make a breaking change and move advanced parsers into NCalc.AdvancedParser plugin

0 replies

emayevski · 2025-06-01T18:40:50Z

emayevski
Jun 1, 2025

@Bykiev
What do you want to exclude? It may be easier and even more flexible to enable and disable individual features like dates or guids via the ExpressionOptions enum.

0 replies

Bykiev · 2025-06-02T05:05:11Z

Bykiev
Jun 2, 2025
Collaborator Author

@emayevski, ExpressionsOptions can't be used in parser, which is defined in a static constructor. If we'll use none-static constructor the performance will be worse and compiled parser will be not working as expected

6 replies

Bykiev Jun 2, 2025
Collaborator Author

@emayevski , agreed, with static constructor it will recieve ExpressionOptions only once, let's benchmark your solution. But I stands for AdvancedParser plugin, parsing dates, guids should be advanced feature

emayevski Jun 2, 2025

@emayevski , agreed, with static constructor it will recieve ExpressionOptions only once, let's benchmark your solution. But I stands for AdvancedParser plugin, parsing dates, guids should be advanced feature

@Bykiev
The main problem with the advanced plugin is that it will have to duplicate the current code that creates parser elements, and with a static constructor (or any static initialization function), a plugin cannot amend the created parser list. I.e., I see how the code can be refactored to make it possible to support different layers, but it requires a virtual function to be available, and thus, either an instance constructor, or an instance initialization method.

With my idea, one would be able to create different parsers and include/exclude elements by overwriting simple functions, individual for each type of parser element (e.g., a CreateDateParsers function, which would return zero or more parsers for date and time, CreateNumberParsers, and so on).

Bykiev Jun 2, 2025
Collaborator Author

I don't see any issues with code duplication (we have some code duplication between sync/async libs too). Let's see and benchmark your solution.

emayevski Jun 2, 2025

I don't see any issues with code duplication (we have some code duplication between sync/async libs too). Let's see and benchmark your solution.

The effect of duplication in this specific case can be significant - if there is some change/addition in the basic code (similar to the changes I am making), one will have to track and update the plugin code. Still, I agree that having separate parsers as replacements for the main one may lead to easier acceptance of the required changes to the main branch.

Bykiev Jun 2, 2025
Collaborator Author

If the main parser will handle strings and numbers only, I don't expect any changes in main parser. Also if we need additional parsers or fix existing, we can publish only plugin changes (not sure if this is possible with existing build infrastructure)

Uh oh!

Uh oh!

LightParser plugin #417

Uh oh!

Uh oh!

Bykiev May 15, 2025 Collaborator

Replies: 5 comments · 6 replies

Uh oh!

Bykiev May 15, 2025 Collaborator Author

Uh oh!

Bykiev May 20, 2025 Collaborator Author

Uh oh!

Bykiev May 21, 2025 Collaborator Author

Uh oh!

emayevski Jun 1, 2025

Uh oh!

Bykiev Jun 2, 2025 Collaborator Author

Uh oh!

Bykiev Jun 2, 2025 Collaborator Author

Uh oh!

emayevski Jun 2, 2025

Uh oh!

Bykiev Jun 2, 2025 Collaborator Author

Uh oh!

emayevski Jun 2, 2025

Uh oh!

Bykiev Jun 2, 2025 Collaborator Author

Bykiev
May 15, 2025
Collaborator

Replies: 5 comments 6 replies

Bykiev
May 15, 2025
Collaborator Author

Bykiev
May 20, 2025
Collaborator Author

Bykiev
May 21, 2025
Collaborator Author

emayevski
Jun 1, 2025

Bykiev
Jun 2, 2025
Collaborator Author

Bykiev Jun 2, 2025
Collaborator Author

Bykiev Jun 2, 2025
Collaborator Author

Bykiev Jun 2, 2025
Collaborator Author