在 shift reduce 解析中，为什么句柄最终总是出现在堆栈顶部而不是内部？

Question

我正在阅读 Ullman 等人撰写的 Compilers Principles, Techniques and Tools 一文。 al 在那里我看到了作者试图证明为什么堆栈是移位减少解析的最佳数据结构的摘录。他们说是因为

“句柄最终总是会出现在堆栈的顶部，而不是内部。”

节选

This fact becomes obvious when we consider the possible forms of two successive steps in any rightmost derivation. These two steps can be of the form

In case (1), A is replaced by , and then the rightmost nonterminal B in that right side is replaced by . In case (2), A is again replaced first, but this time the right side is a string y of terminals only. The next rightmost nonterminal B will be somewhere to the left of y.

Let us consider case (1) in reverse, where a shift-reduce parser has just reached the configuration

The parser now reduces the handle to B to reach the configuration

in which is the handle, and it gets reduced to A

In case (2), in configuration

the handle is on top of the stack. After reducing the handle to B, the parser can shift the string xy to get the next handle y on top of the stack,

Now the parser reduces y to A.

In both cases, after making a reduction the parser had to shift zero or more symbols to get the next handle onto the stack. It never had to go into the stack to find the handle. It is this aspect of handle pruning that makes a stack a particularly convenient data structure for implementing a shift-reduce parser.

我的推理与疑惑

直觉上我觉得中的说法是有道理的

如果堆栈顶部有一个句柄，则算法将在将下一个输入符号压入堆栈之前先减少它。由于在压入之前减少了任何可能的句柄，所以句柄不可能位于堆栈的顶部，然后压入新的输入符号从而导致句柄进入堆栈。

此外，我无法理解作者在摘录的突出显示部分中给出的逻辑，根据他们对 B 的说法以及与之相关的其他事实，证明句柄不能出现在堆栈内。

谁能帮我理解这个概念。

Answer 1

作者所表达逻辑的关键在开头的陈述中（强调已添加）：

This fact becomes obvious when we consider the possible forms of two successive steps in any rightmost derivation.

同样重要的是要记住，自下而上的解析器会向后追踪最右推导。解析器执行的每一次缩减都是推导中的一个步骤；因为推导是最右边的，所以在推导步骤中被替换的非终结符必须是句子形式中的最后一个非终结符。因此，如果我们写下解析器使用的归约动作序列，然后向后读取列表，我们就可以得到推导。或者，如果我们写下最右边推导中使用的产生式列表，然后向后读取它，我们将得到解析器归约序列。

无论哪种方式，关键是要证明推导步骤中的连续句柄对应于原始输入中的单调非后退前缀。作者的证明采取了两个推导步骤（任意两个推导步骤），表明第二个推导步骤的句柄末端不在第一步句柄末端之前（虽然两个句柄的末端可能在输入中的相同点）。