大家好，我是寒草😈，一只草系码猿🐒。间歇性热血🔥，持续性沙雕🌟。
如果喜欢我的文章，可以关注➕ 点赞 👍，，与我一同成长吧～
微信：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
• 那么作为自动机，我们该怎么知道我们的下一个状态是啥呢，所以其实我们需要两个东西，一个是现在的状态，一个是状态转移函数δ，比如：我们现在的阶段是人事审批，我们的输入其实就是人事审批，经过状态转移函数（审批结果判断）之后我们就可以得到下一步的状态，状态可能是工单失败或者待老总审批。

不知道经过我的举例之后，大家有没有对定义有了一定的理解，其实总结起来很简单，其实：

有限自动机 = 有限的内部状态集合 + 一组控制规则

作者：寒草
微信：hancao97
介绍：一个不一样的北漂程序员(工作10个月的年轻程序员)，欢迎加微信批评指正交流技术或者一起玩耍约饭

引言

凡事都可以扯一扯情怀

在我在开始写文章的那一段时间，我发了这样一篇文章
我，24岁，展望一下？里面不仅提到了我的各种离谱的flag，也提到了我的母校，我怀念那段时光，也因整个大四那一年没有在母校度过，因为疫情的原因没有毕业照，没有毕业旅行而十分可惜。
但是，我还是记得我在母校度过的美好时光，而编译原理也正是我在那里求学过程中有印象的最后一个专业课。前两天时间，我也在和别人讨论我的js实现按键精灵——尝试前端实现自动化测试（一），在交流探讨过程中，我感受到其实曾经学习过的编译原理也确实在影响着我的思考方向。
于是我找回了大学的课件资料，并会结合更多的资料，去完成我的前端学编译原理这个系列：

一方面是对知识的回顾
一方面是怀念那曾经在学校里不曾认真听讲，期末突击完成的课（狗头）。

为什么要学编译原理

首先介绍一下，我是一名前端工程师，所以在此以前端的视角出发来思考这个问题：

为什么我们要学习编译原理？

首先我想去纠正一个误区，前端并不是只要去弄好HTML，CSS，JS三大金刚，了解了解各种不同的布局模式，学习一些主流的框架，用一用人家提供好的API，用一下社区成熟的脚手架快速搭建项目就可以了。是这样就能胜任很大部分的前端工作，但是深入学习我们会发现一件可怕的事情，我们会发现在前端这个领域会有层出不穷的各种库，各种工具，各种框架。技术推陈出新，可是万变不离其宗，编译原理作为一个基础理论学科，学习编译原理可以帮助你：

• 更快更容易的学习新的技术

• 可以帮助我们更多的了解语言背后的抽象

• 可以帮助我们用更优雅的形式去描述复杂的模型
  而且可能所谓编译器更像是一个把源语言变成目标语言黑盒子，所以我们其实对他并没有太大的感知，但是其实它已经渗透在我们日常工作的方方面面了：

• eslint：代码检查

• es6，ts转码工具：Babel（将采用 ECMAScript 2015+ 语法编写的代码转换为向后兼容的 JavaScript 语法），tsc（用于将TypeScript 转换为 JavaScript 代码）

• 各种模版引擎（输入模板字符串 + 数据，得到渲染过的字符串）：最早诞生于服务端动态页面的开发，如 JSP、PHP、ASP 等模板引擎，自 Node.js 快速发展以后，前端界又产出了非常多的轮子，包括 EJS、art-template、Pug 、Mustache等等。【个人对模版引擎没什么了解，此处列举的模版引擎来着万能的网友】

• CSS预处理器：sass、less等等，让我们从纯css时代的刀耕火种中解放。赋予了前端工程师们更强大的样式编写能力（虽然我可能用到的也只是他们提供的皮毛，但是支持css嵌套真的是深得我心）。

• 主流框架中的应用：区别于模版引擎，不可将前端框架和模板引擎混为一谈，很多的主流框架都有对编译原理的应用，包括vue，react，angular。

• markdown：比如我现在正在掘金写我的文章，左边是markdown语法，右边就可以同步预览最终的展示效果～

• …

总结一下：
可能我对于学习编译原理的原因描述不是很专业，可能也有我能力所限的原因，也可能是因为我工作年限并没有达到某个地步，但是我希望大家了解的是以下几点：

