Evaluating logical expressions recognized by ANTLR using the System.Linq.Expressions namespace

Question

I've defined a grammar, which I have to parse in C# and evaluate the resulted "constraints" on a list of dictionaries. The grammar is mainly boolean algebra.

Here you can check it:

grammar Constraint;

expr
    :   implyExpr
    ;

implyExpr
    :   orExpr
    |   leftOp=orExpr IMPLY rightOp=orExpr
    ;
    
orExpr
    :   andExpr
    |   leftOp=andExpr OR rightOp=andExpr
    ;
    
andExpr
    :   primaryExpr
    |   leftOp=primaryExpr AND rightOp=primaryExpr
    ;
    
primaryExpr
    :   trueExpr
    |   falseExpr
    |   parenExpr
    |   notParenExpr
    |   statement
    ;
    
trueExpr
    :   TRUE
    ;
    
falseExpr
    :   FALSE
    ;
    
parenExpr
    :   LPAREN expr RPAREN
    ;
    
notParenExpr
    :   NOT LPAREN expr RPAREN
    ;
    
statement
    :   eqValStatement
    |   notEqValStatement
    |   inListStatement
    |   notInListStatement
    ;
    
eqValStatement
    :   key=STR EQ value=val
    ;
    
notEqValStatement
    :   key=STR NEQ value=val
    ;
    
inListStatement
    :   key=STR EQ list=lst
    ;
    
notInListStatement
    :   key=STR NEQ list=lst
    ;

lst
    :   LBRACK values+=val (COMMA values+=val)* RBRACK
    ;

val
    :   strVal
    |   nullVal
    ;

strVal
    :   value=STR
    ;
    
nullVal
    :   NULL
    ;

// Lexer

IMPLY:  '->';
OR:     '|';
AND:    '&';
TRUE:   'true';
FALSE:  'false';
LPAREN: '(';
RPAREN: ')';
NOT:    '!';
EQ:     '=';
NEQ:    '!=';
LBRACK: '[';
RBRACK: ']';
COMMA:  ',';
NULL:   'null';
STR: [a-zA-Z0-9-_]+;
WS: [ \t\n\r]+ -> skip;

My question is that could I use this namespace for my goal or shall I use different delegates, which would take 2 delegates as parameters and would return with a bool value according to the implemented behaviour?

I'm still at the design phase, what I've done already is the grammar definition and generating the listenerbase class for it.

Answer 1

I solved the problem by using delegates in the end. I generated a Predicate for each expression and combined them together. I've also integrated the recognition of the grammar into the listener class, in this way providing a simple interface for getting a predicate from an expression.

Here's the most of it:

public class ConstraintEvaluator : ConstraintBaseListener
{
    
    public Predicate<List<ConfigurationItemHeader>>? Evaluate(string input)
    {
        _exprStack.Clear();
        _strStack.Clear();
        
        var stream = CharStreams.fromString(input);
        ITokenSource lexer = new ConstraintLexer(stream);
        ITokenStream tokens = new CommonTokenStream(lexer);
        ConstraintParser parser = new(tokens);
        IParseTree tree = parser.expr();
        ParseTreeWalker.Default.Walk(this, tree);
        return Result;
    }

    private Predicate<List<ConfigurationItemHeader>>? Result { get; set; }
    
    private readonly Stack<Predicate<List<ConfigurationItemHeader>>> _exprStack = new();
    private readonly Stack<string?> _strStack = new();
    
    private static Predicate<List<ConfigurationItemHeader>> ImplicationFactory(Predicate<List<ConfigurationItemHeader>> left, Predicate<List<ConfigurationItemHeader>> right)
    {
        return config => !left(config) || right(config);
    }
    
    private static Predicate<List<ConfigurationItemHeader>> OrFactory(Predicate<List<ConfigurationItemHeader>> left, Predicate<List<ConfigurationItemHeader>> right)
    {
        return config => left(config) || right(config);
    }
    
    private static Predicate<List<ConfigurationItemHeader>> AndFactory(Predicate<List<ConfigurationItemHeader>> left, Predicate<List<ConfigurationItemHeader>> right)
    {
        return config => left(config) && right(config);
    }
    
    private static Predicate<List<ConfigurationItemHeader>> NotFactory(Predicate<List<ConfigurationItemHeader>> expr)
    {
        return config => !expr(config);
    }
    
    private static Predicate<List<ConfigurationItemHeader>> EqValFactory(string key, string? value)
    {
        return config =>
        {
            if (config.All(x => x.Key != key))
            {
                throw new ArgumentException(KeyNotFoundError(key));
            }
            return config.Find(x => x.Key == key)?.Value == value;
        };
    }
    
    private static Predicate<List<ConfigurationItemHeader>> NotEqValFactory(string key, string? value)
    {
        return config =>
        {
            if (value == null)
            {
                return config.All(x => x.Key != key);
            }
            if (config.All(x => x.Key != key))
            {
                throw new ArgumentException(KeyNotFoundError(key));
            }
            return config.Find(x => x.Key == key)?.Value != value;
        };
    }
    
