正则学习杂感：磨刀不误砍柴功
Sep 23rd
反复读紫龙书第三章，以及网文Write Your Own Regular Expression Parser（链接在这篇文章中找），连同该网文附带的源码，终于破关。一点感悟，写在这里。
使用正则表达式搜索字串，比逐位进行strcmp这样的方法要复杂N倍，如果说strcmp是只支持＋－×÷的计算器的话，那么正则表达式就是一台现代化的电脑。正则式不用逐位比较，它有自己的一整套方法。
要想在源字串找某个正则式模式，需要先详尽地分析该正则式，其过程是将该正则式解剖成不可再分的字符（称为状态），然后从任意一个状态开始，通过不同的路径（字符输入）可以到达不同的状态。第一个字符之前，叫做初始状态；最后一个字符之后，叫做接收状态。这种是NFA（不确定的有穷自动机），因为一个状态上有可能存在不止一条的转出状态。
一旦做好了这样的状态集合，就可以进行匹配了。每输入一个字符，从开始状态上就会产生不同的状态集合；依次输入完毕，如果所得到状态集合中包含了一个接受状态，就证明所输入的串是匹配的。但是NFA的效率低下。因为从每个状态上转出的路径不止一条，因此就有回溯。为提升效率，可以将NFA转成等效的DFA，即确定的有穷自动机。
DFA的原理是，对于每个状态集合D和给定的输入字符a，最多只有一条通路可走。与NFA的区别是，对于每个单个的状态f和给定的字符a，就有N条路可走。但是DFA也不是生来就万能的，比方说，它有死状态需要消除，同构的状态需要合并，还存在对于复杂正则表达式的DFA的转换效率低、实现复杂度高的情况，等等。虽如此，NFA转换为DFA还是值得的，有道是磨刀不误砍柴功。
对于正则表达式做好了DFA，就可以进行匹配了。每输入一个字符，自动机就转至下一个状态集合，直至输入结尾。如果所达到的状态集合中包含了接受状态，那么匹配就是成功的。
以上就是NFA、DFA的原理。当然，细节是简化过的。否则的话，上面任何一个步骤都有N多的细节，需要使用各种奇怪的数据结构来存储，复杂的成员函数来操作。
说到这里，想起python, pcre，以及其它一些正则表达式库，都有compile一个选项。先编译再执行，一次编译多次执行，文档一再这样强调。这比一上来就execute效率要高，如果重复执行多次的话。以前总是图方便直接就execute了，现在想想，实现一个正则表达式多不容易呀，对于多次重复的匹配，还是老老实实地compile一次才有礼貌。正则引擎在幕后默默无闻地做了那么多工作，不应该老是麻烦它老人家，呵呵。
正则学习杂感，附几枚链接
Sep 18th
最近在学习编译原理，尤其是正则表达式的实现这一节。从网上搜索到有用的链接，张贴在这里。一个感受是，数学知识是非常有用的，尤其是创造性的编程。如果数学知识足够，完全可以写出更加高效的算法；如果数学知识不够，最多只是重复别人已经写好的算法而已。因此在初步学习时，可以不必另造车轮，老老实实地学习已经很成熟的算法，才是正途。
至于正则表达式的实现，其实也只是先有数学思想，然后将其使用编程语言实现而已。准备步骤是先归纳语法树，自顶至下，逐级细分；而实现步骤是从现有的正则表达式自叶至顶，先将正则式转换为NFA图，再优化，转为DFA，这时才可与目标字串进行比较。
在看紫龙书时，感觉到其中从思路到算法，从伪代码到实际代码之间，其转换需要太多的细节来补充。而这些知识，不单来自于对具体语言语法的掌握，还需要合适的数据支持，才能化繁为简，事半功倍。顺便读了一些C++ STL的内容，觉得这些标准库真是相当有用，在构建正则表达式时这些库正好可以物尽其用。STL的作者善莫大焉。
从理论上说，即使没有STL支持的纯C语言，对于实现正则表达式也是没有任何问题的，只不过是自己捎带着再写一遍自己需要的数据结构而已。别说C，就是宏汇编，也可以实现的。如果感兴趣，可以自行到Aogo的www.aogosoft.com上自行搜索他的实现。归结到一句话：思路有了，语言的实现只是翻译。我等初学者是无力想出更高级的实现的，只是在这种翻译过程中，作为一种深化理解和课后练习罢。言归正传，下面是我要推荐的几则链接。
1. 《正则表达式识别》 http://blog.csdn.net/slavik/archive/2006…40386.aspx
有图有真相。本文的配图还是挺丰富的。思路也清晰。极具指导意义。
可惜没有源码。该博客的其它相关文章，也值得阅读。
2. 正则表达式 TO NFA表格
http://hi.baidu.com/rabbit5455/blog/item…1aac8.html
这篇文章主要是提供了源码，源码中附注释。也不错。
3. 《Write Your Own Regular Expression Parser》 http://www.codeguru.com/cpp/cpp/cpp_mfc/….php/c4093
本文是英文文章，有图示，有源码，很不错。我正在边阅读，边学习，边翻译，一边自行实现。建议直接阅读英文资料，不必等我的翻译。本文的代码只提供了*,|，以及连接操作的实现。不过也对其它操作的实现给出了指导。我已经在源代码基础上添加了问号和加号的支持。
《精通正则表达式》视频教程提供下载
Aug 17th
偶然从网上找到该教程，下载后觉得不错，可以作为《精通正则表达式》的番外篇，共同学习。
关于此视频的讲师：
此视频的讲师为余晟先生。余先生是抓虾网高级顾问。毕业于东北师范大学，主修计算机，辅修中文。现居北京。曾任高级程序员、技术经理；从事过大量文本解析和数据抽取的工作。对程序语言、算法、数据库和敏捷开发都有兴趣，译有《精通正则表达式》(第3版)一书。
关于此视频
此视频分为5讲，每讲30分钟左右，内容深入浅出，适合以下受众：
- 对正则式感兴趣的人；
- 对正则式不感兴趣的人；
- 正则式初学者，想入门；
- 正则式有所成者，想提高。
当然，如果能静下心来，通读《精通正则表达式》原书，并亲自动手尝试，效果更为显著。 Read the rest of this entry »
windows下的正则式工具介绍之二：powergrep
May 5th
上文介绍了RegexBuddy，本文介绍另一款windows下的正则式软件：PowerGREP，号称“The Most Powerful GREP Tool for Windows”，windows下最强大的GREP工具。看清楚了，是最强大，而非之一。与RegexBuddy一样，也是商业软件，其售价为US$149.00，合人民币1000有奇。如果说RegexBuddy是撰写正则式的贴心助手，那么PowerGREP则是应用正则式在文本文件中搜索替换的强大工具。现在我们看看，它究竟有什么功能敢号称最强。
基本界面
点击可以看大图。另外，还有一组图片来自powergrep官网，附上了官网的部分介绍，以及个人评论。
- 内容搜索图片，点这里；
在本抓图中，我搜索了c:\My Documents\My Web Sites文件夹及其子目录下所有的html文件。我使用了一条正则表达式把搜索范围限定在HTML tag之内，使用另一条正则式在这些标记中搜索所有的email地址。 - 搜索和替换，点这里和这里；
一个好用的功能是可以预览结果而不是立即替换。匹配结果以黄色标出。双击匹配就能打开对应的文档并检验其内容。
点击执行后，颜色改变，表示已经实施替换。 - 收集信息和统计数据，点这里；
本例是“检测Apache网络日志－－google search terms”的例子。本例使用的正则式在PowerGREP帮助文档中有详细讲解。 - 灵活的“撤消”历史记录，让你不再抓狂，点这里；
在执行替换的同时，PowerGREP已经备份了原文件。只要你没有手动删除这些备份的文件，你可以随便撤消你做过的任何操作。世界上真有后悔药的呀。 - 搜索PDF文档，点这里；
PDF也能使用正则式进行搜索？当然了，你没有看错。只是，要确保PDF文档中你要搜索的内容是文字而非图像。也就是说，扫描版的PDF不享受此功能的哟。 - 在MS word 文档中搜索，点这里；
这个功能也十分有用。我记得还有个东东叫ViEmu for Word & Outlook，可以在word和outlook中模拟vim，当然可以使用正则式搜索替换了。不过，ViEmu一来也是收费软件（在2008年5月31日之前是79美刀，之后是99美刀），我还没有找到免费版本；二来其正则式是vim风格的，只习惯Perl风格的同学可能不太习惯。在google documents里也支持正则式搜索了，具体语法、风格尚未广泛测试。 - 在MS Excel中搜索，点这里；
同样也是批量搜索、替换。不单单是对一个文档、一个sheet。 - 以16进制模式，在2进制文档中搜索，点这里；
跟二进制编辑器界面类似，多了正则式批量搜索替换功能。 - 在zip压缩文档中搜索，点这里；
把zip文件当作普通文件夹来搜索。很强大吧？ - 正则表达式序列，点这里；
大多数正则式工具一次只支持一条正则式的操作。而PowerGREP可以一次执行多条正则式！使用checkbox来进行多项选择。 - 定制颜色显示，点这里；
该功能比较一般。除非软件中的颜色设置特傻，一般我是不会改变默认颜色搭配的。
功能演示
PowerGREP官网还提供了一组flash做的demo，见下。
- 使用正则式匹配email地址(2′47”)。点这里；
- 升级版权信息(3′38)。点这里；
- 与RegexBuddy的无缝链接(1′57”)，点这里；两个软件是亲兄弟，当然哥俩好啦！
- 文件选择(3′08”)，点这里；PowerGREP提供了贴心的特性，来帮助你筛选需要的文档。
- 其它特性(8′37”)，点这里；总而言之，PowerGREP是功能强大。自己发掘吧！
软件下载
目前其最新版为3.4.2，更新于2008年1月18日。其官网为www.powergrep.com，可以去下载其最新版试用。该软件为商业软件。
- 如果你偶然路过，尝新而已，那只需下载试用版即可；
- 如果你觉得好用、准备常用、手有余钱、非正版不用，不妨花美金购买；要花人民币1000多块哟^_^
如果你喜欢它，同时你认为优秀的网络资源是应该和朋友免费分享的，从而想获得该软件的全功能免费版，好吧，我也成全你，请在本文后留言（附邮箱），我会把这个小东西的链接发给你(最新版为3.4.2，我手头的全功能版为3.3.3，也足够用了)。更新：
请移步至此下载PowerGREP 3.5.0版。
———————————————————————————————————
Comments