解析器生成器之 JavaCC（3）：如何基于 JavaCC 描述解析器

Author: stormQ

Created: Sunday, 07. March 2021 05:19PM

Last Modified: Sunday, 14. March 2021 04:30PM

摘要

本文介绍了如何基于 JavaCC 描述解析器以及JavaCC 中token 超前扫描的用法。

基于 JavaCC 描述解析器之概述

JavaCC 采用EBNF表示法来描述解析器（又称语法分析器）。EBNF表示法类似于正则表达式，但可以描述的语法范围更广。

需要注意的是， EBNF描述的语法本质上存在具有语法二义性的情况。

解析器的作用就是生成语法树。为了达成该目的，我们需要为每个语法单位描述，它们各自是由怎样的token序列组成的。

JavaCC 的 EBNF 表示法

1） 终端符

终端符是指语法树中的叶子节点。

在 JavaCC 中，终端符除了在扫描器中定义的token以外，"="、"+"、"=="、*、|等字符串字面量也可以作为终端符直接使用。

比如，终端符token如下书写：

<CONTINUE>

终端符=如下书写：

"="

2） 非终端符

非终端符是指语法树中的非叶子节点。它是由终端符排列组成的语法单位。

比如，非终端符expr如下书写：

expr()

需要注意的是， 非终端符后面的英文小括号()不能省略。

3） 连接

如果要识别 C 语言中的continue语句，那么对应的语法规则可以如下书写：

void continue_statement() :
{}
{
  <CONTINUE> ";"
}

注：对于连接，被连接的各部分之间用空格隔开。

4） 重复 0 次或多次

要识别一个模式可以重复 0 次或多次时，可以采用*进行识别。

如果要识别 C 语言中的逻辑或运算，那么对应的语法规则可以如下书写：

void logical_or_expression() :
{}
{    logical_and_expression() ( "||" logical_and_expression())*
}

注：对于可以重复 0 次或多次的模式，需要将模式用英文小括号()括起来，并且在)后面加一个*。

注意： 在 JavaCC 中，重复 0 次或多次等重复性模式中的英文小括号()不能省略。

5） 重复 1 次或多次

要识别一个模式可以重复 1 次或多次时，可以采用+进行识别。

如果要识别“一个或多个语句”，那么对应的语法规则可以如下书写：

void statement_list() :
{}
{
   (statement())+
}

注：对于可以重复 1 次或多次的模式，需要将模式用英文小括号()括起来，并且在)后面加一个+。

6） 选择

要识别从多个模式中选择其中一个时，可以采用选择进行识别。

如果要识别“布尔类型的常量”，那么对应的语法规则可以如下书写：

void boolean_constant() :
{}
{
   "true" | "false"
}

注：对于选择，被选择的各部分之间用|隔开。

7） 可以省略

要识别一个模式可以省略时，可以采用[]进行识别。

如果要识别“变量声明时可以不指定初始值”，那么对应的语法规则可以如下书写：

void variable_definition() :
{}
{
  type() name() ["=" expr()] ";"
}

JavaCC 的 token 超前扫描

token 的超前扫描是指可以指定在扫描多个token后再决定选择哪个语法规则的功能。

在 JavaCC 中，token 的超前扫描的用法如下表所示。

token 超前扫描的用法 适用情况 描述
LOOKAHEAD(n) 可以确定“左侧共同部分的 token 数” 表示读取 n 个token后再判断选择哪个语法规则。其中，n的值等于需要超前扫描的token数（即左侧共同部分的token数）加 1。
LOOKAHEAD(语法规则) 无法确定“左侧共同部分的 token 数” 表示读取符合该规则的所有token后才选择语法规则。
LOOKAHEAD({条件语句}) 满足一定条件时才选择语法规则 表示条件语句的求值结果为真时才选择语法规则。

token 的超前扫描是解决选择冲突的方式之一。除此之外，也可以通过提取左侧共同部分的方式来解决选择冲突。

在 JavaCC 中，可能发生选择冲突的情形及原因如下表所示。

在哪些语法规则中可能发生选择冲突 发生选择冲突的情形描述 发生选择冲突的原因
选择规则 如果选项 1 和选项 2 的左侧有共同部分，那么就会发生“选择选项 1 还是选项 2”的选择冲突 。 JavaCC 默认仅根据读取的 1 个token来判断选择哪个语法规则。
可以省略规则 比如 C 语言中的空悬 else问题，会发生“是省略还是不省略 else”的选择冲突 。 用EBNF表示法描述 C 语言中的if语句的规则时，本质上存在具有语法二义性的情况。
重复 0 次或多次规则 重复的情况下会发生“是作为重复的一部分读入还是跳出重复”这样的选择冲突。 JavaCC 默认仅根据读取的 1 个token来判断选择哪个语法规则。

