用ANTLR4实现一个表达式解析器

March 23, 2016

经过几十年的研究，编译理论已经比较成熟，实现一个编译器前端就像”填表”那么简单，只要告诉生成器语(词)法就可以。在Java的世界里，词法分析工具有JFlex，语法分析工具有BYACC/J、Java Cup。兼具的有JavaCC、ANTLR。

ANTLR4 是目前比较活跃的一个，由Terence Parr编写，采用Adaptive LL(*) 分析方法，有较为成熟的生态链。比起前一个版本，ANTLR4的语法更为简洁，也广受好评。

那么，该从哪里开始呢？还是从大家都熟悉的四则运算开始吧，这基本算是前端的“Hello World” 了。和lex/yacc不同，ANTLR4的词法和语法可以放在同一个.g4文件中，词法单元以大写字母开头，语法单元以小写字母开头作为区分。

grammar Calculator;

/** PARSER */
line : expr EOF ;
expr
    : '(' expr ')'          # parenExpr
    | '-' expr              # negExpr
    | expr ('*'|'/') expr   # multOrDiv
    | expr ('+'|'-') expr   # addOrSubtract
    | ID                    # identifier
    | FLOAT                 # float ;

/** LEXER */

WS : [ \t\n\r]+ -> skip ;
FLOAT
    : DIGIT+ '.' DIGIT* EXPONENT?
    | '.' DIGIT+ EXPONENT?
    | DIGIT+ EXPONENT? ;
ID : LETTER (LETTER | DIGIT)* ;
fragment DIGIT : '0'..'9';
fragment LETTER : 'a'..'z' | 'A'..'Z';
fragment EXPONENT : ('e'|'E') ('+'|'-')? DIGIT+ ;

grammar Calculator; 申明文件为一个词法/语法混合文件，名称必须和文件名相同，即该文法文件的文件名应该是Calculator.g4 。expr 产生式后面’#‘是产生式名(alternative label name)，用来标记该产生式，后面listener会用到。词法单元DIGIT前的fragment表示这这是个词片段，不会生成对应的token。'0'..'9'表示0-9的字符，和[0-9]的意义一样。-> skip 是ANTLR4命令，表示跳过不做任何处理，适用于不同目标语言。

可以看到整个文法是目标语言无关的，同样的文件可以生成Java、JavaScript、Python2/3、C# 文件。

下面我们用MAVEN 来生成Java的代码。首先建立一个MAVEN工程，把上面的文法文件放在src/main/antlr4/org/examples 目录下，org.examples的名称就是package名。

Calculator
├─pom.xml     
├─src
   ├─main
      ├─antlr4
      │  └─org
      │      └─examples
      │              Calculator.g4
      │              
      ├─java
      │  │  Calculator.tokens
      │  │  CalculatorLexer.tokens
      │  │  
      │  └─org
      │      └─examples
      │              CalculatorBaseListener.java
      │              CalculatorLexer.java
      │              CalculatorListener.java
      │              CalculatorParser.java
      │              
      └─resources

src/main/java/org/examples目录下就是生成的Java代码，下面说明如何生成它。在pom.xml文件中添加ANTLR4插件和运行库的依赖。

<dependencies>
    ...
    <dependency>
        <groupId>org.antlr</groupId>
        <artifactId>antlr4-runtime</artifactId>
        <version>4.3</version>
    </dependency>
</dependencies>
<build>
    <plugins>
        <plugin>
            <groupId>org.antlr</groupId>
            <artifactId>antlr4-maven-plugin</artifactId>
            <version>4.3</version>
            <executions>
                <execution>
                    <id>antlr</id>
                    <goals>
                        <goal>antlr4</goal>
                    </goals>
                    <phase>none</phase>
                </execution>
            </executions>
            <configuration>
                <outputDirectory>src/main/java</outputDirectory>
                <listener>true</listener>
                <treatWarningsAsErrors>true</treatWarningsAsErrors>
            </configuration>
        </plugin>
    </plugins>
</build>

antlr4-maven-plugin 用于生成Java代码，antlr4-runtime则是运行时所需的依赖库。注意到我把antlr4-maven-plugin 的phase 设置成none，这样在Maven 的lifecycle种就不会调用ANTLR4。如果你希望每次构建生成文法可以将这个配置去掉。在工程目录下执行

