Categories
不学无术

re -> NFA 正则表达式->不确定自动机

文章来自http://www.360doc.com/content/09/0219/10/98111_2586955.shtml
以及http://hi.baidu.com/tcet030840zxp/item/c923fe885ddd0329100ef3ec

最近得做一些跟自动机有关的东东，其中一部分可以简要地看作是由一套正则文法生成状态自动机的过程。

什么是正则表达式？

首先我们看看什么是正则表达式。这个东东呢，一般用于描述一个字符串的集合——直接说就是一个正则表达式可能可以匹配一大堆字符串，而这一大堆字符串可以形成一个集合，它们的共同特征就是可以被这个正则表达式匹配。就像去死去死团，但是不同的是去死去死团的团员的共同特征是不被任何异性所匹配——但是这没关系，我们不妨取去死去死团的补集就行了。
反正正则表达是很好啦，因为你只要用一点点在脏话里，就可以骂好多好多人，比如：

Mar(y|k|cus) is son of bitch.

真是非常de省力，唯一的缺点是可能对方不知道你在说什么。
好了，从上面我们可以看出正则表达式中的两个基本结构：

  • 连结 (Concatenation)，比如 bitch，由b, i, t, c, h连接而成
  • 联合 (Union)，比如 y|k|cus，可以认为是y或k或者cus

下面是第三个基本结构，被称为Kleene star (或者 Kleene 闭包)的。因为这个操作是Stephen Cole Kleene发明的。啊啊，其实正则表达式这个东西就是Kleene发明的。这个同学真是非常的牛B，因为他是更加牛B的 阿隆佐 – 丘奇 ( Alonzo Church )——历史上和阿兰 – 图灵 ( Alan Turing ) 并称的人物——的学生。有多牛B呢，这个Kleene还和他的老师，还有图灵，就递归论发表了论文，奠定了可计算理论的根基。啊哈哈哈，真是牛B啊。
嗯，所谓Kleene Star的例子就是这样的。

  • Kleene Star，比如a*，可以接受空串和若干个a连结组成的串

当然咯，还有一些别的操作，比如我们知道的+，?，集合[]等等，但是这些操作都可以通过上面三个基本操作的组合来完成。
比如+，a+可以认为是aa*

什么是NFA？

要说NFA嘛，我得先说说DFA。所谓DFA，就是Deterministic Finite state Automata的简称。是状态机的一种。通俗的说，就是一大堆状态的集合，里面有一个初始状态和若干终止状态，每个状态可以有若干个输出边前往别的状态。但是要求每个状态的同一种输出边至多只有一个，所以自动机被称为是”Deterministic”的。
比如下面这个例子：
表述的是一个电灯de开关，这个开关每按一下就从’开’状态转换到’关’状态，或者从’关’状态转换到’开’状态。而为了从环保角度出发，在’关’状态才被认为是终止态。
dfa
上面的自动机呢，就可以描述这个灯泡的行为模式，或者说可以描述电灯的状态转换过程。输出边就是’开’或者’关’的动作，或者说这个灯泡的开关，只接受这两种动作：“Trun On”，“Trun Off”。而”Trun On”动作只会导致灯的状态变成“On”，“Trun Off”动作只会导致灯的状态变成“Off”，这是确定的，你的外婆都可以预料到的。所以说DFA是确定有限状态自动机。
现在可以说NFA了。这个NFA嘛，全称是Non-deterministic Finite state Automata。也是状态自动机的一种。确切地说，刚才的DFA是NFA的一个子集。和DFA唯一的区别就是他是”Non-deterministic”的，哈，非确定的，每个状态的同一种输出边可以不止一个。
还是用刚才的例子。现在假设我们的电灯有一种新的状态咯～：坏掉了。灯丝被过大的电流烧断了，听上去遭透了，因为一”Trun On”就得准备换灯泡了：
nfa
但是我们没法确定的知道哪一次Trun On会导致灯泡坏掉，使得灯泡进入”Down”状态的那次“开”操作看上去跟你昨天开灯的那次操作一模一样（严格的说，每一次点亮灯泡都会导致灯丝的状态发生变化，但是在此简化了）
所以从状态”Off”出来的输出边中，”Trun On”有两条，这就导致没法根据当前状态和输出边确定下一状态，这就是为什么称为非确定性有限自动机的原因。

