1.1 字母表、字符串与文法：先定义什么算合法

先看一门故意做小的语言：只允许 a 和 b，字符串必须以 a 开始、以 b 结束。写 parser 之前，必须先把“合法输入”定义成可判定的规则。

这也是编译器的起点。先写清允许哪些符号、接受哪些序列，再讨论如何识别；否则实现越勤快，误解也会跑得越快。

本课目标

• 区分字母表、字符串和语言；
• 使用连接、长度、闭包等基本记号；
• 理解文法怎样生成语言；
• 区分“生成一个串”和“识别一个串”。

1. 字母表规定可用符号

字母表 $\mathrm{\Sigma }$ 是一个有限、非空的符号集合。符号不一定是自然语言字母：

• 二进制字母表可以是 $\{0,1\}$；
• token 字母表可以包含 IDENTIFIER、NUMBER、PLUS；
• 协议状态序列可以使用 SYN、ACK、FIN。

字母表中的符号是不可再分的抽象单位。若把 Unicode 码点、UTF-16 code unit 或词法 token 当作“一个符号”，得到的是不同层次的语言模型。实现前必须先固定层次。

2. 字符串是有限符号序列

字母表上的字符串是由 $\mathrm{\Sigma }$ 中符号组成的有限序列。空串记作 $\epsilon$，长度为 0；字符串 $w$ 的长度记作 $|w|$。

两个字符串可以连接。若 $x=ab$、$y=ba$，则：

$$xy=abba.$$

连接满足结合律，但一般不满足交换律。空串是连接运算的单位元：

$$w\epsilon =\epsilon w=w.$$

常用集合记号：

记号	含义
${\mathrm{\Sigma }}^0$	只含空串的集合 $\{\epsilon \}$
${\mathrm{\Sigma }}^n$	长度恰好为 $n$ 的所有字符串
${\mathrm{\Sigma }}^{\ast }$	所有有限长度字符串，包括空串
${\mathrm{\Sigma }}^{+}$	所有非空字符串，即 ${\mathrm{\Sigma }}^{\ast }\setminus \{\epsilon \}$

若 $\mathrm{\Sigma }=\{a,b\}$，那么 ${\mathrm{\Sigma }}^{\ast }$ 是无限集合，但其中每个字符串都只有有限长度。

3. 语言是字符串集合

形式语言 $L$ 是 ${\mathrm{\Sigma }}^{\ast }$ 的任意子集：

$$L\subseteq {\mathrm{\Sigma }}^{\ast }.$$

例如“以 a 开头、以 b 结尾”的语言可以写成：

$$L=\{awb\mid w\in \{a,b{\}}^{\ast }\}.$$

因此 ab、aab 和 abb 属于 $L$，空串、a 和 ba 不属于 $L$。

“语言”只规定哪些字符串合法，不规定用什么算法检查。正则表达式、文法、自动机和程序，都可能是描述或识别语言的不同手段。

语言也可以做集合与连接运算：

• 并集 $L_1\cup L_2$：属于任意一种语言；
• 交集 $L_1\cap L_2$：同时属于两种语言；
• 补集 ${\mathrm{\Sigma }}^{\ast }\setminus L$：相对固定字母表的所有非法串；
• 连接 $L_1{L}_2=\{xy\mid x\in L_1,y\in L_2\}$；
• Kleene 星 $L^{\ast }=\bigcup _{n\ge 0}{L}^n$，其中 $L^0=\{\epsilon \}$，$L^{n+1}=L^{n}L$。

补集必须说明全集。换了字母表，同一个规则的补集也会改变。还要留意：空语言的星闭包 ${\varnothing }^{\ast }$ 仍含空串，因为连接零个字符串也算一次选择。

4. 文法可以用有限规则生成无限语言

形式文法通常写成四元组：

$$G=(V,\mathrm{\Sigma },P,S).$$

• $V$：非终结符集合，用来表示尚未展开的结构；
• $\mathrm{\Sigma }$：终结符集合，最终字符串中的符号；
• $P$：产生式规则集合；
• $S$：开始符号，属于 $V$。

