Начнём с проблемы и затем предложу конкретное преобразование, анализ неоднозначности и способ построения AST.
1) Проблема (пример исходной грамматики)
$$G_0:E\to E+E\mid E\ast E\mid (E)\mid id$$ Эта грамматика леворекурсивна и неоднозначна: при выражении $a+b\ast c$ нет правила приоритета, а при $a-b-c$ невозможно однозначно задать ассоциативность.
2) Преобразование для LL(1) — убрать левую рекурсию и ввести уровни приоритета
Обычно вводят нетерминалы для уровней приоритета (E — сумма, T — произведение, F — фактор). Без левой рекурсии:
$$\begin{array}{rl}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 id\mid number\mid -F(\text{унарный минус})\end{array}$$ Этот приём устраняет левую рекурсию и кодирует приоритет $\ast /$ выше чем $+-$. Для правой ассоциативных операторов (например, возведение в степень \(^\)) используют правую рекурсию:
$$P\to B{}^{}P\mid B$$ (чтобы получить правую ассоциативность).
3) Анализ неоднозначности и LL(1)-корректность
- Неоднозначность исходной грамматики снимается: разделение на уровни приоритета однозначно определяет дерево (если вы однозначно задаёте ассоциативность: E' реализует левую ассоциативность через свёртку слева).
- Для LL(1) нужно, чтобы альтернативы имели раздельные FIRST (и при наличии пустой альтернативы — FIRST ∩ FOLLOW = ∅). В приведённой грамматике FIRST-альтернативы для $E^{\prime }$ — $\{+,-,\epsilon \}$ и для $T^{\prime }$ — $\{\ast ,/,\epsilon \}$. Конфликтов нет. Унарный минус в $F$ распознаётся на позициях начала фактора, а бинарный минус — в $E^{\prime }$ после $T$, поэтому они не конфликтуют.
- При добавлении новых операторов нужно проверять FIRST/FOLLOW для конфликтов и при необходимости делать левое факторирование.
4) Построение AST, сохраняющего приоритет и ассоциативность
- Структура AST: листья — числа/идентификаторы; узлы — бинарные операторы с двумя поддеревьями, унарные — один ребёнок.
- Рекомендуемый приём реализации для левоассоциативных уровней — итеративная свёртка (точно соответствует LL(1)-реализации с правой рекурсией $E^{\prime }$), псевдокод для parseE:
parseE():
left = parseT()
while nextToken in {+, -}:
op = nextToken; consume(op)
right = parseT()
left = new BinOp(op, left, right)
return left
parseT() аналогично для {*, /}:
left = parseF()
while nextToken in {*, /}:
op = nextToken; consume(op)
right = parseF()
left = new BinOp(op, left, right)
return left
parseF():
if nextToken == '-':
consume('-')
child = parseF()
return new UnaryOp('-', child)
if nextToken == '(':
consume('(')
node = parseE()
consume(')')
return node
if nextToken is number or id:
return new Leaf(token)
- Этот алгоритм создаёт левую ассоциативность естественным образом: для $a-b-c$ получится дерево $BinOp{(}^{\prime }{-}^{\prime },BinOp{(}^{\prime }{-}^{\prime },a,b),c)$.
- Для правой ассоциативных операторов (например, \(a^b^c\)) парсер-функция должна использовать рекурсивный разбор правой рекурсии:
parsePower():
left = parseBase()
if nextToken == '^':
consume('^')
right = parsePower()
return new BinOp('^', left, right)
return left
5) Дополнительные замечания
- Если нужны разные приоритеты/ассоциативности, добавьте соответствующие уровни нетерминалов; это автоматически сохранит приоритет в форме дерева (глубина отражает приоритет).
- Перед реализацией проверьте FIRST/FOLLOW для каждой альтернативы чтобы гарантировать LL(1). При конфликте примените левое факторирование или перестройте грамматику.
- Семантические действия (или построение узлов в AST) можно привязать к каждой продукции в генераторе парсера (например, ANTLR, hand-written recursive-descent).
Конец.