如何转换？

刚才Shellex说了，正则表达式有三种基本结构。如果能先将这三种基本结构转换成对应的NFA，然后在用这三种基本结构去拼装成完整的NFA是不是很省力呢？
下面就是三种基本正则表达式的NFA
ab:
g_basic_a_concat_b_blog
a*:
g_basic_a_star_blog
a|b:
g_basic_a_union_b_blog
里面出现了一种叫“None”的边。这个不代表这个边是字面上的“None”，而是指这个边是个空边。也就是说任何“动作”都可以从这个边进入下一个状态。它的学名叫 epsilon 边，一般表示成’ε’，Shellex这里表示成“None”了。
下面我们来考虑正则表达式到NFA转换。给出一个正则串的输入，得到一个NFA的输出。被广泛采用的是Thompson Algorithm，也就是所谓的子集算法。该算法的发明人应该就是写ed编辑器的那个Thompson大牛。该算法的实现和算术表达式的求值非常的类似，需要一个符号栈存放操作符，一个自动机栈存放生成的自动机。算法结束后，可以从自动机栈中Pop一个最终的结果。
比如对于正则表达式(a|b)*cd，求值过程如下：

PUSH a To automaton stack
PUSH b To automaton stack
UNION
STAR
PUSH c To automaton stack
CONCAT
PUSH d To automaton stack
CONCAT
POP result

里面的UNION，STAR 和 CONCAT就是三种基本结构的生成操作了。而这三种基本操作的实现是这样的：
Star：

POP T from automaton stack
CREATE state A, B
ADD transition from A to B with 'ε'
ADD transition from A to T.entry with 'ε'
ADD transition from T.exit to A with 'ε'
ADD transition from T.exit to B with 'ε'
ADD state A, B to T
PUSH T to automaton stack

Concat：

POP F, S from automaton stack
ADD transition from F.exit to S.entry with 'ε'
JOIN S to F
SET F.exit = S.exit
SET F.inputSet += S.inputSet
PUSH F to automaton stack

Union:

POP F, S from automaton stack
CREATE state A, B
ADD transition from A to F.entry with 'ε'
ADD transition from A to S.entry with 'ε'
ADD transition from T.exit to B with 'ε'
ADD transition from T.exit to B with 'ε'
JOIN S to F
ADD state A, B to T
SET F.exit = S.exit
SET F.inputSet += S.inputSet
PUSH F to automaton stack
 
/* Regular expression implementation.
 * Supports only ( | ) * + ?.  No escapes.
 * Compiles to NFA and then simulates NFA
 * using Thompson's algorithm.
 *
 * See also http://swtch.com/~rsc/regexp/ and
 * Thompson, Ken.  Regular Expression Search Algorithm,
 * Communications of the ACM 11(6) (June 1968), pp. 419-422.
 * 
 * Copyright (c) 2007 Russ Cox.
 * Can be distributed under the MIT license, see bottom of file.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
/*
 * Convert infix regexp re to postfix notation.
 * Insert . as explicit concatenation operator.
 * Cheesy parser, return static buffer.
 */
