C语言语法的二义性和token的超前扫描

语法的二义性

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() : {}
{
     <SIGNED> <CHAR>    // 选项1
   | <SIGNED> <SHORT>    // 选项2
   | <SIGNED> <INT>        // 选项3
   | <SIGNED> <LONG>    // 选项4
   ...

JavaCC在遇到用“|”分隔的挑三拣四项时,在只读取了1个token的时刻就是见面针对选择进行判定,确切的动作如下:

  1. 读取1个token
  2. 本书写顺序依次查找由上述token开头的抉择
  3. 找到的言语虽选用该选择

也就是说,根据上述规则,JavaCC在读取了<SIGNED>token时就早已选择了<SIGNED><CHAR>,即挑项1,因此就写了增选项2和选项3,无意义。这个题目称为JavaCC的精选冲突。

领取左侧共接有

当你写了会客起选择冲突之条条框框情况下,若用JavaCC处理该语法描述文件就会见受有警示信息。
要是消息中冒出了Choice conflict字眼,就认证了出了选择冲突。
釜底抽薪上述问题之方来零星栽,其一就是讲选项左侧共通的局部提取出来。以刚才之取舍为例,就变更呢如下这样:

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

如此就算无见面由选择冲突了。
倘发生通过这种方法按无法解决的题目得以下下的token超前扫描来缓解。

token的提前扫描

只要明确指定,
JavaCC可以当读取更多之token后重新决定取舍哪个选项。这个力量就是是token的超前扫描。

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

LOOKAHEAD就是”读取2个token后,如果读取的token和该选项符合则选择该选项”。
终极之选取项无欲以LOOKAHEAD, 因为
LOOKAHEAD是以尚剩余多个选择时,为了延迟决定择哪位选项而采用的功力。JavaCC会优先选用先描述的选料项,因此当到最终的挑选项时表示这另外选项都无抱,在特剩下一个选项时,即便推迟选择没有意义。

好省略的平整与冲突

除“选择”外,选择冲突在“可以略”或“重复0浅还是数”中为时有发生或发生。
得大概的平整中见面生出”是简约还是匪略”的冲突,之前的空悬else问题不怕是一个现实的例子。空悬else的问题在于内侧的if语句的else部分是否省略。如果内侧的if语句的else部分没简单,则else部分属于内侧的if语句,如果简单的言辞虽然属于外侧的if语句。
空悬else最直观的判断方式是else属于最内侧的if,因此试着下LOOKAHEAD来进行判定。未使用
LOOKAHEA的规则描述如下所示:

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

利用LOOKAHEAD来避免冲突来的规则如下:

if_stmt() : {}
{
    <IF> "(" expr() ")" stmt() [LOOKAHEAD(1) <ELSE> 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() <IDENTIFIER> ";"
    | storage() type() <IDENTIFIER> 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() <IDENTIFIER> ";")
      storage() type() <IDENTIFIER> ";"
    | storage() type() <IDENTIFIER> arg_decls() block()
    ...
}

只是待以LOOKAHEAD的括号中描绘及待提前扫描的条条框框即可。这样用超前围观能够如愿区分2只选项了。