编译-第11章-词法分析程序的自动生成技术(重要)

Fyw0o Nothing •

2025-11-18

Compiler

Compiler Theory

编译-第11章-词法分析程序的自动生成技术

先*, 后 •, 最后 |。• 在正则表达式中可以省略

正则表达式相等<=>这两个正则表达式表示的语言相等

正则表达式的性质：

正则表达式与3型文法等价

确定：状态转移函数是单值的

一个确定的有穷自动机（DFA）M是一个五元式：
$$M=(S,\Sigma,\delta,s_{0},Z) $$

其中：

S — 有穷状态集
Σ — 输入字母表，在有穷自动机不包括$\epsilon$
δ — 映射函数（也称状态转换函数）——（标注：s’ 叫做 s 的后继状态）
$S\times\Sigma\rightarrow S$

$\delta(s,a)=s’，s,s’\in S，a\in\Sigma $
$ s_{0}$ — 初始状态 $s_{0}\in S $
Z — 终止状态集 $Z\subseteq S$

状态转移函数是多值的，且输入允许为空串

NFA 五元组定义为：

$$
M’ = (S, \Sigma \cup {\varepsilon}, \delta, S_0, Z)
$$

其中：

S — 有穷状态集（与 DFA 相同）
$\Sigma \cup {\varepsilon} $— 输入字母表加上空串 $\varepsilon$ ，即允许弧上标记为 $\varepsilon$（空转移）或 $\Sigma$ 中的字符。
$\delta$ — 状态转换函数
$$
\delta: S \times (\Sigma \cup {\varepsilon}) \to 2^S
$$
这里 $2^S$ 是 S 的幂集（即 S 的所有子集构成的集合），表示从一个状态和一个输入符号（或 $\varepsilon$）可以转移到多个可能的状态（或一个状态集合）。
$S_0$ — 初态集，且 $S_0 \subseteq S$（NFA 允许有多个初始状态）
Z — 终态集，且 $Z \subseteq S$（与 DFA 相同）

$2^S$：S的幂集—S的子集构成的集合
幂集(Power Set)：原集合中所有的子集(包括全集和空集)构成的集族。
例如：
集合B={a, b} => $2^B$ = {∅, {a}, {b}, {a, b}}

NFA -> DFA

两个定义：

集合I的$\varepsilon$-闭包：哪个状态可以是空串
- I是状态集的子集
- 若$s\in I$，则$s\in \varepsilon - closure(I)$
- 若$s \in I$，则从s出发经过任意条$\varepsilon$弧能够到达的任何状态都属于$\varepsilon - closure(I)$
令 I 是 NFA M’ 的状态集的一个子集, a∈Σ
- 定义: $I_a = ε-closure(J)$，其中 $J = ∪_{s∈I} δ(s, a)$
- J 是从状态子集I 中的每个状态出发, 经过标记为 a 的弧而达到的状态集合。
- $I_a$ 是状态子集, 其元素为 J 中的状态, 加上从 J 中每一个状态出发通过ε弧到达的状态。