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

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

S -> aSAbb | аА

Я понимаю, как это выполнить на S -> SA | А

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

РЕДАКТИРОВАТЬ:

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


left-recursion context-free-grammar
person A B    schedule 14.12.2010    source источник
comment
У него нет левой рекурсии, поэтому вам тяжело. Левая рекурсия требует, чтобы правило начиналось с того же нетерминала, который оно пытается создать, например, S->S ... ;   -  person Ira Baxter    schedule 15.12.2010
comment
Я не думаю, что это возможно. Грамматика кажется a^n aA (Abb)^n, и я не думаю, что есть какой-либо способ связать эти два n без рекурсии.   -  person BCS    schedule 15.12.2010

Ответы (1)


arrow_upward
1
arrow_downward

Правило

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

person danportin    schedule 15.12.2010