第4章 词法分析

本章将先介绍基于JavaCC的词法分析的相关内容，之后再介绍C♭的扫描器的实现。

4.1 基于JavaCC的扫描器的描述

本节将结合cbc的扫描器的代码，来介绍基于JavaCC描述扫描器的方法。

本章的目的

第3章中已经介绍过扫描器的作用，扫描器是将由编程语言描述的代码切分成单词，并同时给出单词的语义值。换言之，就是给出token序列。

那么要怎样用JavaCC来制作目标语言的扫描器呢？JavaCC采用正则表达式（regular express）的语法来描述需要解析的单词的规则，并由此来表现扫描器。

正则表达式是以指定字符串模式为目的的微型语言。Linux上的grep命令、awk命令、Perl等，很多情况下都可以使用正则表达式，因此知晓什么是正则表达式的人还是比较多的。如果还不知道正则表达式，也请借此机会试着学习一下。

另外，JavaCC的正则表达式和grep等所使用的正则表达式即便功能相同，字面表述也完全不一样。直接使用grep等的正则表达式的话，将无法按照预期正常运行，这点请注意。

JavaCC的正则表达式

我们来讲解一下JavaCC所使用的正则表达式。首先，JavaCC的正则表达式能够描述的模式如表4-1所示。

表4-1 JavaCC的正则表达式

下面按顺序详细讲解。

固定字符串

JavaCC中要描述“和字符串自身相匹配的模式”时，可以用双引号（""）括起来，比如像"int"和"long"这样。

这里的“匹配”是“适合”“符合”的意思。当字符串很好地符合由正则表达式描述的字符串模式时，就可以说“字符串匹配模式”。例如字符串"int"匹配模式"int"。

连接

像"ABC"之后接着"XYZ"这样表示模式连续的情况下，只需接着上一个模式书写即可。例如"ABC"之后接着"XYZ"的模式如下所示。

"ABC" "XYZ"

像这样由连续模式表现的正则表达式的模式称为连接（sequence）。

上面的例子是固定字符串的连接，因此写成"ABCXYZ"也是一样的。当和之后讲述的模式组合使用时，连接模式就能够体现其价值。

字符组

想要表示“特定字符中的任一字符”时，可以使用方括号，像["X", "Y", "Z"]这样表示，该模式匹配字符"X"或"Y"或"Z"。像这样指定字符的集合称为字符组（character class）。

