Rob Pike 编写的正则表达式程序

前端之家收集整理的这篇文章主要介绍了Rob Pike 编写的正则表达式程序前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

介绍

好的代码可以是简单的----清晰又易懂。好的代码可以是简洁的----解决问题刚好够用,没有多余的部分,但不隐晦以致难看。好的代码也可以是一般的,一石n鸟搞定一大类问题。好的代码甚至可以用优雅、显示好品味、精致等词语来形容。

这一章我要解说一段好的代码,这段代码是用来做正则表达式匹配的,符合上述所有特质。

正则表达式是用来描述文本模式一个符号,简单说就是用来做模式匹配的专有语言。虽然有很多变种,但都基于同一个理念,即在模式中大部分字符表示字符本身,但一些“元字符”有特殊含义,比如“*”表示某种重复,[...]表示任何一个括号里的字符。

实践中,像文本编辑器这样的程序中的大多数的查询都是基于文本的,所以正则表达式通常都是文字串,例如print,就会匹配上任何位置的sprint或printer中的print。对应Unix和Windows中的文件名,通配符(*)可以匹配任何数量的字符,因此*.c可以匹配所有.c结尾的文件名。有很多的正则表达式的变体,甚至有时它们会被认为是相同的。Jeffrey Friedl的《精通正则表达式(O'Reilly,2006) 》在这方面讲的很详细。

正则表达式是Stephen Kleene在1950年代中期作为有限自动机的表示方式而发明的,实际上,正则表达式表现的与其所表示的有限自动机是等价的。1960年代中期,在Ken Thompson的QED文本编辑器的版本里,正则表达式第一次作为程序的设置出现。在1967年,,Ken申请了一项基于正则表达式的快速文本匹配机制的专利;并于1971年被授予专利,这是最早的软件专利之一[US Patent 3,568,156,Text Matching Algorithm,March 2,1971]。

正则表达式先是从QED移植到了Unix的编辑器ed中,然后又被移植到UNIX非常(译注:quint印刷错误?疑是quite)基本的工具grep中,这是Thompson对ed进行了彻底改造时创建的一个工具。通过早期的Unix社区,正则表达式得以被人熟知。

Thompson最初写的匹配器是很快的,因为它包含了两种独立的思想。其一是在匹配过程中动态地生成机器指令,这样就可以以机器指令执行的速度 而不是解释执行的速度来运行。另一种思想是在每个阶段中都尽可能地执行匹配操作,这样无需回朔就可以查找可能的匹配。在 Ken后来写的文本编辑器,例如ed中,匹配代码使用了更简单的算法,在必要的时候才会进行回朔。理论上,这样的运行速度要慢一些,但在实际情况中,这种模式很少需要进行回朔,因此,ed和grep中的算法和代码足以应付大多数的情况。

之后的正则表达式匹配器,例如egrep和fgrep等,都增加了更丰富的正则表达式类型,并且关注的是不管是什么查询模式都能快速进行匹配。功能更为强大的正则表达式开始流行起来,它们不仅被包含在基于C语言开发的库中,也被作为脚本语言如Awk和Perl的语法的一部分。

编程实践

在1998年,Rob Pike和我还在编写《程序设计实践(The Practice of Programming)》("TPOP")一书。书中的最后一章是“标记法”,在这一章中收录了许多例子,这些示例可以带来良好的程序和更好的编程方式。其中包括使用简单的数据规范(例如printf的格式)以及从表中生成代码

由于我们有着深厚的Unix技术背景,以及在使用基于正则表达式记法的工具上有着多年的经验,我们很自然地希望包含一些对正则表达式的讨论,似乎也必须包含一个实现。同时由于我们强调了工具,最好应该把重点放在grep中的正则表达式类型上,而不是类似shell的通配符那样的,随后我们还可以讨论grep本身的设计。

问题是任何存在的正则表达式包都太大了。grep的代码超过500行(差不多得占10页纸).开源正则表达式包几乎得占整本书,因为它们被设计的通用、灵活和高效;没有一个适合教学。
我告诉Rob我们需要一个小的正则表达式包,这个包可以阐明基本的思想,同时可以识别相当一类模式。理想情况下所以的代码仅占一页纸。

Rob回去了他的办公室,不超过一到两个小时之后,他带着30行C代码回来了,这30行代码随后出现在了TPOP的第9章。这些代码实现了处理下述句法结构的正则表达式匹配器:

 c 匹配任意原义字符c
 . 匹配任意单个字符
 ^ 匹配输入字符串的开始端
 $ 匹配输入字符串的结束端
 * 匹配零个或多个前一字符

这是非常有用的一类模式;按照我日常使用正则表达式的经验,这占了95%的情况。在很多情况下,解决正确的问题是通往优美的程序的重要一步。Rob从很多选项中选出了这样一个小而美的子集是值得高度赞扬的。

Rob的实现是优美代码的一个极好的例子:紧凑、优雅、高效、有用。这是我看过的最好的递归的例子,它也展示了C指针的威力。虽然当时我们最关心的是说明记法(notation)的重要性,好的记法可以使程序更容易使用,也更容易编写,正则表达式的代码也是阐释算法、数据结构、测试、性能改善和其它重要主题的极好的例子。

实现

在书中,正则表达式匹配器是模仿grep的一段程序,但是正则表达式代码是可以完全分离出来的。我们这里不关心主程序——它仅仅从标准输入或者文件中读数据,输入匹配正则表达式的行,就像grep和很多其它Unix工具做的那样。
这是匹配代码

01 /* match: search for regexp anywhere in text */
02 intmatch(char*regexp,*text)
03 {
04 if(regexp[0] =='^')
05 returnmatchhere(regexp+1,text);
06 do{/* must look even if string is empty */
07 (matchhere(regexp,text))
08 1;
09 }while(*text++ !='\0');
10 0;
11 }
12
13 /* matchhere: search for regexp at beginning of text */
14 matchhere(15 16 17 1;
18 (regexp[1] =='*'19 matchstar(regexp[0],regexp+2,monospace!important; font-size:10pt!important; min-height:inherit!important; display:block!important">20 '$'&& regexp[1] ==21 *text ==;
22 (*text!=&& (regexp[0]=='.'|| regexp[0]==*text))
23 24 25 26 27 /* matchstar: search for c*regexp at beginning of text */
28 matchstar(c,monospace!important; font-size:10pt!important; min-height:inherit!important; display:block!important">29 30 /* a * matches zero or more instances */
31 32 33 (*text !=&& (*text++ == c || c ==));
34 35 }

方法match(regexp,text)检查text中是否有匹配正则表达式的情况;如果匹配返回1,否则返回0。如果有不止一个匹配,返回最左边最短的那一个。

match的基本操作是很直观的。如果正则表达式的第一个字符是^(一个定位匹配),那么任意可能的匹配发生在字符串的开始位置。也就是,如果正则表达式是^xyz,那么只有xyz出现在字符串开头的时候它才匹配xyz,在中间的某位置就不会匹配。这种情况通过用剩下的正则表达式从头开始匹配字符串来检查,从其它位置开始的字符串子串就不用检查。

否则,如果正则表达式的第一个字符不是^,那么正则表达式可能匹配字符串的任意位置。这通过依此用正则表达式匹配字符串每个位置来测试。如果有多个匹配,只有第一个(最左边的)匹配会被识别到。也就是,如果正则表达式是xyz,那么它将会匹配第一个出现的xyz子串,而不关心出现的位置。

注意程序中是通过do-while循环来推进输入字符串的,这在C语言程序中是一个相对不寻常的构造。用do-while而不是用while,这就引出一个问题:为什么循环终止条件不趁早在循环结构开始的时候检查,而是在循环结构结束的时候?但是这样检查在这里是正确的:因为*符号允许零长度的匹配,所以我们首先不得不检查是不是空匹配。

程序大部分工作是在函数matchhere(regexp,text)中做的,这个函数检查从此处开始的字符串是否匹配正则表达式。方法matchhere尝试匹配正则表达式第一个字符与字符串第一个字符。如果匹配失败,那么从字符串这个位置开始没有匹配,所以matchhere返回0。如果匹配成功,那么就继续检查正则表达式下一个字符与字符串下一个字符是否匹配。通过递归调用matchhere完成上述工作。

由于一些特殊的情况,处理起来就有点儿复杂了。最简单的情况是如果正则表达式读完了(regexp[0] == '\0'),那么之前所有的检查都是成功的,因此正则表达式匹配字符串。

如果正则表达式是跟着*号的字符,那么调用matchstar检查闭包是否匹配。函数matchstar(c,regexp,text)试图匹配重复出现的字符c,从零次重复开始增加,在剩下的字符串中寻找匹配,或者匹配不成功,那就表示没有匹配。这样识别的是一个“最短匹配”,对grep这种简单模式匹配,“最短匹配”还是是蛮好的,这样可以尽快找到一个匹配。“最长匹配”相对更直观,对于文本编辑器的替换匹配功能更适合。大部分现代正则表达式库同时提供两种模式,TPOP提供了matchstar的最长匹配版本,稍后将会展示。

如果正则表达式最后一个字符是$,字符串也到了末尾,那么就匹配了。

否则,如果不是在字符串的末尾(也就是,*text!='\0'),字符串第一个字符匹配了正则表达式第一个字符,那么就递归调用matchhere检查正则表达式下一个字符是否匹配字符串下一个字符。递归调用是算法的核心也是算法如此紧凑简洁的原因。

如果所有的匹配尝试都失败了,那么正则表达式和字符串没有匹配,所有matchhere返回0。

代码使用了C指针。在递归的每个阶段,如果某部分匹配了,接下来的递归调用使用了指针运算(比如,regexp+1和text+1)使得接下来的函数调用传入正则表达式和字符串的下一个字符。递归的深度不超过模式的深度,在通常的使用中都很短,所有没有空间不足的风险。

其他方案

这是一段优雅的写的很好的代码,但是它并不完美。有人可能会按照其他的方式来写。在这里我可能重新组织匹配的顺序,将$匹配的探测置于*之前,尽管这两种处理方式本质上并没有区别,但是这样做看起来更自然些。在处理难题之前先做一些容易的事是一个很好的习惯。

一般情况下,匹配测试的顺序是非常重要的。比如下面的frommatchstar测试:

1 ));

无论什么时候,我们必须向后取一个字符,所以增量intext++必须每次都被执行。

这段代码对于终止条件敏感。一般情况下,匹配成功与否是由正则表达式和文本是否同时结束决定,如果正则表达式和文本一起结束,就表明匹配成功,反之如则匹配失败。这和下面的这种写法很像:

)
2 ;
但这种终止条件也可能出现在其他地方。

matchstar的这个版本实现了左边最长匹配,它开头定义了一个最长的序列,对输入字符进行检索。之后它使用matchhere去尝试将匹配扩展到模式的其余部分,以及文本的剩余部分。每次失败将使c的数值减少一,同时它会再次尝试,其中包含了零匹配的情形。

/* matchstar: leftmost longest search for c*regexp */
*t;
for(t = text; *t !=&& (*t == c || c ==); t++)
/* * matches zero or more */
(t-- > text);
}

