javacc

JavaCC官方入门指南-概述

解析器生成器之 JavaCC（1）： JavaCC 准备篇

编译原理之Javacc使用

JavaCC是一个词法分析器和语法分析器的生成工具。其主要功能是通过用户给定的文法规则，生成一个纯Java语言编写的语法分析器。用户输入一段测试字符串，该分析器就能判断该字符串是否满足该文法的规则。检测合法性的同时，也可以生成该字符串的语法分析树。另外，该工具还能根据用户定义的模板文件生成对应的描述该语言的文档。

通常所说的javacc指的是javacc.jar这个jar包，jar包中包含三个主要可执行类

• javacc 根据模板文件生成语法分析器
• jjtree 根据模板文件生成语法生成树
• jjdoc 根据模板文件生成对应语言的文档

javaCC保留关键字

关键字	说明
TOKEN	定义一些确定的普通词或关键词，主要用于被引用
MORE	将一个token分割为由多个词法分析的规则来描述
TOKEN_MGR_DECLS	辅助选项
SKIP	定义一些需要跳过或者忽略的单词或短语，主要用于分词或者注释
SPECIAL_TOKEN	定义一些确定的特殊用途的普通词或关键词，主要用于被引用或抛弃
PARSER_BEGIN	样板代码，固定开头
PARSER_END	样板代码，固定结尾
LOOKAHEAD	语法二义性处理工具，用于预读多个token，以便明确语义
JAVACODE	辅助选项，用于标识本段代码是java
IGNORE_CASE	辅助选项，忽略大小写
EOF	文件结束标识或者语句结束标识

SKIP和SPECIAL_TOKEN命令用来描述不生成token的单词的匹配规则。两者的唯一区别在于是否保存跳过的token。SKIP命令不会保存跳过的token。因此，无法访问被SKIP命令跳过的单词。而SPECIAL_TOKEN命令可以。

JavaCC语法

JavaCC 的语法描述文件以.jj结尾。一般情况下，其内容多采用如下形式：

options {
  JavaCC 的选项
}

PARSER_BEGIN(解析器类名)
package 包名;
import 库名;

public class 解析器类名 {
  任意的 Java 代码
}
PARSER_END(解析器类名)

扫描器的描述

解析器的描述

javacc options

JavaCC语法文件以options列表开始，这个不是必须的，因为这些选项都有默认值。

LOOKAHEAD：设置在解析过程中面临choice point可以look ahead的token数量。默认是LL(1)，但也支持生成LL(k)解析器，这个值越小，解析的速度就越快。这个设置可能会被特定产生式内部的声明给覆盖掉。lookahead详细说明

STATIC：boolean类型的选项，默认值是true。如果为true，那么所有在parser和token manager中生成的方法和属性，都会被声明成static。这样做会导致只允许一个parser对象被创建，但是可以提高parser的性能。如果static为true，那么在需要多parser对象的时候，需要调用ReInit方法去重新初始化parser。如果static为false，就可以通过new操作符来创建对象了，然后他们可以在多个线程中同时被使用。

UNICODE_INPUT：boolean类型的选项，默认值是false。设置为true的时候，生成的解析器将使用一个读取unicode文件的输入流，可以支持中文。UNICODE_INPUT 选项为 false 的情况下只能处理 ASCII 范围内的字符

IGNORE_CASE：boolean类型的选项，默认值是false。当设置成true的时候，生成的token manager会忽略输入的文件和token的声明中的大小写。在书写类似如html的语言的时候，这个选项就会非常有用了，当然你也可以定制化IGNORE_CASE。

BUILD_PARSER：boolean类型的选项，默认值为true。在默认的情况下，javacc会生成一个解析器对象，例如上面提到的MyParser.java文件。在这个选项被设置成false的时候，解析器将不会被生成。一般情况下，如果仅仅需要生成token manager，那个就可以使用这个选项。

DEBUG_PARSER：boolean类型的选项，默认值是false。这个选项用于从parser中获取debug信息。为true的时候，parser会打印很多日志来显示其工作的路径。日志的跟踪也可以通过调用方法disable_tracing()方法来关闭。然后还可以通过enable_tracing()方法来打开tracing。

