theory - 如何识别文法是LR(0)还是SLR(1)？

Question

这个文法是LR(0)还是SLR(1)？

S -> E $
E -> T + E | T
T -> x

Answer 1

下图证明该文法在 LR(0) 中NOT(它存在移位归约冲突):

+--------------+     E      +------------+
|              |----------> | S -> E . $ |
| S -> . E $   |            +------------+
| E -> . T + E |            
| E -> . T     |     T      +--------------+       state 2
| T -> . x     |----------> | E -> T . + E | This state contains a
|              |            | E -> T .     | Shift-Reduce conflict.
+--------------+            +--------------+
       |                      | +       ^
       | x                    V         | T
       |                    +--------------+
       V                    | E -> T + . E |
+---------------+      x    | E -> . T + E |          +--------------+
|    T -> x .   | <---------| E -> . T     |--------> | E -> T + E . |
+---------------+           | T -> . x     |          +--------------+
                            +--------------+

但是，它在 SLR(1) 中是，因为状态 2 中的冲突可以通过使用 + 标记在 FOLLOW(E) 中不是这一事实来解决。 由于 SLR(1) 解析器可以向前查看 1 个标记，因此如果下一个标记是 +，它们可以决定在状态 2 中转移(并通过这样做解决冲突)。

如果 SLR(1) 解析器处于状态 2，并且下一个标记是 +， 为什么不选择减少？

好吧，假设解析器选择减少 E -> T。 然后最终 + 标记将被读取，并且它将跟随 E、 或 E 派生自的某个其他变量(此语法中只有 S)。 但是 E 和 S 都不能让 + 标记(立即)跟随它们!