最近项目来了一个新需求，要求根据用户输入的表达式进行计算，除了需要支持一般的数学运算，还需要支持在表达式中调用一些预置的函数。为了实现这个需求，特意把编译原理一书拿出来翻了一遍，这些知识对理解接下来的文章很有帮助。我们的程序要能够 理解用户的输入 ，就必须涉及到语法解析了，于是ANTLR进入了我们的视野。

ANTLR （ANother Tool for Language Recognition）是一个强大的解析器生成器，用于读取、处理、执行或翻译结构化文本或二进制文件。 它被广泛用于构建语言、工具和框架。ANTLR 根据语法定义生成解析器，解析器可以构建和遍历解析树。

所有编程语言的语法，都可以用ANTLR来定义。ANTLR提供了大量的 官方 grammar 示例 ，包含了各种常见语言，比如Java、SQL、Javascript、PHP等等。

其他的语法解析器

JavaCC

JavaCC，即Java Cmopiler Compiler，为了简化基于 Java 语言的词法分析器或者语法分析器的开发，Sun公司的开发人员开发了JavaCC(Java Compiler Compiler)。JavaCC是一个基于 Java 语言的分析器的自动生成器。用户只要按照JavaCC的语法规范编写JavaCC的源文件，然后使用JavaCC的编译器编译，就能够生成基于Java语言的某种特定语言的分析器。JavaCC已经成为最受欢迎的Java解析器创建工具。

YACC(Yet Another Compiler-Compiler): 1975 年由贝尔实验室 Mike Lesk & Eric Schmidt 开发，UNIX 标准实用工具 (utility)。

最简单的方法就是使用IntelliJ IDEA作为开发工具，在Preference->Plugins中搜索 antlr 然后安装即可。

定义语法和词法

需要创建一个 .g4 文件，用于定义词法分析器（lexer）和语法解析器(Parser)。具体语法参见 官方文档 。下面是一个简单的例子： Hello.g4 。

