Как определить грамматик 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  |   +--------------+ 
          +--------------+ 

Однако IS в SLR (1) потому что конфликт в состоянии 2 можно разрешить, используя тот факт, что знак + равен не в FOLLOW (E). Поскольку SLR (1) синтаксические анализаторы могут смотреть 1 маркер вперед, они могут выбрать shift в состоянии 2, если следующий токен + (и разрешить конфликт, сделав это).

Если парсер SLR (1) находится в состоянии 2, а следующий токен равен +, , почему бы не выбрать сокращение?

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