Zagnieżdżony analizator składni logicznej za pomocą ANTLR

Question

Próbuję przeanalizować Zagnieżdżoną wyrażenie logiczne i oddzielnie uzyskać indywidualne warunki wyrażenia. Na przykład, jeśli wejściowy ciąg znaków to:

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

Chciałbym uzyskać warunki z prawidłową kolejnością. tj

D = D i E = E lub F = F i G = g I A = B = A lub B lub C = C

mi stosując ANTLR 4 do analizowania tekst wejściowy i oto moja gramatyka:

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; 

a oto kod Java, że ​​używam go do analizowania:

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

oU tput to:

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

Szukam pomocy w analizowaniu tego drzewa, aby uzyskać warunki we właściwej kolejności? W ANTLR 3 moglibyśmy określić^i! aby zdecydować, w jaki sposób drzewo jest budowane (zapoznaj się z tym thread), ale dowiedziałem się, że nie jest to obsługiwane w ANTLR 4.

Czy ktoś może zasugerować, w jaki sposób mogę analizować ciąg w poprawnej kolejności w Javie przy użyciu ParseTree utworzonego przez ANTLR ?

Answer 1

Po prostu zawijam wszystkie wyrażenia do jednej reguły expression. Pamiętaj, aby określić comparator wyrażeń alternatywnych przed Twoja alternatywa binary wyrażenie, aby upewnić się comparator operatorzy wiążą mocniej niż OR i 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; 

Aby przetestować gramatykę powyżej, należy użyć następującego szybki i brzydka testu klasy:

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

przebiegu klasę Main spowoduje następujący wynik:

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