2.2 正则语言与正则表达式

正则语言是可以被有限自动机识别的语言。等价地，它可以由形式语言意义上的正则表达式（regular expression）描述。这个等价性正是词法分析器生成器（lexer generator）存在的原因：使用者把词法单元（token）模式写成正则表达式，工具把这些模式转换成可以高效扫描字符的自动机。

正则语言足够表达很多局部字符模式：标识符（identifier）、整数（integer）、空白（whitespace）、行注释（line comment）、运算符（operator）、字符串定界符（string delimiter）、关键字（keyword）和简单转义序列（escape sequence）。但它不足以表达任意递归结构。匹配嵌套括号、检查每个 begin 是否有对应的 end、证明表达式类型正确，都需要后面的编译阶段。

语言上的运算

语言是集合，因此集合运算可以作用在语言上。令：

text

A = {good, bad}
B = {boy, girl}

两个语言的并（union）包含来自任一语言的串：

text

A ∪ B = {good, bad, boy, girl}

两个语言的连接（concatenation）会把第一个语言中的每个串与第二个语言中的每个串相连：

text

A ∘ B = {goodboy, goodgirl, badboy, badgirl}

一个语言的克林闭包（Kleene closure）包含该语言中字符串的所有有限次连接：

A^* = {ε, good, bad, goodgood, goodbad, badgood, badbad, ...}

这些运算不是单纯的数学练习。正则表达式正是由这些思想构造出来的：选择、连接和重复。

正在加载交互实验...

形式化正则表达式

在形式核心里，正则表达式递归构造：

∅ 表示空语言。
ε 表示只包含空串的语言。
Σ 中的符号 a 表示语言 {a}。
如果 r 和 s 是正则表达式，那么 r | s 表示并（union）。
如果 r 和 s 是正则表达式，那么 rs 表示连接（concatenation）。
如果 r 是正则表达式，那么 $r^*$ 表示克林闭包（Kleene closure）。

编程工具通常增加方便的缩写：

$r^+$ 表示一次或多次： $rr^*$ 。
$r^?$ 表示可选：r | ε。
[0-9] 表示数字字符中的一个选择。
[A-Za-z_] 表示字母或下划线中的一个选择。
. 经常表示除换行外的任意字符，具体取决于引擎。

编译器课程常使用形式化 regex 语法，而生产工具会使用扩展语法。但理论仍然驱动实现。字符类会展开为选择，或者表示成紧凑的转移类（transition class）。+ 和 ? 会降低为连接、并集和星号的组合。最终结果仍然可以转换为自动机。

正在加载概念检查...

优先级与歧义

正则表达式运算符有优先级。通常约定克林星号绑定最紧，连接次之，并优先级最低。因此：

ab^* | c

表示：

(a(b^*)) | c

而不是：

((ab)^*) | c

写词法单元规范时这很重要。表达式 $[0-9]^+$ 表示一个或多个数字。表达式 $[0-9]^+ "." [0-9]^+$ 可以描述 3.14 这样的十进制字面量（decimal literal），具体取决于记法。像 $[0-9] | [0-9][0-9]^*$ 这样的表达式可能是冗余的，因为右侧已经覆盖了一位数字的情况。

好的词法分析器规范不追求炫技。它会命名词法单元规则，测试边界情况，并把词法规则和语法规则分开。例如，一个词法分析器可以把 - 识别为运算符，而不是把它当作负整数的一部分。语法分析器或语义分析器（semantic analyzer）可以再决定 -42 是对 42 应用一元取负（unary negation）。

正在加载交互实验...

正在加载概念检查...

正则语言的边界

正则表达式无法无界计数。经典非正则语言是：

{ a^n b^n | n ≥ 0 }

这个语言包含 ε、ab、aabb、aaabbb 等等。要识别它，机器必须记住出现了多少个 a，然后要求 b 的数量完全相同。有限自动机只有有限个状态，因此无法存储无界计数。

