[转]正则表达式匹配算法

 

 《The Practice of Programming》 一书中有很多优美的示例代码。

下面的这个关于正则表达式的匹配算法的C语言版是 作者之一 Rob Pike的作品。

 

/* match: 在 text 中查找 regexp */

int match(char *regexp, char *text)
{
	if(regexp[0] == '^'){
		return matchhere(regexp+1, text);
	}
	
	do{ /* 即使字符串为空时也必须检查 */
		if(matchhere(regexp, text)){
			return 1;
		}	
	} while(*text++ != '\0');
	return 0;
}

/* matchhere： 在 text 的开头查找 regexp */
int matchhere(char *regexp, char *text)
{
	if(regexp[0] == '\0'){
		return 1;
	}
	if(regexp[1] == '*'){
		return matchstar(regexp[0], regexp+2, text);
	}
	if(regexp[0] == '$' && regexp[1] == '\0')){
		return *text == '\0';
	}
	if(*text != '\0' && (regexp[0] == '.' || regexp[0] == *text){){
		return matchhere(regexp+1, text+1);
	}
	return 0;
}

/* matchstar: 在text 的开头查找 C*regexp */
int matchstar(int c, char *regexp, char *text)
{
	do{ /* 通配符 * 匹配零个或多个实例 */
		if(matchhere(regexp, text)){
			return 1;
		}
	} while(*text != '\0' && (*text++ == c || c == '.'));
	
	return 0;
}


matchstar 的变体变体
/* matchstar: 搜索 C*regexp 的最左以及最长的匹配 */
int matchstar(int c, char *regexp, char *text)
{
	char *t;
	for(t = text; *t != '\0' && (*t == c || c == '.'); t++){
			;
	}
	
	do{ /* 通配符 * 匹配零个或多个实例 */
		if(matchhere(regexp, t)){
			return 1;
		}
	} while(t-->text);
	
	return 0;
}