考虑到通常的表达式(.*),它对括号内的任意字符进行匹配。我们给出目标文本

); t++)

最长的匹配是始自于对整个带括号表达式的定义,而最短的匹配则终止于第一个右括号。(当然从第二个左括号开始的最长匹配,将扩展到文本的最末端。)

基于它创建

TPOP的目的在于传授良好的编程方法。当此书撰写时,Rob和我仍然在贝尔实验室,所以我们没有关于此书怎样能最佳的应用于课堂的第一手经验。发现其中的一些材料在课堂教学中发挥了积极作用实在是令人高兴。我自2000年开始使用这些代码,作为教授关于编程的重要观点的辅助工具。

首先,它显示出在一个新的环境中,递归是如何有用并能带来干净的代码;它不是Quicksort(或阶乘!)的另一个版本,也不是某种对树的遍历。

它同时也是性能实验的良好例子。它的性能与系统版本的grep差异不是很大,这显示出递归技术并不是非常有价值,尝试优化代码也是并不值得的。

另一方面, 它也体现了一个好算法的重要性。 如果一个正则表达式包含了多个.*s, 直观的实现需要多次回溯,而且在某些情况执行的确实非常慢。 (标准的Unix grep具有同样的特点。) 比如,如下命令

grep'a.*a.*a.*a.a'

