65.9K
CodeProject 正在变化。 阅读更多。
Home

多机解析 #1：简介

Peter Belcak
starIconstarIconstarIconstarIconstarIcon

5.00/5 (3投票s)

2021年1月10日

CPOL

8分钟阅读

viewsIcon

4243

提出一种从多个部分构建通用解析器的方案

动机

在为新语言（或现有语言）构建解析器时，人们通常面临两种标准选择：

  • 使用解析器生成器（Wikipedia 谦虚地列出了约80种），这涉及将语言的语法输入生成器，并在另一端获得一个即用型解析器；以及
  • 从头开始完全自己编写解析器。

无论做出何种选择，人们很可能最终会使用一种标准的解析算法，例如LALR/GLR（与Bison一起使用），或者在从头开始编写解析器时，大部分情况使用递归下降LL(k)/LL-regular解析。

这会导致问题，而这种“一种算法适用于我的所有语法”的方法是高效解析仍然是一个难题的主要原因之一，尽管在它的黄金时代过去约50年后，尽管已经发明了大量的解析算法和生成器。

我们可以将使用单个解析器生成器所引起的大多数问题粗略地分为四类：

  1. 对期望的本质歧义的盲目性
  2. 产生非本质歧义
  3. 解析器规模过大
  4. 解析器性能不佳

在本文的其余部分，我们将逐一讨论这些问题，并在适当的地方给出示例，并暗示多机解析器将如何解决仅限于单一解析算法所带来的问题，并概括解决方案。本系列后续文章将详细介绍这些问题的解决方案。

存在的问题

问题 #1：对期望的本质歧义的盲目性

编程语言的语法可能会遇到“构造性同形异义”：我们构建了我们认为最简单的语法来捕捉语言的结构，然后发现存在一个输入，它可以被理解为多种方式（即，对于相同的终端字符串可以构造多个等效的解析树）。

对于某些（罕见的）语言来说，这是一种特性，因为这种“本质歧义”（即，它是语法的属性，而不是所用解析方法本身的属性）可能反映了存在语义歧义的潜在现实。借用Chomsky 1956年的开创性论文中的一个例子，语法...

Sentence -> NounPhrase VerbPhrase

VerbPhrase -> Verb NounPhrase
Verb -> are flying
Verb -> are

NounPhrase -> they
NounPhrase -> flying planes
NounPhrase -> planes

...可能包含

引用

他们正在驾驶飞机

...两种方式：

  • “他们”——地平线上的那些点——“是”——存在作为——“正在飞行的飞机”——正在飞行的交通工具，以及
  • “他们”——飞行员——“正在驾驶”——控制飞行——“飞机”——飞行交通工具。

示例的语义含义仅用于说明，这里重要的区别在于输入字符串的语法理解方式。

在这种情况下，识别这两种替代方案，然后让解析之后的语义分析阶段根据上下文决定意图，可能是可取的。

虽然有一些算法可以相当有效地找到一种语法对输入的任何可能理解方式（Earley, 1970；Hext and Roberts 1970），但对于普通语法，它们的解析内部结构会变得非常庞大，而且对于解析现代通用的编程语言来说，它们通常太慢而无法部署，并且难以找到能够生成它们的生成器。目前，它们更像是解析技术博物馆中的古董花瓶，而不是编译器设计者用于处理手头更特殊任务的可靠工具。

因此，我们得出了这个问题：任何常见、易于理解的标准算法很可能对本身期望的或甚至是语言特性的歧义视而不见；但正是因为我们习惯于使用单一解析算法，迫使我们在语法分析层面剥离语言中的所有非确定性。一个实际的例子来自C++：`typename`关键字的使用。

多机解决方案

将包含期望的本质歧义的部分语法隔离出来。如果您自己设计语言，您可能会有意使用这种歧义实例，但要保持其规模较小。

一旦您隔离了语法的关键部分，就使用一种能够很好地处理歧义的算法（参见上面链接的参考文献）来处理它，并对语法的其余部分使用一种高效的确定性方法。

问题 #2：产生非本质歧义

这是迄今为止最常见的问题。假设您选择使用解析算法 `A`。由于没有真正通用的高效解析算法，总会存在一个细节，如果引入它，就无法构造类型为 `A` 的解析器。

对于典型的LL(k)解析器，这种细节在于有两个产生式，它们仅在尾部有所不同，且从它们的开始处由任意长度的非终结符分隔。对于典型的LR(k)解析器，这种细节是语法中任何导致移入/归约冲突或归约/归约冲突的调整——对于LR(k)解析的通用性较差的变体（如SLR或LALR），违反所选解析方法的约束更容易。

这里的要点是：*选择一种解析方法会迫使您将语法适应于该方法的约束。*

我们将通过一个具体例子来演示这一点。考虑以下代码片段，用一种为仓库排序机器人配置设计的语言编写：

node Sorter : OutputTrackSolids OutputTrackLiquids {
    use input InputTrackA;
    // the description of the sorting process
}

