网站改版准备,三维宣传片制作公司,怎么在网站后台挂马,网站前后端的关系说明#xff1a;本系列文章介绍的算法均来自编译原理#xff08;龙书#xff09;一书#xff0c;如果读者对代码没有兴趣#xff0c;只想了解算法思路#xff0c;完全可以阅读龙书相关章节内容#xff0c;比我讲得清晰透彻。 序#xff1a; 啃编译原理半年以来#xf…说明本系列文章介绍的算法均来自编译原理龙书一书如果读者对代码没有兴趣只想了解算法思路完全可以阅读龙书相关章节内容比我讲得清晰透彻。 序 啃编译原理半年以来任然徘徊在前4章其间反反复复时而不求甚解时而略有所悟。其间接触到正则表达式对其实现原理颇有兴趣于是百度之、谷歌之以求解惑。 先是搜索到不少国内发表的学术论文和各位大侠博客上的文章后又通过文章链接中的链接找到一篇不错的老外写的文章并附有源码看完了其文章基本上和编译原理龙书中介绍的先从正则表达式构造NFA再将NFA转化为DFA最后在优化、化简DFA的思路一样。而我在下载其代码后稍微看了一些片段试运行了一下发现代码写的有BUG内存释放有问题略觉不爽。于是便想自写一个玩玩但如若还按照从正则表达式到NFA再从NFA到DFA的过程又觉得重复别人的老路参考别人的代码颇无趣味。 老外的文章和代码下载地址在这里http://www.codeproject.com/Articles/5412/Writing-own-regular-expression-parser 于是翻看龙书第三章后半部分看到有直接从正则表达式构造得到DFA的算法过程。觉得可以一试于是就有了这篇系列文章有了2个来星期的1000多行代码含空行^_^。 根据正则表达式构造最小DFA的过程总结如下 1 根据正则表达式构造抽象语法树T。 2 从T的根节点开始进行深度优先遍历对每一个节点计算该节点的4个函数nullable, firstpos, lastpos, followpos。 3 从T的根节点N0开始构建状态集列表LIST开始时状态集链表LIST中只包含firstpos(N0)。 4 遍历LIST中的各个元素开始的时候LIST中只有一个元素假设当前遍历到第i个元素LIST(I)是一个集合集合中每个节点对应的输入字符是不一样的按照输入字符对节点进行分组例如代表字符a的分在一个组中代表字符b的分在一个组中对每个组中各个节点K计算followpos(K)followpos(K)也是一个集合K可能不止一个得到的结果可能是多个集合将这多个集合合并为一个集合S。如果这个集合S在LIST中还没有出现过则将这个集合S加入到LIST中。同时不管S是否在LIST中出现过没有都需要记录下转换过程LIST(i)经过某个字符前面分组过程依据的字符到达集合S。就这样一边处理LIST链表一边记录转换过程直到LIST中的元素依次从头到尾都被处理完毕。 最后得到的LIST链表和所有转换过程记录就构成了一个有向图实质上就是一个DFA确定性有穷状态自动机。 5 对得到的DFA进行最小化处理。 转载于:https://www.cnblogs.com/snake-hand/archive/2013/06/09/3129886.html
