Изменения

рассмотреть все правила вывода из <tex>A_j</tex>: <tex>A_j \rightarrow Rightarrow \delta_1 | \ldots | \delta_k</tex>. заменить каждое правило <tex>A_i \rightarrow Rightarrow A_j \gamma</tex> на <tex>A_i \rightarrow Rightarrow \delta_1\gamma | \ldots | \delta_k\gamma</tex>.

Таким образом, после применения алгоритма все правила вывода имеют вид: *<tex>A \rightarrow c \alpha </tex>, где <tex>c</tex> {{---}} терминал, <tex>A</tex> {{---}} произвольный нетерминал;*<tex>A_i \rightarrow A_j \alpha </tex>, где <tex>i < j</tex>, <tex>A_i , A_j</tex> {{---}} нетерминалы из исходной грамматики;*<tex>A_i^{\prime} \rightarrow A_j \alpha </tex>, где <tex>A_i^{\prime}</tex> {{---}} новый нетерминал, <tex>A_j</tex> {{---}} нетерминал из исходной грамматики. Если теперь перенумеровать нетерминалы, сохранив порядок для старых и присвоив всем новым меньшие номера, то все правила будут иметь вид:*<tex>B_i \rightarrow c \alpha </tex>, где <tex>c</tex> {{---}} терминал;*<tex>B_i \rightarrow B_j \alpha </tex>, где <tex>i < j</tex>. После <tex>i^ой</tex> итерации внешнего цикла в любой продукции вида <tex>A_k \rightarrow Rightarrow A_l\alpha</tex> где </tex> i > k </tex> будет <tex> l > k</tex>.В результате после каждой итерации растет нижний предел m, таких, что существует продукция всех продукций вида <tex>A_i \rightarrow Rightarrow A_m\alpha</tex> до тех пор, пока не будет достигнуто <tex>m \geq i</tex>. Затем из <tex>A_i</tex> устраняется непосредственная левая рекурсия и достигается m > i.