JavaCC的语法描述

基于JavaCC的语法描述

只要为JavaCC描述"语句"、“表达式”、“函数调用” 这样的语法单位各自是由怎样的token序列构成的，就能够对该语法进行分析。

例如，最简单的赋值表达式可以描述为 "符号" = "表达式" 的排列。换言之，如果存在 "符号" = "表达式" 表达式这样的排列，那就是赋值表达式。

这个规则在 JavaCC 中表示成下面这样

assign():						//定义赋值表达式，名字任取
{}
{
 <IDENTIFIER> "=" expr()		//<IDENTIFIER> 对应 token 标识符,"=" 对应 "=" token，expr() 对应表达式，名字可以任取
}

expr():							//表达式 expr() 自身也是由多个 token 构成的,这样的情况下需要进一步对 expr() 的规则进行描述
{}
{    expr() "+" expr()
  或 expr() "-" expr()
  或 expr() "*" expr()
  ......
}

像这样写好所有语法单位的规则之后，基于 JavaCC 的解析器的描述也就完成了。

终端符和非终端符

JavaCC 中将刚才的“语句”、“函数调用”、“表达式” 等非 token 的语法单位称为非终端符。

JavaCC 中除了扫描器中定义的 token 以外，"="、"+"、"==" 这样的字符串字面量也可以作为终端符来使用。

种类	含义	例
终端符	token	、、"="、"=="
非终端符	由终端符排列组成的语法单位	stmt()、expr()、assign()

JavaCC 的 EBNF 表示法

JavaCC使用EBNF(Extended Backus-Naur-Form)的表示法来描述语法规则

种类	例子
终端符	或","
非终端符	name()
连接
重复0次或多次	(","expr())*
重复1次或多次	(stmt())+
选择	丨丨丨
可以省略	[stmt()]

1. 连接

   连接是指特定符号相连续的模式。例如C语言continue语句是保留字continue和分号的排列。JavaCC中将该规则写成如下形式:

<CONTINUE> ";"

是表示保留字continue的终端符，“:”是表示字符自身的终端符。

2. 重复0次或多次

下面的写法表示0个或多个语句排列:

(stmt())*

下面的例子，函数的参数是由逗号分隔的表达式排列组成的，即expr之后排列着0个或多个逗号和expr的组合:

expr() ("," expt())*

3. 重复1次或多次

(stmt())+

上面的代码描述了非终端符stmt()重复1次或多次

4. 选择

选择即为从多个选项中选择1个的规则。例如cflat的类型由void、char、unsigned、char等:

<VOID> | <CHAR> | <UNSIGNED> | <CHAR> | ...

5. 可以省略

定义变量时可以设置初始值也可以不设置，这种在JavaCC中可以写成:

storage() typeref() name() ["=" expr()] ";"

语法的二义性

空悬 else 问题，C 语言中的 if 语句用 JavaCC 的 EBNF 可以如下这样描述

"if" "(" expr() ")" stmt() ["else" stmt()]

作为符合上述规则的具体代码

if (cond1)
 	if (cond2)
 		f();
 	else
		g();

if (cond1)
 	if (cond2)
 		f();
else
	g();

JavaCC 的局限性

刚才的空悬 else 问题，其语法在本质上就存在二义性。除此之外，也存在因为 JavaCC 本身的局限性而无法正确解析程序的情况。例如像下面这样描述语法时就会发生这种问题。

type(): {}
{
 <SIGNED> <CHAR> 		// 选项 1
 | <SIGNED> <SHORT> 	// 选项 2
 | <SIGNED> <INT> 		// 选项 3
 | <SIGNED> <LONG> 		// 选项 4
 ……
}

事实上，JavaCC 在遇到用 “|” 分隔的选项时，在仅读取了 1 个 token 的时刻就会对选项进行判断，确切的动作如下所示。

1. 读取 1 个 token

2. 按照书写顺序依次查找由上述 token 开头的选项

3. 找到的话就选用该选项

也就是说，根据上述规则，JavaCC 在读取了 token 时就已经选择了 ，即选项 1。因此即便写了选项 2 和选项 3，也是完全没有意义的。这个问题称为JavaCC 的选择冲突（choice conflict）。

提取左侧共通部分

若用 JavaCC 处理该语法描述文件，就会给出如下警告消息。因此如果是无法分析的语法，马上就能知道。

Java Compiler Compiler Version 4.0 (Parser Generator)
(type "javacc" with no arguments for help)
Reading from file Parser.jj . . .
Warning: Choice conflict involving two expansions at
 line 642, column 8 and line 643, column 7 respectively.
 A common prefix is: "unsigned"
 Consider using a lookahead of 2 for earlier expansion.
Parser generated with 0 errors and 1 warnings.

消息中如果出现了 Choice conflict 字眼，就说明发生了选择冲突。