    private static Predicate<List<ConfigurationItemHeader>> InListFactory(string key, List<string?> values)
    {
        return config =>
        {
            if (config.All(x => x.Key != key))
            {
                throw new ArgumentException(KeyNotFoundError(key));
            }
            // if x.Value is null, it means that it is a flag and the values list should contain the null value too,
            // to allow the flag to be set (usually the flag shouldn't be allowed to have any other value, than null)
            return values.Contains(config.Find(x => x.Key == key)?.Value);
        };
    }
    
    private static Predicate<List<ConfigurationItemHeader>> NotInListFactory(string key, List<string?> values)
    {
        return config =>
        {
            if (config.All(x => x.Key != key))
            {
                throw new ArgumentException(KeyNotFoundError(key));
            }
            return !values.Contains(config.Find(x => x.Key == key)?.Value);
        };
    }
    
    private static Predicate<List<ConfigurationItemHeader>> FalseFactory()
    {
        return _ => false;
    }
    
    private static Predicate<List<ConfigurationItemHeader>> TrueFactory()
    {
        return _ => true;
    }
    
    private static string StackNotEmptyError(string stackName, string methodName)
    {
        return $"{stackName} is not empty after {methodName}!";
    }
    
    private static string KeyNotFoundError(string key)
    {
        return $"Key <{key}> not found in config!";
    }
    
    public override void ExitExpr(ConstraintParser.ExprContext context)
    {
        Result = _exprStack.Peek();
    }
    
    public override void ExitImplyExpr(ConstraintParser.ImplyExprContext context)
    {
        if (context.leftOp == null || context.rightOp == null) return;
        var right = _exprStack.Pop();
        var left = _exprStack.Pop();
        if (_exprStack.Count > 0)
        {
            throw new ApplicationException(StackNotEmptyError(nameof(_exprStack), nameof(ExitImplyExpr)));
        }

        _exprStack.Push(ImplicationFactory(left, right));
    }
    
    public override void ExitOrExpr(ConstraintParser.OrExprContext context)
    {
        if (context.leftOp == null || context.rightOp == null) return;
        var right = _exprStack.Pop();
        var left = _exprStack.Pop();
        if (_exprStack.Count > 0)
        {
            throw new ApplicationException(StackNotEmptyError(nameof(_exprStack), nameof(ExitOrExpr)));
        }
        _exprStack.Push(OrFactory(left, right));
    }
    
    public override void ExitAndExpr(ConstraintParser.AndExprContext context)
    {
        if (context.leftOp == null || context.rightOp == null) return;
        var right = _exprStack.Pop();
        var left = _exprStack.Pop();
        if (_exprStack.Count > 0)
        {
            throw new ApplicationException(StackNotEmptyError(nameof(_exprStack), nameof(ExitAndExpr)));
        }
        _exprStack.Push(AndFactory(left, right));
    }
    
    public override void ExitTrueExpr(ConstraintParser.TrueExprContext context)
    {
        _exprStack.Push(TrueFactory());
    }
    
    public override void ExitFalseExpr(ConstraintParser.FalseExprContext context)
    {
        _exprStack.Push(FalseFactory());
    }
    
    public override void ExitNotParenExpr(ConstraintParser.NotParenExprContext context)
    {
        var expr = _exprStack.Pop();
        if (_exprStack.Count > 0)
        {
            throw new ApplicationException(StackNotEmptyError(nameof(_exprStack), nameof(ExitNotParenExpr)));
        }
        _exprStack.Push(NotFactory(expr));
    }
    
    public override void ExitEqValStatement(ConstraintParser.EqValStatementContext context)
    {
        var key = context.key.Text;
        var value = _strStack.Pop();
        if (_strStack.Count > 0)
        {
            throw new ApplicationException(StackNotEmptyError(nameof(_strStack), nameof(ExitEqValStatement)));
        }
        _exprStack.Push(EqValFactory(key, value));
    }
    
    public override void ExitNotEqValStatement(ConstraintParser.NotEqValStatementContext context)
    {
        var key = context.key.Text;
        var value = _strStack.Pop();
        if (_strStack.Count > 0)
        {
            throw new ApplicationException(StackNotEmptyError(nameof(_strStack),nameof(ExitNotEqValStatement)));
        }
        _exprStack.Push(NotEqValFactory(key, value));
    }
    
    public override void ExitInListStatement(ConstraintParser.InListStatementContext context)
    {
        var key = context.key.Text;
        var values = _strStack.ToList();
        _strStack.Clear();
        _exprStack.Push(InListFactory(key, values));
    }
    
    public override void ExitNotInListStatement(ConstraintParser.NotInListStatementContext context)
    {
        var key = context.key.Text;
        var values = _strStack.ToList();
        _strStack.Clear();
        _exprStack.Push(NotInListFactory(key, values));
    }
    
    public override void ExitStrVal(ConstraintParser.StrValContext context)
    {
        _strStack.Push(context.value.Text);
    }
    
