编译技术2-6

从正则表达式到实现：DFA 最小化与扫描器构建

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

  • 归纳法 (Inductive method)：通过结构归纳将正则表达式转换为非确定性有限自动机（NFA）

2. 从 NFA 到 DFA (From NFA to DFA)

  • 子集构造算法 (Subset construction algorithm)：将 NFA 转换为等价的确定性有限自动机（DFA）

3. DFA 最小化 (Minimizing DFA)

3.1 状态最小化算法 (State-Minimization Algorithm)

目标：将 DFA 的状态数减少到最小，同时保持其识别的语言不变。

  • 理论依据：
    • 给定任何 DFA，都存在一个等价的最小状态 DFA
    • 这个最小状态 DFA 是唯一的

3.2 等价状态 (Equivalent States)

两个状态 s 和 t 等价，当且仅当：

  1. s 和 t 同为接受状态或同为非接受状态
  2. 对于每个字符 a ∈ Σ，s 和 t 在 a 上的转移都到达等价的状态

示例：

  • C 和 F 都是接受状态。 它们在 'a' 上都转移到 C，在 'b' 上都转移到 E，因此它们是等价状态。
  • S 是非接受状态而 C 是接受状态。 它们不是等价状态。
img

3.3 算法步骤

Step 1：初始划分 将状态集划分为接受状态集和非接受状态集

Step 2：迭代细分

  • 对每个子集和每个输入符号 a ∈ Σ 进行检查
    • 如果子集中存在两个状态 s 和 t，它们在 a 上的转移到达不同的子集 ⇒ 用 a 区分 s 和 t
    • 根据转移目标将当前子集进一步划分

Step 3：终止条件

  • 所有子集都只包含单个状态（原始 DFA 已最小化） 或
  • 无法再进行划分

3.4 算法示例

示例 1：

  1. 初始划分：{S, A, B}（非接受） 和 {C, D, E, F}（接受）
  2. 细分 {S, A, B}：
    • S 在 'a' 上转移到 A，在 'b' 上转移到 C
    • A 在 'a' 上转移到 B，在 'b' 上转移到 D
    • B 在 'a' 上转移到 B，在 'b' 上转移到 E ⇒ 划分为 {S}, {A}, {B}
  3. {C, D, E, F} 无法细分，用 D 代表
img

示例 2：

  1. 所有状态都是接受状态：{1, 2, 3}
  2. 'a' 区分状态 1 与状态 2、3： ⇒ {1}, {2, 3}
  3. {2, 3} 无法被进一步区分
img

4. 扫描中的冲突解决 (Conflict Resolutions in Scanning)

4.1 扫描中的挑战 (Challenges in Scanning)

  1. 如何确定哪些词素（lexemes）与每个标记（token）相关联？
  2. 当有多种扫描输入的方式时，如何选择正确的方式？
  3. 如何高效地解决这些问题？

4.2 基于 DFA 的扫描器 (DFA-based Scanner)

  • 使用最小化 DFA 构建高效的词法分析器
  • 最小化状态数可减少内存使用并提高匹配速度

✅ 1. 关键概念总结

概念 说明
正则表达式 → NFA → DFA 编译器中词法分析器的标准构建路径
DFA 最小化 通过合并等价状态优化自动机
等价状态 行为完全一致的状态可以合并
状态划分 通过转移行为逐步细分状态集合

最小化 DFA 不仅能提高扫描器效率，还能简化后续处理步骤，是编译器前端优化的重要环节。