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

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工程。有任何问题或建议欢迎在评论区留言。

References

  1. ANTLR 4 Documentation
  2. A Tale of Two Grammars
  3. ANTLR 4: using the lexer, parser and listener with example grammar