在一台普通设备上处理一个4 MB的文本文件花了大约20秒。 一种基于转换不确定有限自动机为确定自动机的实现方法,比如egrep, 会在困难的情况下表现得更好 -- 同样的表达式和输入处理起来只用了不到十分之一秒,通常运行时间和表达式是相会独立的。

对正则表达式类的扩展形成各种任务的基础。例如:

(1)增加其他元字符,例如+表示前面字符的一个或多个出现,或者?表示前面字符零个或一个字符匹配。还可以增加一些引用元字符的方法,例如\$表示出现了$字母。

(2)将正则表达式处理过程分成编译阶段和执行阶段。编译阶段把正则表达式转换为内部形式,使匹配代码更为简单或者使这样的后续匹配运行得更快。对于最初设计里的简单正则表达式类来说,这种拆分并不是必须的,但在类似grep的应用里,这种拆分是有意义的,因为这种类型的正则表达式要更为复杂,而且同样的正则表达式将可用在大量的输入行上。

(3)增加像[abc]和[0-9]这样的字符类,在传统的grep表示里,它分别匹配a或b或c和一个数字。这可通过几种方式实现,其中最自然的方式似乎是使用下面的机构替代原始代码中的char*:
typedef struct RE {
            int     type;   /* CHAR,STAR,etc. */
            char    ch;     /* the character itself */
            char    *ccl;   /* for [...] instead */
            int     nccl;   /* true if class is negated [^...] */
    } RE;