1） token 超前扫描的用法

a） 情形 1——可以确定“左侧共同部分的 token 数”

LOOKAHEAD(2) <SIGNED> <CHAR>

上述语法描述表示的含义，读取 2 个token后，如果读取的 2 个token分别是<SIGNED>和<CHAR>，那么视为超前扫描成功，于是选择<SIGNED> <CHAR>规则。

b） 情形 2——无法确定“左侧共同部分的 token 数”

LOOKAHEAD(storage() typeref() <IDENTIFIER> "(")
defun()

上述语法描述表示的含义，读取符合storage() typeref() <IDENTIFIER>规则的所有token后再读取一个token，如果这些token满足storage() typeref() <IDENTIFIER> "("规则，那么视为超前扫描成功，于是选择defun()规则。其中，storage() typeref() <IDENTIFIER>规则是左侧共同部分。

c） 情形 3——满足一定条件时才选择语法规则

LOOKAHEAD({isType(getToken(1).image)}) <IDENTIFIER>

上述语法描述表示的含义，执行花括号{}中的 Java 代码，如果条件语句isType(getToken(1).image)的求值结果为真，那么视为超前扫描成功，于是选择<IDENTIFIER>规则。

2） 选择冲突示例及解决

a） 选择规则中，发生选择冲突的示例及解决

选择冲突示例：

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

上述语法描述存在的问题为，JavaCC 默认在匹配<SIGNED> token后就会选择<SIGNED> <CHAR>规则，而后面的规则永远不会被匹配。也就是说，当代码中出现有符号整型时，JavaCC 一定会选择<SIGNED> <CHAR>规则。从而，被判定为语法错误。

解决方式 1——提取左侧共同部分：

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

解决方式 2——token 的超前扫描：

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

上述语法描述表示的含义：

i）读取 2 个token后再决定选择哪个语法规则。如果读取的 2 个token分别是<SIGNED>和<CHAR>，那么就选择<SIGNED> <CHAR>规则。

ii）否则，如果读取的 2 个token分别是<SIGNED>和<INT>，那么就选择<SIGNED> <INT>规则。

iii）否则，选择<SIGNED> <LONG>规则。由于该规则是最后一个。因此，如果仍匹配失败，那么表示代码存在语法错误。

需要注意的是， 由于<SIGNED> <LONG>规则是最后一个，不存在发生选择冲突的情形。因此，该规则的前面不需要添加LOOKAHEAD(2)。

b） 可以省略规则中，发生选择冲突的示例及解决

选择冲突示例：

void if_statement() :
{}
{
   <IF> "(" expression() ")" statement() [<ELSE> statement()]
}

上述语法描述存在的问题为，内侧的if语句的else部分是否省略。如果内侧的if语句的else部分没有省略，那么else部分属于内侧的if语句；否则，属于外侧的if语句。

解决方式 1——token 的超前扫描：

void if_statement() :
{}
{
   <IF> "(" expression() ")" statement() [LOOKAHEAD(1) <ELSE> statement()]
}

上述语法描述通过添加LOOKAHEAD(1)，表示读取 1 个token后再决定选择哪个语法规则。如果读取的 1 个token是<ELSE>，那么就选择<ELSE> statement()规则。也就是说，明确了else部分始终属于最内侧的if语句。从而，解决了空悬 else问题。

解决方式 2：

我们可以规定if 分支的花括号不能省略来解决空悬 else问题。至于该语法限制是否合理，就是仁者见仁，智者见智了。

c） 重复 0 次或多次规则中，发生选择冲突的示例及解决

选择冲突示例：

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

上述语法描述存在的问题为，可变长参数...永远不会被匹配。这是因为，读取type()后又读到,时，预期是选择"," type()或"," "..."规则被。但,与"," type()的开头一致，所以 JavaCC 会一直判断为重复("," type())*)。也就是说，当代码中出现, ...时，JavaCC 一定会选择"," type()规则。从而，被判定为语法错误。

解决方式——token 的超前扫描：

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

上述语法描述通过添加LOOKAHEAD(2)，表示读取 2 个token后再决定选择哪个语法规则。如果这 2 个token符合"," type()规则，那么就继续重复("," type())*)；否则，跳出重复，并判断是否符合"," "..."规则。

References

下一篇：解析器生成器之 JavaCC（4）：如何基于 JavaCC 生成抽象语法树

上一篇：解析器生成器之 JavaCC（2）：如何基于 JavaCC 描述扫描器

首页