探索正则表达式背后的语言学

正则表达式让新手和经验丰富的程序员都感到恐惧。当我第一次看到正则表达式（通常缩写为“regex”）时，我记得自己当时被一长串括号、星号、字母和数字弄得头晕目眩。正则表达式看起来毫无意义，令人费解。

我以为正则表达式会在我的高级计算机科学课程中再次出现——也许到那时我终于觉得自己准备好了去学习它们——但我在一门我推迟到高三的入门课上遇到了它。这门课的目的是通过向那些从未写过一行代码的学生介绍密码学、人机交互、机器学习等概念——你知道，只是最新、最棒的科技流行语而已。

我听的课不多，但其中一项作业让我印象深刻。我必须写一篇关于一位著名计算机科学家或学者的文章，他的工作对计算机科学产生了影响。我选择了诺姆·乔姆斯基。

我当时根本没想到，学习乔姆斯基会把我带回正则表达式的世界，然后神奇地将正则表达式变成了让我着迷的东西。正则表达式真正让我着迷的是它背后的同音异义语言学概念。

我也希望用正则表达式背后的语言学知识来吸引你，这是大多数程序员都不知道的背景故事。虽然我不会教你如何在任何特定的编程语言中使用正则表达式，但我希望我的语言学介绍能激励你更深入地了解你所选编程语言中正则表达式的工作原理。

首先，让我们回到乔姆斯基：他和正则表达式有什么关系？天哪，他和计算机科学又有什么关系？

偶然成为一名计算机科学家

维基百科将诺姆·乔姆斯基尊称为语言学家、哲学家、认知科学家、历史学家、社会评论家和政治活动家，但并非计算机科学家。由于他在所有这些领域都享有盛誉，他对计算机科学领域的间接贡献常常被忽视。

我对乔姆斯基学术著作的研究越深入，就越觉得乔姆斯基涉足计算机领域纯属偶然。这更加坚定了我的信念：所有领域——即使是那些看似与计算机科学毫不相关的领域——都能为计算和科技行业做出贡献。

他在语言学领域的贡献尤其体现了跨学科研究对计算机科学的影响。乔姆斯基的“层级结构”彻底改变了当今计算机科学家、软件工程师和业余爱好者编写的代码。

是的，正是这种层次结构将正则表达式引入了计算机科学。但是，在我们理解从乔姆斯基到正则表达式的飞跃之前，我先概述一下乔姆斯基的层次结构。

语言法与秩序

乔姆斯基层次结构是对形式语法 （例如形式语言的句法规则）的一种排序， 其中每个语法都作为其上级语法的真子集存在。有些形式语言的语法比其他语言更严格，因此乔姆斯基试图将形式语法组织到他同名的层次结构中。

我曾简要提到，形式语法是句法规则：它为给定的形式语言提供所有可能的有效短语。语法提供了构建语言的规则。用语言学家的话来说，一种语言的形式语法提供了一个框架，通过这个框架，非终结符（输入或中间字符串值）可以转换为终结符（输出字符串值）。

为了阐明这套新词汇，我将通过一个示例，使用一种虚构的形式语法，将一组非终结符转换为终结符。假设我们虚构的形式语言Parseltongue具有以下形式语法：

• 终端：{s, sh, ss}
• 非终结符：{snake, I, am}
• 产生规则：{I → sh, am → s, snake → ss}

使用生成规则，我可以将输入句子“I am snake”转换为“sh s ss”。这种转换是逐步进行的：“I am snake”→“sh am snake”→“sh s snake”→“sh s ss”。

正如我的蛇佬腔示例所示，形式语法将非终结符字符串解析为仅包含终结符的字符串——语法正确的短语。但形式语法不仅充当语言的生成器，还能识别字符串是否符合形式语法。示例字符串“I am a snake”可以完全转换为终结符，而字符串“I am not a snake”则无法用蛇佬腔书写，因为非终结符“not”无法翻译成蛇佬腔终结符。

再次强调我之前说过的一点：形式语法生成形式语言。这意味着，通过创建形式语法的层次结构，乔姆斯基也对语言本身进行了分类。

有了这些引人深思的介绍，我们来看看乔姆斯基层级结构中的四种形式语法。从严格程度来看，它们分别是：

• 常规语法，不保留从输入字符串到输出字符串的过去状态知识
• 上下文无关语法，仅保留从输入字符串到输出字符串的最近状态知识
• 上下文敏感语法，保留从输入字符串到输出字符串的所有过去状态知识
• 不受限制的（或递归可枚举的）语法，具有所有状态知识，因此可以根据给定的输入字符串创建可以想象到的每个输出字符串

