词法分析——基础内容

基本定义

词法分析是编译器前端的第一阶段，它负责将文本输入转化为词素并提供给语法分析器。除此之外，词法分析器通常还负责将无用的注释和空白符去掉，将语法分析产生的错误对应到正确的位置，偶尔还负责将宏展开。

在讨论词法分析时，我们使用以下这些名词：

词法单元是一个表示某种词法单位（比如一个关键字）的抽象符号，通常由词法单元名和属性构成。我们使用黑体字$\mathbf{lex}$表示一个词法单元。
词素是源程序中的一个字符串，是某个词法单元的实例。
模式表示词法单元的词素所具有的形式。如果一个字符串和某个词法单元的模式匹配，那么它就是这个词法单元的一个实例。

例如，C语言中的字符串字面量$\mathbf{literal}$的模式就是被双引号包括的字符串，而"string"就是其一个词素。

通常语言中的词法单元分为五类：

关键字：一般每个关键字对应一个词法单元；
运算符：可以每个运算符对应一个词法单元，也可以一类运算符对应一个词法单元；
标识符：变量名、函数名和类型名等标识符通常对应一个词法单元（和符号表内的条目）；
字面量：整数、浮点数和字符串常量等通常对应一个词法单元；
分隔符：左右括号、逗号和分号（甚至空格）通常对应一个词法单元。

如果多个不同的词素可以和同一模式匹配（如+、-都是运算符、114、514都是数字），那么需要额外的信息来区别它们。因此，除了词法单元名之外，词法分析器还需要为语法分析提供额外的信息。这种信息就是词法单元的属性。特别地，对于标识符$\mathbf{id}$来说，其词法单元通常对应符号表中的一个条目，而信息一般放在符号表中，而非词法单元的属性中。这些信息通常包括其词素（即标识符的名字）、类型和初次出现的位置，其生命周期贯穿整个编译始终，甚至在链接时也会大量使用。

词法分析器很难独自发现程序中的错误，因为其对程序的了解实在有限。但是如果源程序不能和任何一个模式匹配，那么显然出现了错误。词法分析器有多种处理错误的方式，最常见的错误恢复策略称为“恐慌模式”恢复，即从剩余输入中不断删去字符直到可以进行匹配为止。

正则表达式

在本节中，我们将形式化地定义正则表达式，并用它来表示词法单元的模式。虽然正则表达式不能表示所有模式，但对于计算机程序来说已经绰绰有余了。

我们先给出几个基本的定义。

字母表是一个有限的符号的集合。
字母表上的字符串，简称串，是此字母表中符号的一个有限序列。串$s$的长度，记为$|s|$，是其中含有的符号的个数。长度为零的串称为空串，记为$\epsilon$。
形式语言，或简称语言，是给定字母表上任意可数的串的集合。

这个语言的定义是相当宽泛的，比如空集和仅含空串的集合都是语言。不严格地说，所有语法正确的自然语言组成的句子的集合也是形式语言。

在处理串时我们会经常使用以下术语：

前缀；
后缀；
字串；
真前缀、真后缀、真子串；
子序列；
连接。

这些术语和其在算法设计中的通常定义没有区别。需要注意的是，空串是连接运算的单位元，任何串在前面或后面连接空串都能得到原串。

语言的运算

我们先定义语言之间的运算：

两个语言的连接就是以两个语言按顺序取串并连接形成的新串组成的语言。形式化地说，设$L, M$为两个语言，那么其连接为： $LM = \left\{ st \; \middle| \; s \in L , \; t \in M \right\}$ 此外，我们递归地定义 $L^{i} = L^{i-1} L, \quad L^0 = \{ \epsilon \}$ 两个语言的并即这两个集合的并。形式化地说，设$L, M$为两个语言，那么其并为： $L \cup M = \left\{ s \; \middle| \; s \in L \; \mathrm{or} \; s \in M \right\}$ 语言的克莱尼星号（Kleene star，也称克莱尼闭包）为其所有次幂的并： $L^* = \bigcup_{i=0}^\infty L^i$ 语言的克莱尼加号，或称正闭包，为其所有非零幂次的并： $L^+ = \bigcup_{i=1}^\infty L^i$

如果我们设$L$表示所有字母的集合，那么$L^4$表示所有四个字母的串组成的集合，$L^*$表示所有由字母组成的串组成的集合（含空串）。

如果熟悉正则表达式，不难发现，正则表达式中的星号和加号表示的是同样的意思。

正则表达式的形式定义

我们设$L(a)$表示正则表达式$a$所表示的语言，用以下归纳法递归地给出正则表达式的形式定义：

