为正则表达式编写解析器

Question

为正则表达式编写解析器

pythonregexparsing

79

即使我已经编程多年，但我很惭愧地说，我从来没有完全掌握正则表达式。通常情况下，当遇到需要使用正则表达式的问题时，我可以（在查看语法后）编写出一个合适的表达式，但这是一种技术，我发现自己越来越频繁地使用。

因此，为了教自己并正确地理解正则表达式，我决定做我学习某些东西时总是做的事情，那就是尝试编写一些雄心勃勃的东西，但只要我感觉已经学到足够多，就会放弃。

为此，我想在Python中编写一个正则表达式解析器。在这种情况下，“学到足够多”意味着我想实现一个完全理解Perl扩展正则表达式语法的解析器。然而，它不必是最有效的解析器，甚至不必在实际应用中可用。它只需要正确匹配或不匹配字符串中的模式。

问题是，我从几乎不知道正则表达式如何解析和解释（除了涉及有限状态自动机），怎么入手呢？欢迎提供任何建议，以应对这个相当令人生畏的问题。

编辑：我应该澄清的是，虽然我将在Python中实现正则表达式解析器，但我对示例或文章所写的编程语言并不过分关注。只要不是Brainfuck，我通常都能理解足够多，让它值得我的努力。

- Chinmay Kanchi

1

+1 有趣的想法。如果你能实现它，你将成为正则表达式专家 ;) - Byron Whitlock

2

这篇文章介绍了如何构建一个简化的正则表达式解析器（不涉及Python），非常有趣。 - systempuntoout

2

http://perl.plover.com/Regex/article.html 是一个使用自动机解释正则表达式引擎的文章。您可能还想考虑一个更简单的项目，这个项目之前在这里提出过，就是编写一个将正则表达式翻译成英语的翻译器。例如，(foo|bar)(baz)+ 应该翻译为 要么是 "foo" 或者 "bar"，然后是一个或多个 "baz"。Pyparsing (http://pyparsing.wikispaces.com/Documentation) 可以帮助实现这个项目。 - Katriel

2

好的，我会从简单的开始，实现一个正则表达式解析器（不是Perl风格的正则表达式，而是原始类型的）。如果我没记错的话，书籍《编写优美代码》的第一章是一个漂亮、优雅的正则表达式解析器实现。虽然它是用C语言编写的，而不是Python，但仍然是一个不错的起点。 - Mic

1

@Chinmay：只是出于好奇，你的正则表达式解析器写得怎么样了？花了多长时间？它有效吗？我也在考虑自己做一个。 - jackthehipster

显示剩余4条评论

5个回答

22

我已经为Mark Byers点了一个+1，但据我记得，这篇论文并没有详细说明正则表达式匹配的工作原理，只是解释了为什么一种算法很差而另一种算法好得多。也许链接中有相关内容？

我将专注于好的方法——创建有限状态自动机。如果你限制自己只使用没有最小化的确定性自动机，那么这并不太困难。

我将（非常快速地）描述现代编译器设计中采用的方法。

想象你有以下正则表达式...

a (b c)* d

这些字母代表要匹配的文字。星号 * 通常表示零个或多个重复。基本思想是根据点规则推导出状态。我们将零状态视为尚未匹配任何内容的状态，因此点放在最前面...

0 : .a (b c)* d

唯一可能的匹配是 'a'，因此我们推导出的下一个状态是...

1 : a.(b c)* d

现在我们有两种可能性 - 匹配'b'（如果至少重复了'bc'）或匹配'd'。注意 - 我们基本上在进行二元图搜索（深度优先或广度优先或其他），但我们是在搜索时发现二元图的。假设采用广度优先策略，我们需要将其中一个情况排队以供稍后考虑，但我将在此忽略此问题。无论如何，我们已经发现了两个新状态...

2 : a (b.c)* d
3 : a (b c)* d.

第三状态是一个结束状态（可能不止一个）。对于第二状态，我们只能匹配“c”，但在点后面的位置需要小心处理。我们得到了“a。（b c）* d” - 这与第一状态相同，因此我们不需要新的状态。

如果我没记错，在现代编译器设计中的方法是当你遇到运算符时翻译规则，以简化点的处理。状态1将被转换为...

1 : a.b c (b c)* d
    a.d

换句话说，你的下一个选择是匹配第一个重复项或跳过重复项。从这个状态开始的下一个状态等价于状态2和3。这种方法的优点是可以丢弃所有过去的匹配（'.'之前的所有内容）因为只关心未来的匹配。通常这会产生一个较小的状态模型（但不一定是最小的）。

