第5章 基于JavaCC的解析器的描述

本章将介绍基于JavaCC的解析器的描述方法。

5.1 基于EBNF语法的描述

本节我们将一边制作C♭语言的解析器，一边对使用JavaCC制作解析器的方法进行介绍。

本章的目的

首先，让我们来回顾一下解析器的作用。

编译器中解析器的作用是利用扫描器生成的token序列来生成语法树。例如，生成如图5-1所示的语法树。

图5-1 语法树的例子

如图5-1所示，字符串和"（"、"）"等对应代码中的1个单词。换言之，就是能够作为扫描器中的1个token被识别。

另一方面，“语句”和“函数调用”则对应多个单词，即对应多个token。但这样的语法扫描器是无法识别的。

将上述这样由多个token构成的语法单位识别出来，正是解析器最重要的工作。在token序列中，只要知道了“这个单词列是语句”“这是函数调用”等，接下来就只需根据token信息来构建语法树即可，并不是什么太难的工作。

基于JavaCC的语法描述

下面就来讲一下使用JavaCC从token序列中识别出“语句”“表达式”“函数调用”等语法单位的方法。

只要为JavaCC描述“语句”“表达式”“函数调用”这样的语法单位各自是由怎样的token序列构成的，就能够对该语法进行分析（parse）。

例如，让我们以最简单的赋值表达式为例来思考一下。最简单的赋值表达式可以描述为“符号”“"="”“表达式”的排列。换言之，如果存在“符号”“"="”“表达式”这样的排列，那就是赋值表达式。这个规则在JavaCC中表示成下面这样。

assign（　）:
{}
{
    <IDENTIFIER> "=" expr（　）
}

assign（　）对应赋值表达式，<IDENTIFIER>对应token标识符，"="对应"="token, expr（　）对应表达式。assign（　）和expr（　）是笔者随便取的名字，并不是说赋值表达式就必须是assgin（　），表达式必须是expr（　）。

像<IDENTIFIER>这样已经在扫描器中定义过的token，在描述解析器时可以直接使用。其他的如"="这样的固定字符串因为同样可以表示token，所以也能在规则中使用。

另外，表达式expr（　）自身也是由多个token构成的。这样的情况下需要进一步对expr（　）的规则进行描述。夹杂着中文来写的话大致如下所示。

