C注释正则式及其效率思考

下面给出C注释正则式与自动机相互转换的例子。两个例子都不考虑注释标识符在字符串常量中的情形(如:const char* start = "/*", *end = "*/";)。

自动机转换成正则式:

识别C注释的自动机很容易画出来(^/*表示除'/'及'*'以外的所有字符):

C注释正则式及其效率思考

图1

TMS_LI的正则为:/\*[^*]*\*(\*|[^/*][^*]*\*)*/

正则式转换成自动机:

参考了一下Mastering Regular Expressions, 3rd Edition By Jeffrey E. F. Friedl,其中 6.7节有提到C注释正则式匹配问题。没有仔细看他的推导过程,反正蛮啰嗦。 下面是Jeffrey 给的正则式:

/\*[^*]*\*+([^/*][^*]*\*+)*/

为验证其正确性,必须正则式转换成自动机。

C注释正则式及其效率思考

图2

显然,这两个自动机是等价的。这也验证了这两个正则式的正确性。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:http://www.heiqu.com/psgwd.html