利用ANTLR 4的左遞歸消歧

Question

我想要一個只包含二進制非終端的語法和評估器（ANTLR解析樹walker），而不需要在訪問表達式節點時切換操作符以確定要執行的操作因爲訪問者將訪問「additionNode」，因此訪問者可以靜態假設它必須執行另外的）。

相當直接的問題。 ANTLR支持左遞歸，所以這是一個有效的語法

expr : 
    | expr ('+'|'-') expr 
    | expr ('*'|'/') expr 
    | '(' expr ')' 
    | literal 
    ; 

漂亮的，但是任何沃克/參觀者/編譯器後端的這個現在已經做到對各類自身的調度，它太臭：

onVisitExit(ExprContext ctx){ 
    left = compiledMap.get(ctx.getChild(0)); 
    right = compiledMap.get(ctx.getChild(2)); 
    operator = ctx.getChild(1); 
    switch(operator.getToken()){ 
     case "+": compiledMap.put(ctx, left + right); 
     case "-": compiledMap.put(ctx, left - right); 
     case "*": compiledMap.put(ctx, left * right); 
     case "/": compiledMap.put(ctx, left/right); 
    } 
} 

利弊這一戰略：

• ANTLR建立二叉樹對我來說，在哪裏（二）每個規則有一個左和右的說法，意思是我不擔心，而對克林循環關閉。我真的很喜歡這個
• 我必須在令牌上手動調度（切換），而不是在節點的類型上。

使用更傳統的&已經離開-因素語法

expr    : addOrSub ; 
addOrSub   : multOrDiv (('+'/'-') multOrDiv)* ; 
multOrDiv   : bracks (('*'/'/') backs)* ; 
bracks    : '(' expr ')' | literal ; 
literal    : TOKEN ; 

此相應的訪問者有相反的利弊上面的一個2語法：ANTLR會做類型此調度對我來說 - 大多數情況下，仍然必須區分'+'和' - ' - 但現在我必須包含用於那些kleene閉包的while循環，因爲我沒有嚴格的二叉樹了，這很煩人。

我想，我理想中的語法會是這樣

expression : expr ; 

fragment expr : 
    (addition | subtraction) 
    | (multiplication | division) 
    | brackets 
    | literal 
    ; 

addition  : expr '+' expr ; 
subtraction  : expr '-' expr ; 
multiplication : expr '*' expr ; 
division  : expr '/' expr ; 
brackets  : '(' expr ')' ; 
literal   : TOKEN ; 

這將解決我的所有問題，當然除了在ANTLR

Answer 1

非法寫出這個問題，這讓我以後想多一點點功能

長話短說，我使用的語法

expr : 
    | expr (plus|minus) expr 
    | expr (multi|div) expr 
    | '(' expr ')' 
    | literal 
    ; 

plus : '+' ; 
minus : '-' ; 
multi : '*' ; 
div : '/' ; 

這讓我們聆聽一位訪問者：

onVisitExit(ExprContext ctx){ 
    left = values.get(ctx.child(0)); 
    right = values.get(ctx.child(2)); 
    operator = binaryOperators.get(ctx.child(1)); 

    result = operator.doUsing(left, right); 
    values.put(ctx, result); 
} 

onVisitExit(PlusContext ctx){ 
    binaryOperators.put(ctx, (left, right) -> left + right); 
} 

onVisitExit(MinusContext ctx){ 
    binaryOperators.put(ctx, (left, right) -> left - right); 
} 

//... 

解決了我所有的問題--infact第一訪問者實施很可能會沒有一個單一的if或for聲明它，這將是真的很漂亮。

但要保持很長的故事長：

標準多態性技術將讓你嘗試的開關切換功能到變量您接通。因此，代碼

switch(operator.getToken()){ 
    case "+": do(left + right); 
    //... 

成爲

operator.doOperationUsing(left, right); 

，然後運營商的各種實現方式會做不同的事情。問題是爲操作員生成不同的實現。對於典型的多態，如果你只是使用一個枚舉，每個枚舉實例定製實現的枚舉實際上並不比僅僅切換更好。但在這裏，我們可以使用訪問過非終端的規則，以生成執行，有拉姆達 :)