// file Hello.g4
// Define a grammar called Hello
grammar Hello; // 1. grammer name
@header { package pers.me.expression.parser; } // 2. java package
r  : 'hello' ID ;         // 3. match keyword hello followed by an identifier
ID : [a-z]+ ;             // match lower-case identifiers
WS : [ \t\r\n]+ -> skip ; // 4. skip spaces, tabs, newlines
定义了 grammar 的名字，名字需要与文件名对应
定义生成的Java类的package
r 定义的语法，会使用到下方定义的正则表达式词法
定义了空白字符，后面的 skip 是一个特殊的标记，标记空白字符会被忽略
在IDEA中右键点击.g4文件，选择Generate ANTLR Recognizer，插件会自动在gen目录下生成一堆Java代码，我们需要移动到对应的package中。如果定义了@header，IDEA也会自动生成package信息。
我们可以利用下面这段代码来测试一下ParseTree。
public class HelloTest {
    public static void main(String[] args) throws Exception {
        HelloLexer lexer = new HelloLexer(CharStreams.fromString("hello parrt"));
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        HelloParser parser = new HelloParser(tokens);
        ParseTree tree = parser.r();
        System.out.println(tree.toStringTree(parser));
运行上面的代码可以得到如下输出，程序识别出输入的字符串符合r的语法。
(r hello parrt)
Listener和Visitor
ANTLR提供了两种方法来访问ParseTree：
一种是通过Parse-Tree Listener的方法
另一种是通过Parse-Tree Visitor的方法
Listener有以下特点：
访问AST的所有节点
重写（Override）进入时（enterXXX方法）和退出时（exitXXX方法）要执行的方法
要重写的方法没有返回值，因此需要在属性中保留所需的值
Visitor有以下特点：
并非所有 AST 节点都被访问
根据目的重写进入节点时要执行的过程（visitXXX方法）
重写方法有一个返回值，因此您不必在属性中保存所需的值
最大的区别是Listener会自动访问 AST 的所有节点，而Visitor如果要访问当前节点的子树，则需要手工实现。
Visitor 较为简单方便，继承 HelloBaseVisitor 类即可，内部的方法与 g4 文件定义相对应，对照看即可理解。实现了 visitor 之后，就可以完成一个简单的自定义解析器了。自动生成的HelloBaseVisitor.java如下：
// Generated from Hello.g4 by ANTLR 4.9.1
import org.antlr.v4.runtime.tree.AbstractParseTreeVisitor;
 * This class provides an empty implementation of {@link HelloVisitor},
 * which can be extended to create a visitor which only needs to handle a subset
 * of the available methods.
 * @param <T> The return type of the visit operation. Use {@link Void} for
 * operations with no return type.
public class HelloBaseVisitor<T> extends AbstractParseTreeVisitor<T> implements HelloVisitor<T> {
    * {@inheritDoc}
    * <p>The default implementation returns the result of calling
    * {@link #visitChildren} on {@code ctx}.</p>
   @Override public T visitR(HelloParser.RContext ctx) { return visitChildren(ctx); }
接下来，我们来实现一个简单的计算器。
定义语法和词法
创建Expression.g4。
// 定义了 grammar 的名字，名字需要与文件名对应
grammar Expression;
@header {
// 定义package
package pers.me.expression.parser;
 * parser
 * calc 和 expr 就是定义的语法，会使用到下方定义的词法
 * 注意 # 后面的名字，是可以在后续访问和处理的时候使用的。
 * 一个语法有多种规则的时候可以使用 | 来进行配置。
     : (expr)* EOF                                    # calculationBlock
// 四则运算分为了两个非常相似的语句，这样做的原因是为了实现优先级，乘除是优先级高于加减的。
    : BR_OPEN expr BR_CLOSE                           # expressionWithBr
    | sign=(PLUS|MINUS)? num=(NUMBER|PERCENT_NUMBER)  # expressionNumeric
    | expr op=(TIMES | DIVIDE) expr                   # expressionTimesOrDivide
    | expr op=(PLUS | MINUS) expr                     # expressionPlusOrMinus
 * lexer
BR_OPEN:   '(';
BR_CLOSE:  ')';
PLUS:      '+';
MINUS:     '-';
TIMES:     '*';
DIVIDE:    '/';
PERCENT:   '%';
POINT:     '.';
// 定义百分数
PERCENT_NUMBER
    : NUMBER ((' ')? PERCENT)
NUMBER
    : DIGIT+ ( POINT DIGIT+ )?
DIGIT
   : [0-9]+
// 定义了空白字符，后面的 skip 是一个特殊的标记，标记空白字符会被忽略
SPACE
   : ' ' -> skip
实现Visitor
生成Java文件之后，我们来实现自己的Visitor，用于支持BigDecimal。
public class BigDecimalCalculationVisitor extends ExpressionBaseVisitor<BigDecimal> {
     * 100
    private static final BigDecimal HUNDRED = BigDecimal.valueOf(100);
     * DECIMAL128のMathContext (桁数34、RoundingMode.HALF_EVEN)
    private static final MathContext MATH_CONTEXT = MathContext.DECIMAL128;
    @Override
    public BigDecimal visitCalculationBlock(ExpressionParser.CalculationBlockContext ctx) {
        BigDecimal calcResult = null;
        for (ExpressionParser.ExprContext expr : ctx.expr()) {
            calcResult = visit(expr);
        return calcResult;
    @Override
    public BigDecimal visitExpressionTimesOrDivide(ExpressionParser.ExpressionTimesOrDivideContext ctx) {
        BigDecimal left = visit(ctx.expr(0));
        BigDecimal right = visit(ctx.expr(1));
        switch (ctx.op.getType()) {
            case ExpressionLexer.TIMES: return left.multiply(right, MATH_CONTEXT);
            case ExpressionLexer.DIVIDE: return left.divide(right, MATH_CONTEXT);
            default: throw new RuntimeException("unsupported operator type");
    @Override
    public BigDecimal visitExpressionPlusOrMinus(ExpressionParser.ExpressionPlusOrMinusContext ctx) {
    // 此处加减法的实现类似上面的乘除法，省略
    @Override
    public BigDecimal visitExpressionWithBr(ExpressionParser.ExpressionWithBrContext ctx) {
        return visit(ctx.expr());
    @Override
    public BigDecimal visitExpressionNumeric(ExpressionParser.ExpressionNumericContext ctx) {
        BigDecimal numeric = numberOrPercent(ctx.num);
        if (Objects.nonNull(ctx.sign) && ctx.sign.getType() == ExpressionLexer.MINUS) {
            return numeric.negate();
        return numeric;
    private BigDecimal numberOrPercent(Token num) {
        String numberStr = num.getText();
        switch (num.getType()) {
            case ExpressionLexer.NUMBER: return decimal(numberStr);
            case ExpressionLexer.PERCENT_NUMBER: return decimal(numberStr.substring(0, numberStr.length() - 1).trim()).divide(HUNDRED, MATH_CONTEXT);
            default: throw new RuntimeException("unsupported number type");
    private BigDecimal decimal(String decimalStr) {
        return new BigDecimal(decimalStr);
调用解析器
在Calculator类中调用Expression。
public class Calculator {
    public BigDecimal execute(String expression) {
        CharStream cs = CharStreams.fromString(expression);
        ExpressionLexer lexer = new ExpressionLexer(cs);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        ExpressionParser parser = new ExpressionParser(tokens);
        ExpressionParser.CalcContext context = parser.calc();
        BigDecimalCalculationVisitor visitor = new BigDecimalCalculationVisitor();
        return visitor.visit(context);
最后，我们用一个jUnit来测试一下我们的计算器。
public class CalculatorUnitTest {
    private final Calculator calculator = new Calculator();
    @DisplayName("Test Calculator")
    @ParameterizedTest
    @CsvSource({
        "1 + 2, 3",
        "3 - 2, 1",
        "2 * 3, 6",
        "6 / 3, 2",
        "6 / (1 + 2) , 2",
        "50%, 0.5",
        "100 * 30%, 30.0"
    void testCalculation(String expression, String expected) {
        assertEquals(expected, calculator.execute(expression).toPlainString());
    翠云山柠檬丸
       
粉丝