DEBUG_LOOKAHEAD：boolean类型的选项，初始值是false。设置为true的时候，可以显示在paraser执行lookahead 的时候把动作打印出来。

DEBUG_TOKEN_MANAGER：boolean类型的选项，默认值为false。用于打开token manager的debug日志。当选项为true的时候，token manager就会打印出其所有的动作。这中类型的日志非常多，所有应该在你面对一个文法错误，但是又不知道是怎么回事的时候才被使用。一般来说，你只需要看日志的最后几行应该就能够定位到错误了。

其它option

JavaCC 的正则表达式

1. 固定字符串

要识别 C 语言中的保留字int时，可以采用固定字符串进行识别。对应的正则表达式如下：

"int"

注：对于固定字符串，需要用英文双引号""括起来。

对应的TOKEN如下：

TOKEN :
{
  < INT: "int" >
}

注：上面的INT为自定义的token名称

2. 连接

要识别 C 语言中的十六进制整数时，可以采用连接进行识别。

如果十六进制整数需要满足如下规则：“必须以 0x 或 0X 开头，后续字符可以是数字 0~9、大写字母 A~F、小写字母 a~f 中的任意一个，后续字符的个数至少为 1”，那么对应的正则表达式如下：

("0x" | "0X") (["0"-"9","A"-"F","a"-"f"])+

注：对于连接，被连接的各部分之间用空格隔开。

上面的连接由两部分组成：("0x" | "0X")和(["0"-"9","A"-"F","a"-"f"])+

对应的TOKEN如下

TOKEN :
{
  < HEXADECIMALINT : ("0x" | "0X") (["0"-"9","A"-"F","a"-"f"])+ >
}

由于 JavaCC 支持忽略大小写的特性。因此，上述TOKEN可以简化为：

TOKEN [IGNORE_CASE] :
{
 < HEXADECIMALINT : "0x" (["0"-"9","a"-"f"])+ >
}

这样，诸如：0x0、0X0、0x12fF 等十六进制整数都会被识别为HEXADECIMALINTtoken

3. 字符组

要识别特定字符中的任意一个时，可以采用字符组进行识别

如果要识别“1、0、2、4 四个数字中的任意一个”，那么对应的正则表达式如下：

["1","0","2","4"]

注：对于字符组，需要用方括号[]括起来，并且各部分之间用英文逗号,隔开。

对应的TOKEN如下：

TOKEN :
{
  < DAY: ["1","0","2","4"] >
}

4. 限定范围的字符组

要识别指定范围内的任意一个时，可以采用限定范围的字符组进行识别。

如果要识别“a~z 26 个小写字母中的任意一个”，那么对应的正则表达式如下：

["a"-"z"]

注：对于限定范围的字符组，需要用方括号[]括起来，并且在范围的上界和下界部分之间加上一个中划线-。

对应的TOKEN如下：

TOKEN :
{
  < LOWERCASE: ["a"-"z"] >
}

5. 排除型字符组

要识别任意一个非数字的字符时，可以采用排除型字符组进行识别。对应的正则表达式如下：

~["0"-"9"]

注：对于排除型字符组，只需要在要排除的字符组前面加上一个英文波浪号~。

对应的TOKEN如下：

TOKEN :
{
 < NONDIGITAL: ~["0"-"9"] >
}

6. 任意一个字符

要识别任意一个字符时，可以采用排除型字符组进行识别。对应的正则表达式如下：

~[]

对应的TOKEN如下：

TOKEN :
{
  < ANY: ~[] >
}

“[]”是不包含任何字符的字符组，因此将其反转就是包含所有字符

7. 重复

