编译原理课程笔记

概论

编程语言的发展：

第一代 机器语言: 能够被计算机的硬件系统直接执行的指令程序, 如“0001000101”。
第二代 汇编语言: 将硬件指令用一些助记符表示, 即符号化的机器语言, 如“ADD, MOV”。
第三代 高级语言: 从程序员的角度出发, 对汇编语言进一步抽象, 使用便于理解的“自然语言”表述。

高级语言的实现

编译方式

将⾼级语⾔（源语⾔）翻译成低级语⾔（如汇编语⾔或机器语⾔）的⽬标程序的翻译⽅式。⼀次性将源程序翻译为⽬标程序，之后直接运⾏⽬标程序，⽆需重复翻译。

适⽤场景：程序需要频繁运⾏时，编译⽅式更⾼效，因为它省去了反复翻译的过程。

解释方式

逐⾏翻译并同时执⾏⾼级语⾔程序，翻译与执⾏同步完成。⽆需⽣成独⽴的⽬标程序，边翻译边运⾏。

适⽤场景：程序较简单且需要灵活修改时，例如 Excel 表格中的脚本，解释⽅式更具灵活性。

转换方式

将⼀种⾼级语⾔（A 语⾔）转换为另⼀种⾼级语⾔（B 语⾔），再利⽤ B 语⾔的编译器执⾏。不直接属于⾼级语⾔的实现⽅式，⽽是⼀种变通策略。

适⽤性：依赖已有编译器，适⽤于语⾔间转换的场景。

编译程序的组成

表处理和错误处理也可以算作编译程序的组成部分，但是主要还是中间的六个部分。

词法分析

词法分析器

词法分析器也叫 Scanner，输入是源程序的字符序列，输出是单词序列。它按顺序扫描源程序，识别出具有独立意义的单词，并检查词法错误。

词法分析的输出通常采用二元组形式：<单词类别, 单词内容>。例如：