还可以用中划线“-”来指定字符的范围。例如["0"-"9"]表示字符"0"到"9"范围内包含的字符都能够匹配。也就是说，它和["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]是相同的。

也可以组合使用“, ”和“-”。例如标识符中能够使用的字符（字母、数字或下划线）可以如下这样描述。

["a"-"z", "A"-"Z", "0"-"9", "_"]

排除型字符组

字符组通过指定集合中包含的字符来表现字符集合，反之也可以指定集合中不包含的字符。也就是说，能够描述像“数字之外的所有字符”这样的模式。这样的模式称为排除型字符组（negated character class）。

排除型字符组的写法如下所示，通常是在字符组前面加上“～”。

～["X", "Y", "Z"]

这样就能表示"X"、"Y"、"Z"以外的字符。

下面的写法能够表示任意一个字符，这是非常实用的排除型字符组的用法。

～[]

“[]”是不包含任何字符的字符组，因此将其反转就是包含所有字符。

重复1次或多次

JavaCC的正则表达式能够描述一个模式的重复，分为重复0次或多次和重复1次或多次。我们先从重复1次或多次开始讲解。

例如，要描述字符"x"重复1次或多次，可如下这样使用“+”。

（"x"）+

"x"两侧的括号无论在何种模式下都是必需的，这点请注意。

上述模式匹配"x"重复1次或多次，即和“x”“xx”“xxxxxxx”等匹配。

重复0次或多次

如果要描述重复0次或多次，可以如下这样使用“＊”。

（"x"）＊

使用“＊”时两侧的括号也是必不可少的。该模式和“x”“xx”“xxxxxx”以及“”（空字符）匹配。

和空字符匹配，这也是“＊”的关键之处（同时也是问题）。例如，调查一下模式（"y"）＊和字符串xxx的开头是否匹配。字符串xxx中一个y字符也没有，因此感觉是不匹配的，但实际是（"y"）＊和xxx的开头匹配。原因是字符串xxx的开头可以看作是长度为0的空字符。

像这样错误地使用“＊”很容易产生奇怪的现象。在使用“＊”时要注意，结合其他的模式，模式整体不能在不经意之间和空字符串匹配。

重复n次到m次

“重复0次或多次”和“重复1次或多次”都是重复次数上限不固定的模式，JavaCC的正则表达式还可以描述“重复n次到m次”的模式。要描述重复n次到m次，可以如下这样使用{n, m}。

（"o"）{3,9}

该模式和3个至9个字符的o相匹配。匹配的字符串的例子有“ooo”“oooooo”“ooooooooo”等。

正好重复n次

JavaCC的正则表达式也可以描述“正好重复n次”。如下所示，使用{n}来描述正好重复n次。

（["0"-"7"]）{3}

该模式和3个0到7范围内的数字字符相匹配。匹配的字符串的例子有“000”“345”“777”等。

可以省略

要表示某个模式出现0次或1次，即可以省略，如下这样使用“? ”即可。

（"0x"）?

上述模式描述了"0x"是可有可无（可以省略）的。还要注意的是两侧的括号是必需的。

例如很多语言中的整数字面量能够添加正号和负号，但也可以省略。这样的模式可以如下这样描述。

（["+", "-"]）?（["0"-"9"]）+

该模式和“5”“+1”“-35”等匹配。

选择

最后的模式是“选择”，能够描述“A或者B或者C”这样“选择多个模式中的一个”的模式。

例如描述“"ABC"或者"XYZ"”，如下这样使用竖线“|”即可。

"ABC" | "XYZ"

请注意“|”的优先级非常低。例如有如下这样的模式，你知道选择对象的范围是从哪里到哪里吗？

"A" "B" | "C" "D"

正确的答案是“模式全体”，即如下这样解读。

（"A" "B"）|（"C" "D"）

而不是像下面这样只是将"B"和"C"作为选择的对象。

"A"（"B" | "C"）"D"

如果想按上述这样解读的话，要明确地用括号括起来。

4.2 扫描没有结构的单词

从本节开始我们将实际使用JavaCC来制作cbc的扫描器。

首先来看一下用JavaCC的TOKEN命令对最简单的标识符和保留字进行扫描的方法。

TOKEN命令

JavaCC中扫描token要像下面这样使用TOKEN命令（TOKEN directive），并排记载token名和正则表达式。

TOKEN: {
      <token名1 : 正则表达式1>
    | <token名2 : 正则表达式2>
    | <token名3 : 正则表达式3>
          …
          …
    | <token名n : 正则表达式n>
}

这样记载后就会生成扫描器，扫描器扫描符合正则表达式模式的字符串并生成对应的token。

并且TOKEN命令的块在一个文件中可以出现任意多次，因此按照逻辑上的相关性分开记载TOKEN命令比较好。

扫描标识符和保留字

cbc中扫描标识符和保留字的部分是最简单的，下面让我们一起来看一下这部分的代码示例（代码清单4.1）。

代码清单4.1 扫描标识符和保留字（parser/Parser.jj）

TOKEN: {
      <VOID      : "void">
    | <CHAR      : "char">
    | <SHORT     : "short">
    | <INT       : "int">
    | <LONG      : "long">
    | <STRUCT    : "struct">
    | <UNION     : "union">
    | <ENUM      : "enum">
    | <STATIC    : "static">
    | <EXTERN    : "extern">
    | <CONST     : "const">
    | <SIGNED    : "signed">
    | <UNSIGNED : "unsigned">
    | <IF        : "if">
    | <ELSE      : "else">
    | <SWITCH    : "switch">
    | <CASE      : "case">
    | <DEFAULT_ : "default">
    | <WHILE     : "while">
    | <DO        : "do">
    | <FOR       : "for">
    | <RETURN    : "return">
    | <BREAK     : "break">
    | <CONTINUE : "continue">
    | <GOTO      : "goto">
    | <TYPEDEF  : "typedef">
    | <IMPORT    : "import">
    | <SIZEOF    : "sizeof">
}


TOKEN: {
    <IDENTIFIER: ["a"-"z", "A"-"Z", "_"]（["a"-"z", "A"-"Z", "_", "0"-"9"]）＊>
}

第1个TOKEN命令描述了保留字的规则，第2个TOKEN命令描述了标识符的规则。保留字的正则表达式都是固定字符串的模式，很容易理解。意思是发现固定字符串"void"就生成VOID token，发现"char"就生成CHAR token……

与之相比，IDENTIFIER的正则表达式就稍显复杂。该模式描述了第1个字符是字母或下划线，第2个字符及以后是字母、下划线或数字这样的规则。

选择匹配规则

严谨地思考一下的话，刚才说明的内容其实存在模棱两可之处。例如，代码中写有voidFunction的话会生成何种token呢？理想的情况当然是生成IDENTIFIER的token，但开头的void部分和VOID token的正则表达式匹配，所以也有可能生成VOID token。

事实上voidFunction不会生成VOID的token。原因是JavaCC会同时尝试匹配所有的正则表达式，并选择匹配字符串最长的规则。voidFunction和VOID token的正则表达式匹配的部分是只有4个字符的void，而IDENTIFIER token的正则表达式和voidFunction的12个字符匹配。12个字符比4个字符长，因此对于voidFunction, JavaCC会生成IDENTIFIER token。

那么和多个规则的正则表达式匹配的字符串长度相同的情况下又会怎样呢？例如代码void f（　），和VOID token以及IDENTIFIER token的正则表达式都匹配void这4个字符。

像这样和多个规则的正则表达式匹配的字符串长度相同的情况下，JavaCC优先选择在文件中先定义的token规则。也就是说，如果VOID token的规则写在IDENTIFIER token规则之前，那么生成VOID token。而如果IDENTIFIER token的规则先定义的话，则生成IDENTIFIER token。

因此，如果将IDENTIFIER token的规则定义写在保留字的规则之前，那么所有保留字都会被扫描成为IDENTIFIER token，所以所有保留字的规则必须在写在IDENTIFIER的规则之前。

扫描数值

作为使用TOKEN命令的另一个例子，我们来看一下扫描数值的代码。cbc中相应部分的代码如代码清单4.2所示。

代码清单4.2 扫描数值（parser/Parser.jj）

TOKEN: {
    <INTEGER: ["1"-"9"]（["0"-"9"]）＊（"U"）?（"L"）?
            | "0" ["x", "X"]（["0"-"9", "a"-"f", "A"-"F"]）+（"U"）?（"L"）?
            | "0"（["0"-"7"]）＊（"U"）?（"L"）?
            >
}

这次的正则表达式稍微有些复杂，我们试着将其分解后来看。

首先是下列3个正则表达式的组合，从上到下分别是十进制、十六进制、八进制的数值字面量的模式。

["1"-"9"]（["0"-"9"]）＊                            （"U"）?（"L"）?
"0" ["x", "X"]（["0"-"9", "a"-"f", "A"-"F"]）+（"U"）?（"L"）?
"0"（["0"-"7"]）＊                                   （"U"）?（"L"）?

上述各个正则表达式中用到的模式有下面这些。

["1"-"9"]

0以外的1位数字

["0"-"9"]

任意1位数字

（["0"-"9"]）＊

任意的数字，0位或多位排列

（"U"）?

可省略的字符"U"

（"L"）?

可省略的字符"L"

["x", "X"]

字符"x"或字符"X"

["0"-"9", "a"-"f", "A"-"F"]

任意1位数字或a～f、A～F的任意1个字符（十六进制的字符）

（["0"-"9", "a"-"f", "A"-"F"]）+

十六进制字符1位或多位排列

["0"-"7"]

0到7的1位数字（八进制的字符）

（["0"-"7"]）＊

八进制字符0位或多位排列

（"U"）?（"L"）？这两部分是等同的。该模式下两者都省略的话为“”（空字符）；省略一者的话为“U”或“L”；两者都不省略的话是“UL”。这可以用来描述表示数值类型的结尾词“U”“L”“UL”。

4.3 扫描不生成token的单词

本节将介绍空白符和注释这种不生成token的字符串的扫描方法。

SKIP命令和SPECIAL TOKEN命令

上一节中介绍的都是生成token的规则，例如扫描到"void"会生成VOID token。

与之相对，编程语言的代码中存在本身不具有意义的部分，例如空白符和注释，这一部分在扫描后必须跳过。

要跳过这部分代码，可以如下使用SKIP命令（SKIP directive）。

SKIP: {
      <token名： 模式>
    | <token名： 模式>
          …
          …
    | <token名： 模式>
}

不使用TOKEN命令而使用SKIP命令的话就不会生成token，因此使用SKIP命令可以省略token名。

还可以用SPECIAL_TOKEN命令（SPECIAL_TOKEN directive）来跳过token。SKIP命令和SPECIAL_TOKEN命令的区别在于是否保存跳过的token。使用SKIP命令无法访问跳过的字符串，使用SPECIAL_TOKEN命令就可以借助下面被扫描的TOKEN对象来取得跳过的字符串。相应的方法将在第7章详细说明。

跳过空白符

让我们试着看一下使用SKIP命令和SPECIAL_TOKEN命令的例子。从cbc的代码中提取出跳过token之间的空白符的规则，如代码清单4.3所示。

代码清单4.3 跳过空白符（parser/Parser.jj）

SPECIAL_TOKEN: { <SPACES:（[" ", "\t", "\n", "\r", "\f"]）+> }

[" ", "\t", "\n", "\r", "\f"]表示" "（空格）、"\t"（制表符）、"\n"（换行符）、"\r"（回车）、"\f"（换页符）之中的任意一个，后面加上“+”表示上述5种字符之一1个或多个排列而成的字符串。

因为使用了SPECIAL_TOKEN命令，所以上述描述表示读取并跳过由空格、制表符、换行、回车、换页符之中的任意一个排列组成的字符串。

另外，因为使用了SPECIAL_TOKEN命令而非SKIP命令，所以读取跳过的部分可以通过下面要扫描的Token对象进行访问。

跳过行注释

再来看一下另一个扫描后不生成token的例子。扫描行注释的cbc代码如代码清单4.4所示。代码清单4.4跳过行注释（parser/Parser.jj）

SPECIAL_TOKEN: {
    <LINE_COMMENT: "//"（～["\n", "\r"]）＊（"\n" | "\r\n" | "\r"）? >
}

这里又用到了新的模式，同样让我们按顺序来看一下。

"//"

字符串“//”

["\n", "\r"]

换行（"\n"）或回车（"\r"）

～["\n", "\r"]

换行（"\n"）或回车（"\r"）以外的字符

（～["\n", "\r"]）＊

换行（"\n"）或回车（"\r"）以外的字符0个或多个排列

"\n"|"\r\n"|"\r"

各种平台上的换行符

（"\n"|"\r\n"|"\r"）?

换行符，可省略

总结一下，上述代码所描述的模式是以“//”开始，接着是换行符以外的字符，并以换行符结尾的字符串。简单来说，这里描述的是从“//”开始到换行符为止的字符串。文件的最后可能没有换行符，因此换行符是可以省略的。

4.4 扫描具有结构的单词

本节将为大家介绍对块注释和字符串字面量这样有起始符号和终结符号的token的扫描方法。

最长匹配原则和它的问题

让我们试着思考一下块注释（/＊......＊/）的扫描方法。这个例子中包含了几个比较棘手的问题，让我们按顺序来看一下。

首先要注意的是下列模式是无法正确地扫描块注释的。

SKIP { <"/＊"（～[]）＊ "＊/"> }

如果这样写，那么直到注释的终结符为止都和模式“（～[]）＊”匹配，最终下面代码中底纹较深的部分都会被作为注释扫描。

import stdio;
          /＊ 本应只有这一行是注释…… ＊/
int
main（int argc, char ＊＊argv）
{
    printf（"Hello, World! \n"）;
    return 0;        /＊ 以状态0结束 ＊/
}

原因在于“～[]”和任意一个字符匹配，所以和“＊”“/”也是匹配的。并且“＊”模式会尽可能和最长的字符串进行匹配，因此结果就是和最后（第2处）出现的“＊/”之前的部分都匹配了。

这里的“尽可能和最长的字符串匹配”的方针称为最长匹配原则（longest match principle）。扫描块注释的情况下最长匹配原则表现得并不理想，但一般情况下最长匹配原则并不是太糟糕。也有一些其他的正则表达式的实现方式，但首先我们还是默认使用能够正确运行的最长匹配。

基于状态迁移的扫描

为了解决模式“（～[]）＊”在块注释的情况下过度匹配的问题，需要进行如下修改。

SKIP: { <"/＊"> : IN_BLOCK_COMMENT }
<IN_BLOCK_COMMENT> SKIP: { <～[]> }
<IN_BLOCK_COMMENT> SKIP: { <"＊/"> : DEFAULT }

上述例子中的IN_BLOCK_COMMENT是扫描的状态（state）。通过使用状态，可以实现只扫描代码的一部分。

让我们来讲解一下状态的使用方法。首先再看一下上述例子中的第1行。

SKIP: { <"/＊"> : IN_BLOCK_COMMENT }

这样在规则定义中写下{模式：状态名}的话，就表示匹配模式后会迁移（transit）到对应的状态。上述例子中会迁移到名为IN_BLOCK_COMMENT的状态。

扫描器在迁移到某个状态后只会运行该状态专用的词法分析规则。也就是说，在上述例子中，除了IN_BLOCK_COMMENT状态专用的规则之外，其他的规则将变得无效。

要定义某状态下专用的规则，可以如下这样在TOKEN等命令前加上<状态名>。

<状态名> TOKEN: {～}
<状态名> SKIP: {～}
<状态名> SPECIAL_TOKEN: {～}

再来看一下扫描块注释的例子中的第2行和第3行。

<IN_BLOCK_COMMENT> SKIP: { <～[]> }
<IN_BLOCK_COMMENT> SKIP: { <"＊/"> : DEFAULT }

只有当扫描器处于IN_BLOCK_COMMENT状态下时，这两个规则才有效，而其他规则在这个状态下将变得无效。

最后再看一下示例代码的第3行。

<IN_BLOCK_COMMENT> SKIP: { <"＊/"> : DEFAULT }

该行中的<"＊/">:DEFAULT也表示状态迁移，意思是匹配模式"＊/"的话就迁移到DEFAULT状态。

DEFAULT状态（DEFAULT state）表示扫描器在开始词法分析时的状态。没有特别指定状态的词法分析规则都会被视作DEFAULT状态。也就是说，至今为止所定义的保留字的扫描规则、标识符的规则以及行注释的规则实际上都属于DEFAULT状态。

<"＊/">:DEFAULT的意思是匹配模式"＊/"的话就回到最初的状态。

MORE命令

至此，扫描块注释的代码如下所示。

SKIP: { <"/＊"> : IN_BLOCK_COMMENT }
<IN_BLOCK_COMMENT> SKIP: { <～[]> }
<IN_BLOCK_COMMENT> SKIP: { <"＊/"> : DEFAULT }

但实际上上述代码仍然存在问题，上述代码在扫描过程中到达文件的尾部时会出现很糟糕的情况。

例如，对下面这样（存在语法错误）的C♭代码进行词法分析。

int
main（int argc, char ＊＊argv）
{
    return 0;
}
/＊ 文件结束

上述代码应该是忘记关闭块注释了。如果对上述程序进行处理，理想的情况是提示“注释未关闭”这样的错误，但如果使用刚才的词法分析规则，则不会提示错误而是正常结束。

未提示错误的原因在于使用了3个SKIP命令的规则进行扫描。像这样分成3个规则来使用SKIP命令的话，3个规则就会分别被视为对各自的token的描述，因此匹配到任何一个规则都会认为扫描正常结束。所以即使块注释中途结束，上述规则也无法检测出来。实际是用3个规则对一个注释进行词法分析，所以要将“这3个规则用于解析一个注释”这样的信息传给扫描器。

这时就可以使用MORE命令（MORE directive）。通过使用MORE命令，可以将一个token分割为由多个词法分析的规则来描述。

首先，使用MORE命令改进后的块注释的词法分析规则如下所示。

MORE: { <"/＊"> : IN_BLOCK_COMMENT }
<IN_BLOCK_COMMENT> MORE: { <～[]> }
<IN_BLOCK_COMMENT> SKIP: { <"＊/"> : DEFAULT }

第1行和第2行的SKIP命令被替换为了MORE命令，这样就能向扫描器传达“仅匹配该规则的话扫描还没有结束”。换言之，如果使用MORE命令扫描后遇到文件末尾，或无法和之后的规则匹配，就会发生错误。

因此只要使用MORE命令，在块注释的中途遇到文件结尾时就可以正确提示错误了。

跳过块注释

关于跳过块注释我们已经讨论了很多，这里再来总结一下。我们从cbc的代码中提取出扫描块注释的部分，如代码清单4.5所示。

代码清单4.5 跳过块注释（parser/Parser.jj）

MORE: { <"/＊"> : IN_BLOCK_COMMENT }
<IN_BLOCK_COMMENT> MORE: { <～[]> }
<IN_BLOCK_COMMENT> SPECIAL_TOKEN: { <BLOCK_COMMENT: "＊/"> : DEFAULT }

我们主要解决了两大问题。

首先，使用（～[]）＊这样一个模式一口气扫描注释的话，就会越过注释的终结符而引发过度匹配问题，因此我们引入了状态迁移对其进行改善。

其次，只使用SKIP命令或SPECIAL_TOKEN命令进行扫描的话，在注释的中途遇到文件结尾时就无法正确提示错误。因此除最后的规则之外我们全部使用MORE命令，以便能够明示扫描器正在扫描一个token。

解决了上述两个问题，就能够正确扫描块注释，也能够很好地处理错误了。

虽然看起来有些复杂，但所有具有起始符和终结符的单词都可以用类似的方法进行扫描。此后还将介绍类似的例子，所以请掌握状态迁移和MORE命令的用法。

扫描字符串字面量

让我们再来看一个使用MORE命令的例子。提取出字符串字面量（"Hello"等）的扫描规则，如代码清单4.6所示。字符串字面量同样具有起始符和终结符，所以也使用了状态迁移和MORE命令。

代码清单4.6 扫描字符串字面量（parser/Parser.jj）

MORE: { <"\""> : IN_STRING }                               // 规则1
<IN_STRING> MORE: {
      <（～["\"", "\\", "\n", "\r"]）+>                      // 规则2
    | <"\\"（["0"-"7"]）{3}>                                // 规则3
    | <"\\" ～[]>                                             // 规则4
}
<IN_STRING> TOKEN: { <STRING: "\""> : DEFAULT }         // 规则5

首先，借助状态迁移可以用多个规则来描述token。扫描到规则1的起始符“"”后迁移到IN_STRING状态，只有规则2、3、4在该状态下是有效的。

其次，除了最后的规则5之外，规则1～4都使用MORE命令将用多个规则扫描一个token这样的信息传达给了JavaCC。这样一来，在token扫描到一半而中途结束时就能够给出正确的错误提示。

扫描字符字面量

最后来看一下扫描字符字面量（'A’等）的代码。字符字面量的规则如代码清单4.7所示。代码清单4.7扫描字符字面量（parser/Parser.jj）

MORE: { <"'"> : IN_CHARACTER }                             // 规则1
<IN_CHARACTER> MORE: {
      <～["'", "\\", "\n", "\r"]> : CHARACTER_TERM       // 规则2
    | <"\\"（["0"-"7"]）{3}>       : CHARACTER_TERM       // 规则3
    | <"\\" ～[]>                    : CHARACTER_TERM       // 规则4
}
<CHARACTER_TERM> TOKEN: { <CHARACTER: "'"> : DEFAULT } // 规则5

从代码上看和字符串字面量的分析规则非常相似，但也有一些不同之处。相同之处在于扫描到规则1的起始符“'”之后迁移到IN_CHARACTER状态，但之后若扫描到一个字符或转义字符（escape sequence），则要迁移到CHARACTER_TERM状态。

至此我们所看过的块注释或字符串字面量中，从起始符到终结符之间的长度是任意的，但字符字面量的内容不允许超过一个字符的字面量，因此扫描到一个字符的内容后能接受的就只有终结符“'”了。这里迁移到CHARACTER_TERM状态即表示“下一个符号只接受终结符”。

SKIP : { < "/＊"（～["＊"]）＊（"＊"）+（～["/", "＊"]（～["＊"]）＊（"＊"）+）＊ "/" > }