ANTLR v4 学习笔记（二）－实现变种计算器

发表于 2017-09-21 更新于 2017-09-23 分类于解释器构造阅读次数：

继续学习解释器构造和 ANTLR。在系列博文的上一篇 ANTLR v4 学习笔记（一）－ANTLR 初体验，我们已经学习了如何安装、使用 ANTLR，并研究了构建语言应用程序所需的关键过程、术语和构建块。接下来，我们将通过一个不算复杂的例子来描述 ANTLR 的功能，来让我们对 ANTLR 有个大概的感觉。

我将用 ANTLR 来实现一个变种计算器（变种意指它和普遍看到的计算器不太一样），它遵循上学期编译原理课程第一次实践作业要求。稍后我也将给出对这个计算器的要求描述。

这篇博文对应着《The Definitive ANTLR 4 Reference》中的 Chapter 4 A Quick Tour，但示例和内容与书上有些区别，而且没有覆盖整个 Chapter 4 的所有内容。我会更多地介绍实现学习过程中的经历和错误、自己对 ANTLR 的理解，以及一些实践经验和心得等等。

计算器描述

计算器接受四则运算表达式为输入（如下所示）。如果表达式语法正确，则输出计算结果，否则报错，指出错误位置及原因。

例子1:

1	Input 1: a=(10.44356+1.28)/2+10241.6; b=a*2-a/2; print(b); print(a); Output 1: 5246.04 3497.36

例子2:

1	Input 2: a=(10.44356+1.28)/2+10241.6; b=a*2-c/2; print(b); Output 2: Error(line 2,position 6): undefined identifier.

以上两个示例包含了这个计算器的全部特性：

每个语句需要以“;”结束；
涉及的操作符只要求加减乘除；支持括号；
操作数为整数或浮点数；
变量不需要先声明，可直接赋值，它的类型由右边表达式的类型决定；每个变量在使用之前必须要已经有赋值；
变量名可以是由数字和字母组成，但首字符必须是字母；
输出语句使用print()函数，输出并换行；
print()函数不仅可以输出变量，还可以直接输出表达式的值，例如print(1+2)；
尽量考虑周全，顾及corner cases。例如除零；
程序不需要 GUI，接受一个源文件路径为命令行参数。

匹配运算表达式的语法

在经过之前的学习后，我们可以比较轻松地写出一份匹配运算表达式的 ANTLR 语法：

/**
 * Define a grammar called Calculator
 */
grammar Calculator;
// 程序起始规则，语法分析的起点
program : stat+;

stat: define NEWLINE?            # defineStat
    | print NEWLINE?             # printStat
    | NEWLINE                    # blank
    ;
// 声明
define: VAR '=' expr ';';
// 计算表达式
expr: expr op=('*'|'/') expr     # MulDiv 
     | expr op=('+'|'-') expr    # AddSub
     | '('expr')'                # parens
     | NUMBER                    # number
     | VAR                       # var
     ;

// 输出
print: 'print''('VAR')'';'       # printVAR
      | 'print''('expr')'';'     # printExpr 
      ;
// 操作数类别
NUMBER: INT|FLOAT;
VAR : [a-zA-Z][a-zA-Z0-9]*;
INT : [0-9]+;
FLOAT : [0-9]+'.'[0-9]+;
NEWLINE: '\r'? '\n'? ;
WS : [ \t]+ -> skip;
MUL : '*' ;  
DIV : '/' ;  
ADD : '+' ;  
SUB : '-' ;

这份语法有一些值得注意的地方：

语法分析器的规则以小写字母开头；
词法分析器的规则以大写字母开头；
我们使用|来分隔同一个语言规则的若干备选分支，并使用圆括号把一些符号组合成子规则；
WS 词法规则中，-> skip是一条指令，告诉词法分析器匹配并丢弃空白字符；
你也许会注意到一些#开头的标签。如果备选分支上没有标签，ANTLR 就只为每条规则生成一个方法；
我们为运算符等词法符号定义了一些名字，这样，在之后访问器的编写中，我们可以将这些词法符号的名字当作常量使用，使代码更加清晰。

现在我们已经可以通过 ANTLR 内置的测试组件来进行测试。由于 Eclipse 的最新版本 ANTLR 插件里的 ANTLR 版本仍然是 4.4（官网的 ANTLR 包已到 4.7 版本），所以我们还是自己通过命令行生成 java 文件并编译：

添加的-gui参数使我们可以看到关于输入的语法分析树：

