序章
对读者的话
前一阵，我发了一篇文章前端学编译原理（一）：编译引论，粗略的介绍了一下编译原理这门学科，我也想到一个问题：
单纯枯燥的讲解编译原理这门课程大家可能并不会很接受这系列文章，并且单纯的讲解编译原理肯定有很多人比我讲的要好要细致。
所以我做了这样一个决定：我是一个前端，读我文章的大多数人可能也是前端，所以我不妨接下来将前端的一些应用或者实践和编译原理结合起来。所以这篇文章是本系列的全新实践🌟，如果大家喜欢可以留下你们的点赞👍 或者关注➕，你们的支持是我更文的最大动力🔥。
本篇文章，我将从自动机出发，扩展到我们常用的正则匹配，最后我也会带着大家亲手实现一个简单的正则匹配。干货满满，也会有一己之言，如果大家有疑问或者指正请留在评论区，我会仔细阅读。
仓库地址：js-regular，照例放出仓库的地址，请各位大佬忽视我没写
gitignore不小心把node_modules上传上来了，失误，纯属失误
文章大纲
有限自动机基础：DFA与NFA正则原理浅析手摸手，带你实现简易版正则引擎
和文章目录一致，其中如果不阅读第一章自动机科普，也可以直接跳转到第二章开始阅读，但是推荐全文阅读， 因为第一章也干货满满， 第一章过于生硬的地方我也有举例说明或者用更加接地气的手段做了描述总结✨，以获得完整的思考体验，感受一遍我完整学习实践的过程，属于正则的那如烟火🔥 般绚烂的夏日诗篇也会徐徐展开。
那么我们咸盐少许（闲言少叙），开始我们的正篇吧～
有限自动机基础
章节引论—有限自动机（FA）
tip: 如果看不懂特点和形式定义中的话，请大家移步后面
我来总结一下部分，帮助大家对有限自动机的定义有一个粗略的理解。
首先在开始下面的话题之前，我们有必要去了解一下，什么是有限自动机， 有限自动机也被称为：时序机。
有限自动机有以下特点：
- 系统具有有限个状态，不同的状态代表不同的意义。按照实际的需要，系统可以在不同的状态下完成规定的任务。
- 我们可以将输入字符串中出现的字符汇集在一起构成一个字母表。系统处理的所有字符串都是这个字母表上的字符串。
- 系统在任何一个状态下，从输入字符串中读入一个字符，根据当前状态和读入的这个字符转到新的状态。
- 系统中有一个状态，它是系统的开始状态。
- 系统中还有一些状态表示它到目前为止所读入的字符构成的字符串是语言的一个句子。
有限自动机的形式定义：
有限状态自动机是一个五元组 M=(Q, Σ, δ, q0, F)，其中：
- Q——状态的非空有穷集合。∀q∈Q，q称为M的一个状态。
- Σ——输入字母表。
- δ —— 状态转移函数，有时又叫作状态转换函数或者移动函数，δ：Q×Σ→Q，δ(q,a)=p。
- q0 —— M的开始状态，也可叫作初始状态或启动状态。q0∈Q。
- F —— M的终止状态集合。F被Q包含。任给q∈F，q称为M的终止状态
我来总结一下：
大家不要被上面列出的一大堆定义和特点绕晕，其实总结起来非常简单：
- 首先有限状态机有一个开始状态，具一个不太恰当的例子：比如说你要提交一个工单，你会经历直属领导审批，人事审批，老总审批几个阶段。那么
提交工单就是这个工单系统的有限自动机的开始状态，对应五元组里面的q0 - 当然，除了开始状态我们还有一个结束状态，那么对于我们提交工单这个流程来讲，我们的结束状态就是
工单成功或者工单结束，大家可以发现这个有限自动机具有两个终止状态，所以终止状态是一个集合，并不一定只有一个结束状态，这个结束状态就是五元组里面的F - 还有我们有限自动机有限两个字很重要，有限指的是具有有限个状态，就像我们下图中的
提交工单,待上级领导审批，待人事审批，待老总审批，工单成功，工单失败就是我们的状态集，即五元组中的Q - 那么作为自动机，我们该怎么知道我们的下一个状态是啥呢，所以其实我们需要两个东西，一个是现在的状态，一个是状态转移函数δ，比如：我们现在的阶段是人事审批，我们的输入其实就是人事审批，经过
状态转移函数（审批结果判断）之后我们就可以得到下一步的状态，状态可能是工单失败或者待老总审批。
不知道经过我的举例之后，大家有没有对定义有了一定的理解，其实总结起来很简单，其实：
有限自动机 = 有限的内部状态集合 + 一组控制规则
DFA — 确定有限自动机
定义
前文我们已经了解了有限自动机，那么确定有限自动机有哪些特别的点呢，下面我们来看一下确定有限自动机的定义：
- 确定有限自动机M为一个五元组 M = ( S, ∑, s0, f, Z)
- S:一个有穷状态集，它的每个元素称为一个状态;
- ∑:一个有穷字母表，它的每个元素称为一个输入字符;
- s0∈S:唯一的初始状态(开始状态);
- f:状态转换函数:S×∑→ S，且单值函数，f(Si,a)=Sk。
当前状态Si，遇输入字符a时，自动机将唯一地转换到状态 Sk，称Sk为 Si的一个后继状态; - Z⊆S:终止状态集(可接受状态集、结束状态集) 其中每个元素称为终止状态(可接受状态、结束状态), Z可空.
我来总结一下：
我们其实可以和上面的形式定义做一个比较，我们会发现一些很重要的点：
- 初始状态唯一
- 状态转换函数是单值函数
- 终止状态集Z可以为空
举个例子
M=({S,U,V,Q}, {a, b}, f, S, {Q}), 其中f定义为： f(S, a)=U f(S, b)=V f(U, a)=Q f(U, b)=V f(V, a)=U f(V, b)=Q f(Q, a)=Q f(Q, b)=Q
那么我们就可以画出它对应的自动状态机
DFA接受的字符串
- 对于 ∑ 中任何字符串t，若存在一条从初始结点到某一终止结点 的路径，且这条路上所有弧上的标记符连接成的字符串等于t， 则称 t 可为DFA M所接受
- 若DFA M的初始状态同时又是终止状态，则空字符串可为DFA M所接受.
- DFA M 所能接受的字符串的全体记为L(M)
再次举个例子说明，如果一个自动机是这样的：
那么：L(M1) = { aba, abaa, abab, abaab,...}
大家有没有发现，正则匹配的雏形已经有了🌟
DFA的确定性
那么我们为什么说 DFA 是确定有限自动机呢，确定这两个字体现在哪里呢？
- 初始状态唯一
- 状态转换函数f: S×∑→S是一个单值函数，即对任何状态s∈S，输入 符号a∈∑， f(S, a)唯一确定下一状态.
DFA如何代码实现
比如自动机如图所示：
其实我们想要实现简易的 DFA 自动机可以借助 swicth case 实现
// 简单写个switch switch (currentChar) { case 'a': goto Lj; break; case 'b': goto Lk; break; default: throw err; }
NFA — 非确定有限自动机
定义
非确定有限自动机M为一个五元组 M = ( S, ∑, S0, f, Z)
- S: 一个有穷状态集，它的每个元素称为一个状态;
- ∑: 一个有穷字母表，它的每个元素称为一个输入字符;
- S0 ⊆ S: 非空初始状态集;
- Z⊆S: 终止状态集;
- f : 状态转换函数，是从S×(∑∪{ε}) 到 S 子集的映射，即S×(∑∪{ε})→ 2^S
注意，这里的后继状态不是单一状态，而是状态集S的子集, 即转换函数不是单值.
我这里总结一下，大家看区别就是状态转换函数的结果不再是单值了, 起始状态也这是一个集合而不是一个确定的值，以及转换函数的的输入是∑∪{ε}就表示有向弧上面的标记可以是空。
举个例子
NFA M = ({0, 1, 2}, {a, b}, f, {0}, {2}) 状态转换函数如下： f(0,a)={0,1} f(1,a)=∅ f(2,a)={2} f(0,b)={0} f(1,ε)={2} f(2,b)={2}
那么我们就可以画出它对应的有限自动机
NFA接受的字符串
设M是一个NFA，M=(S, ∑, f, S0, Z)，则定义L(M)为从任意初始 状态到任意终止状态所接受的字符串的集合，我们拿上面的自动机举例。 上面自动机接受的字符串集合是： L(M) = { β | β是形如...a...的由a, b构成的字符串 }
比如：aaa, bab, abaa...
DFA 与 NFA 对照
那在本章结束之前，我们回顾一下～
DFA：
- 开始状态唯一
- 状态转换函数为单值函数
NFA：
- 开始状态是一个状态集合
- 状态转换函数的结果是一个集合
- 有向弧上面的标记可以是空
更多扩展内容
tip: 此处还会很多值得讲的内容，比如
NFA到DFA的转换,DFA的化简等，但是因为文章内容有限，而且与本文主题关系不大，感兴趣的人可以留言，我们继续开坑。当然我也更加鼓励大家自我学习。
