解析器生成器DSL：使用Babel和JavaScript模板构建解析器

自从我开始处理样式化组件以来，我一直对解析器着迷。第一次为Webpack或Babel编写插件感觉就像是纯粹的魔术，尤其是如果该插件不只是出于兼容性原因而传递一些可移植的代码或添加一些元数据，而是生成了全新的编码器或启用了无法在运行时实现的功能时，仅代码。

这些天来，JavaScript开发人员解析器无处不在。当我们启动Webpack或汇总过程时，Acorn会在后台解析我们的代码。当我们使用CSS-in-JSlibrary时，stylis很可能会解析CSS代码。当我们使用GraphQL时，参考实现的解析器会在后台努力工作。

对我而言，没有什么比“ BabelMacros”更能说明这种解析器的无处不在了。BabelMacros是一个Babel插件，它本身可以运行其他插件，这些插件嵌入特殊的npm软件包中，称为“ macros”。非常具有元功能，有了宏，程序包就可以看起来像只是一个JS库，但是可以使用编译时编译的全部功能，而无需更新Babel配置。例如，eval.macro在标记的模板文字中评估JS代码在编译时。正如Axel Rauschmayer博士在其主题文章中所写的那样，带有标记的模板文字甚至甚至旨在将特定领域的语言（“ DSLs”）嵌入到JavaScript中：

“在ECMAScript 6中，模板字符串是一种语法构造，有助于在JavaScript中实现嵌入式DSL。”

鉴于可以立即使用宏来转译任何代码，包括加标签的模板文字，只需使用导入包，eval.macro之类的插件（其技术上就将JS嵌入JS中）可以预编译其某些功能：

从'eval.macro'导入eval; //使用以下宏：const val = eval`7 * 6`; // ...变成这样：const val = 42;

解析器确实无处不在，并经常赋予我们惊人的新能力。但是，如果我们从本地编译语言的角度看待JavaScript生态系统的状态，我们可能会注意到，我们可以通过元编译器（比这还不错的程序类别，还包括解析器生成器）在此方面走得更远。解析器生成器（在JavaScript中是peg.js的一个示例）使我们可以在DSL中编写解析器，该解析器通常看起来与正则表达式类似，然后自动生成解析器的代码。

解析器生成器使我们可以在DSL中编写解析器，该DSL通常看起来与正则表达式相似，然后自动输出解析器本身。

这本身是非常有用的知识，但是了解Babel Macros后，我想知道创建一个宏是否可行，该宏可以使我以标记模板文字编写解析语法并将其转换为解析器。如果JS中的解析器生成器能够输出仍然相当快的紧凑代码，那么创建可在浏览器中运行的小型且快速的DSL本身将非常有用。让我们看看我如何构建RegHex！

当进入这样一个复杂的项目时，我通常从流程的两端开始，问：“库的API应该是什么样？”和“小的实施细节是什么，我首先需要进行调查？”但是，计划和开始是两个步骤，由于拖延，我花了相当多的时间。

对于这个项目，我大约在一年前的2019年提出了一个粗略的想法。然后，我在2020年4月编写了第一个API设计草案，并在2020年5月一个月后实现了该库。没有任何借口，让我们继续前进。 API设计的初稿如下所示：

const identifier = match（'identifier'）`$ {/ [-\ w] + /}`; const string = match（'string'）`（$ {/“ [^”] *“ /} | $ {/'[^'] *'/}）`; const values = match（'values'）`（ $ {identifier} | $ {string}）*`; //输入：“ string” //输出：[['“ string”'，.tag：'string']，.tag：'values'] //输入：ident //输出：[['ident'，.tag：'identifier']，.tag：'values']

API的一般想法是公开一个使用语法分析名称调用的match函数。然后将其称为带有正则表达式样语法的标记模板文字，其中包含具有正则表达式或其他语法的插值，用于对输入的位进行递归解析.match的输出可用于开始解析a字符串，并将返回一个抽象语法树（“ AST”），该嵌套节点描述输入的解析内容。

为了控制如何在插值周围解析输入的逻辑，使用了类似于正则表达式语法的“运算符”，而正则表达式将在输入的当前索引处匹配。由于正则表达式语法在解析器生成器中很常见，并且对许多语法生成器来说都很熟悉，因此编写例如|如果组的第一部分不匹配，则用于匹配其他内容；或*允许多个匹配。

此初稿显示了我计划的API的关键功能。因为我选择通过标记的模板文字将解析语法嵌入JS代码，所以草稿开始看起来像“解析器组合器”。简而言之，解析器组合器是接受其他解析器作为输入并返回新解析器的函数。在这种情况下，比赛的模板可以选择接受其他比赛解析器作为插值。

API草案中的语法指出，标识符或字符串尽可能匹配，而两者也是它们自己的语法。

简而言之，解析器组合器是接受其他解析器作为输入并返回新解析器的函数。

