编译器构造/编写可重用语法的秘诀

所以你需要编写一个语法。但你需要处理多个重要的实际问题

• 你需要你的解析器能够从你的语言中使用。
• 你可能还想从其他语言中重用它。
• 你使用的语言可能有一个非常不成熟的解析器生成器，很难用于任何复杂的事情
  • 它可能完全缺乏调试工具。
  • 它可能返回非常奇怪的错误消息，即使你的语法看起来正常。
  • 即使所有内容都编译得很好，生成的解析器也可能在运行时崩溃。
• 方便的解析器生成器生成的解析器可能非常慢。

所以我们来看看如何解决这些问题。解决这些问题的总体思路很简单

• 一步一步地做所有事情；
• 使用正确的工具。

1. 创建足够多的简单的你要解析的语言样本。

2. 看一看。问问自己你的语法必须是什么样的最小语法类。是否可以创建上下文无关语法？如果不是，是否可以将你的语法简化为上下文无关语法，在解析树构建完成后解决非上下文无关问题？

3. 选择你要的目标语言。在我的例子中是 Python。

4. 为它找到解析器生成器。对于每个生成器，获取以下已知信息

• 它可以生成的语法类；
• 它是分词器/无词法器还是带词法器的；
• 它是否支持模块化语法，每个子部分可以分别开发和测试；
• 调试和可视化工具的可用性
  • 如果解析器带词法器，应该可以解析前打印词法单元；
  • 跟踪器；
  • 树可视化器；
• 预创建语法的库的可用性；
• 良好的文档和示例的可用性；
• 它是否被编译成目标语言结构直接进行解析，还是被编译成一个由运行时解释的数据结构？
• 即使它被转换成代码，代码可能仍然使用一些运行时。使用的运行时的效率和依赖性是什么？
• 解析器生成器支持哪些其他编程语言？

5. 在互联网上搜索预创建语法。可能已经存在该语法，你只需要将其适应你的解析器生成器。

6. 选择你的初始解析器生成器。现在你需要在高层次上编写你的语法，并使其工作。我的意思是，你现在的主要目标是创建一个能够正确解析字符串的语法，而不是与生成器作斗争。

• 它应该是GLR。你可以降低类并优化后续部分。它可以让你免于解决冲突。
• 它应该是无词法器的。它可以让你免于为每个词法单元定义不同的字符类。
• 它必须有工具允许你跟踪它的执行。
• 它必须返回一个解析树，而不是使用语义动作构建它。语义动作是特定于语言的，它们的语法通常是特定于解析器的。在一些解析器生成器中，它们允许使用自己的代码进行消歧，但这并不是通用的，并且 API 使用高度依赖于解析器生成器。
• 它必须能够可视化解析树。
• 它必须支持命名词法单元和跳过不相关的词法单元。

我使用了 GLR 模式下的 parglare。parglare 有一个调试工具，允许我看到转换图及其中的路径，以及可能的路径以及错误发生的位置。

7. 选择其他解析器生成器。标准相同，但它们可能属于另一个类。你的最终目标是让你的语法与所有这些生成器兼容，并将生成的解析树包装在一个抽象层中，以便你的手写代码只处理抽象层。将解析器生成器更改为相同或更高类通常很简单：只需确定一个语法DSL 语法特征到另一个语法 DSL 语法特征的映射。

降级语法类可能需要更改解析器生成器和语法。保持所有不同生成器的语法同步非常重要，以便具有相同的结构。你的目标是为一个解析器生成器编写一个语法，使其能够自动转换为其他解析器生成器。保持同步可能意味着更高类甚至相同类的语法将变得不必要地更难看：不同的解析器生成器具有不同的语法糖，因此你必须使用公共子集。它变得有点难看并不重要。你可以在解析树解析完成后对其进行后处理，以使它更方便以后使用。重要的是，当你降级解析器时，你会提高

• 性能
• 错误消息的可解释性
• 增加可以使用你的语法的解析器生成器集合（可以在PEG 和LR(1) 解析器生成器中使用 LL(1) 语法，但不能在LL(1) 解析器生成器中使用LR(1) 语法，也不能在LR(1) 解析器生成器中使用GLR）。
  • 你增加了在进一步开发语法时可以使用调试工具的集合；
  • 你的语法变得有用，因为更多人可以在他们语言中可用的解析器生成器中重用它；
  • 你将语法限制为所有解析器生成器通用的功能，因此更容易移植。

幸运的是，我已经开发了一个名为UniGrammar 的工具。它具有以下功能

