代码之家 › 专栏 › 技术社区 › Chinmay Kanchi

为正则表达式编写分析器

parsing regex python

Chinmay Kanchi · 技术社区 · 14 年前

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

所以,自学和理解正则表达式 适当地 我已经决定做我一直在做的事情,当我试图学习一些东西时;也就是说,尝试写一些有雄心壮志的东西,当我觉得我已经学到了足够的东西,我可能会放弃。

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

问题是,我从哪里开始?除了它以某种方式涉及有限状态自动机之外,我几乎不知道如何解析和解释正则表达式。对于如何解决这个令人望而生畏的问题,任何建议都会受到赞赏。

编辑: 我要澄清一下实施 python中的regex解析器,我不太担心用什么编程语言编写示例或文章。只要它不在脑浆里,我可能会理解的足够多,使它值得我的一段时间。

5 回复 | 直到 8 年前

Mark Byers 14 年前

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

但是,如果您对如何实现它感兴趣,即使您对实现它的细节还不够了解,我建议您至少看看本文:

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

它解释了有多少流行的编程语言以对某些正则表达式非常缓慢的方式实现正则表达式,并解释了一种稍有不同的更快的方法。这篇文章详细介绍了所提议的实现的工作原理,包括一些C语言的源代码。如果您刚开始学习正则表达式,可能会读得有点重,但我认为了解这两种方法之间的区别是值得的。

Steve314 8 年前

我已经给出了一个+1来标记byers,但据我所知,这篇文章并没有真正说明正则表达式匹配的工作原理,只是解释了为什么一种算法不好,而另一种算法好得多。可能链接中有什么?

我将重点介绍好的方法——创建有限自动机。如果你把自己局限于确定性自动机而没有最小化,这并不太困难。

我要(很快)描述的是 Modern Compiler Design .

假设您有以下正则表达式…

a (b c)* d

字母表示要匹配的文字字符。*通常是零次或多次重复匹配。基本思想是基于点规则导出状态。状态0,我们将把它作为一个还没有匹配的状态,所以圆点在前面…

0 : .a (b c)* d

唯一可能的匹配是“a”,所以我们得出的下一个状态是…

1 : a.(b c)* d

我们现在有两种可能性-匹配“b”(如果至少有一个重复出现“b c”)或匹配“d”,否则。注意-我们基本上在这里进行有向图搜索(深度优先或宽度优先或其他),但是我们在搜索时发现了有向图。假设采用广度优先策略,我们将需要对其中一个案例进行排队以备日后考虑,但从现在起我将忽略这个问题。总之,我们发现了两个新的州…

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

状态3是结束状态(可能有多个)。对于状态2,我们只能匹配“c”,但之后需要注意点的位置。我们得到“a.(b c)*d”-与状态1相同,因此我们不需要新的状态。

IIRC,现代编译器设计中的方法是当你点击一个操作符时翻译一个规则,以简化点的处理。状态1将转换为…

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

也就是说,您的下一个选项要么匹配第一个重复,要么跳过重复。接下来的状态相当于状态2和3。这种方法的一个优点是,您可以丢弃所有过去的匹配项(在“.”之前的所有内容),因为您只关心将来的匹配。这通常会给出一个较小的状态模型(但不一定是最小的)。

编辑如果您确实放弃已经匹配的详细信息,那么您的状态描述就是从现在开始可能出现的一组字符串的表示。

在抽象代数中,这是一种集合闭包。代数基本上是一个有一个(或多个)运算符的集合。我们的集合是状态描述,我们的操作符是转换(字符匹配)。闭集是将任何运算符应用于集中的任何成员时,总是生成集中的另一个成员。一个集合的闭合是闭合的最小较大集合。所以基本上,从明显的开始状态开始,我们正在构造相对于我们的转换操作符集闭合的最小状态集-最小可到达状态集。

这里的minimal指的是关闭过程——可能有一个较小的等价自动机,通常被称为minimal。

有了这个基本思想,就不难说“如果我有两个状态机代表两组字符串,如何得到第三个代表联合的状态机”(或者交集,或者集差…)。您的状态表示将来自每个输入自动机的当前状态(或一组当前状态),而不是点式规则,可能还有其他详细信息。

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

Hopcrofts算法是处理这一基本思想的有效方法。

关于最小化的一个特别有趣的事情是,每一个确定性有限自动机都有一个精确的极小形式。此外,Hopcrofts算法将产生该最小形式的相同表示,不管它从哪个大的案例开始。也就是说,这是一种“规范”表示,可用于派生散列或用于任意但一致的排序。这意味着可以使用最小自动机作为容器中的键。

上面的定义可能有点草率,所以在你自己使用之前,一定要先查一下你自己的术语,但是如果幸运的话,这会很快地介绍一下基本的概念。

顺便说一句-看看剩下的 Dick Grunes site -他有一本关于解析技术的免费PDF书。现代编译器设计的第一版在我看来相当不错,但正如你所看到的,第二版即将问世。

dhaffey 14 年前

This paper 采取一种有趣的方法。在Haskell中给出了实现,但是 reimplemented in Python 至少一次。

Richard Fearn 14 年前

有一个有趣的(如果稍微短一点)章节 Beautiful Code 由布莱恩·克尼根,恰当地称之为“正则表达式匹配器”。在本文中,他讨论了一个简单的匹配器,它可以匹配文字字符,并且 .^$* 符号。

A_Var 14 年前

我同意写一个regex引擎可以提高理解度,但是你看过antlr吗??它自动为任何类型的语言生成解析器。所以,也许你可以尝试一下你的手上列出的语言语法之一 Grammar examples 并运行它生成的AST和解析器。它生成了一个非常复杂的代码,但您将对解析器的工作方式有很好的了解。