使用 ANTLR 的嵌套布尔表达式解析器

Question

我正在尝试解析嵌套布尔表达式并分别获取表达式中的各个条件。例如，如果输入字符串是：

(A = a OR B = b OR C = c AND ((D = d AND E = e) OR (F = f AND G = g)))

我想以正确的顺序获取条件。即，

D =d 和 E = e 要么 F = f 和 G = g 和 A = a 或 B = b 或 C = c

我正在使用 ANTLR 4 来解析输入文本，这是我的语法：

grammar SimpleBoolean;

rule_set : nestedCondition* EOF;

AND : 'AND' ;
OR  : 'OR' ;
NOT : 'NOT';

TRUE  : 'TRUE' ;
FALSE : 'FALSE' ;

GT : '>' ;
GE : '>=' ;
LT : '<' ;
LE : '<=' ;
EQ : '=' ;

LPAREN : '(' ;
RPAREN : ')' ;

DECIMAL : '-'?[0-9]+('.'[0-9]+)? ;

IDENTIFIER : [a-zA-Z_][a-zA-Z_0-9]* ;

WS : [ \r\t\u000C\n]+ -> skip;

nestedCondition : LPAREN condition+ RPAREN (binary nestedCondition)*;
condition: predicate (binary predicate)*
            | predicate (binary component)*;
component: predicate | multiAttrComp;
multiAttrComp : LPAREN predicate (and predicate)+ RPAREN;
predicate : IDENTIFIER comparator IDENTIFIER;
comparator : GT | GE | LT | LE | EQ ;
binary: AND | OR ;
unary: NOT;
and: AND;

这是我用来解析它的 Java 代码：

ANTLRInputStream inputStr = new ANTLRInputStream(input);
SimpleBooleanLexer lexer = new SimpleBooleanLexer(inputStr);
TokenStream tokens = new CommonTokenStream(lexer);
SimpleBooleanParser parser = new SimpleBooleanParser(tokens);
parser.getBuildParseTree();
ParseTree tree = parser.rule_set();
System.out.println(tree.toStringTree(parser));

输出为：

(rule_set (nestedCondition ( (condition (predicate A (comparator =) a) (binary OR) (component (predicate B (comparator =) b)) (binary OR) (component (predicate C (comparator =) c)) (binary AND) (component (multiAttrComp ( (predicate ( D (comparator =) d) (and AND) (predicate E (comparator =) e) ))) (binary OR) (component (multiAttrComp ( (predicate F (comparator =) f) (and AND) (predicate G (comparator =) g) )))) ) )) <EOF>)

我正在寻求有关如何解析此树以按正确顺序获取条件的帮助？在 ANTLR 3 中，我们可以指定 ^ 和 !决定如何构建树（参考这个 thread），但我了解到 ANTLR 4 不支持它。

有人可以建议我如何使用 ANTLR 创建的 ParseTree 在 Java 中以正确的顺序解析字符串吗？

Answer 1

我只是将所有表达式包装到一个 expression 规则中。请务必在 之前定义 comparator 表达式替代项 您的 binary 表达式替代项以确保 comparator 运算符比 OR 绑定得更紧密并且AND:

grammar SimpleBoolean;

parse
 : expression EOF
 ;

expression
 : LPAREN expression RPAREN                       #parenExpression
 | NOT expression                                 #notExpression
 | left=expression op=comparator right=expression #comparatorExpression
 | left=expression op=binary right=expression     #binaryExpression
 | bool                                           #boolExpression
 | IDENTIFIER                                     #identifierExpression
 | DECIMAL                                        #decimalExpression
 ;

comparator
 : GT | GE | LT | LE | EQ
 ;

binary
 : AND | OR
 ;

bool
 : TRUE | FALSE
 ;

AND        : 'AND' ;
OR         : 'OR' ;
NOT        : 'NOT';
TRUE       : 'TRUE' ;
FALSE      : 'FALSE' ;
GT         : '>' ;
GE         : '>=' ;
LT         : '<' ;
LE         : '<=' ;
EQ         : '=' ;
LPAREN     : '(' ;
RPAREN     : ')' ;
DECIMAL    : '-'? [0-9]+ ( '.' [0-9]+ )? ;
IDENTIFIER : [a-zA-Z_] [a-zA-Z_0-9]* ;
WS         : [ \r\t\u000C\n]+ -> skip;

