正则表达式引擎如何实现?

boilplate

[i=s] 本帖最后由 boilplate 于 2010-08-27 05:20 编辑 [/i]

具有 perlre 那些功能的正则表达式引擎都是如何实现的?

龙书上的 nfa 模拟，其实是运行时的 dfa。 没想出提供 perlre 那样功能的严谨的 nfa 模拟算法。

看了网上的现成作品， 一部份编译成中间代码, 有的甚至直接操纵表达式……

perl 本身是翻译成 perl 操作符?

pcre 用的似乎是 dfa,   但 dfa 不可能做出这些功能 , 况且其中   #if  #ifdef   过多， 不容易分清哪些是备用算法。 由于代码量过大，没细看。

如果用 nfa 实现， backreference 还好说， 如 {n,m} 这样的 Quantifier，豈不平添 m 个状态？ 况且后视怎么做？

网上不易找到相关讨论，不管中文/英文/德文的都很少。   是否有人能点拨点拨?  最好能顺帯推荐些大牛的文章。

prolj

亮点：英文/德文。

boilplate

P阿姨是专业打酱油的 ^^

Solidus

回复 1# boilplate


    跟你遇到过相同的问题，断断续续搜了一年左右才找到答案，其实是个挺容易的事儿，主要是你得换个实现思路。我当初也是没办法套用龙书上那计算regexp分析树的first-follow集合并生成DFA那个算法实现预搜索功能，主要是类似预搜索一类功能接受的语言就不是单纯的正则了，如果以前迭代一个表能解决的话，那么现在就得加点东西了（计数，堆栈等等）。实现方法很多，基本思想还是NFA那套，就是如果有N种可能，给他们排列个优先级，然后穷举它们，从实现上看，如果教科书上那些DFA是输入驱动状态的话，那么现在你可以用状态去消耗输入，当然，本身没什么不同，我这么说只是认为好理解一些。

我知道的有这么几种办法：

1.最容易的，例如有限次数的循环，预搜索，捕获等等功能，先确定你regexp的语法，之后生成分析树，然后执行这颗树，从根节点起，去匹配输入，如果根节点是a{3,5}，那你执行个for循环，匹配就得了，同理，如果跟节点是分支，则从左到右匹配子节点，预搜索也类似，子节点匹配成功了，则此节点成功，以此类推。

2.把regexp翻译成带无条件转移指令的中间代码（或者干脆就机器码，Ken Thompson大神196X年就这么干的，所以这玩意儿也是老掉牙的东西了），这个东西说白了就是，先做一个机器，这个机器有几种指令吧，例如匹配某个字符，匹配行首，行尾，预搜索，捕获，分支，JMP等等吧，生成指令这块和就和代码生成一样了，例如循环，(expr)*，那么会存在一个分支，一个是不断JMP到分支点，另一个是expr的下一个指令，(a|b|c|d)也一样，你就想成if(input == a) else .....这类东西，生成的分析树和代码都何其类似，最后就出来这么个编译好的一段指令。然后加载到这个机器上执行它们，然后你会发现，所有跳转和分支都跟NFA很相似，所以你就把它们想成一堆线程（这玩意儿就是NFA的转移），你得存储所有线程的上下文，例如input指针，当前指令等等，都加入到一个队列，之后顺序执行这个队列里的所有线程，这时候会有个很奇怪的问题，就是和分析树一样，你会发现有好几个接受状态，所以你得自己确定一个到底是接受哪个，例如是最左呢，还是最长呢，优先级问题哪个算法都存在，我也不知道标准做法是什么，我自己的选择是接受最左最长。
我的词法分析部分的执行模块用的就是这个方法，因为是我只是提取符号，所以回避了后向引用和捕获，不过也许对你有点帮助。http://code.google.com/p/arsenal ... enal/Lex/rgx_exec.c

3.就是给DFA增加状态，这个玩意儿我没实现过，也没读过具体引擎，所以不好瞎说说，大概思路应该是你得把所有乱七八糟的操作，例如捕获，预搜索等等，变成一个个状态，在到达这个状态后得执行附加的操作，例如捕获状态你可以记录一个输入点等等，这块我没搞过，所以不好细说了，例如怎么生成这个DFA等等我也不清楚，你要找到了答案不妨告诉我。


PS：我对这玩意儿的研究也很有限，所有可能有很多不对的地方，仅供参考。最好去编译器的新闻组上问问，我知道的东西都是那里面帖子里讨论的，就这个问题来说，其实挺老的了，60年代中期估计就成型了，主要是属于工程实现问题，所以书上都不写，其实也不太好写这东西，一般常见的编译器的书籍都是前面讲regex，后面分析和生成代码，总不能把这玩意儿移到前面讲去，也没见过什么专门讲实现regex引擎的书，所以这类东西主要都在乱七八糟的文献里，这玩意儿得慢慢搜，像我这种自学的就吃苦头了，要是有个Ken Thompson那样的老家伙在旁边告诉你点什么，这类玩意儿估计几个小时就能搞定，何苦费劲四处找去。

boilplate

回复  boilplate


    跟你遇到过相同的问题，断断续续搜了一年左右才找到答案，其实是个挺容易的事儿 ...
Solidus 发表于 2010-09-01 01:53

多谢椦楼上


虽然原理知道,但实际操作起来巨难, 用NFA试的时候容易 stack overflow 不说, 效率很不理想.    况且通过添加特殊状态来实现复杂的功能也不易设计出优美的方案.

boilplate

不过直接通过词法树来匹配,  想来实现某些 perlre 类似的复杂功能也容易.
那时也想做过. 但觉得优化潜力没有自动机大(毕竟树的结构比较死板)



我写这些是纯娱乐的, 没什么实际需求，只是想把所学的练一练， 所以暂且挌一挌   等有了优美的方案再继续

sonald

http://swtch.com/~rsc/regexp
正则表达式的历史、一些典型实现的分析，说的挺明白的。应该有点帮助。

flw2

没学习过perlre 到底有什么特征， 所以没法回答你的问题
你需要这种特征最好的方法就是看一个实现，通常代码也就1-2万行吧
看别的资料或者空想很难得到答案

你说pcre是dfa的，我怀疑里面压根就没有dfa
grep里面先用dfa去搜索，解决backreference 再用nfa，构造dfa用的龙书上一模一样的算法

a{n,m}在grep中就是  aaaaaaa*a*的简写

flw2

正则表达式的历史、一些典型实现的分析，说的挺明白的。应该有点帮助。
sonald 发表于 2010-10-10 21:22

    这个内容很不错