文档章节

实现一个正则表达式库 (1)

o
 osc_4nmshwhm
发布于 2018/08/07 00:39
字数 788
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

实现正则库 1

我的完整实现代码

正则表达式简介

正则表达式(英语:Regular Expression,在代码中常简写为regex、regexp或RE),又称正规表示式、正规表示法、正规表达式、规则表达式、常规表示法,是计算机科学的一个概念。正则表达式使用单个字符串来描述、匹配一系列匹配某个句法规则的字符串。在很多文本编辑器里,正则表达式通常被用来检索、替换那些匹配某个模式的文本。 许多程序设计语言都支持利用正则表达式进行字符串操作。例如,在Perl中就内建了一个功能强大的正则表达式引擎。正则表达式这个概念最初是由Unix中的工具软件(例如sed和grep)普及开的。正则表达式通常缩写成regex,单数有regexp、regex,复数有regexps、regexes、regexen。

由于这篇文章的重点在正则表达式的实现,而非正则表达式的使用。故我将忽略正则表达式的详细介绍,可参考:

在正式开始实现之前,我们来定义一个正则表达式的子集方便第一步的实现——一个完整的正则表达式是:

  • 单个字符
  • 一个包含在括号中的正则表达式
  • 两个及以上连接的正则表达式
  • 两个及以上被 | 分开的正则表达式
  • 一个跟着 * 的正则表达式

非确定性有限状态自动机 (NFA)

非确定有限状态自动机(Nondeterministic Finite-state Automata)与一般的状态机不同,NFA 在接受一个输入时,不只从一个状态决定是否转移或转移到哪个状态,而是由一组状态 (A) 通过判断输入来得到一组转移之后的状态 (B)。而之前的一组状态 (A) 是由上一次得到的状态所等价的所有状态的集合。

图片来自《算法 第四版》

有上面的叙述可以知道,NFA 虽然不是确定的,但是它可以知道哪一个状态率先到达最终状态。从这个性质我们可以联系两点:

  1. 这与正则表达式有关,要判断一个字符串是否满足一个正则表达式,我们只需知道当遍历到该字符串最后一个字符的时候是否刚好符合正则表达式,符合则证明匹配,否则不匹配。
  2. 找到一个率先到达最终状态的问题可以联系到图的深度遍历 DFS

由此,我们找到了解决表达 NFA 的数据结构:(显然是有向的,因为状态判断是单向的)。也有了匹配的方法:深度遍历。剩下的就是用代码一步一步实现了。

class NFA {
private:
    digraph graph;
    std::string re; // regular expression
public:
    NFA(const std::string& regexp); // constructor
    bool recognize(const std::string& txt); // whether the given string match the pattern
};

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

物联网开发服务开发虚拟设备需要几步?

云栖号快速入门:【点击查看更多云产品快速入门】 不知道怎么入门?这里分分钟解决新手入门等基础问题,可快速完成产品配置操作! 物联网平台设备的正常开发流程是:设备端开发完成,设备上报...

osc_2axit9df
17分钟前
18
0
互联网互联网必看文章墙裂推荐

后端必看文章系列 大型项目架构演进过程及思考的点

code-ortaerc
18分钟前
14
0
ACL2020论文整理 - 知乎

ACL2020录取文章已经放出,链接如下: ACL2020论文集合 www.aclweb.org 为了以后更加方便地阅读论文,也本着一颗开源之心,花一个下午的时间整理了一下相关论文。鉴于本人精力有限,并且也只...

osc_5w65ebjo
18分钟前
0
0
SU(N) Hubbard 模型平均场

osc_31d5oo2i
20分钟前
18
0
Python语言及其应用PDF高清完整版百度云盘免费下载|python基础教程PDF电子书推荐

编辑推荐 本书内容易于理解,而且读起来生动有趣,是编程和Python初学者不可多得的教程。书中首先介绍了Python的基础知识,然后逐渐深入多种主题,结合教程和攻略式风格来讲解Python 3中的概...

osc_nbg2lo7i
21分钟前
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部