用有限自动机实现正则表达式的匹配

问题：在主串中查找是否存在正则表达式为 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 <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#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 中用的方法比较简洁，直接匹配，可能库的实现原理与之类似。

用有限自动机实现正则表达式的匹配,布布扣,bubuko.com

用有限自动机实现正则表达式的匹配

原文：http://blog.csdn.net/justme0/article/details/20790389