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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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名。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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插件和运行库的依赖。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
<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。如果你希望每次构建生成文法可以将这个配置去掉。
在工程目录下执行

1
mvn antlr4:antlr4

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
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);
}
}
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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