Задача с обратным выводом с простой суммой и умножением грамматики

Question

У меня возникли проблемы с пониманием того, как, используя анализатор снизу вверх и, например, строку ввода 1 + 2 * 3, перейдите от "снизу" к "вершине".

Вот грамматика, которую я использую (я бы сказал, что она правильная, так как она найдена в Crafting a Compiler)

E = E plus T
  | T;

T = T times integer
  | integer;

Это мой обратный вывод:

int(1)
T(1)
E(1)
E(1) plus int(2)
E(1) plus T(2)
E(1) plus E(2)
E(1) plus E(2) times int(3)
E(1) plus E(2) times E(3) <-- can't do anything here

Проблема в том, что каждый раз, когда я получаю целое число в качестве входных данных, оно будет автоматически "преобразовано" в E,

Я уверен, что данная грамматика верна. Я также попробовал это в sablecc с некоторыми входными строками (используя созданный мной посетитель Pretty Printer), и все они дают правильный результат.

Таким образом, я знаю, что проблема во мне, а не в самой грамматике. Что я делаю не так, тогда?

Спасибо!

Answer 1

Конфликт сдвига-уменьшения является наиболее распространенным типом конфликта, встречающегося в грамматике. В вашем случае T(2) может быть уменьшено до E(2), или времена могут быть сдвинуты. По умолчанию большинство генераторов парсеров предпочитают сдвигать, а не уменьшать. Но они все равно уменьшат T(1) до E(1), потому что они знают, что нет смысла сдвигать плюс после T.