Левые вопросы устранения рекурсии - PullRequest
Новая
       29

Левые вопросы устранения рекурсии

1 голос
/ 01 мая 2020

Я работаю над удалением левой рекурсии в грамматике. (3 грамматики) 

1. A->Ab | aC
   B->BaBB | BA       
   C->bC | BA                     

2. T->Txxy | TaabT | TTa               


3. A-> BA | Baa         
   B-> Ab | Abb

Я пытался это сделать, но я не уверен в своих ответах. Первый, я понятия не имею, как это сделать. Во-вторых, третий, я думаю, что это не удастся. Правильный ли мой ответ? Как я могу это изменить? Пожалуйста, кто-нибудь объяснит это подробно.

1 Ответ

0 голосов
/ 01 мая 2020

Я написал решение. У меня не было много времени, чтобы напечатать все это, а также я не был уверен, что этот вопрос будет доступен больше из-за offtopi c.

Проверьте решение для первой грамматики здесь на first Грамматическое решение

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

Для третьей грамматики мы можем сделать 

A-> BA | Baa         
B-> Ab | Abb  

Replace All B's into A
A-> AbA | Abaa | AbbA | Abbaa

Теперь снова все произведения рекурсивны и не могут даже завершить грамматика. Вам нужно либо нулевое производство, либо производство только с терминалами.

...