要测试上面的语法，请使用以下快速测试 classes:

public class Main {

  public static void main(String[] args) throws Exception {

    Map<String, Object> variables = new HashMap<String, Object>() {{
      put("A", true);
      put("a", true);
      put("B", false);
      put("b", false);
      put("C", 42.0);
      put("c", 42.0);
      put("D", -999.0);
      put("d", -1999.0);
      put("E", 42.001);
      put("e", 142.001);
      put("F", 42.001);
      put("f", 42.001);
      put("G", -1.0);
      put("g", -1.0);
    }};

    String[] expressions = {
        "1 > 2",
        "1 >= 1.0",
        "TRUE = FALSE",
        "FALSE = FALSE",
        "A OR B",
        "B",
        "A = B",
        "c = C",
        "E > D",
        "B OR (c = B OR (A = A AND c = C AND E > D))",
        "(A = a OR B = b OR C = c AND ((D = d AND E = e) OR (F = f AND G = g)))"
    };

    for (String expression : expressions) {
      SimpleBooleanLexer lexer = new SimpleBooleanLexer(new ANTLRInputStream(expression));
      SimpleBooleanParser parser = new SimpleBooleanParser(new CommonTokenStream(lexer));
      Object result = new EvalVisitor(variables).visit(parser.parse());
      System.out.printf("%-70s -> %s\n", expression, result);
    }
  }
}

class EvalVisitor extends SimpleBooleanBaseVisitor<Object> {

  private final Map<String, Object> variables;

  public EvalVisitor(Map<String, Object> variables) {
    this.variables = variables;
  }

  @Override
  public Object visitParse(SimpleBooleanParser.ParseContext ctx) {
    return super.visit(ctx.expression());
  }

  @Override
  public Object visitDecimalExpression(SimpleBooleanParser.DecimalExpressionContext ctx) {
    return Double.valueOf(ctx.DECIMAL().getText());
  }

  @Override
  public Object visitIdentifierExpression(SimpleBooleanParser.IdentifierExpressionContext ctx) {
    return variables.get(ctx.IDENTIFIER().getText());
  }

  @Override
  public Object visitNotExpression(SimpleBooleanParser.NotExpressionContext ctx) {
    return !((Boolean)this.visit(ctx.expression()));
  }

  @Override
  public Object visitParenExpression(SimpleBooleanParser.ParenExpressionContext ctx) {
    return super.visit(ctx.expression());
  }

  @Override
  public Object visitComparatorExpression(SimpleBooleanParser.ComparatorExpressionContext ctx) {
    if (ctx.op.EQ() != null) {
      return this.visit(ctx.left).equals(this.visit(ctx.right));
    }
    else if (ctx.op.LE() != null) {
      return asDouble(ctx.left) <= asDouble(ctx.right);
    }
    else if (ctx.op.GE() != null) {
      return asDouble(ctx.left) >= asDouble(ctx.right);
    }
    else if (ctx.op.LT() != null) {
      return asDouble(ctx.left) < asDouble(ctx.right);
    }
    else if (ctx.op.GT() != null) {
      return asDouble(ctx.left) > asDouble(ctx.right);
    }
    throw new RuntimeException("not implemented: comparator operator " + ctx.op.getText());
  }

  @Override
  public Object visitBinaryExpression(SimpleBooleanParser.BinaryExpressionContext ctx) {
    if (ctx.op.AND() != null) {
      return asBoolean(ctx.left) && asBoolean(ctx.right);
    }
    else if (ctx.op.OR() != null) {
      return asBoolean(ctx.left) || asBoolean(ctx.right);
    }
    throw new RuntimeException("not implemented: binary operator " + ctx.op.getText());
  }

  @Override
  public Object visitBoolExpression(SimpleBooleanParser.BoolExpressionContext ctx) {
    return Boolean.valueOf(ctx.getText());
  }

  private boolean asBoolean(SimpleBooleanParser.ExpressionContext ctx) {
    return (boolean)visit(ctx);
  }

  private double asDouble(SimpleBooleanParser.ExpressionContext ctx) {
    return (double)visit(ctx);
  }
}

运行 Main class 将导致以下输出：