1. 学习编译原理可以帮助我们更好更快的学习新的技术。
2. 在前端领域，编译原理已经有了大范围的应用，所以想成为一个更加优秀的前端工程师，编译原理也是一项必修课。
3. 学习cs专业的基础理论学科，可以帮助你获得突破，去做一些之前只敢想象的事情。

开始前说点什么

我也不知道以我这粗浅的掌握和拙劣的语言功底能否把这样一个较大的课题讲的清楚明白，但是事在人为，我会尽我所能，让这个系列可以在保证正确性的基础之上保持更新，并以我的视角带大家与我一起感受编译之美。
之前我也出过很多系列性质的文章：
浏览器渲染机制
Promise专题
如果大家对以上内容有一丢丢兴趣，也欢迎阅读并与我交流探讨，作为刚入行不到一年的新人也期望收到各位大佬各位前辈的批评指正。

ok，闲言少叙，我们进入正题。

程序设计语言和编译程序

低级语言基本概念

介绍：

包括机器语言和汇编语言
机器语言：指的是机器能直接识别的程序语言。无需经过翻译，每一操作码在计算机内部都有相应的电路来完成它，或指不经翻译即可为机器直接理解和接受的程序语言或指令代码。计算机硬件只能识别“断开”和“闭合”两种物理状态，也就是0和1。机器语言使用绝对地址和绝对操作码。不同的计算机都有各自的机器语言，即指令系统，不同型号的计算机其机器语言是不相通的，按着一种计算机的机器指令编制的程序，不能在另一种计算机上执行。从使用的角度看，机器语言是最低级的语言。

• 操作码：操作码给出指令完成的功能
• 地址码：地址码给出与操作数相关的地址或者操作数本身
• 指令 10110110【操作码】 00000000【地址码】 表示进行一次加法操作
• 指令 10110101【操作码】 00000000【地址码】 表示进行一次减法操作

汇编语言：是任何一种用于电子计算机、微处理器、微控制器或其他可编程器件的低级语言，亦称为符号语言。在汇编语言中，用助记符（Mnemonics）代替机器指令的操操作码，用地址符号（Symbol）或标号（Label）代替指令或操作数的地址。在不同的设备中，汇编语言对应着不同的机器语言指令集，通过汇编过程转换成机器指令。普遍地说，特定的汇编语言和特定的机器语言指令集是一一对应的,不同平台之间不可直接移植。举个例子，a = a + b的表达方式：

• MOV AX,1
• MOV BX,2
• ADD AX,BX
  ps：是不是相较于之前的0和1，现在已经可以大致看懂了？

优点：

• 速度快

缺点：

• 难理解，出错率高，难维护
• 依赖于具体机器，移植性差

发现：

• 越是低级的语言对机器越是友好，越是符合机器的思考方式，因此执行效率高。
• 越是高级的语言对人类越是友好，越是符合人类的思考方式，因此开发效率高。

  高级语言基本概念

  形式语言

介绍：

用精确的数学或机器可处理的公式定义的语言。与自然语言对应，自然语言就是人类讲的语言，这类语言不是认为设计，而是自然进化的。形式语言是为了特定的应用而人为设计的语言，存在领域之分，例如数学家用的各种运算符号，化学家用的各种分子式，而编程语言也是一种形式语言，是专门设计用来表达计算过程的形式语言。

特点：

• 高度的抽象化：采用形式化的手段-专用符号,数学公式-来描述语言的结构关系,这种结构关系是抽象的
• 是一套演绎系统：形式语言本身的目的就是要用有限的规则来推导语言中无限的句子,提出形式语言的哲学基础也是想用演绎的方法来研究自然语言
• 具有算法的特点

  高级语言

介绍：

高度封装了的编程语言，与低级语言相对，它更接近于我们平时正常的人思维，其最大的特点是编写容易，代码可读性好。实现同样的功能，使用高级语言耗时更少，程序代码量更短，更容易阅读。其次，高级语言是可移植的，也就是说，仅需稍作修改甚至不用修改，就可将一段代码运行在不同类型的计算机上。现在大多数人使用的语言，如C、C++、Python、Java、Javascript等等，都属于高级语言。
优点：

• 面向自然表达
• 更易于学习，易于理解，易于修改
• 可移植性高

缺点：

• 运行需要其他程序支撑（编译程序等）
• 运行速度相比汇编要慢
• 占用空间相对较多