Коротко и по делу.
1) Преобразование грамматики в однозначную (задать приоритет и ассоциативность: $\ast$ выше, обе — левосторонние):
$$E\to E+T\mid T$$ $$T\to T\ast F\mid F$$ $$F\to (E)\mid id$$
Эта грамматика однозначна: она задаёт приоритет $\ast$ над $+$ и лево‑ассоциативность обоих операторов.
Для удобства парсинга верхнего уровня (убрать левую рекурсию) эквивалентная LL‑форма:
$$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$$
2) Алгоритм парсинга
- Для LL(1) (рекурсивный спуск, predictive parsing) можно реализовать функции:
parseE():
parseT()
parseEprime()
parseEprime():
if (current == '+') { consume('+'); parseT(); parseEprime(); }
else return
parseT():
parseF()
parseTprime()
parseTprime():
if (current == '*') { consume('*'); parseF(); parseTprime(); }
else return
parseF():
if (current == '(') { consume('('); parseE(); consume(')'); }
else if (current == id) consume(id);
else error
(Лексемы и ошибки — стандартно.)
- Для LR‑парсеров (LR(0)/SLR(1)/LALR(1)/LR(1)) можно взять исходную (лево-рекурсивную) форму
$$E\to E+E\mid E\ast E\mid (E)\mid id$$ но лучше использовать однозначную с разделением уровней (первые правила выше). LR‑парсер автоматически управляет левой рекурсией и ассоциативностью; при конфликтах применяют декларации приоритета/ассоциативности или переписывают грамматику.
3) Когда нужна более мощная модель (LR vs LL)
- LL(1) (рекурсивный спуск) прост и прозрачен, но требует:
- отсутствие левой рекурсии (надо её устранять),
- отсутствие неоднозначных выборов без достаточного lookahead,
- грамматика должна быть LL(1) (или преобразуема в неё).
- LR (особенно LALR(1) / LR(1)) мощнее:
- поддерживает левую рекурсию напрямую,
- допускает больше конструкций (непрямое/жёсткое факторирование, более сложные разветвления),
- лучше справляется с грамматиками реальных языков (C, Java) и с конфликтами, которые трудно устранить для LL(1).
Примеры, когда нужен LR:
- грамматика не может быть преобразована в LL(1) без существенной потери структуры,
- конструкции с «развешенным» контекстом (dangling else — хотя его часто решают приоритетом),
- необходимость точного анализа без ручного переписывания множества правил.
Вывод: для арифметики достаточно LL(1)‑грамы (представленной выше) и рекурсивного спуска; для сложных языков и грамматик с леворекурсией/конфликтами предпочтителен LR‑парсер.