expr（　）:
{}
{
          expr（　）"+" expr（　）
      或   expr（　）"-" expr（　）
      或   expr（　）"＊" expr（　）
          …
          …

像这样写好所有语法单位的规则之后，基于JavaCC的解析器的描述也就完成了。大家应该有一个大致的印象了吧。

终端符和非终端符

这里请记住1个术语。JavaCC中将刚才的“语句”“函数调用”“表达式”等非token的语法单位称为非终端符（nonterminal symbol），并将非终端符像Java的函数调用一样在后面加上括号写成stmt（　）或expr（　）。

既然有“非”终端符，自然也有终端符。终端符（terminal symbol）可以归纳为token。使用在扫描器中定义的名称，可以写成<IDENTIFIER>或<LONG>。并且JavaCC中除了扫描器中定义的token以外，"="、"+"、"=="这样的字符串字面量也可以作为终端符来使用（表5-1）。

表5-1 终端符和非终端符

在讲解token时我们提到了“token是单词的字面表现和含义的组合”，这里的终端符和非终端符中的“符”可以说蕴含了相同的意思。

也就是说，这里的“符”也兼具字面表现和含义两重功能。举例来说，赋值表达式这样的非终端符就既有i=1这样的字面表现，又有“将整数1赋值给变量i”这样的含义。字面表现和含义两者的组合才能称为“符”。

顺便提一下，至于为什么称为终端和非终端，是因为在画语法树的图时，终端符位于树的枝干的末端（终端）。非终端符由于是由其他符号的列组成的，因此一定位于分叉处，而非树的末端。

JavaCC的EBNF表示法

下面具体地说一下JavaCC中语法规则的描述方法。

JavaCC使用名为EBNF（Extended Backus-Naur Form）的表示法来描述语法规则。EBNF和描述扫描器时使用的正则表达式有些相似，但比正则表达式所能描述的语法范围更广。

首先，表5-2中罗列了JavaCC的解析器生成器所使用的EBNF表示法。

表5-2 JavaCC的EBNF表示法

我们已经讲过了终端符和非终端符，下面我们从第3项的“连接”开始来看一下。

连接

连接是指特定符号相连续的模式，比如首先是符号A，接着是符号B，再接着是符号C……

例如C语言（C♭）的continue语句是保留字continue和分号的排列。反过来说，如果保留字continue之后接着分号，就说明这是continue的语句。JavaCC中将该规则写成如下形式。

<CONTINUE> "; "

<CONTINUE>是表示保留字continue的终端符，"; "是表示字符自身的终端符。像这样，JavaCC中通过简单地并列符号来表示连接。

表示连接的符号可以是终端符也可以是非终端符，当然两者混用也是可以的。

重复0次或多次

接着我们来看一下如何描述将符号重复0次或多次。重复是指相同的符号X并排出现多次的模式。

例如，C语言（C♭）的代码块中可以记载0个或多个语句的排列，我们来试着描述一下。下面的写法就能表示0个或多个语句（stmt:statement）排列。

（stmt（　））＊

和正则表达式相同，＊是表示重复0次或多次的特殊字符。并且此处stmt（　）两侧的括号不能省略。

再来看一个例子。函数的参数是由逗号分隔的表达式（expr:expression）排列而成的。换种说法就是expr之后排列着0个或多个逗号和expr的组合。这样的规则在JavaCC中写成如下形式。

expr（　）（", " expr（　））＊

上述表述中，＊的作用域是与其紧挨着的左侧括号中的内容，也就是说，作用对象是逗号和expr这两者。因此上述规则能够表现下面这样的符号列。

expr（　）
expr（　）", " expr（　）
expr（　）", " expr（　）", " expr（　）
expr（　）", " expr（　）", " expr（　）", " expr（　）
              …
              …

在编程语言的语法中，“期间○○重复多次”是非常常见的，因此请将刚才的写法作为常用的语法描述记忆下来。

重复1次或多次

刚才我们看了重复0次或多次，JavaCC同样可以表示重复1次或多次。和正则表达式一样，重复1次或多次也使用+写成如下形式。

（stmt（　））+

上述代码描述了非终端符stmt（　）重复1次或多次。如果stmt（　）是语句的话，（stmt（　））+就是1个或多个语句的排列。

选择

接着是符号的选择（alternative）。选择是指在多个选项中选择1个的规则，比如选择符号A或者符号B。

例如C♭的类型有void、char、unsigned char等，可以写成如下形式。

<VOID> | <CHAR> | <UNSIGNED> <CHAR> | ……

即<VOID>或<CHAR>或<UNSIGNED><CHAR>或……的意思。

可以省略

某些模式可能出现0次或1次，即可以省略。表示这样的模式时使用[]。

以变量的定义为例。定义变量时可以设置初始值，但如果不设置的话也没有问题。也就是说，初始值的记载是可以省略的。这样的情况下，在JavaCC中可以写成如下形式。

storage（　）typeref（　）name（　）["=" expr（　）] "; "

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

本节将介绍使用JavaCC进行语法分析时所遇到的各类问题，以及其解决方法之一——token的超前扫描。

语法的二义性

事实上，JavaCC并非能够分析所有用上一节叙述的方法（EBNF）所描述的语法。原因在于用EBNF描述的语法本质上存在具有二义性的情况。

举一个有名的例子，让我们试着考虑下C语言中if语句的语法。C语言中的if语句用JavaCC的EBNF可以如下这样描述。

"if" "（" expr（　）"）" stmt（　）["else" stmt（　）]

另一方面，作为符合上述规则的具体代码，我们来看一下下面的例子。

if（cond1）
    if（cond2）
        f（　）;
    else
        g（　）;

让我们根据刚才的规则试着分析下这段代码。

乍看之下会觉得第2个if和else是成对的，这一整体位于最初的if条件之下。加上括号后的代码如下所示。

if（cond1）{
    if（cond2）{
        f（　）;
    } else {
        g（　）;
    }
}

但实际上，如果不依赖直觉，仅依据刚才的规则仔细思考一下，下面这样的解释也是可能的。

if（cond1）{
    if（cond2）{
        f（　）;
        }
} else {
    g（　）;
}

也就是说，对于1份具体的代码，可以如图5-2这样生成2棵语法树。像这样对于单个输入可能有多种解释时，这样的语法就可以说存在二义性。

图5-2 对应两种解释的语法树

顺便说一下，C语言中的if语句的规则存在二义性的问题是比较有名的，俗称空悬else（dangling else）。

JavaCC的局限性

刚才的空悬else问题，其语法在本质上就存在二义性。除此之外，也存在因为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的选择冲突（choice conflict）。

提取左侧共通部分

值得庆幸的是，当你写了会发生选择冲突的规则的情况下，若用JavaCC处理该语法描述文件，就会给出如下警告消息。因此如果是无法分析的语法，马上就能知道。

$ javacc Parser.jj
Java Compiler Compiler Version 4.0（Parser Generator）
（type "javacc" with no arguments for help）
Reading from file Parser.jj . . .
Warning: Choice conflict involving two expansions at
          line 642, column 8 and line 643, column 7 respectively.
          A common prefix is: "unsigned"
          Consider using a lookahead of 2 for earlier expansion.
Parser generated with 0 errors and 1 warnings.

像这样，消息中如果出现了Choice conflict字眼，就说明发生了选择冲突。

解决上述问题的方法有两个，其中之一就是将选项左侧共通的部分提取出来。以刚才的规则为例，修改为如下这样即可。

type（　）: {}
{
      <SIGNED>（<CHAR> | <SHORT> | <INT> | <LONG>）
      ……

这样就不会发生选择冲突了。

当遇到JavaCC的上述局限性时，应首先考虑是否可以用提取共通部分的方法来处理。但还是存在使用此方法仍然无法描述的规则，以及提取共通部分的处理非常复杂的情况，这样的情况下就可以通过接下来要讲的“token的超前扫描”来解决。

token的超前扫描

之前提到了JavaCC在遇到选项时仅根据读取的1个token来判断选择哪个选项。事实上这只是因为JavaCC默认仅根据读取的1个token进行判断。只要明确指定，JavaCC可以在读取更多的token后再决定选择哪个选项。这个功能就称为token的超前扫描（lookahead）。

刚才列举的语法规则也能够用token的超前扫描进行分析，为此要将规则写成如下形式。

type（　）: {}
{
      LOOKAHEAD（2）<SIGNED> <CHAR>       // 选项1
    | LOOKAHEAD（2）<SIGNED> <SHORT>      // 选项2
    | LOOKAHEAD（2）<SIGNED> <INT>        // 选项3
    | <SIGNED> <LONG>                     // 选项4
      以下省略

添加的LOOKAHEAD（2）是关键。LOOKAHEAD（2）表示的意思为“读取2个token后，如果读取的token和该选项相符合，则选择该选项”。也就是说，读取2个token，如果它们是<SIGNED>和<CHAR>的话，就选用选项1。同样，第2个选项的意思是读取2个token，如果它们是<SIGNED>和<SHORT>的话，就选用选项2。

需要超前扫描的token个数（上述例子中为2）是通过“共通部分的token数+1”这样的算式计算得到的。例如，上述规则中选项之间的共通部分为<SIGNED>，只有1个，因此需要超前扫描的token个数为在此基础上再加1，即2。

为什么这样能够解决问题呢？因为只要读取了比共通部分的token数多1个的token，就一定能读到非共通部分的token，也就是说，能够读到各选项各自特有的部分。经过了这样的确认后再进行选择就不会有问题了。

最后的选项（选项4）不需要使用LOOKAHEAD。这是因为LOOKAHEAD是在还剩下多个选项时，为了延迟决定选择哪个选项而使用的功能。

正如之前所讲的那样，JavaCC会优先选用先描述的选项，因此，当到达最后的选项即意味着其他的选项都已经被丢弃，只剩下这最后1个选项了。在只剩下1个选项时，即便推迟选择也是没有意义的。如果和任何一个选项都不匹配的话，那只能是代码存在语法错误了。

最后，无法获知“共通部分的token数”的情况也是存在的。这样的例子以及解决方案将在稍后介绍“更灵活的超前扫描”这一部分时进行讨论。

可以省略的规则和冲突

除“选择”以外，选择冲突在“可以省略”或“重复0次或多次”中也可能发生。

可以省略的规则中，会发生“是省略还是不省略”的冲突，而非“选择选项1还是选项2”的冲突。之前提到的空悬else就是一个具体的例子。空悬else的问题在于内侧的if语句的else部分是否省略（图5-3）。如果内测的if语句的else部分没有省略，则else部分属于内侧的if语句，如果省略的话则属于外侧的if语句。

图5-3 空悬else问题和冲突

空悬else最直观的判断方法是“else属于最内侧的if”，因此试着使用LOOKAHEAD来进行判断。首先，未使用LOOKAHEAD进行判断的规则描述如下所示。

if_stmt（　）: {}
{
    <IF> "（" expr（　）"）" stmt（　）[<ELSE> stmt（　）]
}

使用LOOKAHEAD来避免冲突发生的规则如下所示。

if_stmt（　）: {}
{
    <IF> "（" expr（　）"）" stmt（　）[LOOKAEHAD（1）<ELSE> stmt（　）]
}

如你所见，判断方法本身非常简单。通过添加LOOKAHEAD（1），就可以指定“读取1个token后，如果该token符合规则（即如果是<ELSE>）则不省略<ELSE> stmt（　）”。这样就能明确else始终属于最内侧的if语句，空悬else的问题就可以解决了。

重复和冲突

重复的情况下会发生“是作为重复的一部分读入还是跳出重复”这样的选择冲突。

来看一个具体的例子，如下所示为C♭中表示函数形参的声明规则。

param_decls（　）: {}
{
    type（　）（", " type（　））＊ [", " "..."]
}

这个规则中，表示可变长参数的", " "..."不会被解析。原因大家应该知道的吧。

根据上述规则，在读取type（　）后又读到", "时，本来可能是", " type（　）也可能是", " "..."的，但JavaCC默认向前只读取1个token，因此在读到", "时就必须判断是继续重复还是跳出重复。并且恰巧", "和（", " type（　））的开头一致，所以JavaCC会一直判断为重复（", " type（　））＊，而规则", " "..."则完全不会被用到。实际上如果程序中出现", ""..."，会因为不符合规则", " type（　）而判定为语法错误。

要解决上述问题，可以如下添加LOOKAHEAD。

param_decls（　）: {}
{
    type（　）（LOOKAHEAD（2）", " type（　））＊ [", " "..."]
}

这样JavaCC在每次判断该重复时就会在读取2个token后再判断是否继续重复，因此在输入了", " "..."后就会因为检测到和", " type（　）不匹配而跳出（", " type（　））＊的重复。

更灵活的超前扫描

关于token的超前扫描，JavaCC中还提供了更为灵活的方法。之前提到的LOOKAHEAD可以指定“恰好读取了几个token”，除此之外还可以指定“读取符合这个规则的所有token”。

让我们来看一下需要用到上述功能的例子。请看下面的规则。

definition（　）: {}
{
      storage（　）type（　）<IDENTIFIER> "; "
    | storage（　）type（　）<IDENTIFIER> arg_decls（　）block（　）
    以下省略

上述是C♭的参数定义和函数定义的规则。左侧的部分完全一样，也就是说，这样的规则也会发生选择冲突。虽说可以通过提取左侧共通部分来解决问题，但这次让我们考虑尝试用超前扫描的方法。

用超前扫描来分析上述规则，读取“恰好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个选项了。

超前扫描的相关注意事项

这里讲一个和token的超前扫描相关的注意事项。

即便写了LOOKAHEAD也并非一定能按照预期对程序进行分析。添加LOOKAHEAD后Choice conflict的警告消息的确消失了，但实际上JavaCC不会对LOOKAHEAD描述的内容进行任何检查。在发生选择冲突的地方加上LOOKAHEAD后不再显示警告，仅此而已。LOOKAHEAD处理的描述是否正确，我们必须自己思考。