ANTLR 语法分析器能够自动报告语法错误并从错误中恢复。例如，我们的输入少一个;，语法分析器会自动输出错误信息：

添加-gui参数生成的可视化语法分析树会将错误节点自动标红：

语法优化

这里的“优化”不是指对语法本身，而是对 ANTLR 语法文件，即.g4作为扩展名的文件。ANTLR 允许我们将非常大的语法拆分为多个部分，根据习惯，我们将其分为语法分析器的语法和词法分析器的语法两部分。

这样做的好处是对于两种词法规则或者语法规则相同的语言，我们可以复用这些“模块”来构建语法分析器。

词法规则文件 CalculatorLexerRules.g4：

// 注意开头是 "lexer grammer"
lexer grammar CalculatorLexerRules;

// 操作数类别
NUMBER: INT|FLOAT;
VAR : [a-zA-Z][a-zA-Z0-9]*;
INT : [0-9]+;
FLOAT : [0-9]+'.'[0-9]+;
NEWLINE: '\r'? '\n'? ;
WS : [ \t]+ -> skip;
MUL : '*' ;  
DIV : '/' ;  
ADD : '+' ;  
SUB : '-' ;

语法规则文件 CalculatorExpr.g4，之前语法中的词法规则全部通过 import 语句导入：

/**
 * Define a grammar called CalculatorExpr
 */
// 注意 grammer 要和文件名相同
grammar CalculatorExpr;
// 引入词法规则
import CalculatorLexerRules;
// 程序起始规则，语法分析的起点
program : stat+;

stat: define NEWLINE?            # defineStat
    | print NEWLINE?             # printStat
    | NEWLINE                    # blank
    ;
// 声明
define: VAR '=' expr ';';
// 计算表达式
expr: expr op=('*'|'/') expr     # MulDiv 
     | expr op=('+'|'-') expr    # AddSub
     | '('expr')'                # parens
     | NUMBER                    # number
     | VAR                       # var
     ;

// 输出
print: 'print''('VAR')'';'       # printVAR
      | 'print''('expr')'';'     # printExpr 
      ;

要生成 java 文件，我们只需要对语法文件使用antlr4命令即可。这样我们就得到了和之前一样的 java 文件（测试就不贴图了）：

import 语句赋予我们编写模块化语法的能力，这使得 ANTLR 语法文件的耦合度降低，复用性提高。

使用 Visitor 构建计算器

我们最终的目的是将生成的语法分析器集成到程序中，因此我们需要写一些 Java 代码。我们会用 Visitor（访问者模式）来实现我们的变种计算器。

由于我的实现代码基于 Calculator.g4 生成的 java 文件，而非拆分后的 CalculatorExpr.g4，所以之后的文件名、类名和方法名还是会以 Calculator 开头。当然，所有功能都是相同的，使用哪份语法文件生成的 java 文件都不会有影响。

我们通过以下命令来让 ANTLR 生成 Visitor 而非 Listener：

1	antlr4 -no-listener -visitor -encoding UTF-8 Calculator.g4

这样，ANTLR 会自动生成一个访问器接口文件 CalculatorVisitor.java，以及该访问器的一个默认实现类 CalculatorBaseVisitor。实现时，我们需要自己写一个 Visitor 的子类，继承
CalculatorBaseVisitor（这样表达式的计算结果都是浮点数），并重写其中的方法，以实现变量键值对存储、计算、打印等需求。

以下是我们实现的 Visitor 子类 MainVisitor 的完整代码：

import java.util.HashMap;
import java.util.Map;

public class MainVisitor extends CalculatorBaseVisitor<Float> {
    // 声明一个 map，存放变量与值的键值对
    Map<String, Float> memory = new HashMap<String, Float>();

    /**
     * define: VAR '=' expr ';';
     */
    @Override
    public Float visitDefine(CalculatorParser.DefineContext ctx) {
        String var = ctx.VAR().getText();
        float value = visit(ctx.expr());
        memory.put(var, value);
        return value;
    }

    /**
     * expr op=('*'|'/') expr
     */
    @Override
    public Float visitMulDiv(CalculatorParser.MulDivContext ctx) {
        float left = visit(ctx.expr(0));
        float right = visit(ctx.expr(1));
        if (ctx.op.getType() == CalculatorParser.MUL)
            return left * right;
        return left / right;
    }

