26
правок
Изменения
Нет описания правки
Запишем все правила вывода из <tex>A</tex> в виде
<mathtex>A \rightarrow A\alpha_1\,|\,\ldots\,|\,A\alpha_n\,|\,\beta_1\,|\,\ldots\,|\,\beta_m </mathtex>
где
Заменим правила вывода из <tex>A</tex> на:
<mathtex>A \rightarrow \beta_1A^\prime\, |\, \ldots\, |\, \beta_mA^\prime \,|\, \beta_1 \,|\, \ldots \,|\, \beta_m</mathtex>
И создадим новый нетерминал
<mathtex>A^\prime \rightarrow \alpha_1A^\prime\, |\, \ldots\, |\, \alpha_nA^\prime</mathtex>
===Устранение произвольной левой рекурсии===
: for i = 1 to n {
::for j = 1 to i – 1 {
:::* рассмотреть все правила вывода из <mathtex>A_j</mathtex>:::<mathtex>A_j \rightarrow \delta_1 | \ldots | \delta_k</mathtex>:::* заменить каждое правило <mathtex>A_i \rightarrow A_j \gamma</mathtex> на:::<mathtex>A_i \rightarrow \delta_1\gamma | \ldots | \delta_k\gamma</mathtex>
::}
:: устранить непосредственную левую рекурсию для <mathtex>A_i</mathtex>
:}
Инвариант: после <tex>j</tex> итераций внутреннего цикла для <tex>i</tex>
