Chi*_*chi 68 python regex parsing
即使经过多年的编程,我也很惭愧地说我从未真正完全掌握正则表达式.一般来说,当一个问题需要一个正则表达式时,我通常(在一堆引用语法之后)得出一个合适的一个,但这是一种我发现自己经常使用的技术.
所以,为了自学并正确地理解正则表达式,我决定在尝试学习时做我一直做的事情; 也就是说,一旦我觉得我已经学到了足够多的东西,就试着写一些我可能会放弃的野心勃勃的东西.
为此,我想在Python中编写一个正则表达式解析器.在这种情况下,"学习足够"意味着我想实现一个可以完全理解Perl的扩展正则表达式语法的解析器.但是,它不一定是最有效的解析器,甚至不一定在现实世界中可用.它只需要正确匹配或不匹配字符串中的模式.
问题是,我从哪里开始？我几乎不知道如何解析和解释正则表达式,除了它以某种方式涉及有限状态自动机这一事实.如何处理这个相当艰巨的问题的任何建议将非常感激.
编辑:我应该澄清一下,当我要在Python中实现正则表达式解析器时,我并不过分讨论编写示例或文章的编程语言.只要它不在Brainfuck中,我可能会理解这让它值得我这么做.
Mar*_*ers 38
编写正则表达式引擎的实现确实是一项非常复杂的任务.
但如果您对如何操作感兴趣,即使您无法理解实际实现它的详细信息,我建议您至少看一下这篇文章:
正则表达式匹配可以简单快速 (但在Java,Perl,PHP,Python,Ruby等方面很慢)
它解释了有多少流行的编程语言以某种方式实现正则表达式,这种方式对于某些正则表达式来说可能非常慢,并且解释了一种稍微不同的方法,它更快.这篇文章包含了一些关于提议实现如何工作的细节,包括C中的一些源代码.如果你刚开始学习正则表达式,可能会有点沉重的阅读,但我认为值得了解两者之间的区别.方法.
Ste*_*314 21
我已经给Mark Byers +1了 - 但据我记得,这篇论文并没有真正说明正则表达式匹配如何解释为什么一个算法是坏的而另一个算法更好.也许链接中有什么东西？
我将专注于良好的方法 - 创建有限自动机.如果你将自己限制在没有最小化的确定性自动机上,这实际上并不太难.
我(很快)描述的是现代编译器设计中采用的方法.
想象一下,你有以下正则表达式......
a (b c)* d
这些字母代表要匹配的文字字符.*是通常的零次或多次重复匹配.基本思想是基于虚线规则导出状态.状态为零,我们将把它作为尚未匹配的状态,所以点在前面......
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.(bc)*d" - 这与状态1相同,所以我们不需要新状态.
IIRC,现代编译器设计中的方法是在击中操作符时转换规则,以简化点的处理.州1将转变为......
1 : a.b c (b c)* d
a.d
也就是说,您的下一个选项是匹配第一次重复或跳过重复.接下来的状态相当于状态2和3.这种方法的一个优点是你可以丢弃所有过去的匹配('.'之前的所有内容),因为你只关心未来的匹配.这通常会提供较小的状态模型(但不一定是最小的模型).
编辑如果丢弃已匹配的详细信息,则状态描述表示此时可能出现的字符串集.
就抽象代数而言,这是一种集合闭包.代数基本上是具有一个(或多个)运算符的集合.我们的集合是状态描述,我们的运算符是我们的转换(字符匹配).封闭集是将任何运算符应用于集合中的任何成员的集合始终生成集合中的另一个成员.集合的闭包是闭合的较小的较大集合.所以基本上,从明显的开始状态开始,我们构建了相对于我们的转换运算符集关闭的最小状态集 - 最小的可达状态集.
这里的最小值是指闭包过程 - 可能有一个较小的等效自动机,通常称为最小值.
考虑到这个基本思想,说"如果我有两个表示两组字符串的状态机,如何导出第三个表示联合"(或交集,或设置差异......)并不太难.而不是点状规则,您的状态表示将是来自每个输入自动机的当前状态(或当前状态集)以及可能的其他细节.
如果您的常规语法变得复杂,您可以最小化.这里的基本想法相对简单.您将所有状态分组为一个等价类或"阻止".然后,您反复测试是否需要针对特定转换类型拆分块(状态不是真正等效).如果特定块中的所有状态都可以接受相同字符的匹配,并且在这样做时,到达相同的下一个块,它们是等效的.
Hopcrofts算法是处理这一基本思想的有效方法.
关于最小化的一个特别有趣的事情是每个确定性有限自动机都有一个最小的形式.此外,Hopcrofts算法将产生该最小形式的相同表示,无论它从哪个更大的情况开始表示.也就是说,这是一个"规范"表示,可用于导出散列或任意但一致的排序.这意味着您可以使用最小的自动机作为容器的密钥.
以上可能有点草率的WRT定义,因此请确保在自己使用它们之前自己查找任何术语,但运气方面,这可以快速介绍基本概念.
BTW - 浏览一下Dick Grunes网站的其他部分- 他有一本关于解析技术的免费PDF书籍.现代编译器设计的第一版是相当不错的IMO,但正如您将看到的那样,第二版即将推出.
Brian Kernighan 在Beautiful Code中有一个有趣的(如果稍短)章节,恰当地称为"A Regular Expression Matcher".在其中,他讨论了一个简单的匹配器,可以匹配文字字符和.^$*符号.