Начальная грамматика:
$$E\to E+T\mid T;T\to T\ast F\mid F;F\to (E)\mid id$$
Правило устранения немедленной левой рекурсии: для формы $A\to A\alpha \mid \beta$ заменить на
$$A\to \beta A^{\prime };A^{\prime }\to \alpha A^{\prime }\mid \epsilon$$
Применяя это к $E$ и $T$, получаем грамматику, пригодную для рекурсивного нисходящего парсера:
$$E\to T{E}^{\prime }$$ $$E^{\prime }\to +T{E}^{\prime }\mid \epsilon$$ $$T\to F{T}^{\prime }$$ $$T^{\prime }\to \ast F{T}^{\prime }\mid \epsilon$$ $$F\to (E)\mid id$$
Краткое пояснение: левой рекурсии нет, порядок правил сохраняет приоритеты операций ($\ast$ выше $+$). Для реализации в рекурсивном нисходящем парсере удобно реализовать $E^{\prime }$ и $T^{\prime }$ как циклы: например
parseE():
- node = parseT()
- while lookahead == '+': consume('+'); rhs = parseT(); node = makePlus(node, rhs)
- return node
parseT() аналогично для '*'.
Эта грамматика пригодна для рекурсивного нисходящего парсера и позволяет построить левоассоциативные суммы и произведения.