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。移动一个+。我们现在处于第三状态。我们移动一个2。我们处于状态4。我们减少到状态5。我们到达堆栈的末尾，最后得到如下所示的表达式树：

  E
  |
E + T
|   |
T   2
|
2

Answer 2

根据语法，E永远不能跟随+。这就排除了这种状态下的E = T生产。

要完全理解这一点，可以手工构造解析器表--这个示例足够小，可以实现这一点。