词法分析
字母表的运算
易错点：
运算优先级
常见表达
例题
词法分析关键知识点
2024.3.14
正则表达式、NFA、DFA、最简DFA的转换
在编译原理中，正则表达式、NFA（非确定有穷自动机）、DFA、最小化DFA的转换在词法分析中是十分重要的一个环节。
- 一般来说：我们经常碰到的问题类型都是如下类型的： 正则表达式->NFA->DFA->最小DFA。
- 对于这类问题我们可以经过以下三个步骤进行解决： （1）正则表达式->NFA（三个替换规则/MYT算法）； （2）NFA->DFA （子集构造法）； （3）DFA->最小DFA（分割法）。
1. 如何将正则表达式转为NFA
McNaughton-Yamada-Thompson算法（MYT算法）
2. 如何将NFA转为DFA
可以证明，L(NFA) ⊆ L(DFA)且L(NFA) ≡ L(DFA)
子集构造法
- 预备知识
(1 )状态集的ε-闭包：状态集I中的==任何状态s经任意条ε弧能到达的所有状态的集合，定义为状态集I的ε -闭包，表示为ε -closure()。
(2)状态集的a弧转换: 状态集I中的任何状态s经过一条a弧而能到达的所有状态的集合，定义为状态集I的a弧转换，表示为move(l,a)。
(3)状态集的a弧转换的闭包： la= ε-closure(move(l,a))。
- 子集构造法求DFA的步骤
对于输入字符集合∑={a1,a2…ak}，我们构造一张k+1列的表格（行数未做限制）。一般来来讲，步骤如下：
（1）表格的第一行第一列的位置写的是从NFA的起始节点经过任意个ε所能到达的结点集合S0的ε-closure(S0)。
（2）接着填写该行剩余位置的信息，做法是在对应的位置上填写la= ε-closure(move(l,a))。Ia表示从该集合开始经过一个a所能到达的集合，经过一个a的意思是可以略过前后的ε。
（3）检查该行上的所有状态子集，如果未在第一列出现，则将该状态子集写到第一列。
（4）重复（2）（3）的步骤，直到所有状态子集均在第一列上出现即可。(也就是不产生新状态)
（5）然后给状态子集重新编号，需要注意的是，包含原来终态的状态子集为新的终态，按照对应的转换函数f，构造对应的DFA即可。
另一种描述方法：正则表达式和自动机（DFA&NFA）
NFA的确定化：由NFA构造出与其等价的DFA称为NFA确定化。其算法如下：
已知 $ A:NFA$， 构造$A’:DFA$。
- 令$A’$’的初始状态为$I_0’=ε_CLOSURE({S1,S2,…Sk})$，其中$S1…Sk$是A的全部初始状态。
- 若$I={S_1,…,S_m}$是$A’$的一个状态，$ a∈∑$，则定义$ f’(I, a)=I_a$，将$ I_a$加入$ S’$’，重复该过程，直到$S’$不产生新状态。
- 若$ I’={S_1,…,S_n}$是$A’$的一个状态,且存在一个$S_i$是$A$的终止状态，则令$ I’$为$ A’$的终止状态。
举个例子：
这个NFA确定化的过程如下：
- NFA的初始状态是1，该状态可以接收一个空闭包ε到状态2。因此DFA的初始状态是 {1,2}
- 由上可知DFA的初始状态是 {1,2}，{1,2} 中的 1 接收输入字a可转换到 {4,5}，而 {4,5} 接收空闭包到状态 {6,7}，其中 6 还可以接收空闭包到状态 2。 而 2 不能接收输入字 a。因此 {1,2} 接收输入字a可转换到 {2,4,5,6,7}。
- {1,2} 中的 1 不能接收输入字 b；2 接收输入字 b 到 状态3，状态 3 还可以接收空闭包到状态 8。因此 {1,2} 接收输入字b到状态 {3,8}。
- 进行如上三步后，DFA 中的状态有 {1,2}、{2,4,5,6,7}、{3,8}，其中 {1,2} 状态转换后的状态已经算完。
- 接下来，我们再看DFA的状态 {2,4,5,6,7}。该状态不能接收输入字a；该状态中的2状态接收 b 到达 3 状态，该 3 状态接收空闭包还可到达8状态。其中的 6 状态和 7 状态均可接收输入字b到达9状态。于是DFA的状态中多了一个状态{3,8,9}。
- 我们再看DFA中状态{3,8}。其中的状态8接收输入字a可以到达状态9；状态{3,8}不能接收输入字b。因此 DFA 的状态增加一个状态{9}。
- 再来看状态{3,8,9}，其中的状态8接收输入字a可以到达状态9；该状态不能接收输入字b。由于DFA中已经有状态{9}，不再重复加入 DFA 的状态。
- 最后只有一个状态 {9} 了，该状态不能接收任何输入字。
- 总结出DFA中有状态 {1,2}，{2,4,5,6,7}，{3,8}，{3,8,9}，{9}。其中包含有NFA的终止状态 6 7 9 中任意一个状态的状态是DFA的终止状态。
表格如下：
状态 \ 输入字 a b +{1,2}（新的1） {2,4,5,6,7}（新的2） {3,8}（新的3） -{2,4,5,6,7}（新的2） {} {3,8,9}（新的4） {3,8}（新的3） {9}（新的5） {} -{3,8,9}（新的4） {9}（新的5） {} -{9}（新的5） {} {} 最终转化出来的DFA如下：
例子
先从初态0开始求：【因为每个状态通过一条ε弧到达自己本身，所以求得ε的闭包包含自己】
-
（1）求0的ε的闭包：经过任意条ε所能到达的状态，集合为{0,1,3,4,5,6,7,9}
-
（2）求0的a弧转换：1经过a弧到达2，4经过a弧到达4，其余没有经过一条a弧到达某个状态，所以集合为{2,4}
-
（3）求a弧转换的闭包：{2,4}分别经过任意条ε所能到达的状态，集合为{2,4,6,7,9}
-
（4）求0的b弧转换：5经过b到5，7经过b到8，，其余没有经过一条b弧到达某个状态，所以集合为{5,8}
-
（5）求b弧转换的闭包：{5,8}分别经过任意条ε所能到达的状态，集合为{5,6,7,8,9}
0的ε-闭包：{0,1,3,4,5,6,7,9} 0的a弧转换：{2,4} 0的a弧转换的ε-闭包：{2,4,6,7,9} 0的b弧转换：{5,8} 0的b弧转换的ε-闭包：{5,6,7,8,9}
现在列一个表格：
-
（1）表格的列数为输入字符的个数+1，此题为a，b两个输入字符，所以为3列。
-
（2）第一列第一行填写初态的ε-闭包（此题0的ε-闭包），第二列第一行填写初态的a弧转换的ε-闭包（此题0的a弧转换的ε-闭包），第三列第一行填写初态的b弧转换的ε-闭包（此题0的b弧转换的ε-闭包）……以此类推。
-
（3）第一列的第二行以下填入上一行第二列以后的没有出现过的状态集。（此题第一行第二列第三列都没有出现在第一列中，将他们填入第一列）
| $I$ | $I_a$ | $I_b$ |
|---|---|---|
| {0,1,3,4,5,6,7,9} | {2,4,6,7,9} | {5,6,7,8,9} |
| {2,4,6,7,9} | ||
| {5,6,7,8,9} |
下图为填好的表：
-
新的终态的判断方法就是包含原来终态的集合就为终态，例如此题原来终态为9，所以包含9的集合就为终态，[双圈代表终态]；
-
新的初态就是包含原来初态的集合就为初态，例如此题原来初态为0，所以包含0的集合就为初态
为表里的状态集重新标上号：
可以得到下面的图：
这个图是还不是最小化的DFA，还需要DFA最小化。但下面DFA最小化重新举例。
3. 如何最小化DFA
一句话简单描述就是，首先初始化分为两个集合{Final-state}{Non-final state}，然后看集合中状态是不是等价（经过ε的输入后，新状态是否还在集合中），不是的话就要划分，划分规则就是产生状态一致的分到一起。
分割法
预备知识
（1）无关状态
- ①多余状态：对于一个状态Si ，若从开始状态出发，不可能到达该状态Si，则Si为多余（无用）状态。
- ②死状态：对于一个状态Si，对任意输入符号a，若转到它本身后，不可能从它到达终止状态，则称为Si为死状态。S2为死状态。多余状态和死状态又称为无关状态。
（2）等价状态：若Si为自动机的一个状态，我们把从Si出发能导出的所有符号串集合记为L(Si)。设有两个状态Si和Sj，若有L(Si)=L(Sj)，则称Si和Sj是等价状态。
（3）可区别状态：Si，Sj不是等价状态即为可区别状态。一般有两种情况：
- ①终止状态和非终止状态是可区别状态。
- ②状态Si，Sj对于∀a∈∑，必须转到等价的状态里面，否则称其实可区别的。
分割法求最简DFA的步骤
（1）首先将DFA的状态集进行初始划分，分成π=(S-Z,Z)。【其中Z为终态集合，S-Z为非终态，终态对于非终态是可以区分的】
（2）用下面的过程对π构造新的划分π new， 对π中每个组G，满足以下条件：
- ① 任意两个状态Si和Sj在同一组中
- ② move(Si, a) 和move(Sj, a) 是到不同的组中 则说明Si和Sj是可区别的，可进行划分，在π new中用刚完成的对G的划分代替原来的G， 否则不可以进行划分。
（3）重复执行(2)的操作，直到π中每个状态集都不能再进一步划分为止。
（4）合并等价状态，在每个G中，取任意状态作为代表，删去其它状态。将删去的状态关系全部转到代表状态。
（5）删去无关状态，包括从其它状态到无关状态的转换弧都都删掉。
例子
易错点
lec_3
NFA→DFA的空间复杂度和时间复杂度
lec-3
