2018-01-15 Antlr4: 修改語法規則更接近普通BNF格式

經 @沈默 在上文Antlr4添加中文變數賦求值,括弧,各種問題評論中指出, 語法規則描述依賴於Antlr4生成的語法分析器的預設分析方法, 比如運算符的左聯繫, 以及優先順序處理等等. 於是將語法修改為下麵(源碼版本號: program-in-chinese/quan5):

表達式: 求積表達式 (('+'|'-') 求積表達式)*;

求積表達式: 最小表達式 (('*'|'/'|'×'|'÷') 最小表達式)*;

最小表達式
  : 字面量
  | '(' 表達式 ')'
  ;

字面量
  : T數
  | T變數名
  ;

這樣做的結果是, Antlr4會分析生成一個多叉樹. 比如 1+2-3, 生成樹如下:

於是在生成抽象語法樹時手動轉換為二叉樹. 代碼如下:

private 節點 構建二叉樹(List<ParseTree> 子節點) {
    if (子節點.isEmpty()) {
      return null;
    } else if (子節點.size() == 1) {
      return visit(子節點.get(0));
    } else {
      ParseTree 最後運算符節點 = 子節點.get(子節點.size() - 2);
      運算符號 運算符 = ((TerminalNodeImpl)最後運算符節點).symbol.getType() == 圈5Parser.T加 ? 運算符號.加 : 運算符號.減;
      運算式節點 節點 = new 運算式節點();
      節點.運算符 = 運算符;
      節點.左子節點 = 構建二叉樹(子節點.subList(0, 子節點.size() - 2));
      節點.右子節點 = visit(子節點.get(子節點.size() - 1));
      return 節點;
    }
  }

開發過程中發現一些坑(如果是小白錯誤請指出). 一個比較費解的是, 不能省去"字面量"規則如下:

最小表達式
  : T數
  | T變數名
  | '(' 表達式 ')'
  ;

不然生成的分析器會有編譯錯誤:

com/中文編程/圈5/分析器/圈5Parser.java:403: error: unreachable statement
                enterOuterAlt(_localctx, 3);

Antlr4有個github庫彙集了社區維護的各種語言的語法規則文件, 其中有Java8, 根據註釋說明它的語法規則描述"極度"接近Java標準, 於是參考了它的實現. 其中看到這樣的模式(已轉成中文):

求和表達式
    :   求積表達式
    |   求和表達式 '+' 求積表達式
    |   求和表達式 '-' 求積表達式
    ;

求積表達式
    :   最小表達式
    |   求積表達式 '*' 最小表達式
    |   求積表達式 '/' 最小表達式
    ;

感覺這樣會讓語法樹轉換這一步的實現更加方便(應該可以省去多叉樹轉換成二叉樹的那個遞歸演算法). 在添加新功能之前, 打算嘗試修改成這樣.

已完成:

表達式
  : 求積表達式
  | 表達式 '+' 求積表達式
  | 表達式 '-' 求積表達式;

求積表達式
  : 最小表達式
  | 求積表達式 '*' 最小表達式
  | 求積表達式 '/' 最小表達式
  | 求積表達式 '×' 最小表達式
  | 求積表達式 '÷' 最小表達式;

的確省去了多叉樹轉換. 代碼整理完畢(program-in-chinese/quan5). 接下去, 是條件判斷還是函數定義?

補記

Antlr4自帶的語法分析可視化工具, 以antlr/grammars-v4為例:

$ alias grun='java -cp "{PATH_TO_antlr-4.7-complete.jar}:$CLASSPATH" org.antlr.v4.runtime.misc.TestRig'
$ java -cp "{PATH_TO_antlr-4.7-complete.jar}:$CLASSPATH" org.antlr.v4.Tool -visitor  -no-listener Java8.g4 
$ javac -cp "{PATH_TO_antlr-4.7-complete.jar}:$CLASSPATH" Java8*.java
$ grun Java8 expression -tree <--- 將輸入字元串進行語法解析, 生成樹結構
Warning: TestRig moved to org.antlr.v4.gui.TestRig; calling automatically
a>1
(expression (assignmentExpression (conditionalExpression (conditionalOrExpression (conditionalAndExpression (inclusiveOrExpression (exclusiveOrExpression (andExpression (equalityExpression (relationalExpression (relationalExpression (shiftExpression (additiveExpression (multiplicativeExpression (unaryExpression (unaryExpressionNotPlusMinus (postfixExpression (expressionName a)))))))) > (shiftExpression (additiveExpression (multiplicativeExpression (unaryExpression (unaryExpressionNotPlusMinus (postfixExpression (primary (primaryNoNewArray_lfno_primary (literal 1)))))))))))))))))))
$ grun Java8 expression -gui <--- 圖形化
Warning: TestRig moved to org.antlr.v4.gui.TestRig; calling automatically
2>1
^D