这允许较大的解析器由较小的可重用语法位逐渐组成，这也将一次生成解析代码的任务的范围缩小到一个小的匹配标记。作为Asan API，这就是使标记模板文字成为真正引人注目的选择的原因。对我来说，这类似于样式化组件如何将CSS拆分为单独的组件，每个组件都使用自己的样式来呈现单个元素。 🤩带有标签的模板文字自然会迫使库的API简化并拆分暴露的API表面。

到目前为止，解析器生成器通过创建较小的语法片段来工作，这些语法片段是通过插值其他小的匹配语法或正则表达式来定义的。直观地讲，从中生成代码的最直接方法是仅在模板字符串中转换语法片段，并按原样重用内插的正则表达式。但是，这样做的前提是不跳过输入字符串中的任何字符。

执行正则表达式通常会扫描输入字符串，直到找到匹配为止，这既昂贵又与解析器的工作方式背道而驰。而不是扫描字符串，解析器生成器需要的是尝试仅在精确位置上匹配正则表达式。幸运的是，在ECMAScript 6中添加了对“ stickyflag”的支持，它的作用是：

const regex = new（'hi'，'y'）; const input ='哦嗨';正则表达式。 lastIndex = 0; regex。 exec（输入）; // nullregex。 lastIndex = 3; regex。 exec（输入）; // ['hi'，索引：3] regex。 lastIndex; // 5

现在，lastIndex属性指示应在何处执行正则表达式，而不是从何处开始搜索输入字符串。与往常一样，如果正则表达式已成功匹配输入字符串的一部分，则索引也会随之移动。这非常适合于构建一个连续的解析器组合器，该组合器主要由正则表达式以及一些分支和循环组成，并使解析器生成器仅能够转换我们的自定义DSL，而不必重新实现正则表达式。

开始执行此解析器生成器后，事情就变成了元数据。由于我概述的匹配标签模板API本身就是一种类似于正则表达式语法的语言，因此需要用于此DSL的小型解析器。幸运的是，该特定DSL必须支持的语法很小，因此解析器最终也变得很容易编写和压缩。RegHex的DSL被设置为支持量词，各种类型的组和替换。正如我早在设计过程中所决定的那样，它对于空格的可读性意义不大。以下是以DSL语法结尾的运营商的简要概述：

量词可用于按顺序更改接受多少个匹配：一个或一个，一个或多个或任意数量。

交替可用于匹配事物，当第一个插值失败时回退。

非捕获组类似于常规组，但是内部匹配的插值不会出现在解析器的输出中。

正前瞻将检查插值是否匹配，如果匹配，则匹配器将继续运行而不会更改输入。如果匹配，则基本上被忽略。

否定的超前检查会检查插值是否不匹配，如果匹配不匹配，则匹配器将继续而不更改输入。如果插值匹配，匹配器将中止。

可以说，上面列出的这种语法的最重要特征无疑是交替，因为解析器无法匹配几种替代模式，因此无法表达任何有用的语法。让我们来看一个RegHex DSL的示例，该DSL的语法与重复的“ this”和“ that”字符串匹配：

const thisThat = match（'thisThat'）`（？：$ {/ and /}）（（（？！$ {/。* that /}）$ {/ this /} +）|（（？！$ {/ * * this /}）$ {/ that /} +））`;

如果此代码段以“ and”开头，则只会匹配给定的输入。但是，“ and”属于非捕获组，不会输出到AST节点。然后，它匹配“ this”的重复或“ that”的重复。否定的前瞻性组将确保，如果任何重复序列同时包含“ this”和“ that”，我们就不必不必要地开始解析整个字符串。

鉴于这与正则表达式的行为非常相似并且非常简洁，这使我非常乐观，因为这将是可用的语法和API。

上面的代码段中显示的匹配器较长语法的图。

最后，工作的最后一部分是编写Babel插件代码，该代码将提取所有已编写的语法并将其替换为解析代码。虽然自己编写Babel代码并不难，但由于我之前有编写Babel插件的经验，因为目标之一是为DSL生成小型快速代码，确定应证明生成的解析代码的模式有些棘手。我很早就决定生成尽可能紧凑的代码，这对我来说意味着match的每次使用都应编译为一个函数。

解析语法中有很多地方匹配的一部分可能不成功，并且会跳转到另一部分-主要是由于组周围的交替。这意味着可能会有链式插值，生成的函数将开始匹配，并且在失败之后，可能会在交替后跳到语法的下一部分时放弃。

例如，给定上述代码，语法可能先匹配1，然后重复2。但是，如果在第一部分的任何一点上该语法与输入字符串不匹配，则该函数仍需要尝试匹配3。它需要skipto | $ {3}，并确保丢弃先前尝试失败的结果。

在研究该问题的一些潜在模式时，我发现似乎只有一个解决方案可以在单个函数中拥有如此多的控制权，而该解决方案（我认为）是JavaScript中的一种古老的语言功能：Labeled Block Statements。

