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

Question

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

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

Answer 1

下图证明此文法不在LR(0) 中（存在移位归约冲突）：

+--------------+     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，并且下一个标记是 +，为什么不选择 reduce？

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