1

是否有任何关于如何实现自己的正则表达式库的正式文档？现有正则表达式库的创建者基于哪些正式文档（如果有）来编写代码？

4

4 回答 4

1

我已经编写（并放弃了）一个 javascript 解析器，包括正则表达式支持。我基于 ECMAscript 定义，根据它本身使用 Perl5 正则表达式。这是 ECMA 262，我使用的是 1999 年 12 月的第 3 版。（现在有一个较新的版本，我不知道它在正则表达式的定义中是否完整。）

于 2012-12-03T12:29:35.617 回答
1

任何关于自动机理论和/或编译器构造的优秀教科书，例如Hopcroft 和 Ullman，都涵盖了正则表达式及其与可以编译的有限状态自动机的关系。几本关于自然语言处理的教科书也是如此，其中通常使用有限状态方法，例如Jurafsky 和 ​​Martin。

（Ullman 本人甚至在 Coursera 上开设了一门课程，但新课程尚未公布。）

至于当前 RE 库基于哪些文档的问题：基于我引用的教科书和现有实现。我知道的第一个 RE 实现是Ken Thompson 的 QED 版本，ca。1967. 不幸的是，QED 网站上的技术报告引用了很少的参考文献，并且没有与 RE/FA 理论相关。我确信这些想法最终可以追溯到 Kleene 的正则语言理论，该理论是在 1950 年代发展起来的。

于 2012-12-03T12:30:03.120 回答
0

正则表达式被称为正则，因为这是它们所代表的状态机的属性。简而言之，一种可能的实现可能使用只是表的状态机。正则表达式解析器将为正则表达式创建许多状态和转换，执行它会根据转换遍历状态。

例如 /ab+/ 生成类似：

state \ next char:  a       b       $       *
[initial state]     goto 1  fail    fail    fail
1                   fail    goto 2  fail    fail
2                   fail    goto 2  match   fail

（其中 $ 是字符串的结尾，* 是任何其他字符）

于 2012-12-03T12:32:38.960 回答
0

我一直在寻找正则表达式，并且发现了一个有趣的问题，据我所知关于它们的问题 问题：为什么正则表达式可以具有指数运行时间？

接受的答案表明，基于链接的文章，RegExp实现（也在 Perl 中使用）“有点”慢，并且有一个更快/更简单的算法，被许多好的旧 Unix 工具（如 grep）使用。

这个链接直接引出了前面提到的文章：Regular Expression Matching Can Be Simple and Fast , ( part2 , part3 )

如果它是实际的，你应该使用这个算法而不是 Perl 的算法来考虑它。

于 2014-04-06T09:47:16.060 回答