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