博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
语法的二义性和token的超前扫描
阅读量:7200 次
发布时间:2019-06-29

本文共 3288 字,大约阅读时间需要 10 分钟。

语法的二义性

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. 读取1个token
  2. 按照书写顺序依次查找由上述token开头的选项
  3. 找到的话就选用该选项

也就是说,根据上述规则,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个选项了。

转载地址:http://lcdum.baihongyu.com/

你可能感兴趣的文章
云平台服务器应急检查步骤
查看>>
参照企业微信审批业务,在Winform开发框架中工作流模块的实现业务审批
查看>>
freemark标签从后台接过来数据Boolean在前台还是Boolean输出(四)
查看>>
根据类信息和提供的代理类名称,生成字节码,然后通过流的方式写到磁盘文件中(动态代理)...
查看>>
Linux资源分析工具杂谈(长文慎入)
查看>>
前端组件化Polymer入门教程(7)——Local DOM
查看>>
创业感悟:技术兄弟为什么一直没有起来(1)
查看>>
springboot(九):定时任务
查看>>
UDP转TCP隧道工具udptunnel
查看>>
Unable to launch the IIS Express Web server
查看>>
win7 使用emeidter后无法右键新建记事本
查看>>
向mysql的innodb表快速插入数据的php程序
查看>>
kvm虚拟机操作常用命令
查看>>
mysql管理之安全机制
查看>>
RAID 磁盘阵列
查看>>
Linux服务器部署系列之七—OpenLDAP篇
查看>>
CCNA之ccna-路由器的eigrp协议的配置试验
查看>>
MySQL 异常信息诊断
查看>>
组合模式
查看>>
PMD 插件的安装和使用
查看>>