实现正则表达式

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

具有子匹配跟踪的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进行正则表达式分析和操作的漂亮示例有关。