我所说的“状态知识”是什么？从作用域的角度来思考知识。例如，常规语法在将输入字符串转换为输出字符串的过程中，在其“作用域”中不知道字符串过去的状态。这意味着，一旦语法进行了一次非终结符到终结符的转换（以及一系列零个或多个非终结符），语法就会“忘记”字符串的先前状态。

另一方面，不受限制的语法会保留翻译字符串的所有可能状态。上下文无关语法和上下文敏感语法则介于两者之间。

如果你正在寻找乔姆斯基层次语法的更详细解释，那么你得看看自动机理论。我将重点讨论与正则表达式相关的语法，也就是我们熟知的正则语法。

关于正则表达式

正则表达式和正则语法是等价的。尽管使用不同的形式，但它们传达的是同一组句法规则，并且都产生相同的正则语言。

在语言学中，正则表达式递归定义如下：

• 空集是一个正则表达式。
• 空字符串是正则表达式。
• 对于输入字母表中的任何字符 x，x 都是产生正则语言 {x} 的正则表达式。
• 替换：如果 x 和 y 是正则表达式，则 x | y 也是一个正则表达式。例如，正则表达式0|1生成正则语言{0,1}。
• 连接：如果 x 和 y 是正则表达式，则 x • y 也是正则表达式。例如，正则表达式0•1生成正则语言{01}。
• 重复（也称为克莱尼星）：如果 x 和 y 是正则表达式，则 x* 也是正则表达式。例如，正则语言0•1*产生正则语言{0, 01, 011, 0111, ...}，如此循环往复。

正则语法由类似蛇佬腔的规则组成。正如正则语法可以用来将输入字符串解析为输出字符串一样，正则表达式也可以以类似的方式转换字符串。您可以看到正则表达式所采用的交替、连接和重复操作（或者用我之前的比喻来说，规则）的解析示例。

让我们暂时回到我们的朋友诺姆·乔姆斯基。根据他的语法层次结构，正则语法不保留从输入字符串到输出字符串的中间步骤的信息。这告诉我们关于正则表达式的什么？

正则语法的“遗忘性”意味着，字符串中某一部分的翻译不会影响字符串中其他非终结符在后续步骤中的翻译。在创建输出字符串时，字符串的不同部分之间无需协调。

探究正则语法背后的语言学原理，可以让我们理解程序员最初将正则表达式引入代码的原因。虽然我之前只讨论了形式语法作为语言的生成器和识别器的作用，但正则语法将输入字符串逐个转换为输出字符串，这一事实使其成为模式匹配器。在编程中，正则表达式使用生成规则将输入字符串（一种模式）转换为正则语言（一组与该模式匹配的字符串）。

但是，如果编程语言的创建者完全按照语言学领域的定义来实现正则表达式，我就不会写这篇博文了。计算正则表达式与其语言学前身相去甚远，但我所介绍的语言学正则表达式为理解代码中的正则表达式提供了一个有用的框架。

两个正则表达式，同样尊贵

下文中，我将使用“正则表达式”来表示语言正则表达式，使用“regex”来表示程序正则表达式。通常情况下，语言正则表达式和程序正则表达式都被称为“正则表达式”，尽管它们之间有很大区别——真是令人困惑！

正则表达式和正则表达式的区别在于它们的使用方式。正则表达式（或正则语法）是形式语言理论的一部分，其存在是为了描述自然语言（即随着时间的推移而演变而来的、无需人类预先思考的语言）的共同元素 。语言学家将正则表达式用于理论研究，例如在乔姆斯基层次结构中对形式语法进行分类。正则表达式帮助语言学家理解人类使用的语言。

另一方面，正则表达式则被日常程序员用来搜索与给定模式匹配的字符串。正则表达式是理论性的，而正则表达式是实用性的。编程语言是形式语言：由人（这里指程序员）为特定目的而设计的语言。正如你可能想象的那样，编程语言的创建者在代码中增强了正则表达式的功能。让我们来研究一下这些增强功能。

记住，正则表达式有三种操作：交替、连接和重复。我不是正则表达式专家——或者说正则专家？——但只要看一下正则表达式的维基百科页面，就能注意到正则表达式实现的操作远不止这三种。

例如，使用POSIX 正则表达式语法，该模式 .ork匹配所有以三个字符“ork”结尾的四个字符的字符串。这个句点比简单的交替、连接和重复更强大，对吗？

