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

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

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). И я не могу найти ясного и краткого объяснения, как он выбирает одно над другим.

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


parsing algorithm lr
person Vindicar    schedule 27.11.2018    source источник

Ответы (2)


arrow_upward
2
arrow_downward

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

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. Сдвигаем 2. Теперь мы находимся в состоянии 1. Переходим в состояние 2. Сдвигаем +. Теперь мы находимся в состоянии 3. Мы сдвигаем 2. Мы находимся в состоянии 4. Мы приводим его к состоянию 5. Мы достигаем конца стека и получаем дерево выражений, похожее на следующее:

  E
  |
E + T
|   |
T   2
|
2
person btilly    schedule 27.11.2018
comment
Ах, значит, синтаксический анализатор может находиться в разных состояниях, несмотря на то, что он только что применил одно и то же сокращение, в зависимости от истории сокращений? Как автомат может достигать разных состояний на одном и том же входном символе, в зависимости от того, какое состояние было текущим раньше? - person Vindicar; 28.11.2018
comment
@Виндикар Да. Точно как автомат. - person btilly; 28.11.2018
comment
@Виндикар Да. Вы можете думать, что это точно так же, как автомат, который оставляет и время от времени подчищает след хлебных крошек на своем пути. Эта «хлебная крошка» превращается в дерево синтаксического анализа. - person btilly; 28.11.2018

arrow_upward
1
arrow_downward

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

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

person Henry    schedule 27.11.2018
comment
Видите ли, в том-то и дело, что синтаксический анализатор должен знать, что E = T ведет в тупик на шаг позже. Как бы он узнал это, не попробовав? Он может смотреть вперед во входной строке, но как он может смотреть вперед в своем собственном дереве синтаксического анализа? - person Vindicar; 27.11.2018
comment
Парсер при работе имеет не только символы в стеке, но и состояние парсера. По-разному обстоит дело в том случае, когда сокращение с этим производством разрешено, а где нет. Вы действительно должны попытаться создать состояния вручную. - person Henry; 27.11.2018
comment
Сначала мне нужно понять, что такое состояние синтаксического анализатора... и все же, спасибо! - person Vindicar; 27.11.2018