任务:
源文件->记号流
方法:
1. 手工构造
2. 自动构造
手工构造:
实现标识符与关键字通过转移图完成.
然后再通过hashtable特判即可.
自动构造:
Thompson算法将正则表达式转化为NFA
五种情况,两种基本的直接构造,三种复合的递归构造
子集构造算法 NFA-DFA
stack = []//遍历的结构
Q = []//所以的DFA状态,判重
D[,] = []//DFA结果
push( ε闭包(n0)) //将起始点做为q0
loop until stack==NULL
q = pop() //状态弹栈
loop every char:
t = ε闭包(delta(q,c)) //1.根据转移函数得到NFA状态,求ε闭包
D[q,c] = t//q状态通过c到t状态
if(t not in Q)
add(Q,t),push(t)
如果新状态有NFA的结束态,它就是结束态
//这里的t not in Q 为什额?
//因为构造的NFA比较特殊,往前的转移符号都是因为ε,而这个符号必然导致新生成的点有可能和之前的重复,所以不用加入
Hopcroft 最小化算法
节省空间,缩点缩边(图特别稀疏)
将所有点分为结束与非结束两个集合
loop until all sets not changes:
split(S)//对与同一集合内部的所有点,对同一字符转换至不同集合则就可以切分为若干集合
1. 转移表 与图论中的转移一样
原文链接：https://www.f2er.com/regex/360495.html