平衡括号有同样的问题。识别 ((())) 需要记住嵌套深度，而语言定义允许任意深度，所以有限状态不够。这就是词法分析（lexical analysis）和语法分析（parsing）之间的边界。词法分析器处理正则的局部模式；语法分析器使用上下文无关文法（context-free grammar）和栈处理递归结构。

实践中也有一些注意事项。现实中的正则引擎（regex engine）经常支持反向引用（backreference）或环视（lookaround），这些特性超出了正则语言。它们在文本处理中很有用，但在词法分析器生成器中通常会避免，因为它们会破坏清晰的自动机模型和可预测的线性扫描。

正在加载概念检查...

正在加载本节练习...

把 regex 当代数，不是标点

$(ab|c)^*d$ 表示零次或多次选择 ab 或 c，最后接 d；它接受 d、abd、cd、abcabd，不接受 ad。括号和优先级会改变语言：ab|cd 是 (ab)|(cd)，a(b|c)d 才共享两侧。

编程 regex 的反向引用（backreference）、捕获（capture）、懒量词（lazy quantifier）并不全是正则的。词法分析器故意不用反向引用，因为有限自动机不能普遍记住并比较无界子串。词法单元的形状属于正则模式；嵌套、声明、依赖类型的规则属于后续阶段。

构造提示

把 digit、hexDigit、identifierStart 命名为子模式。

测最短、最长样子、几乎合法的输入，特别是选择（alternation）/可选后缀。

词法分析器从光标（cursor）起错位匹配；search API 的中间匹配不是同一操作。

2.2 正则语言与正则表达式

语言上的运算

语言是集合，因此集合运算可以作用在语言上。令：

text

A = {good, bad}
B = {boy, girl}

两个语言的并（union）包含来自任一语言的串：

text

A ∪ B = {good, bad, boy, girl}

两个语言的连接（concatenation）会把第一个语言中的每个串与第二个语言中的每个串相连：

text

A ∘ B = {goodboy, goodgirl, badboy, badgirl}

一个语言的克林闭包（Kleene closure）包含该语言中字符串的所有有限次连接：

A^* = {ε, good, bad, goodgood, goodbad, badgood, badbad, ...}

这些运算不是单纯的数学练习。正则表达式正是由这些思想构造出来的：选择、连接和重复。

正在加载交互实验...

形式化正则表达式

在形式核心里，正则表达式递归构造：

∅ 表示空语言。
ε 表示只包含空串的语言。
Σ 中的符号 a 表示语言 {a}。
如果 r 和 s 是正则表达式，那么 r | s 表示并（union）。
如果 r 和 s 是正则表达式，那么 rs 表示连接（concatenation）。
如果 r 是正则表达式，那么 $r^*$ 表示克林闭包（Kleene closure）。

编程工具通常增加方便的缩写：

$r^+$ 表示一次或多次： $rr^*$ 。
$r^?$ 表示可选：r | ε。
[0-9] 表示数字字符中的一个选择。
[A-Za-z_] 表示字母或下划线中的一个选择。
. 经常表示除换行外的任意字符，具体取决于引擎。

正在加载概念检查...

优先级与歧义

正则表达式运算符有优先级。通常约定克林星号绑定最紧，连接次之，并优先级最低。因此：

ab^* | c

表示：

(a(b^*)) | c

而不是：

((ab)^*) | c

正在加载交互实验...

正在加载概念检查...

正则语言的边界

正则表达式无法无界计数。经典非正则语言是：

{ a^n b^n | n ≥ 0 }

正在加载概念检查...

正在加载本节练习...

把 regex 当代数，不是标点

构造提示

把 digit、hexDigit、identifierStart 命名为子模式。

测最短、最长样子、几乎合法的输入，特别是选择（alternation）/可选后缀。

词法分析器从光标（cursor）起错位匹配；search API 的中间匹配不是同一操作。