(["0"-"9"])*		//重复 0 次或多次：小括号()括起来，并且在)后面加一个*
(["0"-"9"])+		//重复 1 次或多次：小括号()括起来，并且在)后面加一个+
(["0"-"9"]){3}		//正好重复 n 次：小括号()括起来，并且在)后面加上{n}。其中，n表示可以正好重复的次数。
(["0"-"9"]){3,5}	//重复n次到m 次：小括号()括起来，并且在)后面加上{n,m}。其中 n 表示可以重复的最小次数，m 表示可以重复的最大次数
(["0"-"9"])?		//重复0次或1次： 小括号()括起来，并且在)后面加上英文问号?

8. 选择

要识别从多个模式中选择其中一个时，可以采用选择进行识别。

如果从"1"、"2"两者中选择其中一个，那么对应的正则表达式如下：

"1" | "2"

注：对于选择，被选择的各部分之间用|隔开

如果从"1"、"2"、"3"三者中选择其中一个，那么对应的正则表达式如下：

"1" | "2" | "3"

需要注意：

• "1" "2" | "3" "4"，表示选择"1" "2"、"3" "4"两者中的一个。可以匹配的模式有两个：12、34。
• "1" ("2" | "3") "4"，表示选择"2"、"3"两者中的一个，然后再进行连接。可以匹配的模式有两个：124、134。

9. 不生成 token 的单词

编程语言的代码中存在本身不具有意义的部分，例如空白符和注释，这一部分在扫描后必须跳过。要跳过这部分代码，可以如下使用 SKIP 命令（SKIP directive）

SKIP: {
   <token 名 : 模式 >
 | <token 名 : 模式 >
 | <token 名 : 模式 > 
}

使用 SKIP 命令的话就不会生成 token，因此使用 SKIP 命令可以省略 token 名，如

SKIP : {
    "\n" | "\r" | "\r\n"    //定义了将会被忽略的部分，这几个换行符用一个竖杠分隔，表示“或”的意思。
}

还可以用 SPECIAL_TOKEN 命令来跳过 token。

SKIP 命令和 SPECIAL_TOKEN 命令的区别在于是否保存跳过的 token。

使用 SKIP 命令无法访问跳过的字符串

使用 SPECIAL_TOKEN 命令就可以借助下面被扫描的 TOKEN 对象来取得跳过的字符串

9. 1 跳过空白符示例

SPECIAL_TOKEN: { <SPACES: ([" ", "\t", "\n", "\r", "\f"])+> }

" “(空格)、”\t"(制表符)、"\n"(换行符)、"\r"(回车)、"\f"(换页符) 之中的任意一个，后面加上“+”表示上述 5 种字符之一1 个或多个排列而成的字符串。

因为使用了 SPECIAL_TOKEN 命令而非 SKIP 命令，所以读取跳过的部分可以通过下面要扫描的 Token 对象进行访问。

9. 2 跳过行注释

SPECIAL_TOKEN: {
 <LINE_COMMENT: "//" (~["\n", "\r"])* ("\n" | "\r\n" | "\r")?>
}

"//" 字符串“//”

(~["\n", “\r”])* 换行（"\n"）或回车（"\r"）以外的字符0 个或多个排列

("\n"│"\r\n"│"\r")? 各种平台上的换行符可省略

上述代码所描述的模式是以“//”开始，接着是换行符以外的字符，并以换行符结尾的字符串。简单来说，这里描述的是从“//”开始到换行符为止的字符串。文件的最后可能没有换行符，因此换行符是可以省略的。

10. javacc正则总结

种类	示例
固定字符串	“int”
连接	“ABC” “XYZ”
字符组	[“X”,“Y”,“Z”]
限定范围的字符组	[“0”-“9”]
排除型字符组	~[“X”,“Y”,“Z”]
任意一个字符	~[]
重复 0 次或多次	(“o”)*
重复 1 次或多次	(“o”)+
重复 n 次到 m 次	(“o”){1,3}
重复 n 次	(“o”){3}
可以省略	(“0x”)?
选择	“ABC”

扫描没有结构的单词

TOKEN 命令

TOKEN: {
   <token 名1 : 正则表达式1>
 | <token 名2 : 正则表达式2>
 | <token 名3 : 正则表达式3>
 | <token 名n : 正则表达式n>
}

