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

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

речь идет о грамматике

S->aAb|SA
A->aA|e|S

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

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


java parsing context-free-grammar lr1
person Crysis85    schedule 02.07.2015    source источник

Ответы (1)


arrow_upward
5
arrow_downward

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

S aAb аб

S SA аАбА абА аб

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

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

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

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

person templatetypedef    schedule 02.07.2015