Пошаговое устранение этой непрямой левой рекурсии

Правило состоит в том, что вы сначала устанавливаете какой-то порядок для нетерминалов, а затем находите все пути, где происходит непрямая рекурсия.

В этом случае порядок будет 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 в A -> 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

ууууу! грамматика без левой рекурсии!