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

语法的贰义性

JavaCC不能够分析全体EBNF描述的语法,因为EBNF描述的语法本质上独具2义性的景观。
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();
}

也正是说对于一份代码能够变更如下图那样的二颗语法树,像这么对于单个输入恐怕由各类演说时,那样的语法就足以说存在二义性。
[待截图]

JavaCC的局限性

除此而外下面谈到的难题,JavaCC本人也存在局限性而无法正确解析程序。例如像上面那样描述语法时就会产生那种题材:

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

JavaCC在蒙受用“|”分隔的选项时,在仅读取了一个token的随时就会对选择实行判断,确切的动作如下:

  1. 读取1个token
  2. 按部就班书写顺序依次查找由上述token开首的抉择
  3. 找到的话就采纳该选取

也等于说,依照上述规则,JavaCC在读取了<SIGNED>token时就已经选用了<SIGNED><CHA奥迪Q5>,即选项一,由此固然写了选项2和选项三,无意义。那些题材称为JavaCC的抉择争辨。

领取左侧共通部分

当您写了会产生选取争论的平整意况下,若用JavaCC处理该语法描述文件就会付出警告新闻。
假如新闻中现身了Choice conflict字眼,就印证了暴发了增选冲突。
化解上述难点的措施有三种,其1正是讲选项右边共通的一对提取出来。以刚才的抉择为例子,就改为如下那样:

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

那样就不会由精选龃龉了。
如有通过那种格局仍不或许解决的标题能够动用上边包车型客车token超前扫描来缓解。

token的超前扫描

万1明显钦定,
JavaCC能够在读取越来越多的token后再决定取舍哪位选项。那么些职能正是token的提前扫描。

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

LOOKAHEAD正是”读取1个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暗中认可只前行读取1个token,因而在读到”,”时就不可能不认清是持续重复依旧跳出重复,并且刚刚”,”和(“,”
type())的开首1致,所以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()
<IDENTIFIE宝马X5>中存在非终端符号storage()和type()。因为不亮堂storage()和type()实际对应几个token,所以不可能用“恰好n个token”来拍卖。
那里就须求用”读取符合这么些规则的持有token”那样的装置。上述规则中采用项的共通部分是storage()
type() <IDENTIFIE冠道>,因而假若读取了共通部分加上3个token即storage()
type() <IDENTIFIE途乐>,就能够区分一个选项了。规则改写如下:

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

只需在LOOKAHEAD的括号中写上须求提前扫描的平整即可。这样利用超前围观能够胜利区分3个选项了。