用有限自動機實現正則表達式的匹配

問題：在主串中查找是否存在正則表達式為 abc*d?e 的匹配，下面用有限自動機的方法查找，該正則表達式的最簡 DFA 如下

狀態轉換表如下圖所示

程序中用二維數組定義如下

#define STATES_NUMBER	5
#define LETTER_NUMBER	5

// 表示 abc*d?e 的最簡 DFA 的狀態轉換表（-1表示不接受）
int trans_table[STATES_NUMBER][LETTER_NUMBER] = {
	1, -1, -1, -1, -1,
	-1, 2, -1, -1, -1,
	-1, -1, 2, 3, 4,
	-1, -1, -1, -1, 4,
	-1, -1, -1, -1, -1
};

程序如下

/**************************************************************************
created:	2014/03/08
filename:	main.c
author:		Justme0(http://blog.csdn.net/justme0)

purpose:	模擬 DFA，在主串中搜索模式 abc*d?e，查找是否存在匹配
**************************************************************************/

#include 
#include 
#include 
#include 

#define MAX_LENGTH		100
#define STATES_NUMBER	5
#define LETTER_NUMBER	5

// 表示 abc*d?e 的最簡 DFA 的狀態轉換表（-1表示不接受）
// 查找能否匹配上，無需貪婪匹配，故作為接受狀態的最後一行實際上不會被訪問到
int trans_table[STATES_NUMBER][LETTER_NUMBER] = {
	1, -1, -1, -1, -1,
	-1, 2, -1, -1, -1,
	-1, -1, 2, 3, 4,
	-1, -1, -1, -1, 4,
	-1, -1, -1, -1, -1
};

/*
** 是否是接受狀態
*/
int is_end(const int state) {
	return STATES_NUMBER - 1 == state;
}

/*
** state 是否接受 letter
*/
int is_acceptable(const int state, const char letter) {
	int column = letter - 'a';
	assert(0 <= state && state < STATES_NUMBER);
	if (!(0 <= column && column < LETTER_NUMBER)) {
		return 0;
	}
	
	return -1 != trans_table[state][column];
}

int move(const int state, const char letter) {
	int column = letter - 'a';
	
	return trans_table[state][column];	// is_acceptable 與 move 有冗余，待改進
}

/*
** 若主串中匹配上了模式則返回1，否則返回0
*/
int is_matched(const char *const str) {
	const char *head = NULL;	// head 是當前模式的頭在 str 中的位置
	const char *p = NULL;		// p 指示主串
	int state = 0;				// state 代表模式
	
	for (head = str; '\0' != *head; ++head) {
		state = 0;
		for (p = head; '\0' != *p && (!is_end(state))
			&& is_acceptable(state, *p); ++p) {
			state = move(state, *p);
		}
		
		if (is_end(state)) {
			return 1;
		}
	}
	
	return 0;
}

int main(int argc, char **argv) {
	char str[MAX_LENGTH];
	int ans;
	
	FILE * in_stream = freopen("test.txt", "r", stdin);
	if (NULL == in_stream) {
		printf("Can not open file!\n");
		exit(1);
	}
	
	while (EOF != scanf("%s", str)) {
		scanf("%d", &ans);
		assert(ans == is_matched(str));

		if(is_matched(str)) {
			printf("找到 abc*d?e 匹配\n");
		} else {
			printf("沒有找到 abc*d?e 匹配\n");
		}
	}

	fclose(in_stream);
	
	return 0;
}

/*test.txt
abe 1
abee 1
abde 1
eabcce 1
bb33_aabcabdee 1
-*+68abcdababaabcccccccdeeeesabc 1
a 0
abc 0
b 0
. 0
eab 0
eabcccd 0
abdff 0
&*%&(* 0
*/

有幾點感受：

1、ACM 中常常用到的 AC 自動機與這個應該有區別，那個常用 Trie 樹實現。

2、上面也提到了，用的是暴力匹配，也就是說此次沒匹配上，模式向前移動一個字符，又重新匹配，我想應該有類似 KMP 的算法，沒匹配上可滑動多個字符。

3、提供正則表達式的庫實現的是對任給的一個正則表達式在主串中查找，許多語言都支持，C++11 中也加入了，可能可以查看源碼。這篇文章 http://blog.csdn.net/xiaozhuaixifu/article/details/9875423 中用的方法比較簡潔，直接匹配，可能庫的實現原理與之類似。