使用 ANTLR 的嵌套布尔表达式解析器
Nested Boolean Expression Parser using ANTLR
我正在尝试解析嵌套布尔表达式并分别获取表达式中的各个条件。例如,如果输入字符串是:
(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 中以正确的顺序解析字符串吗?
我只是将所有表达式包装到一个 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
@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");
}
我正在尝试解析嵌套布尔表达式并分别获取表达式中的各个条件。例如,如果输入字符串是:
(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 中以正确的顺序解析字符串吗?
我只是将所有表达式包装到一个 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
@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");
}