Этот генератор синтаксического анализа говорит, что эта грамматика не LR(1), но у меня есть сомнения

Question

Я написал генератор синтаксического анализатора на Java, после нескольких ухищрений (ранняя версия, например, не особенно понравилась левая рекурсия), мне удалось заставить его работать с некоторыми простыми грамматиками (так что я могу вручную проверить правильность произведений)) Я попытался передать более сложную грамматику, и в результате получилось, что это не грамматика LR(1) (полученная из того факта, что анализируемый попытался дважды записать в одну и ту же ячейку таблицы разбора)

рассматриваемая грамматика

S-> AAB |SA
A-> аА | е |S

Я почти уверен, что эта грамматика LR(1), во всяком случае, вот вывод моей программы http://pastebin.com/hJNC9uuN

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

Answer 1

Эта грамматика не может быть LR(1), потому что она неоднозначна. Вот два способа получения строки ab:

S → aAb → ab

S → SA → aAbA → abA → ab

Ваши наборы LR (1) фактически содержат конфликт сдвига / уменьшения. Проверьте состояние 5, которое включает в себя эти пункты:

[A->S. { $a }]
[A->.aA { $a }]

Это конфликт сдвига / уменьшения: переходите ли вы на aили вы уменьшаете на a? Поэтому инструмент выглядит правильно на этом входе: грамматика не является LR(1), и он обнаруживает, что это не LR(1).

Надеюсь это поможет!