语法的二义性
JavaCC不能分析所有EBNF描述的语法,因为EBNF描述的语法本质上具有二义性的情况。
C语言中if语句用JavaCC的EBNF可以是如下描述:"if" "(" expr() ")" stmt() ["else" stmt()]
作为符合上述规则的具体代码,可以由如下例子:
if (cond1) if (cond2) f(); else g();
根据上面的规则分析下这段代码,直观的看上述代码表述的应该是这样的:
if (cond1) { if (cond2) { f(); } else { g(); } }
但是依据规则仔细分析下,下面的解析也是有可能的:
if (cond1) { if (cond2) { f(); } } else { g(); }
也就是说对于1份代码可以生成如下图这样的2颗语法树,像这样对于单个输入可能由多种解释时,这样的语法就可以说存在二义性。
[待截图]JavaCC的局限性
除了上面说到的问题,JavaCC本身也存在局限性而无法正确解析程序。例如像下面这样描述语法时就会发生这种问题:
type() : {}{// 选项1 | // 选项2 | // 选项3 | // 选项4 ...
JavaCC在遇到用“|”分隔的选项时,在仅读取了1个token的时刻就会对选项进行判断,确切的动作如下:
- 读取1个token
- 按照书写顺序依次查找由上述token开头的选项
- 找到的话就选用该选项
也就是说,根据上述规则,JavaCC在读取了<SIGNED>token时就已经选择了<SIGNED><CHAR>,即选项1,因此即便写了选项2和选项3,无意义。这个问题称为JavaCC的选择冲突。
提取左侧共通部分
当你写了会发生选择冲突的规则情况下,若用JavaCC处理该语法描述文件就会给出警告信息。
如果消息中出现了Choice conflict字眼,就说明了发生了选择冲突。解决上述问题的方法有两种,其一就是讲选项左侧共通的部分提取出来。以刚才的选择为例子,就改为如下这样:type() : {}{( | | | ) }
这样就不会由选择冲突了。
如有通过这种方法仍无法解决的问题可以使用下面的token超前扫描来解决。token的超前扫描
只要明确指定, JavaCC可以在读取更多的token后再决定选择哪个选项。这个功能就是token的超前扫描。
type(): {}{ LOOKAHEAD(2)| LOOKAHEAD(2) | LOOKAHEAD(2) | }
LOOKAHEAD就是"读取2个token后,如果读取的token和该选项符合则选择该选项"。
最后的选项不需要使用LOOKAHEAD, 因为 LOOKAHEAD是在还剩下多个选项时,为了延迟决定选择哪个选项而使用的功能。JavaCC会优先选用先描述的选项,因此当到达最后的选项时意味这其他选项都不符合,在只剩下一个选项时,即便推迟选择没有意义。可以省略的规则和冲突
除了“选择”外,选择冲突在“可以省略”或“重复0次或多次”中也有可能发生。
可以省略的规则中会发生"是省略还是不省略"的冲突,之前的空悬else问题就是一个具体的例子。空悬else的问题在于内侧的if语句的else部分是否省略。如果内侧的if语句的else部分没有省略,则else部分属于内侧的if语句,如果省略的话则属于外侧的if语句。空悬else最直观的判断方法是else属于最内侧的if,因此试着使用LOOKAHEAD来进行判断。未使用 LOOKAHEA的规则描述如下所示:if_stmt() : {}{"(" expr ")" stmt() [ stmt()] }
使用LOOKAHEAD来避免冲突发生的规则如下:
if_stmt() : {}{"(" expr() ")" stmt() [LOOKAHEAD(1) stmt()] }
) 则不省略 stmt()。 这样就能明确else始终属于最内侧的if语句。
重复与冲突
重复的情况下会发生"是作为重复的一部分还是跳出重复"这样的选择冲突。
下面是cflat中表示形参的声明规则。param_decls() : {}{ type() ("," type())* ["," "..."] }
根据上述规则,在读取type()后又读到","时,本来可能是"," type()也可能是"," "...",但JavaCC默认只向前读取一个token,因此在读到","时就必须判断是继续重复还是跳出重复,并且恰巧","和("," type())的开头一致,所以JavaCC会一直判断为重复("," type())×,而规则"," "..."则完全不会被用到。实际上如果程序中出现"," "..." 会因为不符合规则"," type() 而判定语法错误。
解决方法如下:param_decls(): {}{ type() (LOOKAHEAD(2) "," type())* ["," "..." ] }
更灵活的超前扫描
JavaCC提供了更灵活的超前扫描功能,可以指定"读取符合规则的所有token"。
definition() : {}{ storage() type()";" | storage() type() arg_decls() block() ... }
上述是cflat的参数定义和函数定义的规则。左侧的部分完全一样,这样的规则会发生选择冲突。
用超前扫描来分析上述规则,读取"恰好n个"token是行不通的。原因在于共通部分storage() type() <IDENTIFIER>中存在非终端符号storage()和type()。因为不知道storage()和type()实际对应几个token,所以无法用“恰好n个token”来处理。这里就需要用"读取符合这个规则的所有token"这样的设置。上述规则中选择项的共通部分是storage() type() <IDENTIFIER>,因此只要读取了共通部分加上1个token即storage() type() <IDENTIFIER>,就能够区别2个选项了。规则改写如下:definition(): {}{ LOOKAHEAD(storage() type()";") storage() type() ";" | storage() type() arg_decls() block() ... }
只需在LOOKAHEAD的括号中写上需要超前扫描的规则即可。这样利用超前扫描能够顺利区分2个选项了。