Я видел этот алгоритм, который нужно использовать, чтобы удалить всю левую рекурсию. Тем не менее у меня возникают проблемы с этой конкретной грамматикой:
A -> Cd
B -> Ce
C -> A | B | f
Независимо от того, что я пытаюсь, я заканчиваю петлями или грамматикой, которая по-прежнему остается косвенной левой рекурсивной.
Каковы шаги по правильному внедрению этого алгоритма в этой грамматике?
Правило заключается в том, что вы сначала устанавливаете какой-то порядок для нетерминалов, а затем находите все пути, в которых происходит косвенная рекурсия.
В этом случае порядок будет A < B < C, а возможные пути для рекурсии нетерминального C будут
C=> A => Cd
и
C=> B => Ce
поэтому новые правила для C будут
C=> Cd | Ce | f
теперь вы можете просто просто удалить прямую левую рекурсию:
C=> fC'
C'=> dC' | eC' | eps
и полученная нерекурсивная грамматика будет:
A => Cd
B => Ce
C => fC'
C' => dC' | eC' | eps
Выяснил это уже.
Моя путаница заключалась в том, что в этом порядке алгоритм, казалось, ничего не делал, поэтому я решил, что это должно быть неправильно, и начал замену A → Cd на первой итерации (игнорирование j не может превысить i) попадание в бесконечные циклы.
1) Переупорядочивая правила:
C -> A | B | f
A -> Cd
B -> Ce
2) заменим C в → Cd
C -> A | B | f
A -> Ad | Bd | fd
B -> Ce
3) B еще не находится в диапазоне j, поэтому оставьте это и замените прямую левую рекурсию A
C -> A | B | f
A -> BdA' | fdA'
A'-> dA' | epsylon
B -> Ce
4) замените C в B → Ce
C -> A | B | f
A -> BdA' | fdA'
A'-> dA' | epsylon
B -> Ae | Be | fe
5) еще не сделано! также необходимо заменить новое правило B → Ae (производство A находится в диапазоне j)
C -> A | B | f
A -> BdA' | fdA'
A'-> dA' | epsylon
B -> BdA'e | fdA'e | Be | fe
6) заменить прямую левую рекурсию в произведениях B
C -> A | B | f
A -> BdA' | fdA'
A'-> dA' | epsylon
B -> fdA'eB' | feB'
B'-> dA'eB' | eB' | epsylon
Woohoo! левая рекурсивная грамматика!