javascript 算法库（JISET:基于IR的）

javascript 算法库（JISET:基于IR的）为了缓解这一问题，我们提出了一种直接从 ECMAScript 自动合成解析器和 AST-IR 翻译器的技术。在合成解析器和翻译器时存在一些技术挑战。在语法方面，ECMAScript 利用了它自己的 EBNF 变体，具有参数非终结符、条件替代符和各种特殊的终结符。因此，现有的解析器生成技术并不直接适用于此变体。此外，JavaScript 在它的解析算法中提供了一些复杂的规则，而不是在词法分析器中自动插入分号。对于语义，ECMAScript 中的抽象算法是用英语编写的。此外，抽象算法的通用和前向兼容表示对于支持 ECMAScript 的未来版本是必要的。据我们所知，所有现有的基于 JavaScript-IR 的语义提取方法都手动构建了解析器和翻译器。在 ECMAScript 5.1 (ES5.1 2011)之前，手动构建它们是合理的，但这无法处理自 ECMAScript 6 (ES6 20

摘要

由于 JavaScript 的语义非常复杂，理解和推理 JavaScript 程序是一项具有挑战性的任务。因此，研究者们提出了几种基于 ECMAScript (JavaScript 的官方规范)定义 JavaScript 的正式语义的方法。然而，现有的方法语义都以 ECMAScript 5.1 (ES5.1 2011)或其以前的版本为目标。因此，它们不适合理解 ECMAScript 6 (ES6 2015)以来引入的现代 JavaScript 语言特性。

为了解决这个问题，我们提出了 JISET，一种基于 JavaScript 的 IR 语义抽取工具链。在语法方面，我们为 BNFES 开发了一种具有前瞻性的解析器生成技术。在语义方面，JISET 使用前向兼容的基于规则的编译来合成 AST-IR 翻译器。编译规则描述了如何将用结构化自然语言编写的抽象算法的每个步骤转换为 IRES IRES 是我们为 ECMAScript 设计的中间表示。对于最近的四个 ECMAScript 版本，JISET 自动为所有版本合成解析器，平均编译了 95.03%的算法步骤。在我们手动完成缺失的部分之后，最新的 ECMAScript (ES10 2019)提取的核心语义通过了所有 18064 个适用测试。

1 介绍

JavaScript 是最广泛使用的编程语言之一，不仅用于客户端，也用于服务器端编程，甚至用于小型嵌入式系统。但其复杂的语义常常给开发人员带来困扰。为了正确地理解和推理 JavaScript 复杂的行为，定义其形式语义是必要的。

定义语言形式语义的传统方法是基于 IR 的语义提取。其具体做法是构建一个编译器前端，该编译器接收程序并产生它们的中间表示(IRs)来间接表示给定程序的语义。如图 1 所示，编译器前端由一个构造给定 JavaScript 程序的抽象语法树(ast)的解析器和一个将 ast 转换为自己的 IRs 的 AST-IR 翻译器组成。

图 1:现有的方法:为 JavaScript 基于 ir 的语义关键字手动构建解析器和 AST-IR 翻译器

据我们所知，所有现有的基于 JavaScript-IR 的语义提取方法都手动构建了解析器和翻译器。在 ECMAScript 5.1 (ES5.1 2011)之前，手动构建它们是合理的，但这无法处理自 ECMAScript 6 (ES6 2015)以来的现代 JavaScript。ES6 引入了许多重要的新功能，如通过 let 的词法绑定、操作符、类、for-of 操作符、异步函数和生成器。因此，手动方法似乎没有足够的可伸缩性来为现代 JavaScript 构建 AST-IR 翻译程序，而且实际上也不存在用于 ES6 到 ES10 的正式语义。

为了缓解这一问题，我们提出了一种直接从 ECMAScript 自动合成解析器和 AST-IR 翻译器的技术。在合成解析器和翻译器时存在一些技术挑战。在语法方面，ECMAScript 利用了它自己的 EBNF 变体，具有参数非终结符、条件替代符和各种特殊的终结符。因此，现有的解析器生成技术并不直接适用于此变体。此外，JavaScript 在它的解析算法中提供了一些复杂的规则，而不是在词法分析器中自动插入分号。对于语义，ECMAScript 中的抽象算法是用英语编写的。此外，抽象算法的通用和前向兼容表示对于支持 ECMAScript 的未来版本是必要的。

2 概述

在本节中，我们将介绍图 2 中描述的 JISET 的总体结构。与图 1 所示的现有方法相比，我们的工具直接从 ECMAScript 自动合成 JavaScript 解析器和 AST-IRES Translator。这项工作的动机有两个:1)ECMAScript 以一种组织良好的风格编写，2)自 2016 年 ES7 以来的写作风格是聚合的。