char*
re2post(char *re)
{
	int nalt, natom;
	static char buf[8000];
	char *dst;
	struct {
		int nalt;
		int natom;
	} paren[100], *p;
	p = paren;
	dst = buf;
	nalt = 0;
	natom = 0;
	if(strlen(re) >= sizeof buf/2)
		return NULL;
	for(; *re; re++){
		switch(*re){
		case '(':
			if(natom > 1){
				--natom;
				*dst++ = '.';
			}
			if(p >= paren+100)
				return NULL;
			p->nalt = nalt;
			p->natom = natom;
			p++;
			nalt = 0;
			natom = 0;
			break;
		case '|':
			if(natom == 0)
				return NULL;
			while(--natom > 0)
				*dst++ = '.';
			nalt++;
			break;
		case ')':
			if(p == paren)
				return NULL;
			if(natom == 0)
				return NULL;
			while(--natom > 0)
				*dst++ = '.';
			for(; nalt > 0; nalt--)
				*dst++ = '|';
			--p;
			nalt = p->nalt;
			natom = p->natom;
			natom++;
			break;
		case '*':
		case '+':
		case '?':
			if(natom == 0)
				return NULL;
			*dst++ = *re;
			break;
		default:
			if(natom > 1){
				--natom;
				*dst++ = '.';
			}
			*dst++ = *re;
			natom++;
			break;
		}
	}
	if(p != paren)
		return NULL;
	while(--natom > 0)
		*dst++ = '.';
	for(; nalt > 0; nalt--)
		*dst++ = '|';
	*dst = 0;
	return buf;
}
/*
 * Represents an NFA state plus zero or one or two arrows exiting.
 * if c == Match, no arrows out; matching state.
 * If c == Split, unlabeled arrows to out and out1 (if != NULL).
 * If c < 256, labeled arrow with character c to out.
 */
enum
{
	Match = 256,
	Split = 257
};
typedef struct State State;
struct State
{
	int c;
	State *out;
	State *out1;
	int lastlist;
};
State matchstate = { Match };	/* matching state */
int nstate;
/* Allocate and initialize State */
State*
state(int c, State *out, State *out1)
{
	State *s;
	nstate++;
	s = malloc(sizeof *s);
	s->lastlist = 0;
	s->c = c;
	s->out = out;
	s->out1 = out1;
	return s;
}
/*
 * A partially built NFA without the matching state filled in.
 * Frag.start points at the start state.
 * Frag.out is a list of places that need to be set to the
 * next state for this fragment.
 */
typedef struct Frag Frag;
typedef union Ptrlist Ptrlist;
struct Frag
{
	State *start;
	Ptrlist *out;
};
/* Initialize Frag struct. */
Frag
frag(State *start, Ptrlist *out)
{
	Frag n = { start, out };
	return n;
}
/*
 * Since the out pointers in the list are always 
 * uninitialized, we use the pointers themselves
 * as storage for the Ptrlists.
 */
union Ptrlist
{
	Ptrlist *next;
	State *s;
};
/* Create singleton list containing just outp. */
Ptrlist*
list1(State **outp)
{
	Ptrlist *l;
	l = (Ptrlist*)outp;
	l->next = NULL;
	return l;
}
/* Patch the list of states at out to point to start. */
void
patch(Ptrlist *l, State *s)
{
	Ptrlist *next;
	for(; l; l=next){
		next = l->next;
		l->s = s;
	}
}
/* Join the two lists l1 and l2, returning the combination. */
Ptrlist*
append(Ptrlist *l1, Ptrlist *l2)
{
	Ptrlist *oldl1;
	oldl1 = l1;
	while(l1->next)
		l1 = l1->next;
	l1->next = l2;
	return oldl1;
}
/*
 * Convert postfix regular expression to NFA.
 * Return start state.
 */
