.(句点) ^ $ *
匹配输入字符串的开头 匹配输入字符串的结尾 匹配前一个字符的零个或者多个出现 这是一个非常有用的匹配器,根据我在日常工作中使用正则表达式的经验,它可以轻松解
决95%的问题.在许多情况下,解决正确的问题就等于朝着创建漂亮的程序迈进了一大步.Rob 值得好好地表扬,因为他从大量可选功能集中选出了一组非常小但却重要的,并且是明确的以
2
及可扩展的功能. Rob的实现本身就是漂亮代码的一个极佳示例:紧凑,优雅,高效并且实用.这是我所见过 的最好的递归示例之一,在这段代码中还展示了C指针的强大功能.虽然当时我们最关心的是通 过使程序更易于使用(同时也更易于编写)来体现良好记法的重要性,但正则表达式代码同样 也是阐述算法,数据结构,测试,性能增强以及其他重要主题的最好方式.
1.2
实现
在《The Practice of Programming》一书中,正则表达式匹配器是一个模拟grep程序中的 一部分,但正则表达式的代码完全可以从编写环境中独立出来.这里我们并不关心主程序;像 许多Unix工具一样,这个程序将读取其标准输入或者一组文件,然后输出包含与正则表达式匹 配的文本行. 以下是匹配算法的代码: 扫p3+p4页代码
1.3
讨论
函数match(regexp,text)用来判断文本中是否出现正则表达式;如果找到了一个匹配的正
则表达式则返回1,否则返回0.如果有多个匹配的正则表达式,那么函数将找到文本中最左边 的并且最短的那个. match函数中的基本操作简单明了. 如果正则表达式中的第一个字符是^ 固定位置的匹配) ( , 那么匹配就一定要出现在字符串的开头.也就是说,如果正则表达式是^xyz,那么仅当xyz出现 在文本的开头而不是中间的某个位置时才会匹配成功.在代码中通过把正则表达式的剩余部分 与文本的起始位置而不是其他地方进行匹配来判断.如果第一个字符不是^,那么正则表达式就 可以在字符串中的任意位置上进行匹配.在代码中通过把模式依次与文本中的每个字符位置进 行匹配来判断.如果存在多个匹配,那么代码只会识别第一个(最左边的)匹配.也就是说, 如果则在表达式是xyz,那么将会匹配第一次出现的xyz,而且不考虑这个匹配出现在什么位置 上. 注意,对输入字符串的推进操作是在一个do-while循环中进行的,这种结构在C程序中使用 相对较少.在代码中使用do-while而不是while通常会带来疑问:为什么不在循环的起始处判断 循环条件,而是在循环末尾当执行完了某个操作之后才进行判断呢 不过,这里的判断是正确 的:由于*运算符允许零长度的匹配,因此我们首先需要判断是否存在一个空的匹配. 大部分的匹配工作是在matchhere(regexp,text)函数中完成的,这个函数将判断正则表达 式与文本的开头部分是否匹配. 函数matchhere把正则表达式的第一个字符与文本的第一个字符 进行匹配.如果匹配失败,那么在这个文本位置上就不存在匹配,因此matchhere将返回0.然
3
而,如果匹配成功了,函数将推进到正则表达式的下一个字符和文本的下一个字符继续进行匹 配.这是通过递归地调用matchhere函数来实现的. 由于存在着一些特殊的情况,以及需要设置终止递归的条件.因此实际的处理过程要更为 复杂些最简单的情况就是,当正则表达式推进到末尾时(regexp[0] == '\0'),所有前面的判断 都成功了,那么这个正则表达式就与文本匹配. 如果正则表达式是一个字符后面跟着一个*, 那么将会调用matchstar来判断闭包 (closure) 是否匹配.函数matchstar(c, regexp, text)将尝试匹配重复的文本字符c,从零重复开始并且 不断累加,直到匹配text的剩余字符,如果匹配失败,那么函数就认为不存在匹配.这个算法 将识别出一个"最短的匹配",这对简单的模式匹配来说是很好的,例如grep,这种情况下的 主要问题是尽可能快地找到一个匹配.而对于文本编辑器来说,"最长的匹配"则是更为直观, 且肯定是更好的,因为通常需要对匹配的文本进行替换.在目前许多的正则表达式库中同时提 供了这两种方法,在《The Practice of Programming》一书中给出了基于本例中matchstar函 数的一种简单变形,我们在后面将给出这种形式. 如果在正则表达式的末尾包含了一个$,那么仅当text此时位于末尾时才会匹配成功: if (regexp[0] == '$' && regexp[1] == '\0') return *text == '\0'; 如果没有包含$,并且如果当前不是处于text字符串的末尾(也就是说,*text!='\0')并 且如果text字符串的第一个字符匹配正则表达式的第一个字符,那么到现在为止都是没有问题 的;我们将接着判断正则表达式的下一个字符是否匹配text的下一个字符,这是通过递归调用 matchhere函数来实现的.这个递归调用不仅是本算法的核心,也是这段代码如此紧凑和整洁的 原因. 如果所有这些匹配尝试都失败了,那么正则表达式和text在这个位置上就不存在匹配,因 此函数matchhere将返回0. 在这段代码中大量地使用了C指针.在递归的每个阶段,如果存在某个字符匹配,那么在随 后的递归调用中将执行指针算法(例如,regexp+1 and text+1),这样在随后的函数调用中, 参数就是正则表达式的下一个字符和text的下一个字符. 递归的深度不会超过匹配模式的长度, 而通常情况下匹配模式的长度都是很短的,因此不会出现耗尽内存空间的危险.

上一页下一页