C注释正则式及其效率思考
2012-5-13 广州•天河 雨
下面给出C注释正则式与自动机相互转换的例子。两个例子都不考虑注释标识符在字符串常量中的情形（如：const char* start = "";）。
自动机转换成正则式：
识别C注释的自动机很容易画出来(^
正则式转换成自动机：
参考了一下Mastering Regular Expressions, 3rd Edition By Jeffrey E. F. Friedl,其中 6.7节有提到C注释正则式匹配问题。没有仔细看他的推导过程，反正蛮啰嗦。下面是Jeffrey 给的正则式：
/\*[^*]*\*+([^
为验证其正确性，必须正则式转换成自动机。
图2
显然，这两个自动机是等价的。这也验证了这两个正则式的正确性。
性能比较：
竟然两个正则式功能一样，那么究竟谁优谁劣呢？正则式优劣如何判断，这个我觉得是个头痛的问题，没有专门研究，直接的判断方法就是正则式是否存在二义性。比如，下面两个正则式可以匹配以a结尾的字符串：
| 1 | .*a |
| 2 | [^a]*a(a|[^a]*a)* |
显然，正则式1中存在二义性，'.'已经包括了字符'a'，碰到输入'a'时，到底用哪项匹配呢？如果匹配一直顺利便罢，但如果输入串不属于正则式所描述语言，那回溯数据将随输入长度呈指数增长！这就是偷懒的结果！下面是用RegexBuddy对俩正则式的debug结果：
图3
图4
而TMS_LI和Jeffrey 的正则式并不存在二义性问题。但用RegexBuddy测试表明，Jeffrey 的正则式比较高效。经过一番折腾，发现Jeffrey 的自动机里用了ε，而ε虽然表示空，但带有方向，所以可以体现匹配先后次序。图2中S35与S4属同一个ε_CLOSURE，在没有合并成S354时，会优先匹配'*'，在不匹配的情况下，使用ε。合并后，存在'*'与[^/*]两种选择并没有体现先后关系。这就是多选的缺陷。
这里顺带总结一个消除多选的算法:
图5
也就是说：（a｜b）* ←→a*(ba*)*。这就不难理解TMS_LI与Jeffrey的正则式了。