编译技术 2-5 ：从正则表达式到实现 - NFA 到 DFA 的转换与扫描器构建

1. 基本概念 (Basic Concepts)

正则表达式到 NFA (From Regular Expressions to NFAs)

正则表达式 (Regular Expression)：用于描述字符串模式的代数形式表示法
NFA (Nondeterministic Finite Automaton)：非确定有限自动机
- 允许空转移(ε-moves)
- 同一输入可能有多个转移
- 同时处于多个状态

NFA 到 DFA (From NFA to DFA)

DFA (Deterministic Finite Automaton)：确定有限自动机
- 每个状态对每个输入字符只能有一个转移
- 不允许空转移
- 一次只能处于一个状态

2. 转换算法 (Conversion Algorithms)

子集构造法 (Subset Construction Algorithm)

此算法用于把一个 NFA 转换成等价的 DFA。

核心思想:

DFA 的每一个状态是 NFA 的一个状态集合

关键计算 (Key Computations)

1. ε-闭包 (Epsilon-closure)

定义：从指定状态集合出发，通过 0 次或多次 ε 转移可达的所有状态的集合
表示式： ε_closure(I)，I 是 NFA 的状态集

2. 移动集 (Move Set)

Move(I, a) ：从状态集 I 通过输入字符 a 能直接达到的状态
表示式：Ia = ε_closure(Move(I, a))

算法步骤 (Algorithm Steps)

计算 NFA 初始状态的 ε-闭包，作为 DFA 初始状态
对于 DFA 中的每个状态集合 S，计算它在每个输入字符 a 下的 Ia = ε_closure(Move(S, a))
如果 Ia 是新的状态集，则将其加入 DFA
重复步骤 2-3，直到没有新状态产生
如果一个 DFA 状态集包含任何 NFA 的接受状态，则将其标记为 DFA 接受状态

3. 示例转换 (Example Conversion)

NFA状态集	DFA状态	a转移	b转移
{0,1,2,4,7}	T0	T1	T2
{8,3,6,1,2,4}	T1	T1	T3
{5,6,7,1,2,4}	T2	T1	T2
{9,5,6,1,2,4}	T3	T1	T4
{10,5,6,1,2,4}	T4	T1	T2

4. 性能比较 (Performance Comparison)

属性	NFA	DFA
时间复杂度	O(mn²)	O(m)
空间复杂度	O(n)	O(2^n) (最坏情况)
确定性	非确定性	确定性
是否允许 ε 转移	是	否

5. 扫描挑战与解决方案 (Scanning Challenges and Solutions)

主要挑战 (Challenges)

词组和标记关联：如何判断词组对应哪个 token
多解释：当有多种解释方式时怎样选择
效率问题：如何快速扫描

DFA 扫描器解决方案

用 DFA 实现词法分析器
优点：
- 线性时间处理 O(m)
- 确定性，无回退
- 支持 最长匹配原则

6. 冲突解决 (Conflict Resolutions)

常见策略:

最长匹配原则 (Longest Match Principle)
先后顺序/优先级 (Priority Rules)
显式解释 (Explicit Disambiguation)：通过语法规则显式指定
状态最小化 (State Minimization)

最小化算法 (Minimization Algorithm)

将 DFA 状态划分为接受和非接受两组
检查同组中状态在相同输入下是否转向同组
不同则继续分组
直到无法再分
合并等价状态

7. 实现考虑 (Implementation Considerations)

表驱动法 (Table-Driven): 用于转移的字表描述 DFA
直接编码 (Hardcoding): 将 DFA 转移算法直接编程序代码
混合法 (Hybrid): 体现两者之优

8. 关键公式 (Key Formulas)

ε-closure 计算:

1	ε_closure(I) = I ∪ { s' \| s ∈ I, s 通过 ε 转移到 s' }

转移集 Ia 计算:

1	Ia = ε_closure({ s' \| s ∈ I, s 通过 a 转移到 s' })

DFA 状态定义:

1	DFA 状态 = NFA 状态集合

✅ NFA 转换为 DFA 的算法步骤（Subset Construction）

Algorithm for constructing a DFA M’ from a given NFA M
从给定的 NFA $ M $ 构造一个 DFA $ M' $ 的算法（子集构造法）：

🧩 0. 基本概念

NFA (非确定性有限自动机) 允许从某状态在相同输入上转移到多个状态，且可以有 ε-transition（空输入转移）。
DFA (确定性有限自动机) 每个状态在每个输入符号上最多只能有一个转移，没有 ε-transition。

📌 步骤详解（含中英文）：

Step 1: Compute ε-closure of the start state of M

计算 NFA 初始状态的 ε-闭包，这作为 DFA 的初始状态。

ε-closure：从一个状态出发，经过任意多步 ε 转移所能到达的所有状态集合。
将这个集合作为 DFA 的起始状态。

✅ Notation 示例：
如果 NFA 的起始状态为 $ q_0 $，则：
> $ (q_0) = {q_0, q_1, q_3} $ DFA 的起始状态是这个集合。

Step 2: For each DFA state S and input symbol a ∈ Σ, compute the transition Sa

对 DFA 中的每个状态集合 $ S $ 和每个输入符号 $ a $，计算转移。

对集合 $ S $ 中的每个状态 $ q $，找出 $ q q' $ 能到达的状态集合。
然后再对这些结果求一次 ε-closure，得到一个新的状态集合。

✅ 这个新的集合就是 DFA 的一个新状态。

Step 3: Repeat until no new states or transitions are created

重复上一步，直到没有新的状态或转移产生为止。

每次得到一个新集合就加入状态集中。
如果所有状态的所有输入的转移都已计算完成，就停止。

Step 4: Mark accepting states

标记 DFA 中的终止状态（接受状态）。

如果某个 DFA 状态集合中包含 NFA 的一个或多个接受状态，那么这个集合就是 DFA 的一个接受状态。

✅ 例如：
若 $ q_3 $ 是 NFA 的接受状态，而某个 DFA 状态集合中包含 $ q_3 $，那么这个 DFA 状态集合是接受状态。

🧠 总结 Summary

步骤	英文	中文
1	Compute ε-closure of NFA start state	计算 NFA 起始状态的 ε-闭包
2	For each DFA state and input symbol, compute transitions and closures	对每个状态集合和输入符号，计算转移和闭包
3	Repeat until no new states/transitions	重复直到不再产生新状态或转移
4	Mark accepting states if any NFA accepting state is in the set	若集合中包含 NFA 的终止状态，则该集合为 DFA 接受状态