228
правок
Изменения
→Устранение непосредственной левой рекурсии
Изначально нетерминал <tex>A</tex> порождает сроки вида <tex>\beta\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. В новой грамматике нетерминал <tex>A</tex> порождает <tex>\beta{A^\prime}</tex>, а <tex>A^\prime</tex> порождает строки вида <tex>\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. Из этого очевидно, что изначальная грамматика эквивалентна новой.
===Пример===
<tex>A \to S\alpha | A\alpha</tex>
<tex>S \to A\beta</tex>
Есть непосредственная левая рекурсия <tex>A \to A\alpha</tex>. Добавим нетерминал <tex>A^prime</tex> и добавим правила <tex>A \to S\alpha{A^{\prime}}</tex>, <tex> A^{\prime} \to \alpha{A^{\prime}} </tex>.
Новая грамматика:
<tex>A \to S\alpha{A^{\prime}} | S\alpha</tex>
<tex>A^{\prime} \to \alpha{A^{\prime}}</tex>
<tex>S \to A\beta</tex>
В новой грамматике нет непосредственной левой рекурсии, но нетерминал <tex>A</tex> леворекурсивен, так как есть <tex>A \Rightarrow S\alpha{A^{\prime}} \Rigtharrow A\beta\alpha{A^{\prime}}</tex>
==Алгоритм устранения произвольной левой рекурсии==
