Разбор LR (0) / SLR / LR (1) - как выбирается производство?

Question

Я пытаюсь обернуть голову вокруг теории парсера, и я продолжаю находить один и тот же пример в разных источниках.Грамматика выглядит примерно так (упрощенно):

E = T
E = E + T
T = 0..9

Итак, предположительно, строка 2 + 2 будет проанализирована как таковая ("|" отделяет стек от напоминания)

|2 + 2 <-can't reduce, shift
2|+ 2  <-reduce by T = 0..9
T|+ 2  <-reduce by E = T
E|+ 2  <-can't reduce, shift
E +|2  <-can't reduce, shift
E + 2| <-reduce by T = 0..9
E + T| <-reduction by E = E + T here?
E|     <-done

Вопрос в том, что на E + T пошаговый синтаксический анализатор может применить два разных сокращения к самой правой части стека: E = T (в результате E + E) и E = E + T (в результате E).И я не могу найти ясного и сознательного объяснения, как оно выбирает одно над другим.

Чего мне не хватает?

Answer 1

Каковы возможные состояния?

0: Beginning
1: Just shifted 0..9 after State 0, recognize a T
2: Reduce State 1 to an E.
3: Just shifted + after State 2 or 5, looking for T
4: Just shifted 0..9 after State 3, recognize a T giving us E + T.
5: Reduce state 4 to an E
6: Reach the end of the stack after state 2 or 5.

Итак, мы начинаем в состоянии 0. Shift a 2.Сейчас мы находимся в состоянии 1. Переход в состояние 2. Сдвиг a +.Сейчас мы в состоянии 3. Мы сдвигаем 2.Мы находимся в состоянии 4. Мы переводим в состояние 5. Мы достигаем конца стека и получаем дерево выражений, похожее на следующее:

  E
  |
E + T
|   |
T   2
|
2

Answer 2

Согласно грамматике, E никогда не может следовать за +.Это исключает производство E = T в этом состоянии.

Чтобы полностью понять это, создайте таблицы синтаксического анализатора вручную - пример достаточно мал, чтобы сделать это возможным.