自下而上的分析者:什么时候应用哪种减少规则？

Question

让我们来看看以下上下文无关语法：

G = ( {Sum, Product, Number}, {decimal representations of numbers, +, *}, P, Sum)

为P：

Sum → Sum + Product
Sum → Product
Product → Product * Number
Product → Number
Number → decimal representation of a number

我试图用自下而上的解析器和长度为1的前瞻性缓冲区(实验室)来解析这种语法产生的表达式(这可能不需要猜测和回溯)。

现在，给定一个堆栈和一个实验室，通常有几种可能的方法来减少堆栈，或者是减少堆栈，还是推送另一个令牌。

目前，我使用此决策树：

如果堆栈的顶部n个令牌加上实验室是规则右侧的起点，那么我将下一个令牌推到堆栈上。 否则，我将减少堆栈顶部的最大令牌数。也就是说，如果有可能减少最上面的项目，同时也有可能减少三个最高的项目，我做的是后者。 如果不可能这样减少，我会将另一个令牌推到堆栈上。 冲洗并重复。

这个，看上去(!)要想工作，但是需要大量的规则搜索，找到匹配的前缀等等。这不可能在O(NM)中运行。

决定是减少还是推(移位)的标准(也可能是唯一明智的)方法是什么?在减少的情况下，采用哪种减少？

预先感谢您的评论和回答。

Answer 1

像您这样的语法(基本上是表达式语法)最简单的自下而上的解析方法是操作符优先解析。

回想一下，自下而上的解析涉及从下到右构建解析树。换句话说，在解析过程中的任何特定时间，我们都有一个部分组装的树，在读取的右侧只有终端符号，左边是终端和非终端的组合(“前缀”)。唯一可能的缩减是适用于前缀后缀的缩减；如果不应用缩减，则必须能够将终端从输入转移到前缀。

运算符语法的特点是在任何生产中从来没有两个连续的非终端。因此，在操作符语法的自下而上的解析中，前缀中的最后一个符号是一个终端，或者第二个-最后的符号是一个。(两者都有可能是。)

运算符优先解析器本质上是对非终端不透明的；它根本不区分它们。因此，不能有两个产品的右侧包含完全相同的终端序列，因为op-prec解析器不知道这两种产品中的哪一种。(这是传统观点。实际上可以将其扩展一点，这样您就可以使用相同的终端拥有两个产品，前提是非终端在不同的地方。例如，这允许具有一元-运算符的语法，因为右手边可以区分<non-terminal> - <non-terminal>和- <non-terminal>，而不知道非终端的名称；只有它们的存在。

另一个要求是，您必须能够在终端之间建立优先级关系。更准确地说，我们定义了三个优先关系，通常写为<·、·>和·=· (或主题上的一些排版变化)，并坚持认为对于任何两个终端( x和y )，最多只有一个关系( x ·> y、x ·=· y和x <· y )是正确的。

粗略地说，关系中的<和>对应于一个产品的边缘。换句话说，如果是x <· y，这意味着x之后可以是一个非终端，其第一个终端是y。类似地，x ·> y意味着y可以跟随一个非终端，其最后一个终端是x的产品。x ·=· y意味着有一些右手边，其中x和y是连续的终端，按顺序排列(可能有一个中间的非终端)。

如果单关系限制为真，那么我们可以解析如下：

让x是前缀中的最后一个终端(也就是最后一个或第二个-最后一个符号)，并让y成为前瞻性符号，它必须是一个终端。如果x ·> y，那么我们减少，并重复这个规则。否则，我们将y转换为前缀。

为了减少，我们需要找到生产的开始。我们向后移动前缀，比较连续的终端(所有这些终端都必须有<·或·=·关系)，直到找到具有<·关系的终端为止。然后，<·和·>之间的终端是我们正在寻找的产品的右侧，我们可以按指示将非终端插入右侧。

不能保证会有适当的产品；如果没有，解析就会失败。但是如果输入是一个有效的句子，如果语法是一个操作符优先文法，那么我们就能够找到合适的结果来减少。

请注意，通常很容易找到产品，因为大多数产品只有一个(<non-terminal> * <non-terminal>)或两个(( <non-terminal> ))终端。一个简单的实现可能只是将终端一起运行到一个字符串中，并将其用作哈希表中的键。

操作符优先分析的经典实现是Edsger Dijkstra设计的所谓的“分流场算法”。在该算法中，通过提供两个函数(左优先和右优先)来建模优先级关系，这两个函数将终端映射到整数，这样只有当x <· y为right-precedence(x) < left-precedence(y)时才为真(对于其他操作符也是如此)。不总是能够找到这样的映射，而且映射是实际优先级关系的一个覆盖，因为通常情况下，存在一对不适用于优先关系的终端。尽管如此，这些映射通常是可以找到的，而对于简单的表达式语法来说，情况几乎总是如此。

我希望这足以让你开始工作。我鼓励大家阅读一些关于自下而上解析的文本，因为我认为我已经写了太多的东西，无法给出答案，而且我还没有包含一行代码。:)