Analizzatore dell'espressione booleana annidato che utilizza ANTLR

Question

Sto cercando di analizzare un'espressione booleana annidata e ottenere separatamente le singole condizioni all'interno dell'espressione. Per esempio, se la stringa di input è:

(A = A o B = B o C = C e ((D = D ed E = e) OR (F = F e G = g)))

Vorrei ottenere le condizioni con l'ordine corretto. Per esempio,

D = D ed E = e OR F = F e G = g E A = A o B = B o C = c

sto usando ANTLR 4 per analizzare la testo di input ed ecco la mia grammatica:

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; 

ed ecco il codice Java che sto usando per analizzarlo:

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)); 

UO tput è:

(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>) 

sto cercando aiuto su come analizzare questo albero per ottenere le condizioni nell'ordine corretto? In ANTLR 3, potremmo specificare^e! per decidere come viene costruito l'albero (fare riferimento a questo thread), ma ho appreso che non è supportato in ANTLR 4.

Qualcuno può suggerire come posso analizzare la stringa nell'ordine corretto in Java utilizzando il ParseTree creato da ANTLR ?

Answer 1

Vorrei semplicemente racchiudere tutte le espressioni in una singola regola expression. Assicurati di definire le comparator espressioni alternative prima vostra alternativa binary espressione per assicurarsi che comparator operatori legano più strettamente di OR e 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; 

Per testare la grammatica sopra, utilizzare il seguente test rapido-and-dirty classi:

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); 
    } 
} 

in corso la classe Main comporterà la seguente output:

012.

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