1 > 2                                                                  -> false
1 >= 1.0                                                               -> true
TRUE = FALSE                                                           -> false
FALSE = FALSE                                                          -> true
A OR B                                                                 -> true
B                                                                      -> false
A = B                                                                  -> false
c = C                                                                  -> true
E > D                                                                  -> true
B OR (c = B OR (A = A AND c = C AND E > D))                            -> true
(A = a OR B = b OR C = c AND ((D = d AND E = e) OR (F = f AND G = g))) -> true

Answer 2

@Bart Kiers 的 C# 等价物：

EvalVistor.cs:

public class EvalVisitor : NOABaseVisitor<object> {
    private readonly Dictionary<string, object> variables = new();


    public EvalVisitor(Dictionary<string, object> variables)
    {
        this.variables = variables;
    }

    public override object VisitParse([NotNull] NOAParser.ParseContext context)
    {
        return base.Visit(context.expression());
    }

    public override object VisitDecimalExpression([NotNull] NOAParser.DecimalExpressionContext context)
    {
        return Double.Parse(context.DECIMAL().GetText());
    }

    public override object VisitIdentifierExpression([NotNull] NOAParser.IdentifierExpressionContext context)
    {
        return variables[context.IDENTIFIER().GetText()];
    }

    public override object VisitNotExpression([NotNull] NOAParser.NotExpressionContext context)
    {
        return !((bool)this.Visit(context.expression()));
    }

    public override object VisitParenExpression([NotNull] NOAParser.ParenExpressionContext context)
    {
        return base.Visit(context.expression());
    }

    public override object VisitComparatorExpression([NotNull] NOAParser.ComparatorExpressionContext context)
    {
        if (context.op.EQ() != null)
        {
            return this.Visit(context.left).Equals(this.Visit(context.right));
        }
        else if (context.op.LE() != null)
        {
            return AsDouble(context.left) <= AsDouble(context.right);
        }
        else if (context.op.GE() != null)
        {
            return AsDouble(context.left) >= AsDouble(context.right);
        }
        else if (context.op.LT() != null)
        {
            return AsDouble(context.left) < AsDouble(context.right);
        }
        else if (context.op.GT() != null)
        {
            return AsDouble(context.left) > AsDouble(context.right);
        }
        throw new ApplicationException("not implemented: comparator operator " + context.op.GetText());
    }

    public override object VisitBinaryExpression([NotNull] NOAParser.BinaryExpressionContext context)
    {
        if (context.op.AND() != null)
        {
            return AsBool(context.left) && AsBool(context.right);
        }
        else if (context.op.OR() != null)
        {
            return AsBool(context.left) || AsBool(context.right);
        }
        throw new ApplicationException("not implemented: binary operator " + context.op.GetText());
    }

    public override object VisitBoolExpression([NotNull] NOAParser.BoolExpressionContext context)
    {
        return bool.Parse(context.GetText());
    }

    private bool AsBool(NOAParser.ExpressionContext context)
    {
        return (bool)Visit(context);
    }

    private double AsDouble(NOAParser.ExpressionContext context)
    {
        return (double)Visit(context);
    }
}

Program.cs:

Dictionary<string, object> variables = new()
{
    {"a", true },
    {"A", true },
    {"B", false },
    {"b", false },
    {"C", 42.0 },
    {"c", 42.0 },
    {"D", -999.0 },
    {"d", -1999.0 },
    {"E", 42.001 },
    {"e", 142.001 },
    {"F", 42.001 },
    {"f", 42.001 },
    {"G", -1.0 },
    { "g", -1.0 },
};

string[] expressions =
{
    "1 > 2",
    "1 >= 1.0",
    "TRUE = FALSE",
    "FALSE = FALSE",
    "A OR B",
    "B",
    "A = B",
    "c = C",
    "E > D",
    "B OR (c = B OR (A = A AND c = C AND E > D))",
    "(A = a OR B = b OR C = c AND ((D = d AND E = e) OR (F = f AND G = g)))"
};

foreach (var expression in expressions)
{
    NOALexer lexer = new (new AntlrInputStream(expression));
    NOAParser parser = new (new CommonTokenStream(lexer));
    Object result = new EvalVisitor(variables).Visit(parser.parse());
    Console.WriteLine($"{expression} - {result}\n");
}

使用 ANTLR 的嵌套布尔表达式解析器

Nested Boolean Expression Parser using ANTLR

java

parsing

antlr

antlr3

antlr4