algorithm - LR(0)/SLR/LR(1) 解析 - 如何选择产生式？

Question

我正在尝试理解解析器理论，并且我不断在不同的来源中找到相同的示例。语法大致如下(简化):

E = T
E = E + T
T = 0..9

因此，假设字符串 2 + 2 将被解析为这样(“|”将堆栈与提醒分开)

|2 + 2 <-can't reduce, shift
2|+ 2  <-reduce by T = 0..9
T|+ 2  <-reduce by E = T
E|+ 2  <-can't reduce, shift
E +|2  <-can't reduce, shift
E + 2| <-reduce by T = 0..9
E + T| <-reduction by E = E + T here?
E|     <-done

问题是，在 E + T 步骤解析器可以对堆栈的最右边部分应用两种不同的归约:E = T(结果为 E + E)和 E = E + T(结果为 E)。我找不到一个清晰简洁的解释来解释它如何选择其中之一。

我错过了什么？

Answer 1

可能的状态是什么？

0: Beginning
1: Just shifted 0..9 after State 0, recognize a T
2: Reduce State 1 to an E.
3: Just shifted + after State 2 or 5, looking for T
4: Just shifted 0..9 after State 3, recognize a T giving us E + T.
5: Reduce state 4 to an E
6: Reach the end of the stack after state 2 or 5.

所以我们从状态 0 开始。移动 2。我们现在处于状态 1。转换到状态 2。按 +。我们现在处于状态 3。我们移动 2。我们处于状态 4。我们减少到状态 5。我们到达堆栈末尾并最终得到如下所示的表达式树:

  E
  |
E + T
|   |
T   2
|
2