Приведу конкретно и коротко.
Исходная (типичная) грамматика с леворекурсией:
$$E\to E+T\mid E-T\mid T$$ $$T\to T\ast F\mid T/F\mid F$$ $$F\to (E)\mid \text{num}$$
Почему левую рекурсию надо убирать:
- LL‑парсер (топ‑даун, рекурсивный спуск или таблица LL(1)) при попытке применить правило $E\to E+T$ начнёт рекурсивно разбирать $E$ снова и получит бесконечную рекурсию — разбор не завершится.
- Левые рекурсивные правила приводят к конфликтам FIRST/FIRST и делают невозможным построение предиктивной (LL(1)) таблицы.
Как устраняют непосредственную левую рекурсию (общий приём):
для всех правил вида
$$A\to A{\alpha }_1\mid A{\alpha }_2\mid \cdots \mid {\beta }_1\mid {\beta }_2\mid \dots$$ где каждая ${\beta }_i$ не начинается с $A$, переписывают как
$$A\to {\beta }_1{A}^{\prime }\mid {\beta }_2{A}^{\prime }\mid \dots$$ $$A^{\prime }\to {\alpha }_1{A}^{\prime }\mid {\alpha }_2{A}^{\prime }\mid \cdots \mid \epsilon$$
Применим к нашей грамматике (сохранится приоритет операций):
$$E\to T{E}^{\prime }$$ $$E^{\prime }\to +T{E}^{\prime }\mid -T{E}^{\prime }\mid \epsilon$$ $$T\to F{T}^{\prime }$$ $$T^{\prime }\to \ast F{T}^{\prime }\mid /F{T}^{\prime }\mid \epsilon$$ $$F\to (E)\mid \text{num}$$
Это устраняет левую рекурсию и одновременно сохраняет приоритеты: $T$ (умножение/деление) вложено в $E$ (сложение/вычитание), поэтому умножение имеет более высокий приоритет.
Как устраняют косвенную (непосредственную) левую рекурсию:
- Упорядочить нетерминалы $A_1,\dots ,A_n$.
- Для i от 1 до n: для каждого правила $A_i\to A_j\gamma$ с $j<i$ подставить все правые части $A_j$; затем убрать непосредственную левую рекурсию для $A_i$ стандартным приёмом.
Коротко о значении для LL‑парсеров:
- Устранение левой рекурсии обеспечивает конечность рекурсивного спуска (нет бесконечной левой рекурсии).
- Тогда можно вычислить корректные множества FIRST/FOLLOW и построить единственную предиктивную продукцию — парсер становится детерминированным и эффективным (LL(1) или расширения LL(k)).