归纳基础：
1. $\epsilon$是一个正则表达式，且$L(\epsilon) = \{\epsilon\}$；
2. 任何字母表中的单个字符构成一个正则表达式，其语言是其自身。
归纳步骤：设$r,s$为两个的正则表达式，那么：
1. $(r)|(s)$是一个正则表达式，表示$L(r) \cup L(s)$；
2. $(r)(s)$是一个正则表达式，表示$L(r) L(s)$；
3. $(r)^*$是一个正则表达式，表示$L(r)^*$；
4. $(r)$是一个正则表达式，表示$L(r)$，即在正则表达式两侧加上括号对其没有影响。

接下来，我们规定，克莱尼星号具有最高的优先级，连接运算次之，并运算最低，且都是左结合的。那么，我们可以省掉一些括号：如$(a) | ((b)^*(c))$就和$a | b^* c$规定了同一种语言。

可以用正则表达式表示的语言称为正则语言，如果两个正则表达式表示的语言相同，那么称其为等价的，记为$r = s$。

承接上文关于语言的运算的定义，我们可以发现正则表达式之间的运算满足一些代数性质：

并运算是可交换、可结合的：$r | s = s | r, \; r | (s | t) = (r | s) | t$；
连接运算是可结合的：$(rs)t = r(st)$；
连接运算关于并运算是左右可分配的：$r(s|t) = rs | rt \quad (s|t)r = sr | tr$；
空串是连接运算的单位元：$\epsilon r = r \epsilon = r$；
克莱尼星号具有幂等性：$r^{**} = r^*$。

正则定义

为了给正则表达式命名，我们引入正则定义的概念：

设$\Sigma$为一字母表，那么正则定义是具有以下形式的定义序列： $\begin{aligned} d_1 &\to r_1 \\ d_2 &\to r_2 \\ &\vdots \\ d_n &\to r_n \end{aligned}$ 其中，$d_1, d_2, \dots , d_n \not\in \Sigma$，且$r_i \in \Sigma \cup \{ d_1, d_2, \dots , d_{i-1} \} $。

我们规定第$i$项只能使用此前的定义，以避免循环定义的问题。显然，我们可以通过递归地将$d_i$替换成其定义来把所有正则表达式转化为在$\Sigma$这一字母表上的表达式。

比方说，以下正则定义中的$id$就是C语言标识符的模式： $\begin{aligned} letter\_ &\to A | a | B | b | \cdots | Z | z | \_ \\ digit &\to 0 | 1 | \cdots | 9 \\ id &\to letter\_ (letter\_ | digit)^* \end{aligned}$

正则表达式的拓展

现在各种程序设计语言中可用的正则表达式和上文介绍的大同小异，只是通常提供了几个拓展：

匹配一次或多次（+）：类比克莱尼加号，我们为正则表达式附加一个加法预算，规定$(r)^+$对应的语言为$(L(r))^+$；
匹配一次或零次（?）：规定$(r)?$对应的语言为$(L(r)) \cup \{ \epsilon \}$，这两个运算的优先级和结合性和星号相同；
字符类：几乎所有正则表达式语言都提供表示或运算的简便方式，比如通常[a-b]就表示$a|b| \cdots |z$；
助记符：诸如^通常表示取反匹配、$通常表示匹配行末等。

识别模式

我们已经给出了利用正则表达式描述模式的方法，接下来需要解决的问题就是如何判定一个字符串是否匹配某一模式。

为方便起见，我们假设语言的所有关键字都是保留字，即虽然关键字可以和其他模式（如标识符）匹配，但总是把它们当作关键字而非其他词法单元。我们还规定词法分析器会“吃掉”所有空白符，即空白符不会进入语法分析，这是通过让其识别词法单元ws做到的： $ws \; \to \; ( \, \text{空格} \, | \, \text{制表符} \, | \, \text{换行符} \, )^*$

接下来我们规定以下正则定义，用来作为识别的例子： $\begin{aligned} digit &\to \mathrm{[0-9]} \\ digits &\to digit^+ \\ number &\to digits \; (. \; digits)? (\mathrm{E} \; [+-]? \; digits)? \\ letter &\to \mathrm{[A-Za-z]} \\ id &\to letter \; (letter|digit)^* \\ if &\to \mathrm{if} \\ then &\to \mathrm{then} \\ else &\to \mathrm{else} \\ relop &\to \mathrm{<} | \mathrm{>} | \mathrm{<=} | \mathrm{>=} | \mathrm{=} | \mathrm{<>} \end{aligned}$ 此外，我们希望对任意number和id词素，其属性都是其在符号表中对应条目的指针。对任意relop词素，其属性都是其运算符的名字，依次为：LT、GT、LE、GE、EQ、NE。

状态转移图

