1. ANTLR4 是什么·

ANTLR 的全称是 ANother Tool for Language Recognition，官方定位为 Parser Generator，即解析器的生成器。很多计算机术语翻译成汉语就显得很奇怪，这或许也是汉语言文化没有孕育出自然科学的一大问题。解析器指的是对语言进行结构的工具，常见的目的是将语言拆分成多个相关的语素，一般的生成目标是 Parse Tree，即语法解析树。

5+6

   ADD
   / \
  /   \
 5     6

比如，5+6 在人看来是一个普通的算术式，但是在计算机看来就是一个字符串。能否通过计算机将之解析成一种结构？如 加数, +, 被加数。答案很显然是可能的。

如果定义一种语言：任意组合的、带算术优先级的代数式。我们能否写出解析器？答案也是可行的。下面举几个这种语言的例句：

5*(6+7)
+9/3
-8-2
(10+2)*(3-9)

如果你多点时间，用 C/Python 就能写出解析器，只是过程可能会非常痛苦，因为需要考虑的东西很多。笔者曾经在本科时写过一个任意数量的浮点数组解析器，难度略高。因为这种解析过程需要瞻前顾后，正则表达式也无法覆盖需求。ANTLR4 就是一种解决上述问题的工具，它可以帮助我们快速写出基于某种高级语言实现的解析器。

如果你对编译器或者自然语言处理一无所知，那么理解上述的术语可能比较困难。那就需要补习功课。

2. 如何使用 ANTLR·

这里引用 Microsoft 公司 YouTube 账号的一个视频截图：

图 1. ANTLR 4 的工作流。

从中可以看到，ANTLR 接收 Grammar 作为输入，生成 Lexer（词法解析器）、Parser（语法解析器）和 Visitor（还有一个 Listener 没写出来），假如我们使用 Python 作为 Target，那么生成的 Lexer/Parse/Visitor/Listener 就是用 Python 写的。目前 ANTLR 可以生成许多种目标语言：

Java
C#
Python (2 and 3)
JavaScript
TypeScript
Go
C++
Swift
PHP
Dart

或许是因为 C 语言没有很好的面向对象能力，因此 ANTLR 不支持 C 目标代码。

综上可知，我们需要准备的就是一份 Grammar 文件。

3. Grammar 文件·

下面直接给出一份第一节描述的计算器语言（Calculator Language）的语法文件：

grammar Calculator;

calc:
    expr;

expr:
       NUM                                  # number
   |    (PLUS|MINUS) expr                   # plusOrMinusExpr
   |   '(' expr ')'                         # parensExpr
   |   left=expr op=('*'|'/') right=expr    # infixExpr
   |   left=expr op=('+'|'-') right=expr    # infixExpr
   ;
NUM :   [0-9]+;
PLUS : '+';
MINUS: '-';
WS : [ \r\n]+ ->channel(HIDDEN);

可以看到，里面的内容似曾相识。学过编译原理的同学一定认出来了，这就是 LL(*) 文法和一部分正则表达式。

NUM，PLUS，MINUS，WS 都是 Lexer 所需，可以理解为正则表达式。词法分析一般很简单，正则表达式就够用了。
expr 是 Parser 所需，正则表达式已经无能为力，必须使用文法。文法是有状态的，可以通过文法列表进行自动推导，确定给定的句子是否符合文法。如果你写的句子是合法的，那么一定存在至少一种推导（一般是一种，出现多种就说明有歧义，这是计算机语言设计所杜绝的！）

语法描述非常简单。一般而言，在设计一种语言的时候要构思它的形式，然后再写出语法。通过语法逆推语言的形式颇为吃力。expr 有 5 种推导（7~11 行）：

#7，第 1 种，推导出 NUM，这是唯一的非终结符。其他四个推导都需要继续推导。后面的 # number 是这个推导的名字，后续代码生成时会根据这个名字生成对应的函数。
#8，第 2 种，推导出 (PLUS | MINUS) expr，即 -128，+916 这种数字，前面的符号也是有意义的。
#9，第 3 种，推导出 '(' expr ')'，即带括号（parentheses）的表达式。
#10，第 4 种，推导出 left=expr op=('*' | '/') right=expr，即 3*4，4/2 这种中缀表达式（infix expression）
#11，第 11 种，推导出中缀表达式 left=expr op=('+'|'-') right=expr.

4. 自定义 `Visitor`·

from antlr4 import *
from CalculatorLexer import CalculatorLexer
from CalculatorParser import CalculatorParser
from CalculatorVisitor import CalculatorVisitor


class EvalVisitor(CalculatorVisitor):
    def visitNumber(self, ctx: CalculatorParser.NumberContext):
        return int(ctx.NUM().getText())

    def visitPlusOrMinusExpr(self, ctx: CalculatorParser.PlusOrMinusExprContext):
        value = self.visit(ctx.expr())
        if ctx.PLUS():
            return value
        else:
            return -value

    def visitParensExpr(self, ctx: CalculatorParser.ParensExprContext):
        return self.visit(ctx.expr())

    def visitInfixExpr(self, ctx: CalculatorParser.InfixExprContext):
        left = self.visit(ctx.left)
        right = self.visit(ctx.right)
        operator = ctx.op.text

        if operator == '*':
            return left * right
        elif operator == '/':
            return left / right
        elif operator == '+':
            return left + right
        elif operator == '-':
            return left - right

        return 0


def evaluate(expression):
    lexer = CalculatorLexer(InputStream(expression))
    tokens = CommonTokenStream(lexer)
    parser = CalculatorParser(tokens)
    tree = parser.calc()

    visitor = EvalVisitor()
    result = visitor.visit(tree)
    return result


def main():
    print("Calculator Program")
    print("Enter 'q' to quit")

    while True:
        expression = input("Enter an arithmetic expression: ")
        if expression == "q":
            break

        try:
            result = evaluate(expression)
            print(f"Result: {result}")
        except Exception as e:
            print(f"Error: {e}")


if __name__ == '__main__':
    main()