前言

前面我们基于 leetcode 的几个问题，手搓了一个表达式求值的编译器，可以用来执行四则运算并使用括号定义优先级。这次我们尝试使用 JavaCC 来实现同样的事情。

因为对于现代编译器来说，纯手写的算法还是过于复杂，尤其是繁多的词法和语法规则，如果每一个都手写效率也是非常低。因此就有了一种编译器的编译器YACC，我们只需要提供词法和语法的定义，以及语法解析时候的动作，即可快速生成一个编译器了。YACC是 C 语言的，Java 生态也有类似的工具叫 JavaCC，接下来，我们继续基于上面的应用场景，用 JavaCC 重新开发一遍我们的编译器。

JavaCC 语法

JavaCC（Java Compiler Compiler）是一个用Java开发的受欢迎的语法分析生成器。它可以读取上下文无关且有着特殊意义的语法，并将其转换为可以识别和匹配该语法的Java程序. 这个工具通常用于生成词法分析器（lexical analyzers）和语法分析器（parsers）。

一个 JavaCC 源文件的后缀是 jj或者jjt。里面主要是下面几个部分：

• 解析器入口：这段是 Java 代码，可以任意写。
• 词法：主要用正则表达式定义。
• 语法分析和对应的动作：主要用 BNF 定义。
• 辅助程序：比如报错方法等。

下面分别来说

解析器入口

首先定义我们的主解析器parser。PARSER_BEGIN 到 PARSER_END之间是纯 Java 代码。

我们定义了一个类 Expr和 main 方法。main方法里面也很简单，就是 new 了自己之后运行 Start 方法。Start 方法定义了整个代码的编译过程。不过你现在看还是比较懵逼，因为Start 的具体定义还在后面。

options {
	STATIC = false;
}

PARSER_BEGIN(Expr)
import java.io.PrintStream;

class Expr {
	public static void main (String[] args)
	throws ParseException, TokenMgrError, NumberFormatException{
		Expr parser = new Expr(System.in);
		parser.Start(System.out);
	}
}
PARSER_END(Expr)

词法分析

SKIP: {" "|"\t"|"\n"|"\r"|"\r\n"}
TOKEN: {<EOL:";">}
TOKEN: {<PLUS:"+">}
TOKEN: {<MINUS:"-">}
TOKEN: {<TIMES:"*">}
TOKEN: {<DIVID:"/">}
TOKEN: {<OPEN_PAR:"(">}
TOKEN: {<CLOSE_PAR:")">}
TOKEN: {<NUMBER:<DIGITS>|<DIGITS>"."<DIGITS>|<DIGITS>"."|"."<DIGITS>>}
TOKEN: {<#DIGITS:(["0"-"9"])+>}

我们的 token 有：结束符、四则运算符、括号、数字。

但是这里面有两个特别的元素，一个是 SKIP，表示跳过不用处理的符号，或者说作为 token的分隔符，在上一个例子中，我在词法解析之前删除了所有的空格，这其实是不严谨的，因为如果空格出现在数字中间，应该是一个语法错误，比如12 34 + 5;

另一个是#DIGITS和 NUMBER 的定义，#DIGITS加了井号，表示不会出现在 token 的清单里面，但是它可以像宏一样，给 NUMBER 使用。在这个实验中，我们允许NUMBER带小数点，这里我们可以看出使用 JavaCC 定义词法的优势了，只需要把我们接受的 NUMBER 的所有模式都列出来即可。竖线|表示或的关系。

语法分析

我们有下面的BNF语法定义。

start => [expression EOL] ... EOF
expression => term [ + term | - term ] ...
term => factor [ * factor | / factor ] ...
factor => NUMER | ( expression ) | -factor

用人话解释一下这几个 BNF:

JavaCC 的语法其实非常凌乱，也就是 java 代码和编译器代码混合出现，经常搞不懂哪个是哪个。基本的原则是每个函数的声明完全是 Java 的，声明下方一对花括号里面也是Java 的，一般是这个函数的初始化代码，定义一些需要的变量。第二个花括号里面就是 JavaCC 的语法了，可以获取 token，也可以继续参杂一些 java 代码。

下面就是语法分析过程的定义代码。

void Start(PrintStream printStream) throws NumberFormatException:
{
	double res;
}
{
	{printStream.print("$ ");}
	(
		try {
			res = Expression()
			<EOL>
			{printStream.println(res);}
			{printStream.print("$ ");}
		} catch (ParseException e){
			System.err.println("caught ParseException");
			error_skipto(EOL);	
		}
	)*
	<EOF>
}

double Expression() throws NumberFormatException:
{
	double value;
	double i;
}
{
	value = Term()
	(
		<PLUS>
		i = Term()
		{value += i;}
	|
		<MINUS>
		i = Term()
		{value -= i;}
	)*
	{return value;}
}

double Term() throws NumberFormatException:
{
	double value;
	double i;
}
{
	value = Factor()
	(
		<TIMES>
		i = Factor()
		{value *= i;}
	|
		<DIVID>
		i = Factor()
		{value /= i;}
	)*
	{return value;}
}

double Factor() throws NumberFormatException:
{
	Token t;
	double d;
}
{
	t = <NUMBER>
	{return Double.parseDouble(t.image);}
	|
	<OPEN_PAR> d = Expression() <CLOSE_PAR>
	{return d;}
	|
	<MINUS> d = Factor()
	{return -d;}
	|
	{error_skipto(EOL);}
}

辅助程序

我们看到上面的 Factor 方法除了BNF 中的定义，还有一个error_skipto，这是用来报错，并跳过当前行的。这个error_skipto函数就定义在辅助程序里面。

JAVACODE
void error_skipto(int kind) {
	ParseException e = generateParseException();
	System.out.println(e.toString());
	Token t;
	do {
		t = getNextToken();
	} while(t.kind != kind);
}

完整示例

完整示例见 https://github.com/yszc/compiler_game/tree/master/javaccexpr

上面的全部代码都来自expr.jj

后记

很多同学会想，编译器这种东西离我们太遥远。我们 99.9999% 的人都不可能发明一个新的语言，实际上编译器有许多应用场景，比如我们 IDE 里面的语法高亮和语法提示，也都是在编译器的基础上实现的，只不过有的编译器是用于执行代码，有的可以用于分析代码。除了编程语言，我们也可以定义一些格式，比如 json，你能不能让 json支持写注释呢？这些我们都可以基于 JavaCC 来辅助我们快速实现。

Ad:欢迎加入我的知识星球

加入知识星球，与我探讨编译原理和算法。