编辑：如果您丢弃已匹配的详细信息，则状态描述是表示从此处开始可能发生的字符串集合的表示形式。

就抽象代数而言，这是一种集合闭包。代数基本上是具有一个（或多个）运算符的集合。我们的集合是状态描述的集合，我们的运算符是转换（字符匹配）。闭合集是应用任何运算符到集合中的任何成员总是产生另一个在集合中的成员的集合。集合的闭包是最小的较大集合，它是封闭的。因此，基本上，从明显的起始状态开始，我们正在构建相对于我们的转换运算符集合封闭的最小状态集合 - 可达状态的最小集合。

这里的“最小”是指闭包过程 - 可能存在一个更小的等效自动机，通常称为最小自动机。

有了这个基本想法，就不太难说“如果我有两个表示两组字符串集合的状态机，如何推导出第三个表示并集”（或交集，或集合差异...）。您的状态表示将是来自每个输入自动机的当前状态（或一组当前状态），以及可能的其他细节，而不是点规则。

如果您的常规语法变得复杂，可以进行最小化。基本思想相对简单。将所有状态分组为一个等价类或“块”。然后，反复测试是否需要拆分块（状态实际上不是等效的），并针对特定转换类型进行处理。如果特定块中的所有状态都可以接受相同字符的匹配，并在此过程中到达相同的下一块，则它们是等效的。

Hopcroft算法是处理这种基本思想的有效方法。

关于最小化的一个特别有趣之处是，每个确定性有限自动机都具有精确的一种最小形式。此外，Hopcrofts算法将生成相同的表示形式，即使它从哪个大型案例的哪个表示开始。也就是说，这是一种“规范”表示，可用于导出哈希或进行任意但一致的排序。这意味着您可以使用最小自动机作为容器键。

以上内容可能在定义方面有些粗略，因此在使用这些术语之前，请确保自己查找任何术语，但是运气好的话，这会给您提供一个基本思想的公平快速介绍。

顺便说一句-浏览Dick Grunes site的其余部分-他有一本免费的解析技术PDF书。《现代编译器设计》第一版在我看来相当不错，但正如您所看到的，第二版即将出版。

- user180247

2

这个技巧与生成LR解析器的方法相同：将代表解析器状态的点通过一组语法规则集合。带点的规则代表解析状态。 - Ira Baxter

好的回答。顺便提一句，现代编译器设计的链接已经失效了。 - rvighne

10

"正则表达式的引用：函数珍珠"采用了一种有趣的方法。虽然该实现是用Haskell编写的，但它至少已经被重新实现为Python。

该程序基于一种将正则表达式转化为有限自动机的旧技术进行开发，这使得它在最坏情况下的时间和空间边界以及实际性能方面都非常高效：尽管简单，但Haskell实现可以与最近发布的专业C++程序相竞争。

- dhaffey

6

在优美的代码（Brian Kernighan所著）中，有一章节名为“正则表达式匹配器”，虽然篇幅稍短但很有趣。其中讨论了一个简单的匹配器，可以匹配字面字符和.^$*符号。

- Richard Fearn

2

我同意编写正则表达式引擎可以提高理解能力，但你是否看过ANTLR？它可以自动生成任何语言的解析器。因此，你可以尝试使用语法示例中列出的一种语言语法，并运行生成的AST和解析器。它会生成非常复杂的代码，但你将对解析器的工作原理有很好的理解。

- A_Var

3

这有点违背初衷，不是吗？ - Chinmay Kanchi

实际上，你可以学习它生成的代码。ANTLR权威指南中每一行指南都有很好的解释。将其作为参考，并学习其在幕后使用的所有技术。这可能是一个很好的起点，至少可以学习到编写正则表达式引擎所需的技术。 - A_Var

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mark Byers · Accepted Answer

编写正则表达式引擎的实现确实是一项相当复杂的任务。

但如果您对如何实现它感兴趣，即使您无法理解足够的细节来实际实现它，我建议您至少查看这篇文章：

正则表达式匹配可以简单快速 （但在Java、Perl、PHP、Python、Ruby等语言中较慢...）

它解释了许多流行的编程语言如何以一种对于某些正则表达式非常慢的方式来实现正则表达式，并解释了一种稍微不同但更快的方法。该文章包括了建议的实现方式的一些细节，包括C语言的部分源代码。如果您刚开始学习正则表达式，这篇文章可能有点艰深，但我认为知道这两种方法之间的差异是值得的。