228
правок
Изменения
→Устранение непосредственной левой рекурсии
<li>Заменим правила вывода из <tex>A</tex> на <tex>A \to\beta_1A^\prime\, |\, \ldots\, |\, \beta_mA^\prime \,|\, \beta_1 \,|\, \ldots \,|\, \beta_m</tex>.</li>
<li>Создадим новый нетерминал <tex>{A^\prime } \to \alpha_1Aalpha_1{A^\prime\}, |\, \ldots\, |\, \alpha_nAalpha_n{A^\prime } | \alpha_1\, |\, \ldots\, |\, \alpha_n</tex>. </li>
</li>
</ol>
Изначально нетерминал <tex>A</tex> порождает сроки вида <tex>\beta\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. В новой грамматике нетерминал <tex>A</tex> порождает <tex>\beta{A_iA^\prime}</tex>, а <tex>A_iA^\prime</tex> порождает строки вида <tex>\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. Из этого очевидно, что изначальная грамматика эквивалентна новой.
==Алгоритм устранения произвольной левой рекурсии==
