2.1 字母表、串、克林闭包与语言

词法分析从一组非常小的数学对象开始：符号、串、以及串的集合。编译器看到的源代码首先是一段有限字符序列。它在讨论标识符（identifier）、数字（number）、关键字（keyword）、运算符（operator）、注释（comment）或空白（whitespace）之前，必须先精确说明哪些字符序列是合法的。形式语言理论提供的就是这套词汇。

字母表是一个非空有限符号集合，通常写作 Σ。这里的符号不一定是英文字母。对于二进制扫描器，Σ = {0, 1}。对于一个极小表达式语言，字母表可能包含字母、数字、+、*、(、)、空格和换行。对于词法分析器（lexer）实现，字母表也可能是输入流可包含的字符编码集合：ASCII、Unicode scalar value、byte，或者更紧凑的字符类字母表，例如 letter、digit、space、other。

串是由字母表中符号构成的有限序列。0011 是 {0, 1} 上的串。count42 是包含字母和数字的字母表上的串。空串写作 ε；它不包含任何符号，长度为 0。这个概念在编译器里很重要，因为很多模式都允许可选部分。数字字面量前面的符号可以有也可以没有。参数列表可以有 0 个参数。注释正文可以包含 0 个字符。

串作为代数对象

串有一组操作，编译器算法依赖这些操作的精确定义：

• |w| 表示串 w 的长度。
• w 的前缀（prefix）是从末尾删去零个或多个符号后得到的串。
• w 的后缀（suffix）是从开头删去零个或多个符号后得到的串。
• w 的子串（substring）是 w 内部连续的一段。
• 连接（concatenation）连接两个串：如果 x = ab 且 y = cd，那么 xy = abcd。
• 幂运算（exponentiation）重复一个串：$x^3 = xxx$，并且 $x^0 = ε$。
• 反转（reversal）反转顺序：如果 w = abc，那么 $w^R = cba$。

空串是连接的单位元：εw = wε = w。这个小事实到处都会出现。如果一个语法规则有可选部分，通常意味着该部分可以推导出 ε。如果一个自动机有空转移（epsilon transition），它可以不消耗输入就改变状态。如果一个正则表达式包含 a?，它的含义就是 a | ε。

固定长度层与克林闭包

$Σ^k$ 表示字母表 Σ 上所有长度为 k 的串的集合。如果 Σ = {a, b}，那么：

• $Σ^0 = {ε}$
• $Σ^1 = {a, b}$
• $Σ^2 = {aa, ab, ba, bb}$
• $Σ^3 = {aaa, aab, aba, abb, baa, bab, bba, bbb}$

一般来说，如果 |Σ| = n，那么 $|Σ^k| = n^k$。这解释了为什么穷举测试会迅速爆炸。假设有 80 个可能输入字符，长度为 5 的所有串已经有 $80^5 = 3,276,800,000$ 个候选。一个词法分析器不可能靠尝试所有字符串来验证正确性；它需要规范（specification）、生成器（generator）、精心挑选的例子和属性测试（property test）。

Σ 的克林闭包是 $Σ^*$，也就是 Σ 上所有有限串的集合：

正闭包（positive closure）是 $Σ^+$，它排除空串：

对于任何非空有限字母表，$Σ^*$ 是无限集合，但 $Σ^*$ 中的每一个具体串都是有限的。这个区别很关键。编译器读取的是有限源文件，但语言定义描述的是无限多个可能源文件的集合。

语言就是串集合

Σ 上的语言是 $Σ^*$ 的一个串集合。在这一部分理论里，语言（language）的含义就这么朴素。它可以是一门编程语言，可以是一个词法单元（token）语言，也可以是一个小数学语言，比如“所有恰好包含一个 1 的二进制串”。

在 Σ = {0, 1} 上的例子：

L1 = { ε, 0, 00, 000, ... }
L2 = { w | w 至少包含一个 1 }
L3 = { w | |w| 是偶数 }
L4 = { w | w 包含 substring 001 }

有些语言是有限的，例如 {if, else, while, return}。有些语言是无限的，例如所有合法标识符（identifier）的集合。在编译器中，词法单元规范经常就是一组语言：

• IF = {if}
• INT = {0, 1, 2, 3, ...}
• IDENT = 以字母或下划线开头，后接字母、数字或下划线的串
• WS = 由空格、tab、回车或换行组成的非空串

词法分析器接收一个很长的源字符串，并反复选择一个属于某个词法单元语言的前缀。语法分析器（parser）稍后接收的是词法单元串，而不是字符串，并检查它是否属于更高层的语法语言。

为什么这对词法分析器很重要

考虑下面的源码片段：

if count42 == 0

在字符层面，它是一个串。在词法单元层面，词法分析器应该产生类似这样的结果：

IF IDENT(count42) EQEQ INT(0)

这个变换本质上是一系列语言成员判断。前缀 if 是否属于关键字语言？是。count42 是否属于标识符语言？是。== 是否属于等号运算符语言（equality-operator language）？是。扫描器（scanner）在看到第二个 = 之前是否应该先接受单个 =？通常不应该，因为词法分析器生成器（lexer generator）一般使用最长匹配。我们会在本章后面回到最长匹配（longest match）。

这些数学词汇不是装饰。它让我们可以不依赖含糊例子，而是精确定义扫描器行为。词法单元不是“看起来像就行”的东西。它是某个指定语言中的串，并且当多个语言同时匹配同一前缀时，由确定性规则选出。

形式记号换来精确边界

若 Σ = {a, b}，则 $Σ^*$ 包含 ε、a、b 及所有有限二进制串；$Σ^+$ 去掉 ε。连接有顺序：{a, ab}{b, aa} = {ab, aaa, abb, abaa}。∅ 没有任何串，{ε} 却有一个长度为零的串，混淆它们会破坏构造与证明。

定义语言时要写成员关系（membership）和边界情况（boundary case）。偶数个 1 的语言应测试 ε、0、1、11、101；标识符要区分字符字母表（character alphabet）与词法单元语言，后者还有首字符/后续字符规则。

证明习惯

• 证明两语言相等要做双向包含；举例不是证明。

• 为每个拒绝边界写见证（witness），常能发现把 * 误写成 +。

• 串是元素，语言是集合，字母表是可用符号集。