这里 $V$ 与 $\mathrm{\Sigma }$ 都有限且互不相交，产生式集合 $P$ 也有限。并非每个文法都生成无限语言；递归规则提供了描述无限集合的可能。

例如下面的文法生成一个或多个 a：

S → aS | a

从 $S$ 出发反复替换非终结符：

S ⇒ aS ⇒ aaS ⇒ aaa

记 $S{\Rightarrow }^{\ast }w$ 表示经过零步或多步推导得到 $w$。文法生成的语言为：

$$L(G)=\{w\in {\mathrm{\Sigma }}^{\ast }\mid S{\Rightarrow }^{\ast }w\}.$$

产生式是有限的，递归却能描述无限多个串。编程语言的表达式、语句块和类型结构正是靠这种递归组织起来。

5. 推导不是解析

文法从开始符号出发生成字符串；解析器从输入字符串出发，寻找它是否存在合法推导以及对应结构。两者面对的是同一关系，方向不同：

生成：S  ⇒*  token 序列
解析：token 序列  ⇒  是否属于 L(G)，若属于则恢复结构

一个字符串可能有多条推导路径。对上下文无关文法，如果同一个终结符串对应两棵不同的语法树，文法就有二义性。单纯展开顺序不同还不够：对 S → AB、A → a、B → b，先展开 A 或先展开 B 都得到 ab，树的结构却相同。第 3 章会处理运算符优先级和“悬空 else”一类实际问题。

6. 编译器会连续更换字母表

以代码 total = price + 1 为例：

1. 源文件层面处理字节、编码和字符；
2. 词法分析把字符分组为 IDENTIFIER ASSIGN IDENTIFIER PLUS NUMBER；
3. 语法分析把 token 序列组织成赋值与加法表达式；
4. 语义分析再判断名称是否声明、类型能否相加。

词法到语法阶段可用有限的 token 类别作字母表，具体名字和值放在 token 属性中。后续 AST 是树结构，不能再把“每一阶段换字母表”当作严格的字符串模型。把所有问题都塞进一个正则表达式或一套文法，会让错误边界和实现复杂度迅速失控。

7. 一个精确的标识符语言

若暂时只允许 ASCII 标识符，可定义：

letter     = A..Z | a..z | _
digit      = 0..9
identifier = letter (letter | digit)*

这一定义还没有处理 Unicode、关键字、最大长度和规范化形式。它说明“形式化”不是写出看似数学的符号，而是明确范围和假设。

词法分析应先读完最长标识符，再查关键字表，例如 if 是关键字，ifx 仍是完整标识符，不能拆成 if 和 x。关键字通常在相同字符模式下被先识别成标识符，再通过关键字表重分类；也可以在自动机接受状态上赋予更高优先级。两种方案的结果需要与语言规范一致。

常见误区

• 字母表就是字符集：token、指令甚至事件都可作为抽象符号。
• 空串等于空集合：$\epsilon$ 是长度为 0 的字符串，$\varnothing$ 是不含任何元素的集合。
• 文法就是解析算法：文法描述语言，解析算法还要考虑可判定性、复杂度与错误恢复。
• 代码能运行就属于规范语言：实现可能接受扩展语法，也可能带 bug；语言规范和实现行为应分开讨论。

练习

1. 对 $\mathrm{\Sigma }=\{0,1\}$ 写出 ${\mathrm{\Sigma }}^0$、${\mathrm{\Sigma }}^1$ 和 ${\mathrm{\Sigma }}^2$。
2. 定义所有包含偶数个 1 的二进制字符串语言，分别用集合条件和自然语言表述。
3. 写一个文法生成语言 $\{a^{n}b\mid n\ge 1\}$，给出 aaab 的推导。
4. 为 JSON 的字符、token 和语法结构分别举一个“符号”例子。

小结

字母表规定积木，字符串排列积木，语言选择哪些排列合法，文法用有限规则生成这些合法串。下一课不急着实现解析器，而是先问：不同规则需要多少记忆，应该交给哪种计算模型。