Quartz 4

词法分析-有限自动机FSM

9 min read

有限自动机（Finite State Machine, FSM）详解

有限自动机（Finite State Machine, FSM）是一种数学模型，用来描述具有有限个状态的系统及其状态之间的转移。它广泛应用于计算机科学中，尤其是在编译器的词法分析阶段、状态控制、正则表达式引擎等领域。

FSM 通过状态和状态转移规则来模拟系统的行为。它的基本构成包括：

  1. 状态集（States）：有限个状态，表示系统在某一时刻可能处于的状态。
  2. 输入符号集（Input Alphabet）：可以使系统发生状态转移的输入符号集合。
  3. 状态转移函数（Transition Function）：定义了从一个状态到另一个状态的转移规则，通常以一个表或图的形式表现。
  4. 初始状态（Initial State）：FSM 开始时的状态。
  5. 终止状态（Accepting State）：一个或多个接受状态，表示系统在这些状态下处理成功或满足某种条件。

1. FSM 的基本结构和工作原理

有限自动机的工作过程可以想象成“阅读输入并在不同的状态之间跳跃”。FSM 从初始状态开始，根据输入符号的不同，转移到下一个状态。FSM 运行时，会从输入符号流中读取一个个字符（或符号），并依据当前状态及符号来决定下一个状态，直到输入完毕。

FSM 的类型

FSM 有两种主要类型：

  • 确定性有限自动机（DFA, Deterministic Finite Automaton）：
    • 对于每个输入符号，在每个状态下只有一个明确的转移。
    • 无论在任何状态下，输入某个字符后，FSM 只能跳到唯一的下一个状态。
    • DFA 的状态转换是确定的，即每个状态对每个可能的输入符号都有唯一的转移。
  • 非确定性有限自动机（NFA, Nondeterministic Finite Automaton）：
    • 对于某个输入符号，某个状态可能有多个不同的转移，甚至可能没有任何转移。
    • NFA 允许同时在多个状态之间跳跃（即并行处理）。
    • 虽然 NFA 在理论上更加灵活，但通常需要转换为 DFA 才能高效地执行。

DFA 和 NFA 的区别

  • 确定性（DFA）：每个状态对每个输入符号有唯一的转移。
  • 非确定性（NFA）：某个状态对某些输入符号可能有多个转移，或者没有任何转移。

尽管 NFA 和 DFA 在理论上等价，NFA 可以转换成等价的 DFA，但 NFA 的实现通常比 DFA 更加灵活和简洁，尤其适用于正则表达式的解析。

2. FSM 的工作过程

假设我们要实现一个简单的有限自动机，用来识别由数字和字母组成的标识符（例如 myVar123）。我们可以设计一个简单的 DFA，定义如下：

  1. 初始状态为 S0，表示输入的字符还未开始处理。
  2. 如果输入的字符是字母，FSM 转移到状态 S1（字母状态）。
  3. 如果输入的字符是数字，FSM 进入状态 S2（数字状态）。
  4. 如果状态是 S1，再输入一个字母或数字，FSM 保持在 S1 状态，继续处理下去。
  5. 如果状态是 S2，再输入一个字母或数字，FSM 会转回 S1 状态。

状态转移图如下所示：

  • 状态 S0（初始状态）：接收字母 → S1，接收数字 → S2。
  • 状态 S1：接收字母 → S1，接收数字 → S1，接收其他字符 → 错误状态。
  • 状态 S2：接收字母 → S1，接收数字 → S2，接收其他字符 → 错误状态。

当输入流结束时，如果当前状态是 S1 或 S2，表示输入的字符是有效的标识符。

状态转移图

  S0 --letter--> S1 --letter/digit--> S1
  |                     |
  |                     v
  +--digit--> S2 --letter--> S1
  |                     |
  +---------------------+

3. FSM 在编译器中的应用

有限自动机在编译器中的应用主要体现在词法分析阶段。编译器的词法分析器（又叫扫描器）使用有限自动机将源代码拆解成一个个 Token。每种 Token 类型（如关键字、标识符、常量等）都可以用一个有限自动机来表示。

例如，假设我们需要处理标识符（由字母和数字组成），可以设计一个 DFA 来识别标识符的 Token；如果是处理数字常量（如 123 或 3.14），我们可以使用另一个 DFA 来识别数字 Token。

词法分析中的应用示例：

假设我们需要实现一个能够识别简单数字字面量（整数）的 DFA：

  1. 状态 S0：表示还未读取任何字符。
    • 如果读取到数字字符（0-9），转移到状态 S1。
    • 如果读取到其他字符，错误结束。
  2. 状态 S1：表示已经读取了一个或多个数字字符。
    • 如果继续读取数字字符（0-9），保持在状态 S1。
    • 如果读取到非数字字符，表示数字字面量结束。

在实际的实现中，这个过程可以通过一个简单的状态机来模拟。

状态转移图示例：

  S0 --digit--> S1 --digit--> S1
  |                     |
  +---------------------+

当输入的字符为 12345 时，FSM 会从状态 S0 转移到状态 S1，并保持在状态 S1，直到输入完毕。

4. FSM 的优化与变种

虽然有限自动机简单且高效，但它也有一些限制。例如，FSM 不能处理某些类型的语言（如上下文相关语言），它只能处理正则表达式定义的语言。为了解决这一问题，通常会将 FSM 和其他类型的自动机（如栈自动机）结合使用。

优化技巧：

  • DFA 最小化：通过合并等价状态来减少状态数量，优化 FSM 的效率。
  • NFA 转换：使用 NFA 来简化正则表达式的处理，再转换为 DFA 进行高效的执行。

5. 总结

有限自动机（FSM）是编译器中不可或缺的工具，尤其在词法分析阶段，用于将输入的字符流转化为具有意义的 Token。通过状态机的方式，它能够高效地完成输入的解析，并为语法分析提供基础。FSM 的核心思想是通过状态和状态转移规则来处理输入，在许多计算机科学领域中都有广泛的应用。

Graph View

Backlinks