草系前端手摸手带你实现正则引擎，点燃夏日最热情的烟火🔥
大家好，我是寒草😈，一只草系码猿🐒。间歇性热血🔥，持续性沙雕🌟。
如果喜欢我的文章，可以关注➕ 点赞 👍，，与我一同成长吧～
微信：hancao97
序章
对读者的话
前一阵，我发了一篇文章前端学编译原理（一）：编译引论，粗略的介绍了一下编译原理这门学科，我也想到一个问题：
单纯枯燥的讲解编译原理这门课程大家可能并不会很接受这系列文章，并且单纯的讲解编译原理肯定有很多人比我讲的要好要细致。
所以我做了这样一个决定：我是一个前端，读我文章的大多数人可能也是前端，所以我不妨接下来将前端的一些应用或者实践和编译原理结合起来。所以这篇文章是本系列的全新实践🌟，如果大家喜欢可以留下你们的点赞👍 或者关注➕，你们的支持是我更文的最大动力🔥。
本篇文章，我将从自动机出发，扩展到我们常用的正则匹配，最后我也会带着大家亲手实现一个简单的正则匹配。干货满满，也会有一己之言，如果大家有疑问或者指正请留在评论区，我会仔细阅读。
仓库地址：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 - 那么作为自动机，我们该怎么知道我们的下一个状态是啥呢，所以其实我们需要两个东西，一个是现在的状态，一个是状态转移函数δ，比如：我们现在的阶段是人事审批，我们的输入其实就是人事审批，经过
状态转移函数（审批结果判断）之后我们就可以得到下一步的状态，状态可能是工单失败或者待老总审批。
不知道经过我的举例之后，大家有没有对定义有了一定的理解，其实总结起来很简单，其实：
有限自动机 = 有限的内部状态集合 + 一组控制规则