使用类Bison的上下文无关语法（CFG）捕获，该语言的语法骨架可描述为：

NodeDefinition = KW_NODE IDENTIFIER OP_COLON NodeOutputList OP_LCURLY NodeBody OP_RCURLY;

NodeOutputList = IDENTIFIER NodeOutputList | /* empty */;
...

语法其余部分可以（很好地）设计成LL(k)的，并且可以使用教科书上的技术构建解析器。

假设正在准备一种新版本的语言，其中任何排序器都可以有任意数量的输入通道——这使得以下内容变得可取：

node Sorter : OutputTrackSolids OutputTrackLiquids with inputs TrackA TrackB {
    // the description of the multi-track sorting process
    // the `use input` directive is prohibited; inputs have already been specified
}

同样，这种结构可以被一个实际上是LL(k)的语法捕获，包含以下内容：

NewNodeDefinition = KW_NODE IDENTIFIER OP_COLON NodeOutputList KW_WITH_INPUTS NodeInputList
...

再假设，任何用于这种新语言的解析器都必须向后兼容，即第一段代码也要被正确识别。**没有**典型的LL(k)解析器，甚至一个LL(有限)解析器也无法成功地区分非终结符`NodeDefinition`和`NewNodeDefinition`，因为任何固定的前瞻量都无法穿过任意长度的非终结符`NodeOutputList`。有几种方法可以解决这个问题，但每种方法都涉及某种“技巧”（例如，使用谓词）或对语法进行其他调整。

同样，这里的重点是：

引用

...通过选择使用单一解析方法，您被剥夺了使用*您*希望使用的语法，并因此设计*您*想要设计的语言的自由。

多机解决方案

巧妙地结合多种类型的解析器可以消除这个问题。对于上面给出的例子，一个使用专用有限自动机来扫描`NodeOutputList`以区分`NodeDefinition`和`NewNodeDefinition`的LL(k)解析器将起作用，即使具有线性时间复杂度。本系列稍后将更详细地阐述这个例子。

问题 #3：解析器规模过大

解析器占用的空间与其底层语法的大小成正比。此外，作为一个经验法则，解析方法`M`可以处理的语法越丰富，`M`-解析器就越大。

使用单一解析方法在此引入的问题是，语法的最复杂部分决定了整个解析器的解析方法。

例如，考虑为一种支持 usual C-like 算术表达式的语言编写解析器，例如，通过实现以下小型子语法的解析例程：

Expression -> Expression - Term
Expression -> Expression + Term
Expression -> Term

Term -> NUMBER /* a number constant */
Term -> IDENTIFIER /* a variable name */
Term -> '(' Expression ')'

该语言其余部分的解析器可能可以用简单的LL(1)解析器实现，但仅算术表达式的存在就迫使您使用一种不同的解析方法，一种可能产生更大解析器的解析方法。

多机解决方案

隔离语法中最复杂的部分，使用复杂机器处理它，然后将该机器附加到一个处理语法其余部分的简单超级解析器上。

在上面的例子中，算术表达式的语法可以被隔离出来，并可以使用算符优先级或LR(1)解析器来解析它。我们语法的其余部分可以采用不同的方式处理，并且仅在需要时调用OP/LR(1)解析器。

问题 #4：解析器性能不佳

设计用于处理更复杂语法的解析方法通常在一个类型的语法上是相当高效的，而在某些特定类型的语法结构上则效率稍低。

一个人为但真实的例子是ANTLR生成的LL(*)解析器，用于以下语法：

A = a* b* B;
B = a b+ c;

...处理形如 anbmc 的字符串，其中 n 为非负数，m 为正数。这个例子模仿了某些斯拉夫语中形容词和两个名词之间没有歧义的竞争，并将触发解析器最坏情况下的指数时间解析行为。然而，根据LL-regular语法的理论，我们确信存在线性时间解析器——如果我们能将这样的解析器用于语法的这一部分，并将LL(*)解析器用于其他所有部分。

多机解决方案

了解主要解析机器选择的局限性，找出触发性能不佳的语法部分。对于这些部分，可以使用专用解析机器，而主解析机器可以处理语法的整体骨架。

要点

仅选择使用一种解析算法，尤其是在使用解析器生成器时，通常会对被解析语言的设计产生重大影响。

通过了解各种解析方法的优缺点并将其结合到单个解析器中，可以改变局面。

虽然当编译器由程序员从头开始编写时，组合各种解析方法是相当常见的，但当使用解析器生成器时，这种情况很少见。在本系列第二部分中，我们将回顾关于该主题的现有文献，并探讨诸如Bison、Yacc、Astir或ANTLR等解析器生成器如何处理多机解析器生成，如果处理的话。

历史

  • 2021年1月10日：初版
  • 2021年1月10日：添加系列缩略图
  • 2021年1月11日：在问题 #1 的“他们正在驾驶飞机”示例中增加了进一步的澄清
© . All rights reserved.