图 2:JISET 的整体结构:自动合成基于 JavaScript ir 语义的 JavaScript 解析器和 AST-IRES Translator

语法：ECMAScript 在附录 A 中使用 EBNF 变体提供了词法和语法图。我们将其命名为 BNFES，并在第 3 节中正式定义。我们的 Spec Extractor 读取 BNFES 中编写的语法，并将它们转换成 JSON 文件。

为了从给定的 BNFES 语法中生成 JavaScript 解析器，我们在 Scala 中构造了解析器生成器。它根据给定的 BNFES 合成一个 JavaScript 解析器，生成的解析器用 Scala 解析器组合子定义。此外，为了正确和有效地解析 BNFES 语法，我们提出了前向解析器，它可以跟踪程序中可能的下一个标记集。使用前向解析，生成的解析器现在可以一对一地映射到相应的语法结果，从而提高了可读性。

语义：ECMAScript 将语言语义描述为英语中的抽象算法。虽然它们是用自然语言编写的，但是编写风格是由有序的步骤和标记标记的。Spec Extractor 读取带有 HTML 标签的抽象算法，并将其转换为 JSON 文件。

为了将这种抽象算法转换为适合操作的表示，我们定义了 IRES，这是 ECMAScript 的一种专门的中间表示。然后在 Scala 中开发算法编译器，再次使用 Scala 解析器组合子将给定的抽象算法转换为 IRES 函数。它还将 Compile Rules 作为另一个输入，该输入包含两个部分:解析规则和转换规则。它们是为 ECMAScript 手动指定的;我们将在第 4 节详细解释它们。因此，每个抽象算法通过算法编译器转换为 IRES 编写的函数。

最后，JISET 使用给定的 IRES 函数和手动指定的全局设置构造 AST-IRES Translator，其中包含一些次要但必要的信息来评估 ECMAScript 中描述的 JavaScript 程序，比如标准内置对象的结构和 ECMAScript 数据类型。把它们放在一起，我们可以通过 JISET 生成的 JavaScript 解析器和 AST-IRES 翻译器将给定的 JavaScript 程序翻译成 IRES。尽管由于编译规则和全局设置，JISET 不是完全自动的，但它可以大大减少从头构建解析器和翻译器的工作。

在本文的其余部分，我们将详细解释如何自动生成解析器(第 3 节)和如何编译抽象算法(第 4 节)。在评估 JISET(第 5 节)之后，我们将讨论相关工作(第 6 节)，并总结(第 7 节)。

3 解析器生成器

在本节中，我们将解释如何从给定的 ECMAScript 自动生成 JavaScript 解析器。

3.1 BNFES: ECMAScript 语法

ECMAScript 使用扩展 BNF 的一个变体来描述 JavaScript 语法。我们正式定义了这种符号，并称之为 BNFES。它由以下形式的若干成分组成：

“::=”的左边表示一个参数非终结符 a，它带有多个布尔参数 p1… pk。如果非终结符没有参数，则为简洁省略括号。一个成分有多个以“|”隔开的可选的条件。条件 c 要么是布尔形参 p，要么是它的否定!p。备选 α 是一个符号序列，其中符号 s 是下列之一:

l є:空序列，不带任何条件地通过；

l a:一个终结符，可以是任意字符。

l A(a1 · · · ak ) :一个非终结符，它接受多个参数，其中每个参数 ai 要么是布尔值#t 或#f，要么是参数 pi；

l s?:选择，和 s | ε 的效果一样；

l • s(−s):有效（无效）前向查看，检查 s 是否成功(失败)，并且从不依赖任何输入

