词法分析学习
发布时间:2020-12-14 01:17:41 所属栏目:百科 来源:网络整理
导读:任务: 源文件-记号流 方法: 1. 手工构造 2. 自动构造 手工构造: 实现标识符与关键字通过转移图完成. 然后再通过hashtable特判即可. 自动构造: Thompson算法将正则表达式转化为NFA 五种情况,两种基本的直接构造,三种复合的递归构造 子集构造算法 NFA-DFA stac
任务: 源文件->记号流
方法: 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)//对与同一集合内部的所有点,对同一字符转换至不同集合则就可以切分为若干集合
根据DFA生成代码
1. 转移表 与图论中的转移一样
2. 跳转表 根据每个状态对应的字符生成代码,这样省空间(图特别稀疏)
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |