Удаление левой рекурсии с помощью терминалов

Question

Как удалить левую рекурсию по следующему правилу:

S -> aSAbb | аА

Я понимаю, как это сделать на S -> SA | A

, который становится S -> A | КАК'; S '-> A | КАК ', но терминалы выбрасывают меня в этом вопросе.

EDIT:

Извините, по-видимому, я не понял, что такое оставленная рекурсия. Я должен был спросить, как убрать символ левой руки с правой стороны.

Answer 1

Правило

S -> aSAbb | aA

не является рекурсивным.Левое рекурсивное правило имеет вид

A -> Au

, где u - последовательность терминалов и нетерминалов.Чтобы удалить символ S с правой стороны правил S, рассмотрите следующее:

S => aSAbb
  => a(aSAbb)Abb
  => a^n(aA)(Abb)^n

Роль рекурсии на S заключается в создании этой последовательности.Эквивалентная грамматика:

S -> aKAbb | aA
K -> aSAbb | aA

Грамматики эквивалентны, так как любой производный

S => aSAbb
  => a(aSAbb)Abb
  => a(a(aSAbb)Abb)Abb

теперь является просто производным

S => aKAbb
  => a(aSAbb)Abb
  => a(a(aKAbb)Abb)Abb

, и каждый производный завершаетсяна aA (думаю: поправьте меня, если я ошибаюсь).