0

让我们采用以下上下文无关语法：

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 的前瞻缓冲区 (LAB) 解析由该语法生成​​的表达式（据推测应该无需猜测和回溯）。

现在，给定一个堆栈和一个 LAB，通常有几种可能性如何减少堆栈或是否完全减少堆栈或推送另一个令牌。

目前我使用这个决策树：

如果堆栈的任何顶部 n 标记加上 LAB 是规则右侧的开始，我将下一个标记压入堆栈。

否则，我会减少堆栈顶部的最大令牌数。即，如果可以减少最顶层的项目，同时可以减少三个最顶层的项目，我会选择后者。

如果没有这样的减少是可能的，我将另一个令牌推入堆栈。

冲洗并重复。

这似乎（！）可以工作，但它需要大量的规则搜索、查找匹配的前缀等。这不可能在 O(NM) 中运行。

决定是减少还是推动（转移）的标准（并且可能是唯一明智的）方法是什么，在减少的情况下，应用哪种减少？

提前感谢您的评论和回答。

4

1 回答 1

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> )) 终端。一个简单的实现可能只是将终端一起运行成一个字符串，并将其用作哈希表中的键。

运算符优先级解析的经典实现是所谓的“Shunting Yard Algorithm”，由 Edsger Dijkstra 设计。在该算法中，优先关系通过提供两个函数来建模，左优先和右优先，它们将终端映射到整数，使得x <· y只有当right-precedence(x) < left-precedence(y)（并且对于其他运算符类似）才为真。并非总是能够找到这样的映射，并且这些映射是实际优先关系的一种覆盖，因为通常情况下存在没有优先关系适用的终端对。尽管如此，通常可以找到这些映射，对于简单的表达式语法几乎总是如此。

我希望这足以让你开始。我鼓励您实际阅读一些有关自下而上解析的文本，因为我认为我已经为 SO 答案编写了太多内容，而且我还没有包含一行代码。:)

于 2013-09-14T04:58:42.727 回答