loop_in_codes

低调做技术__欢迎移步我的独立博客 codemaro.com 微博 kevinlynx

简要实现正则表达式匹配字符串

之所以说是“简要实现”一方面是因为算法不算高深,算法的实现也不精致,甚至连我对其的理解也不够本质。

我只不过不想在工作若干年后还是一个只会打字的程序员。学点什么东西,真正精通点什么东西才对得起喜欢

技术的自己。

 

附件中的代码粗略实现了《编译原理》龙书中的几个算法。包括解析正则表达式,建立NFA,然后用NFA去匹

配目标字符串;或者从NFA建立DFA,然后匹配。解析正则表达式我用了比较繁琐的方法,有词法和语法分析

过程。词法分析阶段将字符和一些操作符整理出来,语法分析阶段在建立语法树的过程中对应地建立NFA。

当然,因为语法树在这里并没有用处,所以并没有真正地建立。

 

从正则表达式到NFA比较简单,很多编译原理书里都提到过,如:s|t表达式对应于下面的NFA:

1

代码中用如下的结构描述状态和状态机中的转换:

#define E_TOK (0)

/* transition */
struct tran
{
    char c;
    struct state *dest;
    struct tran *next;
};

struct state
{
    /* a list of transitions */
    struct tran *trans;
    /* inc when be linked */
    int ref;
};

即,每一个状态都有一个转换列表,每个转换都有一个目标状态(即该转换指向的状态)以及转换字符。

貌似通过以上方法建立出来的状态机每个状态最多只会有2个转换?

 

建立好NFA后,由NFA匹配目标字符串使用了一种构造子集法(《编译原理》3.7.2节):

2

这个算法里针对NFA的几个操作,如e-closure、move等在由NFA转换DFA时也被用到,因此代码里单独

做了封装(state_oper.c)。这个算法本质上貌似就是一次步进(step)多个状态。

 

至于由NFA转DFA,则是相对简单的子集构造法:

3

在我以前编译原理课考试的前一天晚上(你懂的)我就对这些算法颇为疑惑。在以后看各种编译

原理教材时,我始终不懂NFA是怎么转到DFA的。就算懂了操作步骤(我大学同学曾告诉我这些步骤,虽然

不知道为什么要那样做),一段时间后依然搞忘。很喜欢《编译原理》龙书里对这个算法最本质的说明:

 

4

 

源代码我是用GCC手工编译的,连makefile也没有。三个test_XXX.c文件分别测试几个模块。test_match.c

基本依赖除掉test外所有c文件,全部链接在一块即可。当然,就经验而言我知道是没几个人会去折腾我的这些

代码的。这些在china的领导看来对工作有个鸟用的代码读起来我自己也觉得费力,何况,我还不伦不类地用了

不知道算哪个标准的c写了这些。

 

你不是真想下载。对于这种代码,有BUG是必然的,你也不用在此文若干个月后问我多少行是什么意思,因为

那个时候我也忘了:D。

posted on 2010-02-20 14:53 Kevin Lynx 阅读(5192) 评论(4)  编辑 收藏 引用 所属分类: 编译原理

评论

# re: 简要实现正则表达式匹配字符串 2010-02-20 19:25 feizai

还可继续拓展
1、DFA最小化
2、DFA嵌入action,仿Ragel
3、CFG的GA自动机
4、LR(0)->LR(1)->LALR(1)分析器
5、拓展语义action的潜入地方,
6、完全自己的lex和yacc  回复  更多评论   

# re: 简要实现正则表达式匹配字符串[未登录] 2010-02-20 19:34 kevin lynx

@feizai
是啊。  回复  更多评论   

# re: 简要实现正则表达式匹配字符串 2010-02-21 02:19 aaa

http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-156.pdf  回复  更多评论   

# re: 简要实现正则表达式匹配字符串 2010-02-24 21:19 陈梓瀚(vczh)

广告:http://www.cppblog.com/vczh/archive/2008/05/22/50763.html  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理