Обсуждение:Устранение левой рекурсии

☐ написать, почему, собственно, надо ее устранять верно ли что для нормального разбора сверху вних

☐ англоязычные термины и источники

☐ а сложность алгоритма какая? --Дмитрий Герасимов 22:31, 7 декабря 2012 (GST)

1)Таким образом, после применения алгоритма все правила вывода имеют вид:

• [math]A \rightarrow c \alpha [/math], где [math]c[/math] — терминал, [math]A[/math] — произвольный нетерминал;
• [math]A_i \rightarrow A_j \alpha [/math], где [math]i \lt j[/math], [math]A_i , A_j[/math] — нетерминалы из исходной грамматики;
• [math]A_i^{\prime} \rightarrow A_j \alpha [/math], где [math]A_i^{\prime}[/math] — новый нетерминал, [math]A_j[/math] — нетерминал из исходной грамматики.

Если теперь перенумеровать нетерминалы, сохранив порядок для старых и присвоив всем новым меньшие номера, то все правила будут иметь вид:

• [math]B_i \rightarrow c \alpha [/math], где [math]c[/math] — терминал;
• [math]B_i \rightarrow B_j \alpha [/math], где [math]i \lt j[/math].

казалось бы это бред