说明:本系列文章介绍的算法均来自编译原理(龙书)一书,如果读者对代码没有兴趣,只想了解算法思路,完全可以阅读龙书相关章节内容,比我讲得清晰透彻。
序:
啃编译原理半年以来,任然徘徊在前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进行最小化处理。
说明:本系列文章介绍的算法均来自编译原理(龙书)一书,如果读者对代码没有兴趣,只想了解算法思路,完全可以阅读龙书相关章节内容,比我讲得清晰透彻。
序:
啃编译原理半年以来,任然徘徊在前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进行最小化处理。
分享到:
相关推荐
编译原理课的大作业 包含三个小实验 在一个cpp文件里 正则表达式转换为nfa nfa转换为dfa dfa最小化 个人原创代码
构造正则表达式的简化DFA算法论文 介绍了构造等价于给定正则表达式的简化确定有限自动机(DFA) 的算 法. 方法是首先构造与正则表达式等价的非确定有限自动机(NFA) , 这里省略了构 造带E动作的有限自动机的操作, 然后...
JAVA实现的正则表达式转换成DFA,并将DFA用Graph画出,画图须安装Graph。
基于Java实现了DFA,NFA,DFA最小化,NFA转化为DFA以及正则表达式转化为NFA的算法,对于初学者来说,是学习词法分析的一份不错资源
很好的能把正则表达式转化成 nfa 和DFA
正则表达式DFA原理正则表达式DFA原理正则表达式DFA原理正则表达式DFA原理
包含正则表达式解析、生成NFA、生成DFA、生成最小DFA、生成C代码的xlex
内容主要包括:自定义正则文法(在ProgramManager类中自定义),根据正则文法和输入的正则表达式构建NFA,NFA自动构建DFA,DFA最小化,DFA匹配字符串。其中含有大量的中文注释,并提供了测试方法。本人还是学生,...
word文档,里面是一次编译原理作业,为偶数个a和偶数个b构成的a、b串的集合L的正则表达式、右线性表达、及DFA
正则表达式转换为NFA,dfa,确定化 简单 方便实现
用VC 6.0运行,完美编译运行,反正我们老师检查是完美的过
正则表达式转NFA->NFA转DFA->最小化DFA->测试字符串是否匹配
正则表达式到dfa.rar
学校的课程设计,非常完整,里面包含源程序和实验报告,详细的程序流程图。 实验要求:正则表达式--NFA--DFA--最小DFA
正则表达式及NFA-DFA-MFA 正则表达式及NFA-DFA-MFA
编译原理课程设计之正则表达式与自动机之间的变换
精通正则表达式第三版 搜集于网络 前言..........I 第1章:正则表达式入门.... 1 解决实际问题... 2 作为编程语言的正则表达式... 4 以文件名做类比... 4 以语言做类比... 5 正则表达式的知识框架... 6 对于...
上编译原理课的时候做的几个小程序,包含一个简单的词法分析程序、正则表达式-NFA-DFA-MFA转换程序、表达式求值语义分析程序,其中正则表达式-NFA-DFA-MFA重点写的,花了不少心思,写得不是特别满意,今后会重新上传...
(1)C++源代码扫描程序识别C++记号。 C++语言包含了几种类型的记号:标识符,关键字,数(包括整数、浮点数),字符串、注释、特殊符号(分界符)和运算符号等。 (2)打开一个C++源文件,打印出所有以上的记号。 ...