复习材料，不建议阅读

词法分析

形式化描述工具（基础概念）

正规文法

也就是 3 型文法，大家都知道。也就是左边一个非终结符号，右边只能最右出现非终结符号。

正规式

也叫正则表达式，这里不多赘述。只能描述正规语言，不能描述上下文相关的语言。

它和正规文法的等价描述可以相互转换。

有穷自动机

确定有穷自动机 DFA

一个确定的有穷自动机 $M$ 是一个五元组:

M = ( K , \sum , f , S , Z )

其中:

$K$ 是一个有穷集，它的每个元素称为一个状态。
$\sum$ 是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号表。
$f$ 是转换函数，是 $K \times E \to K$ 上的映像。例如， $f(k_i, a)=k_j (k_i \in K, k_j \in K)$ ，就意味着，当前状态为 $k_i$ 、输入字符为 $a$ 时，将转换到下一状态 $k_j$ ，把 $k_j$ 称作 $k_i$ 的一个后继状态。
$S \in K$ ,是唯一的一个初态。
$Z \subseteq K$ ,是一个终集，终态也称可接受状态或结束状态。

初态结点标记 $\Rightarrow$ 、 $-$ ，终添结点标记 $+$ 、双圈。

一个DFA 可以表示成一个状态图(或称状态转换图)。假定 DFA $M$ 含有 $m$ 个状态, $n$ 个输入符号,那么这个状态图含有 $m$ 个结点,每个结点最多有 $n$ 个射出,整个图含有唯一一个初态结点和若干个终态结点。

例3.6 DFA $M=({S,U,V,Q},{a,b},f.S, {Q})$ ,其中 $f$ 定义为

f(S,a) =U f(U,a)=Q f(V,a) =U f(Q,a) = Q \\ f(S,b) =V f(U,b) =V f(V,b) = Q f(Q,b)=Q

作状态图为：

一个 DFA 还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入符号，矩阵元素表示相应状态和输入符号将转换成的新状态，即行列为 $f(k, a)$ 的值，可以用 “ $\Rightarrow$ ” 标明初态；否则第一行即是初态，相应终态行在表的右端标以 1，非终本标以 0。

例 3.6 矩阵为：

状态\符号	a	b	（表外）
S	U	V	0
U	Q	V	0
V	U	Q	0
Q	Q	Q	1

对于 $\sum^*$ 中的任何符号串 $t$ ，若存在一条从初态结点到某一终态结点的道路，且这条路上所有弧的标记符连接成的符号串等于 $t$ ，则称 $t$ 可为 DFA $M$ 所接受,若 $M$ 的初态结点同时又是终结点，则空字可为 $M$ 所识别(接受)。 简单来说就是一个终结符号串能够由初态最终推导至终态，它就是可接受的。

其确定性最终表现在转换函数 $f$ 的单值性，即对任何状态 $k$ 和输入符号 $a$ 通过映射 $f(k, a)$ 唯一确定下一个状态；图中每个结点射出弧不超过输入符号数量，且一定是不同输入符号标记的。

不确定有穷自动机 NFA

定义依然是五元组

M = ( K , \sum , f , S , Z )

和 DFA 区别在于

$f$ 是一个从 $K \times \sum^*$ 到 $K$ 的全体子集的映像，即 $K \times \sum^* \to 2^k$ ，其中 $2^k$ 表示 $K$ 的幂集。

图也是类似，但是结点射出的弧不再有数量和重复的限制，直接使用 $\sum^*$ 中的一个串标记。

例3.7 一个NFA $M=({0,1,2,3,4}, {a,b},f,{0},{2,4})$ ，其中:

f(0,a)={0,3} \\ f(0.b)={0,1} \\ f(1,b)={2} \\ f(2.a)={2} \\ f(2,b)={2} \\ f(3,a)={4} \\ f(4,a)={4} \\ f(4,b)={4}

图和矩阵就是这样，注意弧的标记：

状态	a	b	（表外）
0	{0, 3}	{0, 1}	0
1	∅	{2}	1
2	{2}	{2}	1
3	{4}	∅	0
4	{4}	{4}	1

NFA 转换为等价的 DFA

一般用子集法作表，以 3.7 的为例

把初态写在最左边，然后构建已知符号集转移后状态
状态 a b
{0} {0,3} {0,1}
把所有不在状态列的结果移入状态列，对于这些集合继续构建转移后状态
状态 a b
{0} {0,3} {0,1}
{0,3}
{0,1}

一直这样将结果移入状态列继续构建，直到所有结果都在状态列中

DFA 状态	a	b
{0}	{0,3}	{0,1}
{0,3}	{0,3,4}	{0,1}
{0,1}	{0,3}	{0,1,2}
{0,3,4}	{0,3,4}	{0,1,4}
{0,1,2}	{0,2,3}	{0,1,2}
{0,1,4}	{0,3,4}	{0,1,2,4}
{0,2,3}	{0,2,3,4}	{0,1,2}
{0,1,2,4}	{0,2,3,4}	{0,1,2,4}
{0,2,3,4}	{0,2,3,4}	{0,1,2,4}

根据这个就得出了 NFA 的 DFA。

DFA 化简

无用（多余）状态：从开始状态任何输入都到达不了的状态，或从这个状态没有通路到达终态。

直接删掉无用状态；然后用分割法：

把变换至接受（到终态）的状态和非接受的分割为两块
检查每块转移目标的块存在不同的状态，进行分割
一直进行 2 直到无法分割
合并同一块的状态

例：

假设有以下 DFA：

状态	a	b	类型
0	1	0	初始
1	2	0	-
2	2	3	-
3	2	0	接受

初始分割

分割块	状态
P₀（非接受）	{0, 1, 2}
P₁（接受）	{3}

检查 P₀ = {0, 1, 2}

检查各状态的转移目标所属的分割块：

状态	δ(a)	δ(b)	δ(a)所属块	δ(b)所属块
0	1	0	P₀	P₀
1	2	0	P₀	P₀
2	2	3	P₀	P₁

发现状态 2 的 δ(b) 转移到 P₁，而 0, 1 转移到 P₀，需要分割：

分割块	状态
P₀	{0, 1}
P₁	{2}
P₂	{3}

检查 P₀ = {0, 1}

状态	δ(a)	δ(b)	δ(a)所属块	δ(b)所属块
0	1	0	P₀	P₀
1	2	0	P₁	P₀

发现状态 0 的 δ(a) 转移到 P₀，而 1 转移到 P₁，需要分割：

分割块	状态
P₀	{0}
P₁	{1}
P₂	{2}
P₃	{3}

无法再分割，终止

每个状态独立，该 DFA 已是最小化形式。

唯一性：最小化 DFA 在同构意义下是唯一的
等价性：最小化 DFA 与原 DFA 接受完全相同的语言
死状态：如果存在死状态（所有输入都转移到自身），且不是接受状态，可以删除

# 编译原理——词法分析