扫描器扫描符合正则表达式模式的字符串并生成对应的 token。并且 TOKEN 命令的块在一个文件中可以出现任意多次，因此按照逻辑上的相关性分开记载 TOKEN 命令比较好。

token示例

//扫描保留关键字
TOKEN: {
 <VOID : "void">
 | <CHAR : "char">
 | <SHORT : "short">
 | <INT : "int">
 | <LONG : "long">
 | <STRUCT : "struct">
 | <UNION : "union">
}

//扫描标识符
TOKEN: {
 <IDENTIFIER: ["a"-"z", "A"-"Z", "_"] (["a"-"z", "A"-"Z", "_", "0"-"9"])*>
}

1. JavaCC 的选择匹配规则

JavaCC 的匹配规则用于解决这样一个问题：当一个单词同时满足多个token的匹配规则时，应该选择哪一个作为该单词的token。

JavaCC 的匹配规则为：

1）优先采用最长匹配原则，即选择匹配长度最长的作为该单词的token

2）匹配长度相同时，选择在语法描述文件中先定义的那个token

问题1：上面例中，如voidFunction 开头部分 void既可以匹配IDENTIFIER 的 token也可以匹配VOID token。

事实上 voidFunction 不会生成 VOID 的 token（最长匹配）

原因是 JavaCC 会同时尝试匹配所有的正则表达式，并选择匹配字符串最长的规则。voidFunction 和 VOID token 的正则表达式匹配的部分是只有 4 个字符的 void，而 IDENTIFIER token 的正则表达式和 voidFunction的 12 个字符匹配。12 个字符比 4 个字符长，因此对于 voidFunction，JavaCC 会生成IDENTIFIER token。

问题2：那么和多个规则的正则表达式匹配的字符串长度相同的情况下又会怎样呢？（按声明顺序）

例如代码void f()，和 VOID token 以及 IDENTIFIER token 的正则表达式都匹配 void 这 4 个字符。

像这样和多个规则的正则表达式匹配的字符串长度相同的情况下，JavaCC 优先选择在文件中先定义的 token 规则。也就是说，如果 VOID token 的规则写在 IDENTIFIER token规则之前，那么生成 VOID token。而如果 IDENTIFIER token 的规则先定义的话，则生成IDENTIFIER token。

因此，如果将 IDENTIFIER token 的规则定义写在保留字的规则之前，那么所有保留字都会被扫描成为 IDENTIFIER token，所以所有保留字的规则必须在写在 IDENTIFIER 的规则之前。

2. 扫描数值

TOKEN: {
 <INTEGER: ["1"-"9"] (["0"-"9"])* ("U")? ("L")?						//十进制
 | "0" ["x", "X"] (["0"-"9", "a"-"f", "A"-"F"])+ ("U")? ("L")?		//十六进制
 | "0" (["0"-"7"])* ("U")? ("L")?									//八进制
 >
}

上面是 3 个正则表达式的组合，从上到下分别是十进制、十六进制、八进制的数值字面量的模式

U 表示无符号整数，L 表示长整数，UL 表示无符号的长整数

["1"-"9"] (["0"-"9"])* ("U")? ("L")?

[“1”-“9”] 0 以外的 1 位数字 ([“0”-“9”])* 任意的数字，0 位或多位排列 (“U”)? 可省略的字符 “U” (“L”)? 可省略的字符 “L”

"0" ["x", "X"] (["0"-"9", "a"-"f", "A"-"F"])+ ("U")? ("L")?

[“x”,“X”] 字符 “x” 或字符 “X” ([“0”-“9”,“a”-“f”,“A”-“F”])+ 十六进制字符 1 位或多位排列

"0" (["0"-"7"])* ("U")? ("L")?

[“0”-“7”] 0 到 7 的 1 位数字（八进制的字符） ([“0”-“7”])* 八进制字符 0 位或多位排列

3. 扫描有起始符号和终结符号的 token

块注释（/*......*/）

最长匹配原则和它的问题

下列模式是无法正确地扫描块注释的

SKIP { <"/*" (~[])* "*/"> }				//无法正确地扫描块注释

