Вопрос #1585983
Дана контекстно-свободная грамматика, порождающая арифметические выражения с левой рекурсией: E -> E + T | T; T -> T * F | F; F -> (E) | id — уберите левую рекурсию и преобразуйте грамматику в форму, пригодную для построения рекурсивного нисходящего парсера
\[
E \to E + T \mid T;\quad T \to T * F \mid F;\quad F \to (E) \mid id
\]
Правило устранения немедленной левой рекурсии: для формы \(A \to A\alpha \mid \beta\) заменить на
\[
A \to \beta A';\qquad A' \to \alpha A' \mid \varepsilon
\]
Применяя это к \(E\) и \(T\), получаем грамматику, пригодную для рекурсивного нисходящего парсера:
\[
E \to T\ E'
\]
\[
E' \to +\ T\ E' \mid \varepsilon
\]
\[
T \to F\ T'
\]
\[
T' \to *\ F\ T' \mid \varepsilon
\]
\[
F \to (\,E\,) \mid id
\]
Краткое пояснение: левой рекурсии нет, порядок правил сохраняет приоритеты операций (\(*\) выше \(+\)). Для реализации в рекурсивном нисходящем парсере удобно реализовать \(E'\) и \(T'\) как циклы: например
parseE():
- node = parseT()
- while lookahead == '+': consume('+'); rhs = parseT(); node = makePlus(node, rhs)
- return node
parseT() аналогично для '*'.
Эта грамматика пригодна для рекурсивного нисходящего парсера и позволяет построить левоассоциативные суммы и произведения.