<保留字, void>
<界限符, (>
<保留字, int>
<标识符, x1>
<运算符, =>
<常量, 0>

单词是具有独立含义的最小语义单位。常见单词类型包括保留字、标识符、常量、运算符、界限符、控制符。

实现词法分析器的基本步骤：

明确要识别的单词类型和词法规则。
使用形式化方法描述各类单词，主要工具是正则表达式和自动机。
根据描述设计词法分析算法。

符号和符号串

字母表是元素的非空有穷集合，通常记为 $\Sigma$ 。字母表中的元素称为字母、符号或字符。

例如：

$\Sigma={0,1,\dots,9}$
$\Sigma={a,b,c,\dots,z,A,B,\dots,Z}$
$\Sigma=\text{ASCII}$
$\Sigma=\text{Unicode}$

符号串是由字母表中的符号组成的有穷序列，也称字符串或句子。常用 $\alpha,\beta,x,y,z$ 表示。

长度

符号串长度表示为 $|\beta|$ 。空串记为 $\varepsilon$ ，其长度为 $|\varepsilon|=0$ 。

连接

若 $\alpha$ 和 $\beta$ 都是 $\Sigma$ 上的符号串，则它们的连接记为 $\alpha\beta$ 。例如 $\alpha=abc$ ， $\beta=de$ ，则 $\alpha\beta=abcde$ 。

连接满足：

$|\alpha\beta|=|\alpha|+|\beta|$
$\varepsilon\alpha=\alpha\varepsilon=\alpha$

方幂

符号串的方幂表示重复连接。若 $x$ 是符号串，则：

$x^0=\varepsilon$
$x^1=x$
$x^2=xx$
$x^3=xxx$
$x^n=x^{n-1}x=xx^{n-1}$

符号串集合是由某个字母表上的符号串组成的集合。若 $A$ 和 $B$ 是两个符号串集合，则它们的乘积定义为：

AB=\{xy\mid x\in A \land y\in B\}

例如 $A={a,bc}$ ， $B={de,f}$ ，则：

AB={ade,af,bcde,bcf}

符号串集合的方幂定义为：

$A^0={\varepsilon}$
$A^1=A$
$A^2=AA$
$A^n=A^{n-1}A$

若 $A=\{a,b\}$ ，则：

$A^0={\varepsilon}$
$A^1={a,b}$
$A^2={aa,ab,ba,bb}$
$A^3={aaa,aab,aba,abb,baa,bab,bba,bbb}$

正闭包表示一次或多次连接：

A^+=A^1\cup A^2\cup A^3\cup \dots

星闭包表示零次或多次连接：

A^*=A^0\cup A^1\cup A^2\cup A^3\cup \dots

也可写为：

A^*=\{\varepsilon\}\cup A^+

例如 letter 表示所有英文字母，则 $\text{letter}^+$ 表示所有非空英文字符串， $\text{letter}^*$ 表示包含空串在内的所有英文字符串。

正则表达式

正则表达式是描述正则集的一种代数表达式，也称正规表达式。它使用预先定义的符号和运算规则构造模式，用来描述一类字符串。

正则表达式 $r$ 所描述的符号串集合称为正则集或正规集，记为 $L(r)$ ，也称为由 $r$ 定义的语言。

例如：

(1|2|\dots|9)(0|1|2|\dots|9)^*|0

这个表达式可描述十进制非负整数。

设 $\Sigma$ 为字母表，正则表达式递归定义如下：

$\varepsilon$ 和 $\varnothing$ 是 $\Sigma$ 上的正则表达式：
$L(\varepsilon)=\{\varepsilon\}, L(\varnothing)=\{\}$
对任意 $a\in\Sigma$ ， $a$ 是 $\Sigma$ 上的正则表达式：
$L(a)={a}$
若 $r$ 和 $s$ 是正则表达式，则以下表达式也是正则表达式：
$(r), r|s, r\cdot s, r^*$

它们对应的语言为：

$L((r))=L(r)$
$L(r|s)=L(r)\cup L(s)$
$L(r\cdot s)=L(r)L(s)$
$L(r^*)=(L(r))^*$

正则表达式中的主要运算：

括号 ( )：确定运算优先级
或运算 |：表示多个模式的并集
连接运算 ·：表示前后相邻部分的组合，实际书写中常省略
闭包运算 *：表示零次或多次重复

实际应用中还常使用正闭包 +：

L(r^+)=(L(r))^+

运算优先级为：

( ) > * > \cdot > |

例如 ab* 表示先对 b 做闭包，再与 a 连接，即 $a(b^*)$ 。

正则表达式描述单词

正则表达式可用于化简和构造词法规则。

交换律： $A|B=B|A$
结合律：
- $A|B|C=(A|B)|C=A|(B|C)$
- $ABC=(AB)C=A(BC)$
分配律：
- $A(B|C)=AB|AC$
- $(A|B)C=AC|BC$
幂等律：
- $A^{**}=A^*$
同一律：
- $A\varepsilon=\varepsilon A=A$

例如在字母表 $\Sigma={a,b}$ 上：

ab* 表示所有以 a 开头，后面跟零个或多个 b 的字符串，即：

L(ab^*)={a,ab,abb,abbb,\dots}

a(a|b)* 表示所有以 a 开头，后面跟任意个 a 或 b 的字符串。

整数可用正则表达式描述。设：

D=0|1|2|\dots|9\\ D_1=1|2|\dots|9

则：

$D^+$ 表示允许前导 0 的数字串
$D_1D^*$ 表示无符号正整数
$(+D_1D^*)|(-D_1D^*)|0$ 表示带符号整数和 0
$(+|-|\varepsilon)(D_1D^*)|0$ 表示整数

词法分析中常见单词的正则描述：

保留字：

1	`while\|if\|for\|...`

标识符：

L(L|D)^*

其中：

L=A|B|\dots|Z|a|b|\dots|z|\_\\ D=0|1|\dots|9

整数常量：

(+|-|\varepsilon)(D_1D^*)|0

其中：

D_1=1|2|\dots|9

实数常量：

(+|-|\varepsilon)(D_1D^*|0).D^+

特殊符号包括：

运算符：+|-|*|...
分界符：{|}|;|...
控制符：\t|\n|...

这几部分的核心关系是：词法分析器要识别源程序中的单词，符号串理论提供基本对象，正则表达式提供形式化描述，单词规则可用正则表达式精确表示。

确定有限自动机 DFA

有限自动机 FA 是一种字符串识别装置，可以识别正规集。词法分析中引入 FA，是为了给词法分析程序的自动构造提供形式化工具。

有限自动机分为两类：

确定有限自动机 DFA：Deterministic Finite Automata
非确定有限自动机 NFA：Nondeterministic Finite Automata

DFA 定义为一个五元组：

M=(S,\Sigma,S_0,f,Z)

其中：

$S$ 是有穷状态集，其中每个元素称为一个状态
$\Sigma$ 是有穷字母表，其中每个元素称为输入字符
$S_0\in S$ 是唯一初始状态，也称开始状态
$f$ 是状态转换函数， $f:S\times\Sigma\to S$
$Z\subseteq S$ 是终止状态集，也称可接受状态集或结束状态集

状态转换函数 $f(S_i,a)=S_k$ 表示：当前状态为 $S_i$ ，读入输入字符 a 时，自动机唯一转换到状态 $S_k$ 。 $S_k$ 称为 $S_i$ 的一个后继状态。

例如：

M=({S_0,S_1,S_2,S_3},{a,b},f,S_0,{S_3})

其中转换函数为：

$f(S_0,a)=S_1$
$f(S_0,b)=S_2$
$f(S_1,a)=S_3$
$f(S_1,b)=S_2$
$f(S_2,a)=S_1$
$f(S_2,b)=S_3$
$f(S_3,a)=S_3$
$f(S_3,b)=S_3$

这个 DFA 的初始状态是 $S_0$ ，终止状态是 $S_3$ ，输入字母表是 ${a,b}$ 。

DFA 的表示方式

DFA 有两种常见表示方式。

第一种是状态转换图。状态转换图使用有向图表示自动机：

第二种是状态转换矩阵。矩阵中：

行表示状态
列表示输入字符
矩阵元素表示转换后的状态
初始状态常用 + 标记
终止状态常用 * 或 - 标记

以上面的 DFA 为例，状态转换矩阵为：

状态 \ $\Sigma$	$a$	$b$
$S_0+$	$S_1$	$S_2$
$S_1$	$S_3$	$S_2$
$S_2$	$S_1$	$S_3$
$S_3*$	$S_3$	$S_3$

陷阱状态

陷阱状态是自动机进入错误路径后的状态。进入陷阱状态后，后续任意输入通常都停留在陷阱状态中。

例如某 DFA 中：

$f(0,a)=1$
$f(0,b)=4$
$f(1,a)=4$
$f(1,b)=2$
$f(2,a)=3$
$f(2,b)=4$
$f(3,a)=3$
$f(3,b)=3$
$f(4,a)=4$
$f(4,b)=4$

其中状态 4 就是陷阱状态，因为读入 a 或 b 都回到 4。

DFA 的确定性体现在三个方面：

初始状态唯一
对任何状态 $s\in S$ 和输入符号 $a\in\Sigma$ ， $f(s,a)$ 唯一
状态转换依赖输入字符，DFA 中每一步都有确定的后继状态
$\varepsilon$ 的输入为空边，也就是不接受没有任何输入就进行状态转换的情况

DFA 接受的字符串

对于字母表 $\Sigma$ 上的任意字符串 $a_1a_2\dots a_n$ ，若 DFA $M$ 中存在一条从初始状态到某个终止状态的路径，并且路径上所有边的标记依次连接后等于 $a_1a_2\dots a_n$ ，则称该字符串可被 DFA $M$ 接受或识别。

形式上说，DFA 处理字符串时，从初始状态开始，按字符顺序读取输入，每读入一个字符就根据状态转换函数移动到下一个状态。输入读完后，若当前状态属于终止状态集 $Z$ ，则该字符串被接受。

DFA $M$ 能接受的所有字符串构成的集合，称为 DFA $M$ 接受的语言，记为 $L(M)$ 。

例如某 DFA 的路径可识别形如 aba(ab)* 的字符串，则：

aba 可被接受
abaab 可被接受
abaabab 可被接受
abaa 根据最终状态判断
$\varepsilon$ 是否被接受取决于初始状态是否为终止状态

DFA 的应用包括：

在语言学中，自动机可作为语言识别器
在计算机科学中，自动机可作为计算过程的动态数学模型
在自动控制领域中，自动机可处理控制信号序列

复印机工作过程可用状态转换图描述：

启动命令使复印机从开始状态进入等待状态
复印命令使其从等待状态进入复印状态
复印完成后回到等待状态
关机命令使其进入结束状态
复印时没纸则进入缺纸状态，装纸后回到等待状态
复印时卡纸则进入卡纸状态，故障排除后回到等待状态

这个例子说明：自动机的状态可表示系统所处阶段，输入事件可触发状态转换。

设计识别能被 3 整除的二进制数的 DFA 时，可用余数作为状态：

$S_0$ ：当前二进制数除以 3 余 0
$S_1$ ：当前二进制数除以 3 余 1
$S_2$ ：当前二进制数除以 3 余 2

初始状态是 $S_0$ ，终止状态也是 $S_0$ 。因为余数为 0 表示该二进制数能被 3 整除。

读入一个新二进制位 b 后，原数 $n$ 变为 $2n+b$ ，新余数为：

(2r+b)\bmod 3

其中 $r$ 是原来的余数， $b\in{0,1}$ 。

因此转换规律为：

状态	`0`	`1`
$S_0$	$S_0$	$S_1$
$S_1$	$S_2$	$S_0$
$S_2$	$S_1$	$S_2$

DFA 描述单词

DFA 可以用来描述词法分析中的各种单词。

标识符的描述，设：

L=a|b|\dots|z|A|B|\dots|Z|\_\\ D=0|1|2|\dots|9

标识符的正则表达式为：

L(L|D)^*

对应 DFA 的含义是：第一个字符必须是字母或下划线，后续字符可以是字母、下划线或数字。常数等的命名规则同上。

这些表达式可转成 DFA，用状态表示是否已经读入符号、整数部分、小数点和小数部分。

特殊符号也可由 DFA 描述。例如 {、+、>、= 都可以从初始状态读入单个字符后进入对应终止状态。若要识别复合运算符，例如 >=，则读入 > 后需要继续判断下一个字符是否为 =。

保留字可用字符路径描述。例如 for 的 DFA 路径为：

1	`0 --f--> 1 --o--> 2 --r--> 3`

其中状态 3 是接受状态。

if 的 DFA 路径为：

1	`0 --i--> 4 --f--> 5`

其中状态 5 是接受状态。

实际词法分析中，保留字和标识符容易冲突。常用处理方法是先按标识符规则识别完整字符串，再查保留字表。若识别到的字符串是 if、for、while 等，则输出保留字类别；否则输出标识符类别。

DFA 的程序实现

DFA 的程序实现主要有两种方法。

第一种是直接转向法。它基于状态转换图实现，每个状态对应一段 switch 判断，不同输入字符跳转到不同状态。

示意代码：

L_i:
switch (CurChar) {
    case 'a':
        goto L_j;
    case 'b':
        goto L_k;
    case '#':
        Accept();
    default:
        Error();
}

直接转向法的特点是：程序结构与状态图一一对应，理解直观；当状态图变化时，代码也要跟着变化。

第二种是基于状态转换矩阵的方法。它把 DFA 存成表，通过查表完成状态转换。

示意代码：

state = S0;
curChar = readNextChar();

while (curChar != '#' && T[state][curChar] != error) {
    state = T[state][curChar];
    curChar = readNextChar();
}

if (curChar == '#' && state in FinalState) {
    return true;
} else {
    return false;
}

其中：

state 表示当前状态
curChar 表示当前输入字符
T[state][curChar] 表示状态转换矩阵
FinalState 表示终止状态集合
# 表示输入结束符

状态转换矩阵法的优点是程序框架固定，只需要修改状态表即可适配不同 DFA。它适合词法分析器的自动生成。状态较多、字符集较大时，矩阵可能占用较多存储空间，可使用压缩表或稀疏表优化。

NFA 的确定化

NFA，即非确定有限自动机，是一个五元组：

A=(S,\Sigma,f,S_0,Z)

其中：

$S$ ：有穷状态集
$\Sigma$ ：输入字母表
$f$ ：状态转换函数， $f:S\times(\Sigma\cup{\varepsilon})\to 2^S$
$S_0$ ：初始状态集
$Z$ ：终止状态集

含义是：NFA 在某个状态读入一个字符，或通过 $\varepsilon$ 空边，可以转移到一个状态集合。它允许一个状态对同一输入有多个后继状态，也允许 $\varepsilon$ 转移。

自动机等价的定义：设 $A_1$ 和 $A_2$ 是同一个字母表 $\Sigma$ 上的自动机，若它们接受的语言相同，即：

L(A_1)=L(A_2)

则称 $A_1$ 和 $A_2$ 等价。

重要定理：对任意一个 NFA $A$ ，都存在一个 DFA $A'$ ，使得： $L(A)=L(A')$ 。

由 NFA 构造与其等价的 DFA 的过程，称为 NFA 的确定化。

NFA 确定化的核心方法是子集法。它的思想是：DFA 的一个状态记录 NFA 在读入某个输入符号后可能达到的一组状态。也就是说，NFA 中的一组状态：

\{s_{j1},s_{j2},\dots,s_{jn}\}

可以作为 DFA 中的一个状态 $s_i'$ 。

无 $\varepsilon$ 空边 NFA 的确定化

对于无 $\varepsilon$ 空边的 NFA，确定化时直接计算状态集合在每个输入符号下能到达的新状态集合。

设当前 DFA 状态对应 NFA 状态集合 $I$ ，输入字符为 $a$ ，则新状态集合为：

f(I,a)=\bigcup_{s\in I}f(s,a)

每得到一个新的状态集合，就把它作为 DFA 的一个新状态，继续对所有输入符号求转换，直到没有新状态集合产生。

带 $\varepsilon$ 空边 NFA 的确定化

带 $\varepsilon$ 空边时，需要先引入 $\varepsilon$ 闭包。状态集 $J$ 的 $\varepsilon$ 闭包记为：

\varepsilon\text{-CLOSURE}(J)

定义如下：

若 $q\in J$ ，则 $q\in \varepsilon\text{-CLOSURE}(J)$ 。
若 $q\in \varepsilon\text{-CLOSURE}(J)$ ，并且从 $q$ 出发经过任意条 $\varepsilon$ 边可到达 $q'$ ，则 $q'\in \varepsilon\text{-CLOSURE}(J)$ 。

设 $I={S_1,S_2,\dots,S_m}$ 是 NFA 的一个状态集合，对输入字符 $a\in\Sigma$ ，先求：

J=f(S_1,a)\cup f(S_2,a)\cup\dots\cup f(S_m,a)

再求：

I_a=\varepsilon\text{-CLOSURE}(J)

其中 $I_a$ 就是状态集 $I$ 读入 a 后在 DFA 中应转移到的新状态集合。

完整确定化流程：

求 NFA 初始状态集的 $\varepsilon$ 闭包，作为 DFA 初始状态。
对每个 DFA 状态集合 $I$ ，分别计算每个输入字符下的 $I_a$ 。
若 $I_a$ 是新的状态集合，则加入 DFA 状态集。
重复计算，直到状态集合不再增加。
若某个 DFA 状态集合中包含 NFA 的终止状态，则该 DFA 状态是终止状态。

课件中的例子把 NFA 状态集合转换为 DFA 状态，例如：

$S_1=\{1,2\}$
$S_2=\{4,5,7,6,2\}$
$S_3=\{3,8\}$
$S_4=\{3,9,8\}$
$S_5=\{9\}$

其中包含 NFA 终态 9 的集合，对应 DFA 的终止状态。

NFA 确定化的本质是把“多种可能路径同时存在”的情况压缩进 DFA 的一个集合状态中。每个集合状态代表 NFA 当前可能处于的所有状态。

DFA 的化简

DFA 化简的目标是得到最小自动机。最小自动机的定义是：DFA $M$ 中没有无关状态，也没有等价状态。

无关状态

状态 $S$ 是无关状态，通常有两种情况：

从开始状态没有到 $S$ 的通路。
从 $S$ 出发没有到任意终止状态的通路。

这类状态对识别语言没有实际贡献，可以删除。

等价状态

对 DFA 中两个状态 $S_1$ 和 $S_2$ ，若分别把它们看作初始状态时，能接受的符号串集合相同，则称 $S_1$ 和 $S_2$ 等价。

状态等价需要满足两个条件。

一致性条件： $S_1$ 和 $S_2$ 同时为接受状态，或同时为非接受状态。
蔓延性条件：对所有输入符号， $S_1$ 和 $S_2$ 都必须转换到等价状态中。

也就是说，若输入字符为 $a$ ，则 $f(S_1,a)$ 和 $f(S_2,a)$ 也应等价。

终止状态和非终止状态属于不同类别，二者在初始划分时分开。

状态分离法

DFA 化简常用状态分离法。步骤：

初始划分：把所有终止状态分为一组，所有非终止状态分为一组。
检查每一组中的状态：若它们对某个输入字符转向不同的组，则这些状态应被分离。
得到新分组后继续检查。
重复分离，直到没有新组产生。
每个最终分组中的状态互相等价，可以合并为一个状态。

课件例子中的初始划分为：

\{1,2,3,5\}\cup\{4,6,7,8\}

经过输入字符 a 和 b 的转向检查后，进一步分离为：

\{1,3\}\cup\{2,5\}\cup\{4,6,7,8\}

最终化简后，这三个状态集合分别合并为三个新状态：

$S_0=\{1,3\}$
$S_1=\{2,5\}$
$S_2=\{4,6,7,8\}$

DFA 化简的关键判断是：同组状态在每个输入字符下的后继状态是否仍然落在相同分组中。若转向模式相同，则这些状态保留在同组；若转向模式不同，则继续拆分。

正则表达式和有限自动机的相互转化

正则表达式和有限自动机描述能力等价。课件给出的定理是：对 $\Sigma$ 上的每一个正则表达式 $R$ ，都存在一个 $\Sigma$ 上的 NFA $M$ ，使得：

L(M)=L(R)

因此，正则表达式可以转为 NFA，NFA 也可以转为等价的正则表达式。

正则表达式到 NFA

正则表达式到 NFA 的转换基于基本结构组合。

单个字符 a：构造一条从开始状态到终止状态、标记为 a 的边。
连接表达式 ab：先构造 a 的 NFA，再构造 b 的 NFA，把前一个片段的终止状态连接到后一个片段的开始状态。
或表达式 a|b：从新开始状态通过 $\varepsilon$ 边分别进入 a 和 b 的子自动机，再通过 $\varepsilon$ 边汇合到新终止状态。
闭包表达式 b*：构造 b 的子自动机，并加入 $\varepsilon$ 边，使其可以重复执行，也可以直接从开始状态到终止状态。

课件例子：为正则表达式 (a|b)*aa 构造 NFA。

拆分结构为：

1	`(a\|b)* aa`

再继续拆为：

1	`(a\|b)* a a`

构造思路：

先构造 a|b 的分支结构。
对 a|b 加 *，形成 (a|b)* 的循环结构。
后面依次连接两个 a。
得到接受所有以两个 a 结尾、前面由任意个 a 或 b 组成的字符串的 NFA。

该表达式对应的语言可以理解为：

L((a|b)^*aa)

即所有字母表 ${a,b}$ 上以 aa 结尾的字符串。

NFA 到正则表达式

NFA 到正则表达式的转换可通过逐步消去状态完成。基本思想是把经过中间状态的路径合并为一个正则表达式标记。

常见合并规则：

多条并行边合并为或表达式，例如 a 和 b 合并为 a|b
连续路径合并为连接表达式，例如 a 后接 b 合并为 ab
自环合并为闭包表达式，例如状态上有 a 自环，可形成 a*
经由某个中间状态的路径可合并为“进入路径 + 自环闭包 + 离开路径”

课件例子中，NFA 逐步消去中间状态后得到正则表达式：

a(ab|ba)a^*b

这个表达式表示：

字符串以 a 开始。
中间接 ab 或 ba。
后面接零个或多个 a。
最后以 b 结束。

构造 `(a|b)(c|d)*(e|f)` 的最简 DFA

目标正则表达式：

(a|b)(c|d)^*(e|f)

它描述的字符串结构为：

第一个字符是 a 或 b。
中间可以有零个或多个 c 或 d。
最后一个字符是 e 或 f。

第一步：转为 NFA。

结构可分为三段：a|b、(c|d)*、e|f

NFA 中先通过 a 或 b 进入中间部分，中间部分在 c 和 d 上循环，最后通过 e 或 f 到达终止状态。

第二步：NFA 确定化。

课件给出的 DFA 状态集合包括：

$S_0=\{0\}$
$S_1=\{1,2,3\}$
$S_2=\{2,3\}$
$S_3=\{4\}$

其中 $S_0$ 是初始状态， $S_3$ 是终止状态。

对应转换表可整理为：

状态	`a`	`b`	`c`	`d`	`e`	`f`
$S_0+$	$S_1$	$S_1$
$S_1$			$S_2$	$S_2$	$S_3$	$S_3$
$S_2$			$S_2$	$S_2$	$S_3$	$S_3$
$S_3*$

第三步：DFA 最小化。

初始划分：

\{S_0,S_1,S_2\}\cup\{S_3\}

进一步判断后得到等价状态：

\{S_0\}\cup\{S_1,S_2\}\cup\{S_3\}

因此 $S_1$ 和 $S_2$ 可以合并。

最简 DFA 的结构为：

初始状态 $S_0$
中间状态 $\{S_1,S_2\}$
终止状态 $S_3$

转换关系：

$S_0$ 读入 a 或 b 到达 $\{S_1,S_2\}$
$\{S_1,S_2\}$ 读入 c 或 d 仍留在 $\{S_1,S_2\}$
$\{S_1,S_2\}$ 读入 e 或 f 到达 $S_3$

第 9 到第 11 部分可以串成一条完整流程：先把 NFA 通过子集法确定化为 DFA，再用状态分离法化简 DFA；正则表达式可先转 NFA，再确定化、化简，最终得到可直接实现的最简 DFA。

课程笔记

#编译原理

编译原理课程笔记

https://blog.kisechan.space/2026/notes-compilers/

作者

Kisechan

发布于

2026年6月17日

更新于

2026年6月17日

许可协议

一些精神药物的服用体验下一篇

编译原理课程笔记

概论

高级语言的实现

编译方式

解释方式

转换方式

编译程序的组成

词法分析

词法分析器

符号和符号串

长度

连接

方幂

正则表达式

正则表达式描述单词

确定有限自动机 DFA

DFA 的表示方式

陷阱状态

DFA 接受的字符串

DFA 描述单词

DFA 的程序实现

NFA 的确定化

无 ε\varepsilonε 空边 NFA 的确定化

带 ε\varepsilonε 空边 NFA 的确定化

DFA 的化简

无关状态

等价状态

状态分离法

正则表达式和有限自动机的相互转化

正则表达式到 NFA

NFA 到正则表达式

构造 (a|b)(c|d)*(e|f) 的最简 DFA

无 $\varepsilon$ 空边 NFA 的确定化

带 $\varepsilon$ 空边 NFA 的确定化

构造 `(a|b)(c|d)*(e|f)` 的最简 DFA