l s\s’: 排除，它首先检查 s 是否成功，然后检查解析结果是否不对应于 s’；

l <¬LT> :没有行终止符，这是一个特殊的符号用来限制两个不同符号之间的空白。

3.2 超前解析

为了正确地支持 BNFES，我们使用超前解析扩展了基于 PEG 的解析器生成技术。

大多数解析器生成器以上下文无关语言为目标，使用特定的解析算法进行上下文无关语法(CFG): JavaCC 带有 LL(k)， Bison 带有 GLR， ANTLR 带有 ALL(*)。然而，它们并不直接适用于 ECMAScript 语法，因为 ECMAScript 的词法和语法语法需要上下文敏感的词法分析器和解析器。

与基于 cfg 的解析器生成器不同，基于解析表达式语法(PEG)的解析器生成器可以轻松地解决这些问题。peg 是用具有回溯功能的自顶向下(LL-style)递归下降解析器定义的。它按顺序访问产品的每个备选方案，并在解析失败时回溯到之前的产品。基于 peg 的解析器生成器将词法分析器视为解析器，因此我们可以根据解析上下文使用适当的词法分析器。

虽然基于 peg 的解析器生成器支持上下文敏感性，但 peg 与 BNFES 有一个根本区别:优先选择。peg 在 BNFES 中使用优先级选择操作符' / '，而不是无序管道操作符' | ';即使有多个可选方案，peg 也总是选择第一个成功的方案。

解决方案:使用前瞻的令牌。为了解决这个问题，我们提出了前瞻解析，这是一种针对带前向标记的 peg 的扩展解析算法。前瞻解析的关键思想是通过使用图 3 中的算法静态计算每个符号的第一组标记来跟踪下一个可能的标记。

图 3:BNFES 符号中第一个令牌的近似

我们在图 4 中正式定义了前瞻解析器的语义。辅助函数 gets (L)通过使用优先级选择组合前向 L 中的所有标记来生成解析器。在本例中，顺序不会改变前移解析器的语义，因为 gets (L)只是检查给定标记的存在性。

图 4:前瞻解析器的正式语义

3.3 实现

我们通过扩展 Scala 解析器组合符库实现了前瞻解析技术，该库是一个用于基于 peg 的解析器生成的 Scala 库。我们开发了解析器生成器来合成基于 peg 的解析器和 BNFES 的前向解析。

AST生成：解析器生成器首先从给定的 BNFES 语法自动将 AST 合成为 Scala 类。因为词法结果的结构不影响 ECMAScript 语义，所以我们将词法非终结符表示为字符串值。对于每个句法产生 A(p1，…，pk)::=(c1 ⇒)?α1|···| (cn ⇒)?αn，生成器合成一个特征 A 以及它的多个子类 Ai(0≤i≤n−1)，子类用来表示它的备选项。每个类 Ai 在其对应的备选项中都有非终结符作为其字段。

解析器生成：下一步是为 BNFES 中的每个产品自动合成- size 解析器。我们扩展了 Scala 解析器组合符，以支持前瞻性解析和 BNFES 符号。由于回溯，前瞻性解析将花费指数级的时间。为了将其缩短到线性时间，我们应用了 Packrat 解析时引入的记忆技术。此外，我们还实现了 Warth 等人提出的生长种子技术，以支持直接甚至间接的左递归结果。它可以在不改变 BNFES 中每个产物结构的情况下合成解析器。

合成解析器还支持自动分号插入算法，这是 ECMAScript 中最独特的解析特性之一。我们扩展了解析算法，以跟踪在给定输入中无法解析的最右侧位置。在 ECMAScript 中，该位置的令牌被定义为违规令牌，自动分号插入算法就是用这样的令牌定义的。

4 算法编译器

在本节中，我们将解释将抽象算法编译到 IRES 函数的算法编译器，如图 5 所示。

图 5 算法编译器总体结构

4.1 分词器

在编译抽象算法之前，分词器首先将每个抽象算法标记为一个标记令牌列表。算法由有序的步骤组成，步骤也可以包含子步骤。随后，分词器将结构化步骤简化为单个标记列表，以便轻松处理多步骤语句。抽象算法中的一些语句包含多个步骤。例如，if - then- else 语句通常由两个步骤组成:一个步骤表示 then 分支，另一个步骤表示 else 分支。为了将他们表示为线性结构，我们引入三个特殊标记来分解结构化算法:↓ 表示单个步骤的结束，↘ 和 ↙ 表示嵌套步骤的开始和结束。

