Как удалить левую рекурсию из заданного грамматика

Question

Я пробовал это много раз, но не нашел правильного решения.

A-->Ba/b
B-->Bc/Ad/e

Пожалуйста, предложите мне хороший ответ на экзамен.

Answer 1

Вот решение для получения эквивалентной грамматики, которая не является леворекурсивной (В вопросе, я предполагаю, что e=epsilon):

Не осталось левых рекурсивных A-продукций. Таким образом, удалив A из правой части B-продукции, мы получим:

A -> Ba | б

B -> Bc | Плохо | бд | е

Теперь мы удалим левые рекурсивные B-произведения, введя B ':

A -> Ba | б

B -> bdB '| B"

B '-> cB' | adB '| е

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