27
правок
Изменения
Нет описания правки
<tex>A \rightarrow A\alpha_1\,|\,\ldots\,|\,A\alpha_n\,|\,\beta_1\,|\,\ldots\,|\,\beta_m </tex>, где
<ul>
<li> <tex>\alpha</tex> {{- --}} непустая последовательность терминалов и нетерминалов (<tex>\alpha \nrightarrow \epsilon </tex>);</li><li> <tex>\beta</tex> {{--- }} непустая последовательность терминалов и нетерминалов, не начинающаяся с <tex>A</tex>.</li>
</ul>
<li>Заменим правила вывода из <tex>A</tex> на <tex>A \rightarrow \beta_1A^\prime\, |\, \ldots\, |\, \beta_mA^\prime \,|\, \beta_1 \,|\, \ldots \,|\, \beta_m</tex>.</li>
==Устранение произвольной левой рекурсии==
Пусть <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex> {{- --}} множество всех нетерминалов.
<div>
for i = 1 to n {
Таким образом, после применения алгоритма все правила вывода имеют вид:
*<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>.
