正则表达式引擎的构建——基于编译原理DFA(龙书第三章)——1 概述

说明:本系列文章介绍的算法均来自编译原理(龙书)一书,如果读者对代码没有兴趣,只想了解算法思路,完全可以阅读龙书相关章节内容,比我讲得清晰透彻。


序:

    啃编译原理半年以来,任然徘徊在前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进行最小化处理。

相关文章
相关标签/搜索