在对抽象算法进行标记化后，算法编译器使用标记列表解析器和标记 AST 转换器将标记列表编译成 IRES 函数。它们依赖于编译规则，每个编译规则由解析规则和转换规则组成。对于每个编译规则，其解析规则描述了如何将给定的令牌列表解析为结构化的令牌 AST，其转换规则描述了如何将给定的令牌 AST 结构转换为 IRES 组件。现在，我们将分别用解析规则和转换规则解释令牌列表解析器和令牌 AST 转换器。

4.2 标记列表解析器

标记列表解析器是用解析规则定义的。解析规则是一个基本的解析规则或多个解析规则的组合。两个解析规则 A 和 B 的组合 A | B 使用这两个规则解析输入，并收集最长匹配的结果。如果两个规则都失败或匹配相同长度的输入，组合失败。

我们提供两种基本解析规则:基于标记的规则和基于内容的规则。基于标记的规则只是检查下一个标记是否具有给定标记。例如，基于标记的解析器 varT 和 codeT 检查下一个标记是否分别具有<var>和<code>。基于内容的解析器检查下一个标记是否为文本标记，其内容是否传递给定的条件。例如，字符串字面量“Perform”表示基于内容的解析器，它检查下一个标记是否为内容 Perform 的文本标记。我们还定义了两个基于内容的解析器单词和数字，分别检查下一个令牌的内容是只包含字母还是数字。

4.3 Token AST 转换器

转换规则描述了如何为给定的令牌 AST 生成 IRES 函数，每个转换规则都定义了相应的解析规则。对于基本解析规则，它们的转换规则总是返回已解析标记中内容的字符串值。

我们将 IRES 定义为将抽象算法表示为函数，并定义了 IRES 的语法，它有 15 种指令和 26 种表达式，分别用符号 i 和 e 表示。为了简洁，我们在本文中省略了 IRES 的形式化，并将其包含在附带的报告中。

5 评价

我们开发开源工具 JISET，并基于以下研究问题对工具进行了评估:

•覆盖率:JISET 从 ES7 到 ES10 自动提取的语法和语义占多少百分比?

•正确性:JISET 是否正确地从 ECMAScript 提取了基于 IR 的正式语义?

•向前兼容性:JISET 对于 ES11 的新语法特性是否兼容？

我们在一台配备了 4.2GHz 四核英特尔酷睿 i7 和 64GB RAM 的机器上进行了实验。在机器上，JISET 花了不到一分钟的时间从给定的 ECMAScript 提取基于 IR 的语义。

5.1 覆盖率

我们从两个方面评估了 JISET 的覆盖率:语法和语义。对于语法，我们测量了 JISET 从规范中自动生成解析器的语法产生的数量;对于语义，我们测量了 JISET 从规范中自动生成 JavaScript 语义的抽象算法步骤的数量。

(a) 从 ES7 到 ES10 的每个 ECMAScript 版本

(b) 相邻版本之间的每次更新

图 6:语义覆盖:规范中算法步骤的数量，JISET 从中生成语义

对于语法，JISET 自动为所有词法和语法结果生成解析器。如表 1 所示，词法和句法产生的平均数量分别为 78.75 和 166.25。在相邻版本之间，每年平均更新的词汇和句法结果分别为 4.67 和 54.33。

表 1 语法覆盖率：在每个规范中以及在相邻版本之间的每次更新中，JISET 自动生成解析器的产品数

在语义方面，图 8 显示了 JISET 自动将算法步骤编译到对应的 IRES 指令，从 ES7 到 ES10 的每个 ECMAScript 版本的平均成功率为 95.03%，相邻版本之间的每次更新的成功率为 94.31%。

5.2 正确性