State*
post2nfa(char *postfix)
{
	char *p;
	Frag stack[1000], *stackp, e1, e2, e;
	State *s;
	// fprintf(stderr, "postfix: %sn", postfix);
	if(postfix == NULL)
		return NULL;
	#define push(s) *stackp++ = s
	#define pop() *--stackp
	stackp = stack;
	for(p=postfix; *p; p++){
		switch(*p){
		default:
			s = state(*p, NULL, NULL);
			push(frag(s, list1(&s->out)));
			break;
		case '.':	/* catenate */
			e2 = pop();
			e1 = pop();
			patch(e1.out, e2.start);
			push(frag(e1.start, e2.out));
			break;
		case '|':	/* alternate */
			e2 = pop();
			e1 = pop();
			s = state(Split, e1.start, e2.start);
			push(frag(s, append(e1.out, e2.out)));
			break;
		case '?':	/* zero or one */
			e = pop();
			s = state(Split, e.start, NULL);
			push(frag(s, append(e.out, list1(&s->out1))));
			break;
		case '*':	/* zero or more */
			e = pop();
			s = state(Split, e.start, NULL);
			patch(e.out, s);
			push(frag(s, list1(&s->out1)));
			break;
		case '+':	/* one or more */
			e = pop();
			s = state(Split, e.start, NULL);
			patch(e.out, s);
			push(frag(e.start, list1(&s->out1)));
			break;
		}
	}
	e = pop();
	if(stackp != stack)
		return NULL;
	patch(e.out, &matchstate);
	return e.start;
#undef pop
#undef push
}
typedef struct List List;
struct List
{
	State **s;
	int n;
};
List l1, l2;
static int listid;
void addstate(List*, State*);
void step(List*, int, List*);
/* Compute initial state list */
List*
startlist(State *start, List *l)
{
	l->n = 0;
	listid++;
	addstate(l, start);
	return l;
}
/* Check whether state list contains a match. */
int
ismatch(List *l)
{
	int i;
	for(i=0; i<l->n; i++)
		if(l->s[i] == &matchstate)
			return 1;
	return 0;
}
/* Add s to l, following unlabeled arrows. */
void
addstate(List *l, State *s)
{
	if(s == NULL || s->lastlist == listid)
		return;
	s->lastlist = listid;
	if(s->c == Split){
		/* follow unlabeled arrows */
		addstate(l, s->out);
		addstate(l, s->out1);
		return;
	}
	l->s[l->n++] = s;
}
/*
 * Step the NFA from the states in clist
 * past the character c,
 * to create next NFA state set nlist.
 */
void
step(List *clist, int c, List *nlist)
{
	int i;
	State *s;
	listid++;
	nlist->n = 0;
	for(i=0; i<clist->n; i++){
		s = clist->s[i];
		if(s->c == c)
			addstate(nlist, s->out);
	}
}
/* Run NFA to determine whether it matches s. */
int
match(State *start, char *s)
{
	int i, c;
	List *clist, *nlist, *t;
	clist = startlist(start, &l1);
	nlist = &l2;
	for(; *s; s++){
		c = *s & 0xFF;
		step(clist, c, nlist);
		t = clist; clist = nlist; nlist = t;	/* swap clist, nlist */
	}
	return ismatch(clist);
}
int
main(int argc, char **argv)
{
	int i;
	char *post;
	State *start;
	if(argc < 3){
		fprintf(stderr, "usage: nfa regexp string...n");
		return 1;
	}
	post = re2post(argv[1]);
	if(post == NULL){
		fprintf(stderr, "bad regexp %sn", argv[1]);
		return 1;
	}
	start = post2nfa(post);
	if(start == NULL){
		fprintf(stderr, "error in post2nfa %sn", post);
		return 1;
	}
	l1.s = malloc(nstate*sizeof l1.s[0]);
	l2.s = malloc(nstate*sizeof l2.s[0]);
	for(i=2; i<argc; i++)
		if(match(start, argv[i]))
			printf("%sn", argv[i]);
	return 0;
}
/*
 * Permission is hereby granted, free of charge, to any person
 * obtaining a copy of this software and associated
 * documentation files (the "Software"), to deal in the
 * Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute,
 * sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so,
 * subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall
 * be included in all copies or substantial portions of the
 * Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY
 * KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
 * WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
 * PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE AUTHORS
 * OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.