如果这样写，那么直到注释的终结符为止都和模式“(~[])*”匹配。最终下面代码中较深的部分都会被作为注释扫描

/* 本应只有这一行是注释…… */

int

main(int argc, char **argv) {

printf("Hello, World!\n");

return 0; /* 以状态 0 结束 */

}

原因在于~[]匹配任意一个字符，所以*,/也是匹配的。并且 * 模式会尽可能和最长的字符串进行匹配，因此结果就是和最后（第 2 处）出现的 */ 之前的部分都匹配了。这里的“尽可能和最长的字符串匹配”的方针称为最长匹配原则。

扫描块注释的情况下最长匹配原则表现得并不理想，但一般情况下最长匹配原则并不是太糟糕。也有一些其他的正则表达式的实现方式，但首先我们还是默认使用能够正确运行的最长匹配。

基于状态迁移的扫描

通过使用状态，可以实现只扫描代码的一部分。

/* 本应只有这一行是注释…… */

int

main(int argc, char **argv) {

printf("Hello, World!\n");

return 0; /* 以状态 0 结束 */

}

为了解决模式(~[])*在块注释的情况下过度匹配的问题，需要进行如下修改。

SKIP: { <"/*"> : IN_BLOCK_COMMENT }	
<IN_BLOCK_COMMENT> SKIP: { <~[]> }
<IN_BLOCK_COMMENT> SKIP: { <"*/"> : DEFAULT }

例子中的 IN_BLOCK_COMMENT 是扫描的状态（state）。通过使用状态，可以实现只扫描代码的一部分。

SKIP: { <"/*"> : IN_BLOCK_COMMENT }

在规则定义中写下 { 模式：状态名 } 的话，就表示匹配模式后会迁移（transit）到对应的状态。上述例子中会迁移到名为 IN_BLOCK_COMMENT 的状态。

扫描器在迁移到某个状态后只会运行该状态专用的词法分析规则。也就是说，在上述例子中，除了 IN_BLOCK_COMMENT 状态专用的规则之外，其他的规则将变得无效。

要定义某状态下专用的规则，可以如下这样在 TOKEN 等命令前加上 < 状态名 >

< 状态名 > TOKEN: {~}
< 状态名 > SKIP: {~}
< 状态名 > SPECIAL_TOKEN: {~}

<IN_BLOCK_COMMENT> SKIP: { <~[]> }

只有当扫描器处于 IN_BLOCK_COMMENT 状态下时，这两个规则才有效，而其他规则在这个状态下将变得无效。

<IN_BLOCK_COMMENT> SKIP: { <"*/"> : DEFAULT }

该行中的<"*/">:DEFAULT 也表示状态迁移，意思是匹配模式 */ 的话就迁移到 DEFAULT 状态。

DEFAULT 状态（DEFAULT state）表示扫描器在开始词法分析时的状态。没有特别指定状态的词法分析规则都会被视作 DEFAULT 状态。

<"*/"> : DEFAULT 的意思是匹配模式 */ 的话就回到最初的状态。

至此，扫描块注释的代码如下所示。

SKIP: { <"/*"> : IN_BLOCK_COMMENT }
<IN_BLOCK_COMMENT> SKIP: { <~[]> }
<IN_BLOCK_COMMENT> SKIP: { <"*/"> : DEFAULT }

但实际上上述代码仍然存在问题，上述代码在扫描过程中到达文件的尾部时会出现很糟糕的情况。

例如，对下面这样代码进行词法分析

