228
правок
Изменения
→Устранение непосредственной левой рекурсии
==Устранение непосредственной левой рекурсии==
Опишем процедуру, устраняющую все правила вида <tex>A \rightarrow Rightarrow A\alpha</tex>, для фиксированного нетерминала <tex>A</tex>.
<ol>
<li>Запишем все правила вывода из <tex>A</tex> в виде:
<tex>A \rightarrow Rightarrow A\alpha_1\,|\,\ldots\,|\,A\alpha_n\,|\,\beta_1\,|\,\ldots\,|\,\beta_m </tex>, где
<ul>
<li> <tex>\alpha</tex> {{---}} непустая последовательность терминалов и нетерминалов (<tex>\alpha \nrightarrow \varepsilon </tex>);</li>
<li> <tex>\beta</tex> {{---}} непустая последовательность терминалов и нетерминалов, не начинающаяся с <tex>A</tex>.</li>
</ul>
<li>Заменим правила вывода из <tex>A</tex> на <tex>A \rightarrow Rightarrow \beta_1A^\prime\, |\, \ldots\, |\, \beta_mA^\prime \,|\, \beta_1 \,|\, \ldots \,|\, \beta_m</tex>.</li>
<li>Создадим новый нетерминал <tex>A^\prime \rightarrow Rightarrow \alpha_1A^\prime\, |\, \ldots\, |\, \alpha_nA^\prime | \alpha_1\, |\, \ldots\, |\, \alpha_n</tex>. </li>
</li>
</ol>
Нетерминал A порождает те же строки, что и ранее, но без левой рекурсии. Эта процедура устраняет все непосредственные рекурсии из продукций для A, при условии, что ни одна строка <tex>\alpha_i</tex> не является <tex>\epsilon</tex>.
==Алгоритм устранения произвольной левой рекурсии==
