parsing - 我应该使用什么生产规则来减少自下而上的解析？

Question

到目前为止，我对自底向上解析的算法的理解是这样的。

1. 将令牌移入堆栈
2. 如果某些元素（包括顶部）可以通过某些生产规则减少，则从顶部检查堆栈
3. 如果元素可以减少，弹出并推动生产规则的左侧。
4. 继续这些步骤，直到顶部是开始符号，下一个输入是 EOF

所以用一个示例语法来支持我的问题，

S → aABe

A → Abc
A → b
B → d

如果我们输入字符串为

缩写$

我们将a在堆栈中移动，因为没有减少的生产规则a，我们移动下一个令牌b。然后我们可以找到一个生产规则A → b并减少b到A。

那么我的问题是这个。我们aA在堆栈上，下一个输入是b. 那么解析器如何判断我们是否归约b到A我们等待c来使用的规则A → Abc呢？

当然，减少b到A那个点会导致错误。但是解析器是如何知道我们应该等待的c呢？

如果我在学习时遗漏了什么，我很抱歉。

Answer 1

这是一个很好的问题，将在您课程的下一部分中解决。

现在，假设有一些神奇的黑匣子就足够了，它告诉解析器什么时候应该减少（有时，使用几个可能的产生式中的哪一个）。

各种解析算法解释了这个黑匣子的构造。请注意，一种可能的解决方案是分叉现实并并行尝试这两个动作，但更常见的解决方案是处理语法以找出如何预测正确的动作。