不。说实话，即使是最奇特的正则表达式元字符 （调用正则表达式操作的字符）也源自正则表达式操作。假设字母表中的 26 个小写字母是正则语法中仅有的字符，那么正则表达式模式 .ork可以仅使用正则表达式操作来写成如下形式[a|b|c|...|z]ork。

虽然元字符的数量表明正则表达式比正则表达式本身拥有更强大的操作集，但元字符仅仅是定义正则表达式的操作的各种排列的快捷方式。正则表达式元字符为交替、连接和重复的常见组合提供了一种程序员友好的抽象。

到目前为止，我已经将正则表达式描述为具有出色快捷键和清晰用例的正则表达式。然而，正如你可能还记得乔姆斯基的层次结构一样，正则语法拥有最严格的规则，并且没有范围。幸运的是，正则表达式比其语言学前身拥有更多的灵活性，从而赋予了它们更强大的实用能力。

打破常规语法规则

回想一下，根据乔姆斯基层次结构，正则语法在将输入字符串转换为输出字符串时不保留任何知识。由于正则表达式等价于正则语法，这意味着正则表达式也不记忆字符串从输入到输出的中间状态。这也意味着，翻译正则表达式某一部分中的非终结符与翻译表达式另一部分中的非终结符无关。

对于正则表达式来说，情况就不同了。正则表达式支持反向引用，这违反了正则语法的这一关键特性。反向引用允许程序员用括号分隔正则表达式的子部分，并使用元字符引用它。举个例子，该模式(la)\1通过使用\1元字符重复搜索“la”来匹配“lala”。

由于正则表达式中字符串的不同部分彼此之间不会相互影响，反向引用赋予了正则表达式比其前身更强大的功能。更重要的是，反向引用方便了正则表达式的实际应用，例如查找拼写错误（即同一个单词被意外地连续输入两次）。实用主义让我们得以理解，为什么在编程中需要对正则表达式进行调整以创建正则表达式。

另一个增强正则表达式功能的特性是能够改变匹配的贪婪程度。不同的量词 （正则表达式模式的类别）可能看起来相似，但匹配字符串的不同部分却截然不同。贪婪量词(*) 会尝试匹配尽可能多的字符串，而勉强量词(?) 则会尝试匹配字符串中的最少字符数。假设字符串“abcorgi”，该模式 .*corgi会匹配整个字符串，但最终 .?corgi只会匹配“bcorgi”。

占有量词( +) 也会尝试匹配尽可能多的字符串，但与贪婪量词不同，它不会为了找到最大的匹配项而回溯到字符串中的前几个字符。假设字符串“abcorgi”，模式 .*corgi和 .+corgi将匹配整个字符串。虽然占有量词和贪婪量词通常会产生相同的结果，但占有量词往往更高效，因为它避免了回溯。

由于量词是元字符，因此从技术上讲，它们可以由正则表达式的三种操作（交替、连接和重复）构成。然而，量词创建了一个简单的抽象，允许程序员快速指定他们想要的匹配类型。

结论和进一步阅读

我们经历了一段多么奇妙的旅程！我们学习了乔姆斯基及其同名的层次结构，然后深入研究了正则语法。从正则语法出发，我们探索了正则表达式的语言学定义。最后，我们利用正则表达式和正则表达式之间的差异来启发当今程序员如何使用正则表达式。

虽然我追溯了正则表达式从乔姆斯基到现代编程语言的历史，但这篇博文并非正则表达式故事的终结。如果你想了解更多关于语言学和计算正则表达式的知识，我有一些发人深省的问题想问你。

• 什么是自动机理论？它与乔姆斯基层次结构有何关系？
• 正则表达式是如何实现的？各种正则表达式算法的优缺点是什么？
• 什么时候适合使用正则表达式而不是内置字符串匹配和操作库？

我还准备了一份资源清单，用来学习正则表达式的语言和计算元素。祝你学习正则表达式愉快！

• 正则表达式信息
• 维基百科：正则表达式
• StackOverflow：用简单的英语解释乔姆斯基层次结构
• Hopcroft 等人撰写的《自动机理论、语言和计算简介》
• StackOverflow：自动机中正则表达式和语法的区别
• 如何像计算机科学家一样思考：形式语言和自然语言
• Oracle 的 Java 教程：量词
• StackOverflow：将编程语言中的正则表达式与自动机/形式语言中的正则表达式进行比较
• Quora：正则表达式是如何实现的？

喜欢这篇文章吗？点赞和分享，分享你的爱。有任何想法或疑问？请在Twitter或下方评论区联系我。本文最初发表于Medium。封面图片版权归xkcd所有。