解决上述问题的方法有两个，其中之一就是将选项左侧共通的部分提取出来。以刚才的规则为例，修改为如下这样即可。

type(): {}
{
 <SIGNED> (<CHAR> | <SHORT> | <INT> | <LONG>)
 ……
}

当遇到 JavaCC 的上述局限性时，应首先考虑是否可以用提取共通部分的方法来处理。但还是存在使用此方法仍然无法描述的规则，以及提取共通部分的处理非常复杂的情况，这样的情况下就可以通过接下来要讲的 token 的超前扫描来解决。

token 的超前扫描

JavaCC 在遇到选项时仅根据读取的 1 个 token 来判断选择哪个选项。只要明确指定，JavaCC 可以在读取更多的 token 后再决定选择哪个选项。这个功能就称为 token 的超前扫描 A（lookahead）。

type(): {}
{
 LOOKAHEAD(2) <SIGNED> <CHAR> 		// 选项 1
 | LOOKAHEAD(2) <SIGNED> <SHORT> 	// 选项 2
 | LOOKAHEAD(2) <SIGNED> <INT> 		// 选项 3
 | <SIGNED> <LONG> 					// 选项 4
 .......
}

LOOKAHEAD(2) 表示的意思为读取 2 个 token 后，如果读取的 token 和该选项相符合，则选择该选项。也就是说，读取 2 个 token，如果它们是 和 的话，就选用选项 1。同样，第 2 个选项的意思是读取 2 个 token，如果它们是 和 的话，就选用选项 2。最后的选项（选项 4）不需要使用 LOOKAHEAD。因为当到达最后的选项即意味着其他的选项都已经被丢弃，只剩下这最后 1 个选项了。在只剩下 1 个选项时，即便推迟选择也是没有意义的。如果和任何一个选项都不匹配的话，那只能是代码存在语法错误了。

空悬else问题也可以使用 token 的超前扫描解决

if_stmt(): {}
{
 <IF> "(" expr() ")" stmt() [LOOKAEHAD(1) <ELSE> stmt()]
}

判断方法本身非常简单。通过添加 LOOKAHEAD(1)，就可以指定读取 1 个token 后，如果该 token 符合规则（即如果是 <ELSE>）则不省略 <ELSE> stmt()。

重复和冲突

函数形参的声明规则

param_decls(): {}
{
 type() ("," type())* ["," "..."]
}

这个规则中，表示可变长参数的"," "..."不会被解析

根据上述规则，在读取 type() 后又读到","时，本来可能是 "," type() 也可能是 "," "..." 的，但 JavaCC 默认向前只读取 1 个 token，因此在读到 "," 时就必须判断是继续重复还是跳出重复。并且恰巧 "," 和 ("," type()) 的开头一致，所以 JavaCC 会一直判断为重复 ("," type())*，而规则 "," "..." 则完全不会被用到。实际上如果程序中出现 "," "..."，会因为不符合规则 "," type() 而判定为语法错误。

要解决上述问题，可以如下添加 LOOKAHEAD

param_decls(): {}
{
 type() (LOOKAHEAD(2) "," type())* ["," "..."]
}

这样 JavaCC 在每次判断该重复时就会在读取 2 个 token 后再判断是否继续重复，因此在输入了 "," "..." 后就会因为检测到和 "," type() 不匹配而跳出 ("," type())* 的重复

更灵活的超前扫描

definition(): {}
{
 storage() type() <IDENTIFIER> ";"
 | storage() type() <IDENTIFIER> arg_decls() block()
 ......	 
}

函数定义与参数定义的规则。左侧的部分完全一样，也就是说，这样的规则也会发生选择冲突。虽说可以通过提取左侧共通部分来解决问题，但这次让我们考虑尝试用超前扫描的方法。

用超前扫描来分析上述规则，读取 恰好 n 个 token 是行不通的。因为不知道 storage() 和 type() 实际对应几个 token，所以无法用读取 恰好 n 个 token 来处理

这里就需要使用刚才提到的 读取符合这个规则的所有 token 这样的设置

definition(): {}
{
 LOOKAHEAD(storage() type() <IDENTIFIER> ";")
 storage() type() <IDENTIFIER> ";"
 | storage() type() <IDENTIFIER> arg_decls() block()
 ......
}

只需在 LOOKAHEAD 的括号中写上需要超前扫描的规则即可。这样利用超前扫描就能够顺利地区分 2 个选项了

超前扫描的相关注意事项

即便写了 LOOKAHEAD 也并非一定能按照预期对程序进行分析。添加 LOOKAHEAD 后 Choice conflict 的警告消息的确消失了，但实际上 JavaCC 不会对 LOOKAHEAD 描述的内容进行任何检查。在发生选择冲突的地方加上 LOOKAHEAD 后不再显示警告，仅此而已。LOOKAHEAD 处理的描述是否正确，我们必须自己思考。