Как определить грамматику 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, а следующий токен - +, почему бы не выбрать уменьшение?

Хорошо, предположим, что синтаксический анализатор решает уменьшить E -> T. Затем в конечном итоге будет прочитан токен +, и он будет следовать либо за E, либо за какой-то другой переменной, из которой было получено E (только S в этой грамматике). Но ни E, ни S не могут иметь + знак (сразу), следуя за ними!