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