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

根据语法，E 永远不能跟在 + 之后。这排除了在此状态下的 E = T 生产。

要完全理解这一点，请手动构建解析器表 - 该示例足够小以使其可行。

Answer 2

可能的状态有哪些？

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 开始。移动 a 2。我们现在处于状态 1。转换到状态 2。移动 a +。我们现在处于状态 3。我们移动 a 2。我们处于状态 4。我们减少到状态 5。我们到达堆栈的末尾并以如下所示的表达式树结束：

  E
  |
E + T
|   |
T   2
|
2

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

LR(0)/SLR/LR(1) parsing - how a production is chosen?

algorithm

parsing

lr