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

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

1 голос
/ 09 апреля 2011

У меня возникли некоторые проблемы с пониманием того, как, используя анализатор снизу вверх и, например, строку ввода 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, который я сделал), и все они дают правильный результат.

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

Спасибо!

1 Ответ

1 голос
/ 09 апреля 2011

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

...