Я пытался решить эту проблему часами, и это был бесконечный цикл проб и ошибок. Мне нужно сделать эту грамматику однозначной:
S -> Sa | Sb | aS | bS | aa
Насколько я понимаю, это может генерировать любую комбинацию букв a и b, где где-то появляется «aa». Основная проблема заключается в том, что он может генерироваться с обеих сторон, поэтому существует несколько деревьев синтаксического анализа. Моя лучшая попытка на данный момент выглядит примерно так:
S -> aS | bS | aT
T -> aU | a
U -> bU | b
Это генерирует любые a и b... затем вызывает второе a и позволяет добавить больше b. Однако это не позволяет использовать каждую строку ... не может делать «абааба». Я не могу обернуть голову, как сделать это недвусмысленным.