自己实现一个 DFA 串模式识别器(一)

自己实现一个 DFA 串模式识别器

前言

 这是我编译原理课程的实验。希望读完这篇文章的人即便不知道 NFA,DFA 和正规表达式是什么,也能够对它们有一个简朴的明白,并能自己去实现一个能够识别特定模式的串模式识别器。它可能会像是这样:

  1. 输入一个正规表达式:(s.f.l*.e)|(a*.b*)

  2. 输入:“sfe”

    输出:matched!

    自己实现一个 DFA 串模式识别器(一)

    输入:“sflea”

    输出:failed!

    自己实现一个 DFA 串模式识别器(一)

注:’.’ (点字符)示意毗邻运算

​  文章分为两部门,理论靠山:先容相关观点和原理;程序实现:使用 C++ 实现一个 DFA 串模式识别器。

理论靠山

引入

​  我对照喜欢将任何理论和手艺从自己能应用和明白的最低点最先论述,由于这样往往可以将新的知识与过往的知识系统相联络。同时在一定的场景下思索它若何被应用,以切实的实现将所学流通的抵达所用。这篇文章亦是云云。

​  首先我们要处置一个简朴的问题,给出如下串:

​  例一:

ab,abab,ababab,abababab,…

a,aa,aaa,aaaa,…

aab,aabaab,aabaabaab,…

​  对于第一行给出的这些字符串,叨教你是否能够编写简朴程序,识别出给定的一个字符串 S 是否属于第一行中的某一个字符串?如 ab 属于第一行,abab 属于第一行,但 aab 不属于。我信赖有过一定编程履历的人都可以通过简朴的分支-循环逻辑,或者是一些字符串算法来写出一个判别程序。对于第二、三行也是云云。由于我们发现它们都具有一定的纪律性,或者也可以称为遵照一定的模式。当情形很简朴时我们并不用思索太多,只是不停的庞大化、堆叠我们的逻辑代码,希望代码逻辑能够捕捉特定模式下所有的串。不外有时情形会很庞大,以至于我们异常难题去设计一个逻辑来实现判别(捕捉模式)。好比下面这个串:

​  例二:

abb,aabb,babb,ababb,aaaaaaabb,bbbbbbbbabb,aababbababbbabbabb,

ababababaaaaaaabbbbbbbaaaaaaabbbbbaababbbabababbabbbbaabb,…

​  你可能会以为这些串完全没有任何逻辑和纪律可言嘛!没错,单凭对已给出的这些串很难发现纪律。然则它确实有自己的模式,而且我可以提前告诉你,它们是由我凭据正则(规)表达式:(a|b)*abb 发生的。若是你没有领会过正则(规)表达式也不必忧郁,先跳过它。

.NET Core技术研究-主机

注:在某些不严酷情形下,不区分正规表达式正则表达式

模式串和正规表达式

​  在前文中,我重复了许多次模式这个词。实在我们之前看到的每一组串都是遵照特定的模式。非正式的,我们可以说 一组字符串组成的聚集由一个与该组相关的称为模式的规则来形貌。而且这个模式被说成匹配该聚集中的每个字符串。

注:这里的模式特指 串的模式

​  可以 以例一为例先容模式。非正式的示意:

例一的第一行的模式为:由 a、b 交替泛起组成的串

第二行模式为:由若干个 a 组成的串

第三行模式为:由若干个 abb 组成的串

​  我们可以用自然语言形貌简朴的模式,然则无法去形貌庞大的模式。以是就需要一种形式化的示意方式,来辅助我们表达。这就是正规表达式。正规表达式是示意模式的一种主要方式。每个模式匹配一个字符串集。简朴来说,正规表达式需要一个字母表,其中字母表上的字符串是该字母表中符号的有穷序列。和界说在其上的一些运算。通过归纳已有的模式串,我们可以提出以下几种运算:

毗邻运算:以英文 ‘.‘ 示意。如:a.b 示意 串 ab

或运算:以英文 ‘|’ 示意。如:a|b 示意串 a 或串 b

克林闭包运算:以英文 ‘*’ 示意。如:a* 示意串:\(\epsilon\) ,a,aa,aaa,…

注:1. \(\epsilon\) 示意空串 2. 为了我的程序利便处置,我将毗邻运算设置成了 英文的点。

​  需要注重的是,运算并不止上述三种,然则我们主要讨论他们,而且许多运算可以通过它们复合获得。如:

正闭包:以英文:’+’ 示意,当字母表只有 a 时 a+ 等价于 a.a*

? 运算:以英文:’?’ 示意,当字母表只有 a 时 a? 等价于 (a|\(\epsilon\))

指数运算等

​  现在我们将例二中的正规表达式重新誊写为:(a|b)*a.b.b 。参照上述运算的寄义,我想你应该可以明白这个模式所代表的串的聚集会是什么样的。

​  注重,正规表达式所能形貌的模式是有限的。它只能示意牢固次数的重复或给定结构没有指定次数的重复。它不能用于形貌平衡或者嵌套结构。如具有括号配对的符号串聚集正规文法无法形貌,然则可以通过更庞大的上下文无关文法来形貌。关于文法不作多形貌。

参考资料:https://book.douban.com/subject/2970069/

出于篇幅思量和更好的阅读体验,本文将分成三个部门,迎接继续阅读余下篇章。下一篇内容是正规表达式的实现原理,涉及 NFA、DFA 的观点和相关算法。

作者:Skipper
出处:https://www.cnblogs.com/backwords/p/12726258.html
本博客中未标明转载的文章归作者 Skipper 和博客园共有,迎接转载,但未经作者赞成必须保留此段声明,且在文章页面显著位置给出原文毗邻,否则保留追究法律责任的权力。

原创文章,作者:28x29新闻网,如若转载,请注明出处:https://www.28x29.com/archives/5042.html