为了评估 JISET 的正确性，我们通过执行截至 2019 年 2 月 28 日的 Test262 测试了从最新的 ECMAScript (ES10)中提取的语义。为了关注 JavaScript 的核心语言语义，我们只完成了提取的 AST-IR 翻译器中缺少的必要部分。如图 8(a)所示，对于 ES10 中的抽象算法，10 101 步中有 9 627 步由算法编译器自动编译。它完全覆盖了 2026 种抽象算法中的 1783 种，部分覆盖 243 种算法。如表 4 所示。为了将重点放在 ES10 上，我们排除了 7 038 个附件、国际化和正在进行中的特性测试。我们还过滤了 10888 个使用次要语言特性的测试。最后，提取的语义花了大约三个小时评估 18064 个适用测试，并失败了 1709 个测试。

表 2 Test262 的测试结果

我们调查了失败的测试，发现它们失败是因为 ES10 中的规范错误。使用失败的测试，我们发现了 9 个错误:表 3 中的 ES10-1 到 ES10-9。其中有 5 个错误(ES10-5 ~ ES10-9)是之前在下一个 ECMAScript 的当前草案中报告并修正的，其余 4 个错误(ES10-1 ~ ES10-4)是之前从未报告过的。TC39 确认了所有四个错误，并将在下一个 ECMAScript ES11 中修复。

在解决了 ES10 中的 9 个规范错误之后，我们从修订后的规范中提取了一个语义。从修订的 ES10 中提取的语义通过了 Test262 中所有的 18064 个适用测试，这表明 JISET 正确地从 ECMAScript 中提取了基于 ir 的正式语义。此外，评估证明 JISET 可以有效地检测规范错误。我们不仅可以检测到 5 个已知错误，还可以检测到 4 个新的错误。我们相信 JISET 弥合了用自然语言编写的 ECMAScript 和 Test262 中可执行测试之间的差距。

5.3 向前兼容性

我们通过将 JISET 应用到准备包含在 ES11 中的提案中来评估它是否向前兼容。因为 ECMAScript 是一个开源项目，所以各种关于新特性的建议都有自己的规范变更和测试。一个单独的存储库分 6 个阶段来维护它们:阶段 0 到阶段 3。完成 不活跃。提案从阶段 0 开始，TC39 委员会审查阶段 3 的提案。如果提案得到确认，委员会将其阶段改为完成，并将其集成到下一个 ECMAScript 中。否则，它的阶段就会变成 Inactive。

表 3 将被包含在 ES11 中的提案

我们将 JISET 应用于所有 9 个 Finished 提案，如表 3 所示。这些建议总共修改了 8 个词法和 11 个语法结果，JISET 成功地为它们合成了解析器。综合解析器解析所有提案的所有适用测试。对于抽象算法，算法编译器将 595 步中的 560 步自动转换为对应的 IRES 指令，而不改变编译规则。因此，JISET 对于即将到来的提案的平均成功率为 94.12%。

在修复了提议中的错误之后，我们从修订后的规范中提取了一个语义。提取的语义通过了提案的所有 207 个适用测试和 ES10 的 18064 个适用测试。因此，JISET 还从未来的建议中正确地提取了基于 ir 的语义，这意味着它是向前兼容的。

7 结论

ECMAScript 的年度更新使得构建程序分析或形式的 JavaScript 验证变得困难，因为在建模移动目标时需要人力。在本文中，我们提出了 JISET 工具，能够自动从英语编写的 ECMAScript 中提取语法和语义，作为解析器和 AST-IR 翻译。该工具自动提取 ECMAScript 最近四个版本(ES7 到 ES10)的所有语法和 95.03%的语义。我们通过使用官方的一致性套件 Test262 测试从 ES10 中提取的语义来评估该工具的正确性。通过 1709 次失败的测试，我们发现了 9 个规格错误，其中 4 个是新发现的，并被 TC39 确认，计划集成到 ES11 中。在修复错误之后，提取的语义通过了 Test262 中的所有 18064 个适用测试。通过将 JISET 应用到将要包含在 ES11 中的 9 个提议，我们还展示了 JISET 是向前兼容的，这让我们在 BigInt 提议中发现了 3 个错误。我们相信 JISET 可以极大地减少正确构建各种 JavaScript 工具的人力工作。

致谢

本文由南京大学软件学院 2021 级硕士刘凡翻译转述。