    public override void ExitNullVal(ConstraintParser.NullValContext context)
    {
        _strStack.Push(null);
    }
}

In the end I used List of ConfigurationItems, which have Key and Value properties, bc. of the domain requirements of my application.

Answer 2

I'd simple extend the visitor generated by ANTLR (you'd need to add the -visitor parameter when generating the parser classes). That could look like this:

public class ConstraintEvalVisitor : ConstraintBaseVisitor<object?>
{
  // eval
  //  : expr EOF
  //  ;
  public override object? VisitEval(ConstraintParser.EvalContext context)
    => this.Visit(context.expr());

  public override object? VisitExpr(ConstraintParser.ExprContext context)
    => this.Visit(context.implyExpr());

  public override object? VisitImplyExpr(ConstraintParser.ImplyExprContext context)
  {
    if (context.IMPLY() == null)
    {
      return this.Visit(context.orExpr().Single());
    }

    var lhs = this.Visit(context.leftOp) as bool?;
    var rhs = this.Visit(context.rightOp) as bool?;

    return lhs!.Value ? rhs! : true;
  }

  public override object? VisitOrExpr(ConstraintParser.OrExprContext context)
  {
    if (context.OR() == null)
    {
      return this.Visit(context.andExpr().Single());
    }

    var lhs = this.Visit(context.leftOp) as bool?;
    var rhs = this.Visit(context.rightOp) as bool?;

    return lhs!.Value || rhs!.Value;
  }

  public override object? VisitAndExpr(ConstraintParser.AndExprContext context)
  {
    if (context.AND() == null)
    {
      return this.Visit(context.primaryExpr().Single());
    }

    var lhs = this.Visit(context.leftOp) as bool?;
    var rhs = this.Visit(context.rightOp) as bool?;

    return lhs!.Value && rhs!.Value;
  }

  public override object? VisitPrimaryExpr(ConstraintParser.PrimaryExprContext context)
  {
    if (context.trueExpr() != null)
      return true;

    if (context.falseExpr() != null)
      return false;

    if (context.parenExpr() != null)
      return this.Visit(context.parenExpr().expr());

    if (context.notParenExpr() != null)
      return this.Visit(context.notParenExpr());

    return this.Visit(context.statement());
  }

  public override object? VisitNotParenExpr(ConstraintParser.NotParenExprContext context)
    => this.Visit(context.expr()) as bool?;

  public override object? VisitStatement(ConstraintParser.StatementContext context)
  {
    if (context.eqValStatement() != null)
      return this.Visit(context.eqValStatement());

    if (context.notEqValStatement() != null)
      return this.Visit(context.notEqValStatement());

    if (context.inListStatement() != null)
      return this.Visit(context.inListStatement());

    return this.Visit(context.notInListStatement());
  }

  public override object? VisitEqValStatement(ConstraintParser.EqValStatementContext context)
  {
    var lhs = context.STR().GetText();
    var rhs = this.Visit(context.val()) as string;

    return lhs.Equals(rhs);
  }

  public override object? VisitNotEqValStatement(ConstraintParser.NotEqValStatementContext context)
  {
    var lhs = context.STR().GetText();
    var rhs = this.Visit(context.val()) as string;

    return !lhs.Equals(rhs);
  }

  public override object? VisitInListStatement(ConstraintParser.InListStatementContext context)
  {
    var lhs = context.STR().GetText();
    var rhs = this.Visit(context.lst()) as List<object?>;

    return rhs!.Contains(lhs);
  }

  public override object? VisitNotInListStatement(ConstraintParser.NotInListStatementContext context)
  {
    var lhs = context.STR().GetText();
    var rhs = this.Visit(context.lst()) as List<object?>;

    return !rhs!.Contains(lhs);
  }

  public override object? VisitVal(ConstraintParser.ValContext context)
    => context.strVal() == null ? null : context.strVal().STR().GetText();

  public override object? VisitLst(ConstraintParser.LstContext context)
    => context._values.Select(this.Visit).ToList();
}

It can be tested like this:

Evaluate("true -> true");
Evaluate("true -> false");
Evaluate("false -> true");
Evaluate("false -> false");
Evaluate("false | false");
Evaluate("false | true");
Evaluate("true & false");
Evaluate("true & true");
Evaluate("(true) & true");
Evaluate("A = A");
Evaluate("A = B");
Evaluate("A != A");
Evaluate("A != B");
Evaluate("B = [A, B]");
Evaluate("A = [B, C, D]");

static void Evaluate(string expression)
{
  var lexer = new ConstraintLexer(CharStreams.fromString(expression));
  var parser = new ConstraintParser(new CommonTokenStream(lexer));
  var answer = new ConstraintEvalVisitor().Visit(parser.eval());

  Console.WriteLine($"{expression,-20}{answer}");
}

which will print:

true -> true        True
true -> false       False
false -> true       True
false -> false      True
false | false       False
false | true        True
true & false        False
true & true         True
(true) & true       True
A = A               True
A = B               False
A != A              False
A != B              True
B = [A, B]          True
A = [B, C, D]       False