编译原理：词法分析

发表于 2022-01-03 分类于编译原理本文字数： 1.3k

参考：中国大学 MOOC 国防科技大学编译原理

https://www.icourse163.org/course/NUDT-1003101005

功能

输入源程序、输出单词符号

< 种别, 单词自身的词 >

$ε$ 和 $ϕ$ 都是 $Σ$ 上的正规式，他们所表示的正规集为 ${ε}$ 和 $ϕ$
对任意的 $a \in Σ$ , $a$ 为其上的正规式，表示的正规集为 ${a}$
设 $e_{1}$ 和 $e_{2}$ 为 $Σ$ 上的正规式，表示的正规集分别为 $L (e_{1})$ 和 $L (e_{2})$
1. $(e_{1} | e_{2})$ 为正规式，表示的正规集为 $L (e_{1}) \cup L (e_{2})$
2. $(e_{1} \cdot e_{2})$ 为正规式，表示的正规集为 $L (e_{1}) L (e_{2})$ （集合的连接）
3. $(e_{1})^{*}$ 为正规式，表示的正规集为 $(L (e_{1}))^{*}$
4. 由有限次使用上述 3 步骤定义的表达式才是正规式，这些正规式表示的字集才是正规集

两个正规式的正规集相同

如： $b (a b)^{*} = (b a)^{*} b$

M = (S, Σ, f, S_{0}, F)

S 为有穷状态集， $Σ$ 为字母表，f 为状态转换函数， $S_{0}$ 为初态， $F$ 为终态

状态转换函数：

S \times Σ \to S

f (s, a) = s^{'}

s 状态下接收 a 转化为 s’

M = (S, Σ, f, S_{0}, F)

S 为有穷状态集， $Σ$ 为字母表，f 为状态转换函数， $S_{0}$ 为初态（一个集合）， $F$ 为终态

状态转换函数：

S \times Σ^{*} \to 2^{S}

f (s, a) = s^{'}

s 状态下接收 a 转化为 s’，s’ 为一个状态集合

L(M) = L(M’)，则 M 与 M’ 等价

判定两个自动机等价的算法是存在的

DFA 与 NFA 是等价的，可以将任何 NFA 转化为 DFA

DFA 易于程序实现，NFA 易于人工设计

M = (S, Σ, f, S_{0}, F)

引进新的初态节点 X 和终态节点 Y ， $X, Y \notin S$ ，从 X 到 $S_{0}$ 中任意状态节点连一条 $ε$ 箭弧，从 F 中所有状态结点连一条 $ε$ 箭弧到 Y （消除了 NFA 和 DFA 在初态和终态上的差别，新的初态只有一个为 X，新的终态只有一个为 Y）
引入新的状态来拆分字弧线（简化了弧上的字）

如： $S_{i} \overset{A B}{\to} S_{j}$ ，可以转换为 $S_{i} \overset{A}{\to} k \overset{B}{\to} S_{j}$
子集法：

$ε$ - 闭包： $ε$ - closure(I) 为 I 中的所有元素及从 I 中的元素经过任意条 $ε$ 弧所能到达的任何状态

$I_{a}$ 运算
$I_{a} = ε - c l o s u r e (J)$
$J$ 为 $I$ 经过 $a$ 弧所能到达的所有状态，再取闭包则为 $I_{a}$ ，也就是 $I$ 中的状态经过 1 条 $a$ 弧和若干条 $ε$ 弧所能到达的状态集合即为 $I_{a}$

创建矩阵（X 为转化后的初态）假设 $Σ = {a, b}$

$I$ $I_{a}$ $I_{b}$

$ε$ - closure({X}) $A_{1}$ $A_{2}$

$A_{1}$

$A_{2}$

相同的 $I$ 只在第一列出现一次，空集也需要放到 $I_{a}$ 中，最多会有 $2^{n}$ 行

将表视为状态转换矩阵，子集视为状态并编号。初态是 $ε$ - closure({X})，终态是所有包含 Y 的节点。

状态等价

若两个状态其中一个识别指定字后停留在终态，则另一状态也应如此，反之亦然。

状态可区别

存在某个字，两个状态的其中一个识别后停止于终态，另一个状态没有停止于终态。

状态集划分

划分目标：不相交的子集，两个子集之间是可区别的，而子集内是等价的

按照终态与非终态确定初始划分（ $ε$ 字可以区分它们）
假设划分为 $Π = I^{(1)}, I^{(2)}, . . ., I^{(m)}$ ，检查 $Π$ 中的每个子集，如果出现 $I_{a}^{(i)}$ 其中的元素包含在现行划分的 N 个不同的子集中，则需要将 $I_{a}^{(i)}$ 划分开来，按照其落入的集合划分。
若子集中包含初态，则选为初态，若包含终态，则选为终态。
每个子集选择一个代表代表这个子集中的所有状态，所有射向这个子集的元素的箭弧都射向代表，反之亦然

对任何正规式 r，都存在一个 FA M，是的 L(M) = L®

FA 构造正规式

正规式构造 FA

直到弧上都是字符或空字