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

2018-01-15