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

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

3 голосов
/ 15 декабря 2010

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

S -> aSAbb | аА

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

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

EDIT:

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

1 Ответ

1 голос
/ 15 декабря 2010

Правило 

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 (думаю: поправьте меня, если я ошибаюсь).

...