int
main(int argc, char **argv)
{
 return 0;
}
/* 文件结束

上述代码应该是忘记关闭块注释了。

如果对上述程序进行处理，理想的情况是提示“注释未关闭”这样的错误，但如果使用刚才的词法分析规则，则不会提示错误而是正常结束。

未提示错误的原因在于使用了 3 个 SKIP 命令的规则进行扫描。像这样分成 3 个规则来使用 SKIP 命令的话，3 个规则就会分别被视为对各自的 token 的描述，因此匹配到任何一个规则都会认为扫描正常结束。所以即使块注释中途结束，上述规则也无法检测出来。

实际是用 3 个规则对一个注释进行词法分析，所以要将 “这 3 个规则用于解析一个注释” 这样的信息传给扫描器。

这时就可以使用 MORE 命令。通过使用 MORE 命令，可以将一个 token分割为由多个词法分析的规则来描述。

SKIP: { <"/"> : IN_BLOCK_COMMENT }
<IN_BLOCK_COMMENT> SKIP: { <~[]> }
<IN_BLOCK_COMMENT> SKIP: { <"/"> : DEFAULT }

使用 MORE 命令改进后的块注释的词法分析规则如下所示

MORE: { <"/*"> : IN_BLOCK_COMMENT }					//SKIP->MORE
<IN_BLOCK_COMMENT> MORE: { <~[]> }					//SKIP->MORE
<IN_BLOCK_COMMENT> SKIP: { <"*/"> : DEFAULT }

第 1 行和第 2 行的 SKIP命令 被替换为了 MORE 命令，这样就能向扫描器传达 “仅匹配该规则的话扫描还没有结束” 。换言之，如果使用 MORE 命令扫描后遇到文件末尾，或无法和之后的规则匹配，就会发生错误。因此只要使用 MORE 命令，在块注释的中途遇到文件结尾时就可以正确提示错误了。

关于跳过块注释我们已经讨论了很多，这里再来总结一下。我们主要解决了两大问题。

1.首先，使用(~[])* 这样一个模式一口气扫描注释的话，就会越过注释的终结符而引发过度匹配问题，因此我们引入了状态迁移对其进行改善。

2.其次，只使用 SKIP 命令或 SPECIAL_TOKEN 命令进行扫描的话，在注释的中途遇到文件结尾时就无法正确提示错误。因此除最后的规则之外我们全部使用 MORE 命令，以便能够明示扫描器正在扫描一个 token。

虽然看起来有些复杂，但所有具有起始符和终结符的单词都可以用类似的方法进行扫描。

3. 字符串字面量

字符串字面量同样具有起始符和终结符，所以也使用了状态迁移和MORE 命令

MORE: { <"\""> : IN_STRING } 						// 规则 1
<IN_STRING> MORE: {
 <(~["\"", "\\", "\n", "\r"])+> 					// 规则 2
 | <"\\" (["0"-"7"]){3}> 							// 规则 3
 | <"\\" ~[]> 										// 规则 4 
 }
<IN_STRING> TOKEN: { <STRING: "\""> : DEFAULT } 	// 规则 5

借助状态迁移可以用多个规则来描述 token。扫描到规则 1 的起始符"后迁移到IN_STRING 状态，只有规则 2、3、4 在该状态下是有效的。其次，除了最后的规则 5 之外，规则 1 ～ 4 都使用 MORE 命令将用多个规则扫描一个 token这样的信息传达给了 JavaCC。

这样一来，在 token 扫描到一半而中途结束时就能够给出正确的错误提示。

4. 扫描字符字面量

MORE: { <"'"> : IN_CHARACTER } 								// 规则 1
<IN_CHARACTER> MORE: {
 <~["'", "\\", "\n", "\r"]> : CHARACTER_TERM 				// 规则 2
 | <"\\" (["0"-"7"]){3}> : CHARACTER_TERM 					// 规则 3
 | <"\\" ~[]> : CHARACTER_TERM 								// 规则 4 
 }
<CHARACTER_TERM> TOKEN: { <CHARACTER: "'"> : DEFAULT } 		// 规则 5

描到规则 1 的起始符'之后迁移到 IN_CHARACTER 状态，但之后若扫描到一个字符或转义字符，则要迁移到 CHARACTER_TERM 状态。

至此我们所看过的块注释或字符串字面量中，从起始符到终结符之间的长度是任意的，但字符字面量的内容不允许超过一个字符的字面量，因此扫描到一个字符的内容后能接受的就只有终结符'了。这里迁移到 CHARACTER_TERM 状态即表示“下一个符号只接受终结符”