Коротко: нужно убрать левую рекурсию и явно зая­вить уровни приоритетов и ассоциативность. Привожу устойчивую LL(1)‑версию и вариант для LALR (через либо переработанную грамматику, либо декларации приоритетов).
1) LL(1)‑грамматика (без левой рекурсии, с приоритетом ${}^{\prime }{\ast }^{\prime }{>}^{\prime }{+}^{\prime }$ и левой ассоциативностью):
$$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$$
Пояснения:
- Уровни соответствуют нетерминалам: $E$ — выражение с суммой, $T$ — терм (умножение), $F$ — фактор. Это гарантирует, что операторы $\ast$ связываются сильнее, чем $+$, потому что в $E$ сначала полностью распознаётся $T$ (включая все $\ast$), и только затем возможны «+».
- Ассоциативность «влево» реализуется хвостовой рекурсией $E^{\prime }\to +T{E}^{\prime }$ и $T^{\prime }\to \ast F{T}^{\prime }$: при построении AST принято сворачивать последовательность справа налево в левую цепочку, что даёт семантику $(a+b)+c$ и $(a\ast b)\ast c$.
- Грамматика не содержит левой рекурсии и удовлетворяет условиям LL(1): для каждого нетерминала множества FIRST альтернатив и FOLLOW при $\epsilon$ являются разделимыми.
2) Вариант для LALR (две возможности)
a) Использовать ту же грамматику, что и для LL(1). Она подходит и для LALR(1) парсеров (нет неоднозначности).
b) Если хотите оставить исходную компактную форму (удобно в Yacc/Bison), разрешить неоднозначности с помощью приоритетов и ассоциативности:
Пример в стиле Yacc/Bison (псевдосинтаксис; порядок деклараций определяет приоритет — более поздние выше):
%left '+'
%left '*'
%%
S : S '+' S
| S '*' S
| '(' S ')'
| id
;
Пояснения:
- Директивы `%left` устанавливают левую ассоциативность для указанных токенов.
- Порядок деклараций делает `*` более приоритетным, чем `+` (в Bison/Yacc позднее объявленные токены имеют больший приоритет).
- При возникновении конфликтов shift/reduce парсер использует эти декларации: при конфликте между `+` и `*` выберется соответствующее разрешение по приоритету; при конфликте с одинаковым приоритетом и `%left` — произойдёт reduce (что даёт левую ассоциативность).
Итого:
- Для LL(1) и детерминированного парсинга безопасно применять приведённую «разложенную» грамматику $E,T,F$.
- Для генераторов LALR можно либо использовать ту же неамбициозную грамматику, либо оставить компактную и разрешать конфликты через объявления приоритета/ассоциативности.