如何识别语法是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中的冲突可以通过以下(E)中的+令牌是而不是来解决。因为SLR(1)解析器可以向前看1个令牌，所以如果下一个令牌是+(并通过这样做解决冲突)，它们可以决定在状态2中shift。

如果SLR(1)解析器处于状态2，而下一个令牌是+，为什么不选择减？

那么，假设解析器选择减少E -> T，那么最终将读取+令牌，它将跟随E或E派生的其他变量(只有这个语法中的S)。但是，E和S都不能让+令牌(立即)跟随它们！