• 基于 YAML 的自己的格式（实际上，任何可以序列化任何可以序列化为 JSON 的对象的格式都可以使用），因此不需要语法进行解析和序列化；
• 它为其他 DSL 生成语法；
• 它还生成包装器（目前只在 python 中），将特定于解析器的解析树转换为我们自己的格式中的解析树，这些解析树旨在针对由同一 UniGrammar 语法生成的不同的解析器解析相同的文本时相同；
• 它提供统一的 CLI 来使用支持的解析器的任何子集测试语法；
• 它提供了一个库，可以使将第三方工具插入 UniGrammar 变得更容易；
• 它具有模块化架构，可以轻松地添加对解析器生成器的支持；
• 它有所谓的模板。这些是高级构造，转换成为低级语法块。例如，你可以指定你有一个项目列表，每个项目都使用一些（非）终结符指定，它们之间使用另一个（非）终结符指定分隔符，该工具将为其生成所需的规则，以及一个包装器，允许你将结果作为真正的 python 列表获取，因此你的代码不需要特殊对待第一个项目。

本文的其余部分侧重于使用该工具。

8. 编写一个高层次的GLR 语法。

• 解决生成器发出的所有错误和警告。
• 调试它。使用跟踪和解析树可视化。
  • 无论如何使它在最简单的例子上工作。
  • 然后使它在所有示例上工作。
  • 然后使它返回你想要的解析树，并包含所有示例。

9. 优化语法使其看起来干净。将词法单元与产生式分离。调试并测试它。

9. 使语法退化

• 如果分词器使用正则表达式，则用词法单元和产生式替换正则表达式。大多数生成器不支持正则表达式作为词法单元。这可能会降低性能（正则表达式在本地代码中执行，但解析器在 python 中执行），但这里通用性更有价值；
• 将组分离为单独的词法单元/产生式。理由：一些生成器没有它们；
• 将字符类与由它们组成的词法单元分离。理由：对于某些生成器（更准确地说，是 LL(1) 生成器），词法单元不能包含与其他词法单元中迭代的相同字符，否则它们无法进行消歧。因此，所有词法单元必须被划分为不同的字符类。曾经是一个词法单元现在将成为产生式中的多个词法单元。例如（在 parglare 语法中）

terminals
Something: /[^0-9]+/;
Name : /[a-zA-Z_0-9-]+/;

必须转换为

somethingSegment: NonDigitNonAlphaNum | Alpha;
nameSegment: Digit | Alpha;
name: nameSegment+;
something: somethingSegment+;

terminals
Alpha: /[a-zA-Z_-]/;
NonDigitNonAlphaNum: /[^0-9a-zA-Z_-]/;
Digit: /[0-9]/;

这将有利于转换为 LL。UniGrammar 必须生成 LL 语法，它在自己的语法中强制执行这种结构。（注意：这并不意味着你只能在 UniGrammar 中指定 LL 语法）。

• 将被捕获的内容分离到自己的产生式中。理由：一些解析器生成器没有捕获。因此，我们必须实现一个自己的代理：我们只是保存必须捕获的特定于解析器的 AST 节点名称的映射，并在后处理步骤中从它们中恢复捕获组。

在每一步后测试语法。

10. 将语法文件提交到存储库。

11. 将语法从特定于解析器生成器的 DSL 转换为 UniGrammar DSL。将语法编译到你的解析器生成器。将生成的文

13. 使用 UniGrammar test ... 测试你的语法。

12. 将语法降级为LR(1)（我使用了 LR 模式下的同一个 parglare），解决所有编译问题并再次调试和改进它。

12. 将语法移植到PEG。我使用了waxeye。它没有任何调试工具，但它是一个解释器，而且非常简单，我不得不将一些跟踪代码嵌入到它的 python 运行时中。调试，同步，修复代码测试。

13. 将语法降级为LL(*)。我使用了ANTLR，它有一个调试工具，允许我查看词法单元类型和匹配跟踪并检查解析树。

确保所有后端按预期工作，并修复它们和语法，直到所有内容都工作。

16. 将语法降级为LL(1)。这可能需要在编译时以相同方式进一步解决检测到的冲突（在编译时存在的某些冲突在LL(*)中并非冲突）。我使用了 -CoCoPy 的分支 - w:CoCo/R 的变体。它有非常奇怪的错误消息，几乎没有调试工具。我能够使这种语法在 CoCo/R 上工作的唯一原因是它与其他解析器生成器相似，因此将这种语法改编到它们会导致将这种语法改编到 CoCo/R。

17. 优化、重构、清理、测试所有内容。

18. 添加到语法库中，以便其他人可以使用它。