用 Antlr4 实现表达式计算

(本文章为原创，如转载敬请注明出处)
表达式计算是学生们乐于实现的一个课题。有些人简单粗暴，循环扫描；有些人参考数据结构里面用栈来实现；而最优雅强大，逼格最高的办法，自然是运用编译原理来做了。然而编译原理那些模式匹配，甚是繁琐！于是乎，有个叫Terence Parr的大牛出现了！他发愿要拯救世界上被编译器折磨的人们！就这样，Java界做编译器的不二之选：Antlr！闪亮登场！！Antlr能根据您定义的文法解释(Parser)和词法(Lexer)规则，生成代码来把语言source生成语法树。而Antlr4，则是最智能的一个版本。它可以生成Java，C++，Python，C#等等语言的代码，不过本例用Java实现。

有了这么牛逼的工具！做Expr calculation只是 Piece of cake!好了，我们开始牛逼之旅吧！

下载安装

假设您的系统已经装有Java JDK。

苹果系统是这样做的。Windows的话可以把 alias的那两个搞成 BAT，放在PATH下。

$ cd /usr/local/lib
$ sudo curl -O http://www.antlr.org/download/antlr-4.7-complete.jar
$ export CLASSPATH=".:/usr/local/lib/antlr-4.7-complete.jar:$CLASSPATH"
$ alias antlr4='java -jar /usr/local/lib/antlr-4.7-complete.jar'
$ alias grun='java org.antlr.v4.gui.TestRig'

定义一些基本词法

如果以grammar开头，是普遍语法，可以import那些lexer grammar和parser grammar开头的module, 而lexer 和parser之间不能混着import。lexer可以import lexer, parser 可以 import parser.

定义操作符， 保存为Operators.g4

lexer grammar Operators;

MUL: '*';
DIV: '/';
ADD: '+';
SUB: '-';
POW: '^';
MOD: '%';

定义字符串，标识符，数字等。保存为BasicTypes.g4

lexer grammar BasicTypes;

fragment DIGIT: [0-9]; 
//Fragment修饰的方法，到时候在程序里不会生成 DIGIT()。
//而下面的NUMBER没有fragment, 则可以通过 NUMBER() 来访问。

fragment S_QUOTE: '\'';
fragment QUOTE: '"';
fragment ALPHABET: [A-Za-z_];

NUMBER: DIGIT+('.'DIGIT+)? ; //数字类型，包括浮点和整型

// 两种模式，一种是单引号，一种是双引号
STRING: S_QUOTE (~'\'')* S_QUOTE //单引号字符串
    | QUOTE ('\\"'|~'"')* QUOTE //双引号字符串
    ;

ID: ALPHABET+(DIGIT(ALPHABET)*)*;

WS: [ \r\t\n]+ -> skip; // Skip all the white spaces.

定义语法

保存为 Expr.g4

grammar Expr;
import Operators, BasicTypes; //导入之前定义的符号 和 数据类型

// 加入`#`，叫Annotation, 生成的Listener和visitor会有相应的方法来触发这个事件。
// 我认为这个应该叫 触发器注解。
// 注意，这个注解要么一个都不写，要么整条规则每一个模式都要写。
expr: SUB NUMBER                #NegativeNumber
    | expr POW expr             #Pow
    | expr (MUL|DIV|MOD) expr   #Mul_Div_Mod
    | expr (ADD|SUB) expr       #Add_Sub
    | ID                        #Identifier
    | NUMBER                    #Number
    | '(' expr ')'              #Parentheses
    ;

生成 Java 代码

运行如下命令。如果没有这个命令，参考官网上面 antlr4 的安装

antlr4 Expr.g4

编译生成的Java代码

javac *.java

测试匹配字符串

运行如下命令：

grun Expr expr -gui
> 1 + 2 * 3
> (CTRL+D 于Unix/Linux，CTRL+Z于Windows)

生成如下的语法树：

    expr
  /  |  \
expr +  expr
  |    /  |  \
  1  expr *  expr
      |       |
      2       3

好了！到目前为止，我们已经成功地定义了语法，并通过了测试。下一步，就是和Java结合来实现计算器了。

写代码来实现计算逻辑

既然生成了语法树，要想实现计算，就要遍历它。遍历的方法有两种， Visitor和Listener。Visitor比较直观，上级节点调用下级节点。
参看此例：例子

不过经过山哥的测试，每次调用Visit，都会遍历所有字节点，那么就造成了反复遍历。所以，山哥还是喜欢用Listener，这样一次成型，一滴永固，永不脱落！我中意！！

以下这种方式，也是Terence Parr比较喜欢的用空间换时间的方式。每个节点的值保存在一个Map中，这个Map是专门定制的。不会有Hashcode问题。(ParseTreeProperty类)

注意，因为默认的遍历模式是深度优先，所以如果你在enterVisitor就想取得子节点的值，那是不科学的！所以每次计算，都是在exitVisitor那里作。比如：

/**
 * Created by sam on 8/30/17.
 */
public class CalcExpr extends ExprBaseListener {
    // 用来对应每个节点，保存它的计算值，于是父级节点可以获取子节点的值
    ParseTreeProperty<BigDecimal> numbers = new ParseTreeProperty<>();
    
    // 退出时，把结果保存到本节点对应的Map里
    @Override
    public void exitEntry(ExprParser.EntryContext ctx) {
        // return the expression's value
        numbers.put(ctx, numbers.get(ctx.expr()));
        
        super.exitEntry(ctx);
    }

    @Override
    public void exitMul_Div_Mod(ExprParser.Mul_Div_ModContext ctx) {
        BigDecimal left = numbers.get(ctx.expr(0));
        BigDecimal right = numbers.get(ctx.expr(1));
        if(ctx.MUL() !=  null) {
            numbers.put(ctx, left.multiply(right));
        } else if(ctx.DIV() != null) {
            // Only keep up to 21 digits after the decimal point
            numbers.put(ctx, left.divide(right, 21, RoundingMode.HALF_UP).stripTrailingZeros());
        } else if(ctx.MOD() != null) {
            numbers.put(ctx, left.remainder(right));
        }
        
        super.exitMul_Div_Mod(ctx);
    }

...
    // 在遇到数字时，把它变成BigDecimal
    @Override
    public void exitNumber(ExprParser.NumberContext ctx) {
        numbers.put(ctx, new BigDecimal(ctx.getText()));
        
        super.exitNumber(ctx);
    }
    ...

调用这个遍历器，计算结果

import org.antlr.v4.runtime.CharStream;
import org.antlr.v4.runtime.CharStreams;
import org.antlr.v4.runtime.CommonTokenStream;
import org.antlr.v4.runtime.tree.ParseTree;
import org.antlr.v4.runtime.tree.ParseTreeWalker;
import org.junit.Test;

/**
 * Created by sam on 8/30/17.
 */
public class CalcExprTest {
    @Test
    public void testExpr() {
        CharStream input = CharStreams.fromString("1 + 2 * 3");
        ExprLexer lexer = new ExprLexer(input);

        CommonTokenStream tokenStream = new CommonTokenStream(lexer);
        ExprParser parser = new ExprParser(tokenStream);
        ParseTree parseTree = parser.entry();
        CalcExpr visitor = new CalcExpr();
        ParseTreeWalker walker = new ParseTreeWalker();
        walker.walk(visitor, parseTree);

        System.out.println(visitor.numbers.get(parseTree));

    }

}

运算结果为

7
Process finished with exit code 0

大功告成！亲个嘴儿！！