编译器原理与实现: 自动机理论，RegExp 机器内部 | Automata Theory: inside a RegExp machine

课程大纲

状态机——今天在许多实际应用中使用的基本概念，从像 React 这样的 UI 编程、自动回复系统、解析器中的词法分析和形式语言理论——即 RegExp 机器——一直到现实生活中的用例，比如简单红绿灯、自动售货机等。

状态机得到了被称为计算理论的更大的计算机科学理论领域以及它的直接理论模型——自动机理论的支持。

在这堂课中，我们研究了自动机理论关于实现正则表达式机器的实际例子。

为什么要上这门课？

谷歌、Facebook 等大型科技公司围绕通才工程师组织招聘流程，这已经不是什么秘密了，他们了解基本的基础系统、数据结构和算法。事实上，这是技术招聘中的一个众所周知的问题：有很多“程序员”，但没有那么多“工程师”。在这种情况下，“工程师”的定义是什么？——通过对这些通用概念的理解（和经验）来解决复杂问题的能力。

还有一个简单的技巧可以让您获得将知识转移到其他系统的丰富经验。— 你选择了一些复杂的理论领域，可能（还）与你的主要工作不相关，并用你熟悉的语言来实现它。在你构建它的同时，你会学习适应这个系统的所有不同的数据结构和算法。它应该特别是通用的东西（例如，状态机），因此您可以进一步将这些知识转移到您的“日常”工作中。

在这堂课中，我们采用这种方法。为了研究自动机“理论”，我们使其更加实用：我们采用其广泛使用的应用之一，词法分析和模式匹配，并构建一个RegExp 机器。

我们不仅会完全理解正则表达式是如何在幕后工作的（以及什么会使它们的使用更专业），而且还将能够应用这些关于形式语法、语言、有限自动机的知识——NFA、DFA 等——在我们工作的其他领域。

这门课是为谁准备的？

对于任何愿意获得有关有限自动机和正则表达式的通用知识的好奇工程师。

但请注意，这门课不是关于如何使用正则表达式（你应该已经知道什么是正则表达式，并在实践中积极使用它作为这门课的先决条件），而是关于如何实现正则表达式 – 再次以研究通用复杂系统为目标。

此外，词法分析（特别是 NFA 和 DFA）是解析器理论的基础。因此，如果您想了解解析器的工作原理（更具体地说，是它们的Tokenizer或“Lexer”模块），您也可以从这里开始。编译器工程师的道路正是从有限自动机和词法分析器开始的。

这个班有什么特点？

这些讲座的主要特点是：

• 简明扼要。每个讲座都是独立的、简洁的，并描述了与主题直接相关的信息，不会分散在不相关的材料或谈话上。
• 动画演示与实时编辑笔记相结合。这使得对主题的理解更容易，并显示对象结构是如何（以及何时）连接的。静态幻灯片根本不适用于复杂的内容！

课程内容是什么？

课程分为三个部分，共16节课，每节课有很多子课题。下面是目录和课程表。

第 1 部分：形式语法和自动机

在这部分我们讨论状态机的历史，和正则表达式，谈论语言理论中的形式语法。我们还考虑了不同类型的有限自动机，了解 NFA、ε-NFA 和 DFA 之间的区别。

第 2 部分：RegExp NFA 片段

在这一部分中，我们关注主要的 NFA 片段，即 RegExp 自动机中使用的基本构建块。我们研究如何使用通用的组合原理，我们可以获得非常复杂的机器，并对其进行优化。

第 3 部分：RegExp 机器

最后，我们实现了一个正则表达式的实际测试方法，该方法从一个状态转换到另一个状态，匹配一个字符串。首先，我们通过遍历图来了解 NFA 接受器是如何工作的。然后我们将其转换为 NFA 表，最终转换为 DFA 表。我们还详细讨论和描述了 DFA 最小化算法。

我希望你会喜欢这堂课，并且很乐意在评论中讨论任何问题和建议。

真挚地，

德米特里·索什尼科夫