为了方便讨论，我们假设整个源程序被整个读入无限大的缓冲区之中。我们附加两个指针，lexemeBegin表示目前这个词素的开始位置，而词法分析器希望找到这个词素的结尾； forward指针表示当前正在处理的字符的位置，它将不断前进直到可以确定这个词素的结尾。发现结尾之后，lexemeBegin将移动至forward指针的位置，以便处理下一个词素。

为了处理正则表达式的识别，我们提出状态转移图：

状态转移图是这样一张有向图：其结点表示一个状态，其边带有标号。如果当前处于某个状态，且发现下一个字符，那么如果存在从该状态出发且标号和此字符相同的边，那么将向其所指向的状态移动。如果对任意的状态和任意的字符，满足上述条件的边至多只有一条，那么我们称其为确定的。

某些特别的状态称为接受状态或终止状态，如果当前状态到达这些状态，那么说明已经找到一个词素的末尾。如果我们需要词法分析做出某些动作，那么这些动作的代码也写在该状态旁。

有些时候，我们希望将forward指针退回，这可能是因为词素并不包含到达终止状态之前那一个字符。如果我们希望退回这个指针，那么我们在状态旁以星号标记。有几个星号就将指针退回几次。

有一个状态为开始状态，这是由一条标记为START的边指出的。在读入任何输入之前，其总是处于开始状态。

上图所示的状态转移图可以用来识别上文中的所有relop定义，并给出所识别的运算的属性。需要注意的是几个状态上的星号。如果某个词素的前缀是另一个词素，那么为了区别这两个词素就需要用星号将forward指针回退。

区别关键字与标识符

我们注意到，在上述正则定义中，所有的关键字（if、else、then），都是字母开头且只含字母，因此是合法的标识符（id）。我们已经假设，所有关键字都是保留字，从而它们不可能是标识符。为了区别关键字和标识符，我们主要采用两种手段。

提前把保留字填入符号表中。所有标识符都有对应的符号表条目，如果识别到标识符，那么就检查符号表条目，如果已经标记为关键字，就不再把它当作标识符处理。
为每个关键字单独建立状态转移图。我们可以为每个关键字单独建立转移图，但是要小心不要让匹配过于贪心，比如将ifonly这个标识符识别成if关键字和only标识符。通常我们可以在其接受状态之前添加一个非字母数字的边，这样只有前缀为对应关键字，且下一个符号不是字母或数字才会识别为关键字。此外，不要忘记if这样的关键字仍然能被识别为标识符。我们还必须仔细调整不同模式的优先级，使得可以同时识别为标识符和关键字时，优先识别为关键字。

实现细节

我们为每一个模式都建立好状态转移图后，就可以考虑着手编写程序了。下面是为relop编写的程序示例：

TOKEN getRelop()
{
    TOKEN retToken = new Relop();
    int state = 0;
    while(1)
    {
        switch(state)
        {
        case 0:
            c = nextchar();	// 读取字符并前进forward指针
            if(c == '<') state = 1;
            else if (c == '=') state = 5;
            else if (c == '>') state = 6;
            else throw UnrecognizedLexeme();
        case 1:
            // ...
        case 8:
            retract();  // 撤回forward指针
            retToken.attrib = GT;
            return retToken;
        default:
            throw UnexpectedState();
        }
    }
}

可以注意到我们隐式地使用了状态转移图，而非显式地构建这张图。

当然，这仅仅是一种词素的识别方法。为了构建整个正则定义的识别器，也就是词法分析器，我们需要为每种词法单元构建一个这种函数，然后把它们综合起来。有三种方法可以构建分析整个正则定义的分析器：

顺序尝试每个词法单元。每次抛出UnrecognizedLexeme异常时，主函数（或驱动函数）就重置forward指针并尝试下一种词法单元。这样的话，只需要保证先尝试关键字，再尝试标识符，就可以识别出保留字了。
并行尝试每个语法单元。这一策略和上一策略大同小异，但是需要小心处理某一个状态转移图已经达到接收状态，而还有其他转移图仍可以接受字符的情况。通常我们采用最大匹配的策略，即出现多个接受状态时选择匹配的字符串最长的那个。
将所有状态转移图按某种方法组合到一起。这是最常见的做法。

可以发现，状态转移图和自动机相当相似。而最后一种方法所组成的产物就是一个自动机。我们将在下一篇文章仔细考察这种方法。

Twitter Facebook LinkedIn

词法分析——基础内容

基本定义

正则表达式

语言的运算

正则表达式的形式定义

正则定义

正则表达式的拓展

识别模式

状态转移图

区别关键字与标识符

实现细节

分享

猜您还喜欢

微正则系综

统计物理导论

摄动与变分理论

傅里叶变换与采样