并且修改相应的代码来处理这样的结构数组而不是处理字符数组。在这种情况下,严格的来说,不需要把编译阶段从执行阶段中拆分出来,但是这证明拆分是非常简单的。遵循预编译成这样的结构建议的学生一定比哪些试图在运行过程中解释一些复杂模式的数据结构的学生做得更好。

为字符类编写清晰且无歧义的规范是很困难的,而且完美地实现它们更难,这需要大量的枯燥且无意义的编码。随着时间的推移,我简化了这个任务,之后最常请求的就是像Perl那样的速记,例如\d表示数字,\D表示非数字,而不是最初的那种方括号内限定范围。

(4)使用不透明的类型来隐藏RE结构和所有实现细节。在C语言里这是展示面向对象编程的好方法,不过除此之外它不支持其他东西。实际中,你可以创建一个正则表达式类,并且成员函数的名字像RE_new( )和RE_match( )这样,而不是像面向对象语言的语法那样。

(5)修改正则表达式类,使得它更像各种shell中的通配符:这种匹配隐含地固定匹配的起始为两端,*匹配任意数量的字符,而?匹配任何单个字符。你可以修改这个算法或者把输入引入到已有的算法里。

6.将这段代码转换成Java。最初的代码很好地使用了C指针,并且把这个算法在不同的语言中实现出来是一个很好的实践过程。在Java版本的代码中将使 用String.charAt(使用索引而不是指针)或者String.subString(更接近于指针)。这两种方法都没有C代码整洁,并且都不紧凑。 虽然在这个练习中性能并不是主要的问题,但有趣的是可以发现了Java版本比C版本在运行速度上要慢6到7倍。

7.编写一个包装类把这种类型的正则表达式转换成Java的Pattern类和Matcher类,这些类将以一种与众不同的方式来拆分编译阶段和匹配阶段。 这是适配器(Adapter)模式或者外观(Façade)模式的很好示例,这两种模式用来在现有的类或者函数集合外部设置不同的接口。

我曾经大量地使用了这段代码来研究测试技术。正则表达式非常的丰富,而测试也不是无足轻重的,但正则表达式又是很短小的,程序员可以很快地写出一组测试代码来执行。对于前面所列出的各种扩展,我要求学生用一种紧凑的语言写出大量的测试代码(这是“记法”的另一种示例),并且在他们自己的代码中使用这些测试用例;自然我在其他学生的代码中也使用了他们的测试用例。

结尾

当Rob Pike把刚写的代码给我时,我惊叹于它是如此的简洁和优雅--比我能想到的还要小巧且功能强大。事后才发现 为什么代码如此短小的原因。

首先,选取最有用的特性并给出最具见解的实现,没有任何冗余。比如,定位模式“^”和“$”的实现仅用了3-4行代码,却展现了在统一处理一般情况前如何利索的处理特殊情形。闭合运算*(closure operation)是正则表达式中一个重要的概念,它提供了处理不定长度模式的唯一的方式,因此代码中必须包含该功能。但是同样提供诸如"+"和"?"的实现对正则表达式原理的理解一点用处也没有,因此这些功能留作练习供读者实现。

其次,使用递归是一个优势。作为基本的编程技术,递归几乎总会产生更短小,更简洁和更优雅的代码,这是同样清晰的循环实现无法比拟的,在Bob的代码中同样如此。匹配的思想是从正则表达式和文本的开头剥离匹配的字符,然后对后面的文本重复该过程。该过程类似传统的求阶乘或字符串长度例程中的递归结构,但是以一种更有趣并且更有用的方式调整。

Rob告诉我递归不是那么清晰的设计决策,缘于其如何逼近问题的方式:考虑一个匹配模式和一段文本,写出匹配函数,该函数转而又需要一个“匹配这里”的函数,等等。

“我对代码本身以这样的方式写出来记忆犹新。仅有的挑战是找到正确的结束(边缘)条件(edge condition)跳出(结束)递归。换句话说,递归不仅仅是一种实现方法,当你写代码时,它还是你思维过程的反映。这样的思维过程对代码的简明性负有部分责任。可能,最重要的是,当我着手开始时并没有一个设计方案,我只是开始编码,然后看到开发的结果,突然,我就完成了。”

最后,这段代码使用基础的编程语言获得好的效果。当然,指针可能被误用,但在这里,它们用来创建紧凑的表达式。这些表达式自然的展示了单个字符的提取并推移到下一个字符。同样的效果可通过数组索引或子串的方法获得,但在该段代码中,尤其是在与C的自增惯用法和明确的真值转换联合使用时,指针要技高一筹。

我没听说过存在另一段代码能以如此少行数完成这么多的功能,与此同时,提供如此丰富的见解和进一步想法。

原文链接:https://www.f2er.com/regex/362682.html

猜你在找的正则表达式相关文章