我们可能不会在手写JavaScript代码中经常看到此功能，但是可以使用标签对anyloop或block进行注释。一旦有了标签，我们可以通过调用break突破它。

loop1：for（令i = 0; i <3; i ++）{loop2：for（令j = 0; j <3; j ++）{if（i === 1 && j === 1）中断loop1; }}

这对于试图在其代码输出中避免附加功能的生成代码非常有用。但是，如果您在代码中使用标签，则审阅者可能会感到困惑甚至抱怨甚至惊叹。 M正如MDN所说，他们对带标签的陈述的解释是：

缩环或块很少见。通常，可以使用函数调用来代替循环跳转。”

我写的Babel代码在这一点上并不令人惊讶-尽管它最终变得一团糟-并将语法的每个部分拆分为一个单独的“节点类”，专门用于接受已解析的元DSL的一部分并输出生成的代码只为这部分语法。某些类别的节点为QuantifierNode，AlternationNode或GroupNode。

先前示例的结果输出如下所示。我已注释并修改了代码段，以使其更易于阅读：

//一个辅助函数，用于执行粘性正则表达式并从“ reghex”返回匹配的字符串import {_exec}； const parser = function _parsed（state）{//这将创建AST节点，该节点是带有标签的数组const node = [];节点。 tag =“已解析”；让last_index = state。指标;让比赛; //这个“ block_0”包含我们语法的第一组block_0：{var index_0 = state。指标; var length_0 =节点。长度 ; // //如果（match = _exec（state，/ 1 / y））{node，我们首先尝试匹配“ 1”。推（比赛）; } else {//如果失败，我们将按原样还原该节点，然后脱离“ block_0” node。长度= length_0;状态。索引=索引_0;打破block_0; } //然后，我们尝试反复匹配loop_1的“ 2”：for（var i = 0; true; i ++）{var index_1 = state。指标; // //注意，即使（match = _exec（state，/ 2 / y））{node，即使在循环中，匹配本身也是一样。推（比赛）; } else {//如果我们有结果，我们就很好，如果（iter_1）{state，可以结束循环。 index = index_1;中断loop_1; } //如果没有，则再次还原该节点，然后脱离“ block_0”节点。长度= length_0;状态。索引=索引_0;打破block_0; }} //如果到达此处，则第一个组匹配。成功！返回节点; } //这是语法的第二部分，如果（match = _exec（state，/ 3 / y））{node，我们尝试匹配“ 3”。推（比赛）; } else {//自从语法结束以来，已经一无所有// //从匹配器运行并返回state之前恢复索引。索引= last_index;回报; } //我们匹配了“ 3”。成功！返回节点; };

通常，RegHex生成的每个序列都遵循以下相同的模式：建立一个块，向其添加先验索引和节点长度，然后递归地添加其余语法。它会将break语句传递到较低的节点，这些较低的节点可用于中断一个块。

如果您在代码中使用带标签的语句，则审阅者可能只是抱怨者中的任何一个甚至会感到困惑。 🤷

这里最棘手的部分是甚至阅读生成器输出的代码，因为它对人类不是很可读。但是，我认为这是可以根据要求生成的最紧凑的代码-Google的ClosureCompiler（一种优化的JavaScript编译器）也同意！当将某些函数内联到循环中时，Closure Compiler实际上也会输出标记的语句块。实际上，当我尝试使用内联函数手动编码上面的示例时，Closure Compiler将它们转换回带有标签的语句。

从实现的角度来看，我对结果感到非常满意。我最终使用的API在一个项目中都使用了许多不同的想法和语言功能，这是一次有益的学习体验和练习。如果您到目前为止已读过这篇文章，则已经涵盖了四个主题：

为了使RegHex步入正轨，我为GraphQL查询语言生成了一个解析器，该解析器已发布为graphql-parse。语法结束时长约300行，并且考虑到生成的实现确实非常紧凑，因此编译后的输出仅约2.6kB（最小化并压缩）。

因为它看起来不错并且很合适。一个图像中的graphql-parse捆绑包。好的，老笑话要感谢Jason Miller。

运行一些基准测试表明，可能是由于JavaScript中的正则表达式具有不小的开销，但是，此解析器的性能仅是参考实现的三分之一。话虽这么说，这比我预期的要好一些，因为RegHex仍然是原型制作和创建相当小的解析器实现的好工具，而开发人员的工作量很小。

值得注意的是，RegHex还可以支持解析整个带标签的模板文字，这将进一步提高元性水平，因为它允许RegHex生成自己的DSL分析器，这使其具有某种自我托管分析器的能力。

RegHex也不能很好地支持错误，因为它无法将尼斯栈展开到最终导致解析失败的地方，这意味着它可能根本无法提供任何提示。添加此功能可能是对在构建工具或服务器端代码中使用其生成的解析器的一项重大改进。

但是，考虑到RegHex的代码库涉及多少个概念，尽管存在当前的缺陷，但仍值得从事此概念验证工作。如果您想进一步了解RegHex，请查看代码！