mvn antlr4:antlr4

在src/main/java 目录下就得到4个文件，CalculatorBaseListener.java 是我们主要关心的文件。先看下如何使用这些类来计算表达式： src/test/java/org/examples/CalculatorTest.java

  private Double calc(String expression, Map<String, Double> sym) throws Exception{
        /* 根据表达式创建lexer */
        CalculatorLexer lexer = new CalculatorLexer(new ANTLRInputStream(expression));

        /* 根据lexer 创建token stream */
        CommonTokenStream tokens = new CommonTokenStream(lexer);

        /* 根据token stream 创建 parser */
        CalculatorParser paser = new CalculatorParser(tokens);

        /* 为parser添加一个监听器 */
        ArithmeticListener listener = new ArithmeticListener(sym);
        paser.addParseListener(listener);

        /* 匹配 line, 监听器会记录结果 */
        paser.line();
        System.out.println(expression + " = " + listener.getResult());
        return listener.getResult();
    }

ArithmeticListener 是唯一需要自己实现的监听器，也很简单。它需要一个符号表记录符号的数值，一个栈缓存计算的值。如果符号未定义，我们简单地抛出一个UndefineVariableException 就可以。 src/main/java/org/examples/ArithmeticListener.java

package org.examples;

import org.antlr.v4.runtime.Token;
import org.examples.CalculatorParser.*;

import java.util.Map;
import java.util.Stack;

public class ArithmeticListener extends CalculatorBaseListener
{
    private Stack<Double>       stack  = new Stack<Double>();
    private Map<String, Double> sym ;
    private Double ret;

    public ArithmeticListener(Map<String, Double> sym) {
        this.sym = sym;
    }

    public Double getResult()
    {
        return this.ret;
    }

    @Override
    public void exitIdentifier(IdentifierContext ctx)
    {
        if (!sym.containsKey(ctx.ID().getText())) {
            Token node = ctx.ID().getSymbol();
            throw new UndefineVariableException(
                    "line " + node.getLine() + ":" + node.getCharPositionInLine() +
                    " variable '" + node.getText() + "' is undefined"
            );
        }
        stack.push(sym.get(ctx.ID().getText()));
    }

    @Override
    public void exitFloat(FloatContext ctx)
    {
        stack.push(Double.valueOf(ctx.FLOAT().getText()));
    }

    @Override
    public void exitAddOrSubtract(AddOrSubtractContext ctx)
    {
        Double op1 = stack.pop();
        Double op2 = stack.pop();

        String op = ctx.getChild(1).getText();
        if ("-".equals(op)) {
            stack.push(op2 - op1);
        } else if ("+".equals(op)) {
            stack.push(op2 + op1);
        }
    }

    @Override
    public void exitLine(LineContext ctx) {
        ret = stack.pop();
    }

    @Override
    public void exitNegExpr(NegExprContext ctx) {
        stack.push(-stack.pop());
    }

    @Override
    public void exitMultOrDiv(MultOrDivContext ctx)
    {
        Double op1 = stack.pop();
        Double op2 = stack.pop();

        String op = ctx.getChild(1).getText();
        if ("/".equals(op)) {
            stack.push(op2 / op1);
        } else if ("*".equals(op)) {
            stack.push(op2 * op1);
        }
    }
}

最后，添加一些测试用例，验证一下成果。

    private Map<String, Double> sym = new HashMap<String, Double>();
    @Before
    public void setVariable() {
        sym.put("PI", Math.PI);
        sym.put("radius", 5.0);
    }

    @Test
    public void test1() throws Exception {
        Double ans = calc("2 * PI * radius", sym);
        Assert.assertEquals(ans, 2 * Math.PI * sym.get("radius"), 0.0001);
    }

    @Test(expected = UndefineVariableException.class)
    public void test2() throws Exception {
        calc("2 * -C",sym);
    }

至此，一个初具雏形的表达式解释器就完成了。附上完整Maven工程。有任何问题或建议欢迎在评论区留言。

<twoyao>

用ANTLR4实现一个表达式解析器

References