实现正则表达式

2021-01-29 15:36:40

介绍如何使用有限自动机来实现正则表达式匹配,以及为什么标准回溯实现不是一个好主意。

具有子匹配跟踪的NFA:Perl规则| POSIX负责Jan Burgy编写的字节码机器和x86汤普森代码的音译。

如果您想阅读肯·汤普森(Ken Thompson)的1968年原始论文(请参阅下文),则希望随身携带。

Brian W. Kernighan和Rob Pike撰写的“正则表达式:语言,算法和软件”

您将看到的最干净,最简单的回溯实现。 (但仍回溯,因此在某些输入上运行非常缓慢。)

具有子匹配跟踪功能的高效(非回溯)NFA实现。接受UTF-8和宽字符Unicode输入。仅传统egrep语法,由Rob Pike撰写。

Michael Rabin和Dana Scott,“有限自动机及其决策问题,” IBM Journal of Research and Development 3(1959),第114-125页。 http://www.research.ibm.com/journal/rd/032/ibmrd0302C.pdf

介绍了NFA的概念,表明它们的功能与DFA相当。WonRabin和Scott a Turing Award

Ken Thompson,“正则表达式搜索算法”,ACM通讯11(6)(1968年6月),第419-422页。 http://doi.acm.org/10.1145/363347.363387(PDF)

第一个有效的正则表达式搜索。四页,但很密集:每次阅读时,我都会学到新东西。与您一起获取IBM 7094备忘单。另请参见有关该论文的演讲的旧幻灯片。

维尔·劳里卡里(Ville Laurikari),“带有标记过渡的NFA,它们转换为确定性自动机并应用到正则表达式”,在字符串处理和信息检索研讨会论文集,2000年9月。http://laurikari.net/ville/spire2000-tnfa.ps

M. Douglas McIlroy,“枚举常规语言的字符串”,Journal of Functional Programming 14(2004),第503-518页。 http://www.cs.dartmouth.edu/~doug/nfa.ps.gz(预印本)

与实现正则表达式匹配无关,但与使用Haskell进行正则表达式分析和操作的漂亮示例有关。