Antlr4優先級和相關性

Question

我在分析一個表達式，如(B32|B5)&B31。 我的目標是找出評估這個表達式的順序。所以我的預期結果將是B2然後|B5和最後所有&B31

我的表達式可以有特殊字符。與*,=和{。所以exp可以是B31*{A1,A2}|B35。在這種情況下，我期望B31*{A1,A2}作爲一個令牌，首先得到評估，然後B35。

我創建了以下語法。

grammar Expr; 

prog: (expr NEWLINE)* ; 

expr: '(' expr ')' 
| expr ('&'|'|') expr 
| ID 
; 


NEWLINE:'\r'? '\n' ; 

// lexer/terminal rules start with an upper case letter 
ID 
    : 
    (
    'a'..'z' 
    | 'A'..'Z' 
    | '0'..'9' | ' ' 
    | ('+'|'-'|'*'|'/'|'_') 
    | '=' 
    | '~' 
    | '(' 
    | ')' 
    | '{' 
    | '}' 
    | ',' 
)+ 
    ; 

WS : [ \t]+ -> skip ; 

我編譯上述Expr.g4與-visitor從而產生一個訪問者。 然後我創建了一個訪問者類來遍歷每個表達式並將其捕獲到列表中。

import java.util.ArrayList; 
import java.util.HashMap; 
import java.util.List; 
import java.util.Stack; 

import org.antlr.v4.runtime.tree.ParseTree; 

public class EvaluationVisitor extends ExprBaseVisitor<Value> { 

    public List<EvalExpression> exprList = new ArrayList<EvalExpression>(); 
    public HashMap<String, EvalExpression> evalExprMap= new HashMap<String, EvalExpression>(); 

    public Value visitProg(ExprParser.ProgContext ctx) { 
    return visitChildren(ctx); 
    } 

    public Value visitExpr(ExprParser.ExprContext ctx) { 
    if (ctx.getChildCount() == 3) { 
     String exprEval = ctx.getText(); 
     String leftExpr = ctx.getChild(0).getText(); 
     String token = ctx.getChild(1).getText(); 
     String rightExpr = ctx.getChild(2).getText(); 
     //System.out.println(" exprEval =" + exprEval); 
     //System.out.println("<" + leftExpr + "> " + token + " <" + rightExpr + ">"); 
     EvalExpression evalExprObj = new EvalExpression(exprEval, leftExpr, token, rightExpr); 
     exprList.add(evalExprObj); 
     evalExprMap.put(exprEval, evalExprObj); 
    } 
    return visitChildren(ctx); 
    } 

    public List<EvalExpression> getExprList() { 
    return exprList; 
    } 

    public void setExprList(List<EvalExpression> exprList) { 
    this.exprList = exprList; 
    } 

    public HashMap<String, EvalExpression> getEvalExprMap() { 
    return evalExprMap; 
    } 

    public void setEvalExprMap(HashMap<String, EvalExpression> evalExprMap) { 
    this.evalExprMap = evalExprMap; 
    } 

} 

EvalExpression等級如下表所示

public class EvalExpression { 
    private String expressionEvaluated; 
    private String leftExpr; 
    private String token; 
    private String rightExpr; 


    public EvalExpression(String expressionEvaluated, String leftExpr, String token, 
     String rightExpr) { 
    super(); 
    this.expressionEvaluated = expressionEvaluated; 
    this.leftExpr = leftExpr; 
    this.token = token; 
    this.rightExpr = rightExpr; 
    } 


    public String getExpressionEvaluated() { 
    return expressionEvaluated; 
    } 


    public void setExpressionEvaluated(String expressionEvaluated) { 
    this.expressionEvaluated = expressionEvaluated; 
    } 


    public String getLeftExpr() { 
    return leftExpr; 
    } 


    public void setLeftExpr(String leftExpr) { 
    this.leftExpr = leftExpr; 
    } 


    public String getToken() { 
    return token; 
    } 


    public void setToken(String token) { 
    this.token = token; 
    } 

Value如下

public class Value { 

    public static Value VOID = new Value(new Object()); 

    final Object value; 

    public Value(Object value) { 
     this.value = value; 
    } 

    public Boolean asBoolean() { 
     return (Boolean)value; 
    } 

    public Double asDouble() { 
     return (Double)value; 
    } 

    public String asString() { 
     return String.valueOf(value); 
    } 

    public boolean isDouble() { 
     return value instanceof Double; 
    } 

    @Override 
    public int hashCode() { 

     if(value == null) { 
      return 0; 
     } 

     return this.value.hashCode(); 
    } 

    @Override 
    public boolean equals(Object o) { 

     if(value == o) { 
      return true; 
     } 

     if(value == null || o == null || o.getClass() != value.getClass()) { 
      return false; 
     } 

     Value that = (Value)o; 

     return this.value.equals(that.value); 
    } 

    @Override 
    public String toString() { 
     System.out.println("---------Inside Value to String --------------"); 
     return String.valueOf(value); 
    } 
}  

現在最後我寫了一個測試程序，以打印出憑證清單和順序我需要看看他們

import java.util.ArrayList; 
import java.util.HashMap; 
import java.util.HashSet; 
import java.util.List; 
import java.util.Set; 
import java.util.Stack; 

import org.antlr.v4.runtime.ANTLRInputStream; 
import org.antlr.v4.runtime.CharStream; 
import org.antlr.v4.runtime.CommonTokenStream; 
import org.antlr.v4.runtime.Token; 
import org.antlr.v4.runtime.TokenStream; 
import org.antlr.v4.runtime.tree.ParseTree; 
import org.antlr.v4.runtime.tree.ParseTreeWalker; 
import org.antlr.v4.runtime.tree.TerminalNode; 

import com.inmedius.antlr.ExprLexer; 
import com.inmedius.antlr.ExprParser; 
import com.inmedius.antlr.eval.EvalExpression; 
import com.inmedius.antlr.eval.EvaluationVisitor; 
import com.inmedius.antlr.eval.ExpressionTestVisitor; 

public class EvalExprTest { 

    /** 
    * @param args 
    */ 
    public static void main(String[] args) throws Exception { 
    // TODO Auto-generated method stub 
    try { 
     //String src = "(B1=p & A4=p | A8=p) | (A6=p | ~A5=c)"; 
     String src = "(B32|B5)&B31"; 

     CharStream stream = (CharStream) (new ANTLRInputStream(src)); 
     ExprLexer lexer = new ExprLexer(stream); 
     TokenStream tokens = new CommonTokenStream(lexer); 

     ExprParser parser = new ExprParser(new CommonTokenStream(lexer)); 
     ParseTree tree = parser.prog(); 

     if (!src.contains("&") && !src.contains("|")) { 
     System.out.print("exp=" + src); 
     } else { 
     EvaluationVisitor visitor = new EvaluationVisitor(); 
     visitor.visit(tree); 

     List<EvalExpression> exprOrderList = visitor.getExprList(); 
     HashMap<String, EvalExpression> evalMap = visitor.getEvalExprMap(); 
     for (EvalExpression eval : exprOrderList) { 
      System.out.println(" Expr =" + eval.getRightExpr() + " " 
       + eval.getToken()); 
      if (evalMap.get(eval.getLeftExpr()) == null) { 
      System.out.println(" Expr =" + eval.getLeftExpr()); 
      } 
     } 
     } 

    } catch (Exception e) { 
     e.printStackTrace(System.out); 
     throw e; 
    } 

    } 

} 



     public String getRightExpr() { 
     return rightExpr; 
     } 


     public void setRightExpr(String rightExpr) { 
     this.rightExpr = rightExpr; 
     } 


    } 

我的問題是當我運行EvalExprTest，並在程序中使用String src = "(B32|B5)&B31"進行測試。我得到以下結果。

Expr =B31 & 
Expr =B5) | 
Expr =(B32 

我的目標是得到一個優先級，以便首先評估括號中的表達式。但它似乎總是從最右邊的表達式穿過樹，在這種情況下它是B31。

有人可以幫忙嗎？語法是否正確？訪客的實施是否正確？

Answer 1

目前(和)在ID允許使用的字符，所以你的例子字符串將被分爲下列標記：

• (B32
• |
• B5)
• &
• B31

另一個問題是，您沒有在表達式規則中區分&和|的優先級。這意味着像X|Y&B這樣的表達式將等於您的語言中的(X|Y)&B，其中大多數語言將優先考慮&以使其等於X|(Y&B)。

要更正這些項目，您可能需要執行以下操作。

1. 從ID規則中刪除'('和')'。如果您想要命名令牌，可以選擇添加以下內容。

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

2. 更正expr規則來分別處理&和|。

   expr: '(' expr ')' 
       | expr '&' expr 
       | expr '|' expr 
       | ID 
       ;