    /**
     * expr op=('+'|'-') expr
     */
    @Override
    public Float visitAddSub(CalculatorParser.AddSubContext ctx) {
        float left = visit(ctx.expr(0));
        float right = visit(ctx.expr(1));
        if (ctx.op.getType() == CalculatorParser.ADD)
            return left + right;
        return left - right;
    }

    /**
     * NUMBER
     */
    @Override
    public Float visitNumber(CalculatorParser.NumberContext ctx) {
        return Float.valueOf(ctx.NUMBER().getText());
    }

    /**
     * VAR
     */
    @Override
    public Float visitVar(CalculatorParser.VarContext ctx) {
        String var = ctx.VAR().getText();
        if (memory.containsKey(var))
            return memory.get(var);
        return (float) 0;
    }

    /**
     * '('expr')'
     */
    @Override
    public Float visitParens(CalculatorParser.ParensContext ctx) {
        return visit(ctx.expr());
    }

    /**
     * print: ('print''('VAR')'';');
     */
    @Override
    public Float visitPrintVAR(CalculatorParser.PrintVARContext ctx) {
        String var = ctx.VAR().getText();
        if (memory.containsKey(var))
            System.out.println(memory.get(var));
        else
            System.err.println("undefined identifier");
        return visitChildren(ctx);
    }

    /**
     * print: ('print''('expr')'';');
     */
    @Override
    public Float visitPrintExpr(CalculatorParser.PrintExprContext ctx) {
        System.out.println(visit(ctx.expr()));
        return visitChildren(ctx);
    }
}

然后，我们需要写一个 Calculator.java 来新建所需要的所有对象，并针对 program 规则启动语法分析器：

import java.io.FileInputStream;
import java.io.InputStream;

import org.antlr.v4.runtime.*;
import org.antlr.v4.runtime.tree.*;

public class Calculator {

    public static void main(String[] args) throws Exception {
        
        String inputFile = null;
        
        if (args.length == 0) {
            System.out.println("Usage:\n\tjava -jar Calculator.jar [sourceFile]");
        } else if (args.length == 1) {
            inputFile = args[0];
        } else {
            System.err.println("The file path cannot be recognized");
        }

        InputStream instream = System.in;
        
        if(inputFile != null)
            instream = new FileInputStream(inputFile);
        @SuppressWarnings("deprecation")
        ANTLRInputStream input = new ANTLRInputStream(instream);
        // 新建词法分析器对象
        CalculatorLexer lexer = new CalculatorLexer(input);
        // 新建词法符号流管道
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        // 新建语法分析器对象
        CalculatorParser parser = new CalculatorParser(tokens);
        // 启动语法分析器，从 program 规则开始进行语法分析
        ParseTree tree = parser.program();
        
        MainVisitor cal = new MainVisitor();
        
        cal.visit(tree);
    }
}

OK，现在我们的变种计算器就有了一个初步版本。打包成 jar 包后，我们可以看一下效果：

我觉得可以。

继续完善

那么这时候，一般就会有人跳出来说：“我觉得不行。我觉得很普通。”

其实我也是这么认为的（阿黄真的很严格！）。

实际上，我们这个计算器还有一些需要继续完善的地方。比如下面这种情况：

可以看到并未赋值的变量 c 被当作 0。然而在我们的要求中，这样的变量应该当作未初始化，使用时要报错。另外，当被除数为 0 时，输出的结果会是 “Infinity”，而我们还是希望这种情况发生时会报错。以上情况说明我们定义的语法没有覆盖到所有设想中的错误。

另外，ANTLR 自带的错误报告采用以下的语句，基本算是直接输出了行号、错误信息等：

1	System.err.println("line " + line + ":" + charPositionInLine + " " + msg);

说实话，不是很显眼。我还是喜欢错误报告开头有一些比较明显的标示，比如Error(line 2,position 6): undefined identifier感觉就要好一些。

不幸的是，Chapter 4 尚未涉及到 ANTLR 的错误处理机制。这部分内容在 Chapter 9 Error Reporting and Recovery 中。为了不用麻烦糖糖先记着，我们不妨先对这部分内容进行一些学习。

错误报告格式优化

先从错误报告格式优化开始。ANTLR 的错误报告通过 ANTLRErrorListener 接口，由 ConsoleErrorListener 实现，输出信息比较简单。

ANTLRErrorListener 包含四个方法：syntaxError、reportAmbiguity、reportAttemptingFullContext、reportContextSensitivity。其中 syntaxError 顾名思义用于处理语法错误，而后三个用于二义性处理。

