python - 为正则表达式编写解析器

Question

即使经过多年的编程，我还是很惭愧地说我从未真正完全掌握正则表达式。一般来说，当一个问题需要一个正则表达式时，我通常可以(在一堆引用语法之后)想出一个合适的，但这是我发现自己越来越经常使用的一种技术。

所以，为了自学和理解正则表达式正确，我决定做我在尝试学习某些东西时总是做的事情；即，尝试写一些雄心勃勃的东西，一旦我觉得我学到了足够的东西，我可能会放弃。

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

问题是，我从哪里开始？除了它以某种方式涉及有限状态自动机这一事实之外，我对如何解析和解释正则表达式几乎一无所知。任何关于如何解决这个相当令人生畏的问题的建议都将不胜感激。

编辑:我应该澄清一下，虽然我将在 Python 中实现正则表达式解析器，但我并不会过分关注示例或文章的编程语言只要不是在 Brainfuck 中，我可能会理解得足够多，值得我花时间。

Answer 1

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

但是如果你对如何做感兴趣，即使你不能理解足够的细节来实际实现它，我建议你至少看看这篇文章:

Regular Expression Matching Can Be Simple And Fast(but is slow in Java, Perl, PHP, Python, Ruby, ...)

它解释了有多少流行的编程语言以对某些正则表达式来说可能非常慢的方式实现正则表达式，并解释了一种稍微不同但速度更快的方法。这篇文章包含了一些关于所提议的实现如何工作的细节，包括一些 C 源代码。如果你刚开始学习正则表达式，可能会读起来有点繁重，但我认为了解两者之间的区别是非常值得的接近。