Грамматика (контекстно‑свободная, LL(1)-совместимая, учитывает унарный минус и приоритеты):
$$\begin{array}{rl}& \text{Expr}\to \text{Term}\text{Expr’}\\ & \text{Expr’}\to {}^{\prime }{+}^{\prime }\text{Term}\text{Expr’}|{}^{\prime }{-}^{\prime }\text{Term}\text{Expr’}|ϵ\\ & \text{Term}\to \text{Factor}\text{Term’}\\ & \text{Term’}\to {}^{\prime }{\ast }^{\prime }\text{Factor}\text{Term’}|{}^{\prime }{/}^{\prime }\text{Factor}\text{Term’}|ϵ\\ & \text{Factor}\to {}^{\prime }{-}^{\prime }\text{Factor}|{}^{\prime }{(}^{\prime }\text{Expr}{}^{\prime }{)}^{\prime }|\text{NUMBER}\end{array}$$
Пояснения:
- Приоритеты заданы структурой: $\text{Factor}$ (унарный минус, скобки, число) имеет наибольший приоритет, затем $\ast ,/$, затем $+,-$.
- Унарный минус реализован правилом $\text{Factor}{\to }^{\prime }{-}^{\prime }\text{Factor}$, что делает его правооперавативным: $--a$ парсится как $-(-a)$.
- $ϵ$ — пустая продукция.
Как преобразовать в парсер
1) Рекурсивный нисходящий (recursive‑descent, прямой код):
- Для каждой нетерминальной функции написать процедуру, использующую текущее токен/лексему.
- Пример псевдокода (очень сжато):
parseExpr():
parseTerm()
while currentToken in {'+','-'}:
op = consume()
parseTerm()
buildBinary(op)
parseTerm():
parseFactor()
while currentToken in {'*','/'}:
op = consume()
parseFactor()
buildBinary(op)
parseFactor():
if currentToken == '-':
consume()
node = parseFactor()
return makeUnary('-', node)
elif currentToken == '(':
consume(); node = parseExpr(); expect(')'); return node
elif currentToken is NUMBER:
return makeNumber(consume())
- Эта версия использует устранённую левую рекурсию (см. ниже) и является простым LL(1)-парсером при корректной лексеме NUMBER и разделении токенов.
2) Табличный LL(1)-парсер:
- Построить FIRST/FOLLOW для нетерминалов и таблицу разборов; таблица будет однозначна для предложенной грамматики (при корректном лексическом разборе).
- Алгоритм: стек с начальным символом $\text{Expr}$ и входной поток токенов; применять продукцию по таблице.
Возможные проблемы
- Леворекурсия: простая запись вида $\text{Expr}\to \text{Expr}+\text{Term}$ является лево-рекурсивной и не подходит для рекурсивного нисходящего парсера. Решение — факторизация/преобразование в форму с хвостовой продукцией (как в приведённой грамматике с $\text{Expr’}$ и $\text{Term’}$).
- Неоднозначность: грамматика вида $\text{Expr}\to \text{Expr}{}^{\prime }{+}^{\prime }\text{Expr}|\text{Expr}{}^{\prime }{\ast }^{\prime }\text{Expr}|\dots$ без явного задания приоритетов/ассоциативности будет неоднозначна. В приведённой грамматике приоритеты и левосторонняя ассоциативность для $+,-$ и $\ast ,/$ закодированы структурой (она не неоднозначна).
- Унарный vs бинарный минус: конфликт решается грамматикой контекстно (в позициях начала факторa минус трактуется как унарный, в позиции после терма — как бинарный в $\text{Expr’}$). В лексере/парсере надо отличать только токен '-'; грамматика и алгоритм разбора однозначно определяют роль.
- LR‑парсер: для bottom‑up парсеров возможны shift/reduce конфликты для грамматик с неявными приоритетами; решается либо явным определением приоритетов/ассоциативности, либо использованием той же факторизованной грамматики.
- Error‑recovery и лексические детали (пробелы, целые/вещественные числа, идентификаторы) нужно реализовать отдельно.
Итого: использовать предложенную LL(1)-грамматику, реализовать рекурсивный нисходящий парсер по шаблону parseExpr/parseTerm/parseFactor; избегать исходной леворекурсивной формы и неявных приоритетов, чтобы устранить неоднозначности.