杨文龙的博客 » Blog Archive » 实现正则表达式匹配器 - 个人技术笔记 - 热爱创新发明，专注机器学习、算法、深度学习、自然语言处理及人工智能

实现正则表达式匹配器

发布时间：2015-11-16 栏目：软件算法评论：0 Comments

Rob Pike在《The Practice of Programming》中使用约30行代码，实现了一个正则表达式匹配器，用来处理以下的模型。

字符	含义
c	匹配认字的字母c
.(句点)	匹配任意的单个字符
^	匹配输入字符串的开头
$	匹配输入字符串的结尾
*	匹配前一个字符的零个或者多个出现

这段代码紧凑、优雅，高效并且实用,同时展示了C指针的强大功能。

/*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;
}

以下是另外一个精简版本（主要区别为，去掉了首位符号检测、部分匹配功能以及‘*’单指匹配零个或者多个字符）：

#include <stdio.h>

bool match(char* src, char* dst )
{
while( *src != ‘\0′ && （*src == *dst||*dst==’?’ )) src++, dst++;
if( *src == ‘\0’ && *dst == ‘\0’ ) return true;
if( *dst == ‘*’ )
{
for( ; *src != ‘\0’; src++ )
if( match( src, dst+1 ) )
return true;
}
return false;
}

int main(int agrv, char* argc[])
{
char data[]=”abcdef”;
char pattern[]=”a*c”;
bool result = match(data,pattern);

if(result==true)
printf(“Matched\n”);
else
printf(“Failed\n”);
return 0;
}

第一个版本功能更加强大也更通用，第二种版本比较简单。

让我还有点不太明白的是：这个实现方式并没有使用NFA或者DFA，那么这种方法跟NFA的实现方式的主要区别在哪里？时间复杂度更高么？

留下评论

You must be logged in to post a comment.

相册集

关于自己

杨文龙，微软Principal Engineering Manager, 曾在各家公司担任影像技术资深总监、数据科学团队资深经理、ADAS算法总监、资深深度学习工程师等职位，热爱创新发明，专注于人工智能、深度学习、图像处理、机器学习、算法、自然语言处理及软件等领域，目前发明有国际专利19篇，中国专利28篇。

联系我

个人技术笔记

welonshen@gmail.com

2015 in Shanghai

个人技术笔记

实现正则表达式匹配器

留下评论

近期文章

近期评论

文章归档

分类目录

功能

热情读者

作者其他介绍

友情链接

相册集

关于自己

联系我