ANTLR 也内置了一些 ANTLRErrorListener 的实现。除开默认采用的 ConsoleErrorListener，还有一个空实现 BaseErrorListener。我们可以 new 一个 BaseErrorListener 来自定义一些错误的处理方法，然后通过 addErrorListener 把它添加到语法分析器上。

根据以上思路，我们可以在 Calculator.java 中新建语法分析器对象的语句后加上几行代码，用于移除 ANTLR 默认的错误处理，以及添加一个我们自定义的错误监听器：

// 移除默认的错误处理
parser.removeErrorListeners();
// 添加自定义错误监听器
parser.addErrorListener(new BaseErrorListener() {
    //出现语法错误
    @Override
    public void syntaxError(Recognizer<?, ?> recognizer, Object offendingSymbol, int line, int charPositionInLine, String msg, RecognitionException e) {
        System.err.println("Error(line " + line + ", position " + charPositionInLine + "): " + msg);
    }
});

现在的错误报告看起来就更加有条理了：

部分错误特例的处理方式

不幸的是，读完了 Chapter 9，我仍然没有找到关于调用未初始化变量、被除数为 0 时报错应该怎么写。
现在我的权宜之计是直接System.err.println，也就是跳过错误机制。由于上下文对象会记录根据规则识别词组时产生的所有信息，可以通过ctx.start.getLine()获得ctx.start.getCharPositionInLine()错误出现的行数和行内具体位置。

可以看到所显示的位置好像并不是特别准确，个人认为是 ctx 给出的位置会追溯到所在规则开始的地方。也许随着学习更加深入，我会找到比较优雅的实现方法。

计算器运行截图

计算器实现中遇到的问题

实现这个变种计算器的过程当然也不是一帆风顺的，尤其我是先动手摸索再看的 Chapter 4。以下几个小坑可能还会有新司机踩上，特此写明：

开始的语法写输出语句为print: ('print''('VAR|expr')'';');没有在VAR|expr外加一层括号，导致后续开发匹配错误。当然，我认为现在开两个备选分支的写法应该更好。
第一次实现时，没有给备选分支加上标签，之后实现 Visitor 时很多方法就需要自己写 if 判断，十分麻烦。通过标签来对每种输入都获得一个不同的事件是坠吼的。
开始的语法写的是WS : [ \t\r\n]+ -> skip;。后来测试时感觉直接跳过换行符好像有时对错误定位会有影响，于是改成现在的样子。

我对 ANTLR 的理解

那么到现在为止，我已经使用 ANTLR 写了几个示例，并完成了一个小项目。经过实际体验，ANTLR 真的可以使我们开发语言类应用程序时，少做很多繁琐的工作。

只要输入一份合法的语法（当然用户需要自行保证语法的准确性），无论多复杂，ANTLR 的语法分析器都能够自动识别，并在运行时以动态方式对语法执行分析。相比静态分析必须考虑所有可行的输入序列，动态分析使得我们不必为了适应底层的语法分析策略而扭曲我们语法，从而省略了很多不必要的工作。这是 ANTLR 4 相比其他语法分析器的一个很大的优势。

举个例子，选择使用 ANTLR 进行编译相关的开发工作有一个重要的原因，是它能够自动处理直接左递归（间接左递归暂时不能够）。

我们知道，左递归指某个语言规则在某个备选分支的起始位置调用了自身。由于含有左递归的文法必然不是 LL(1) 文法，也就不可能使用确定的自顶向下分析法。然而，允许使用左递归的文法来表示语言规则又要简洁的多。ANTLR 可以将直接左递归规则自动重写为等价的非左递归形式，省却了不少麻烦。

此外，ANLTR 语法文件独立于程序。在生成的所需的语法分析器之后，我们只需要用熟悉的 Java 来实现我们所需要的语法分析树遍历器（重写部分方法），以符合我们的要求即可。不需要自己去写词法分析器、语法分析器，ANLTR 大大降低了语言类应用程序开发的门槛。

当然，无论工具有多方便，终究只能帮助人完成事务、减少工作量，而非完全替代。想要使用好 ANTLR，还是得对编译原理有透彻的理解。

结语

ANTLR 学习的第二篇笔记到这里就结束了。在这之后我会继续学习解释器构造，阅读《The Definitive ANTLR 4 Reference》，并博客上持续记录学习过程中的一点心得。敬请期待。

参考资料

《The Definitive ANTLR 4 Reference》
antlr入门实例——计算器 - Yue Xiang - CSDN博客