多机解析 #2：文献综述

引言

本系列上一篇文章介绍了在一个解析器中使用多种解析方法的理由，列举了其他情况下会出现的许多问题（尤其是在使用解析器生成器时）。这些问题包括

1. 无法识别期望的本质歧义
2. 产生非本质歧义
3. 解析器体积过大
4. 解析器性能不佳

本系列文章的这一部分简要回顾了关于多机解析主题的一些文献，探讨了历史上提出的三种著名解析器类型的组合。

虽然本文最初可能不完整，但它非常希望将来能够做到这一点，因此欢迎提供关于遗漏工作的评论。

需要指出的是，几乎从定义上讲，*并行解析*本质上就是在一个解析器中使用多个解析机，或者至少在多个上下文中（伪）同时使用一个机器。然而，其动机却大不相同，因此我们将不详细介绍。我们只是注意到，具有异构代理的*进程配置解析器*可以实现与我们希望通过多机解析达到的行为相似的功能，尽管在撰写本文时，我不知道有任何这样的尝试。

综述

LR-LR 解析：Korenjak 方法

也许处理 LR(k) 解析器庞大体积（参见问题 #3）的第一个成功尝试是 Korenjak 方法，该方法将源文法分割成多个部分。 引用作者的话：

引用

该过程涉及将给定文法划分为多个较小的部分。如果可以为每个部分构造一个 LR(k) 处理器（使用 Knuth 算法），并且这些单独的处理器之间存在某些条件，那么就可以为整个文法构造一个 LR(k) 处理器。

生成的 LR(k) 解析表组合比整个文法的单个大表要小得多，有效地解决了这个功能强大的算法的主要限制。

Korenjak 方法最终似乎没有被采纳。在 Grune 和 Jacobs 所著的《解析技术》一书中，该书可被视为“濒危解析器的保留地”（非常值得一读！），作者们总结道：

引用

考虑到增加的复杂性，这[Korenjak 方法] 有所帮助，但帮助不大。

尽管如此，Korenjak 1969 年的论文仍然是一个重要的里程碑，因为它似乎是第一个被记录下来的尝试，通过涉及使用多个独立解析器的方式来修改解析器生成算法。

LL-FA 解析

PCCTS、Astir 和直到使用 LL(*) 解析策略的版本都ANTLR 最初都是为了生成“实用”的 LL/LR 解析器而设计的。这些解析器生成器使用的许多优化都可以被广泛地归类为“分区 LL/LR 解析”，但它们的介绍（可在此处 处 和此处 处 获取）却截然不同。

本质上，LL(k) 解析器可以与有限自动机（有限状态机）结合，生成一个能够在线性时间内处理某些类型 LL-正则文法的解析器。LL-正则文法的类别比 LL(k) 文法的类别大得多，因此这种解析自然受到关注（与问题 #2 相关）。

主要缺点是，识别 LL-正则文法的正则分区至少与Post 对应问题一样困难，而 Post 对应问题本身是棘手的。因此，LL 解析器与有限自动机的组合只能在正则分区易于识别文法的情况下构建。

LL(*) 解析通过在情况不顺利时回溯来解决这个问题，认为这种回溯在实践中很少见，并且很少导致最坏情况下的指数级运行时。

Astir 的 LL(finite) 解析将此责任推给了解析器设计者。Astir 的文法规范语言（截至 v1.0）不实现默认但可能次优的行为，而是允许将源文法分成部分，并附加指定哪些部分应由有限自动机处理，哪些部分由 LL 解析器处理。

LL-LR 解析

LL-LR 解析（最初命名为“LLLR”）的形成是基于这样一个认识：尽管 LL(k) 自顶向下解析器通常体积小且易于编写或设计，但 LL(k) 文法的强大程度远不及它们的 LR(k) 对等项。从介绍该方法的论文的摘要来看：

引用

LLLR 解析器使用 LL 解析器作为其骨干，并尽可能多地使用 LL 解析来解析输入字符串。为了解决 LL 冲突，它会触发小的嵌入式 LR 解析器。嵌入式 LR 解析器开始解析剩余输入，一旦 LL 冲突得到解决，LR 解析器就会生成它刚刚解析的子字符串的左解析，并将控制权交还给骨干 LL 解析器。

进一步

LLLR(k) 解析器适用于 LL(k) 冲突的非终结符出现在推导树的较低层或生成短子字符串的文法。在这种情况下，LLLR 解析器可以比 LR 解析器提供更好的错误恢复，因为大部分输入字符串都是由骨干 LL 解析器解析的。

LL-LR 解析在通过使用另一种解析器类型（即与主要的“骨干”LL(k) 解析器不同）来解决冲突方面，与 LL-FA 解析相似。在这方面，生成 LL-LR 解析器的假设性解析器生成器将与 ANTLR 相似，因为它在识别到冲突时会选择默认的、更复杂的行为。但与 Astir 一样，这样的解析器生成器不会允许输出解析器回溯。

要点

生成多个独立解析器以就单个源文法进行通信的想法至少可以追溯到 1969 年。

三种最熟悉的解析器类型，即有限自动机、LL(k) 解析器和 LR(k) 解析器，都被提议以其默认形式组合使用，以产生比单个解析器更强大或更高效的解析器。

在所有提出的方法中，只有 LL-FA 组合被用于解析器生成器（PCCTS、Astir、ANTLR），并且用于将可以生成解析器的文法类别扩展到 LL(k) 文法的严格超集。在本系列的下一篇文章中，我们将探讨解决 LL(k) 冲突（作为问题 #2 的表现）的具体问题，并展示 LL-FA 解析器组合在该上下文中的应用。

历史

• 2021年1月10日：初始版本