Удаление левой рекурсии
Следующая грамматика имеет левую рекурсию
E= E+T|T
T= T*F|F
F= a|b|c
Как удалить его? Есть ли какая-либо общая процедура его?
4 ответа
Да, существует общая процедура, см., Например, Википедия .
E = TE'
E'= (e) | +TE'
T = FT'
T'= (e) | *FT'
F = a | b | c
Следует отметить, что это изменяет ассоциативность + и * слева направо. То есть, если раньше a + b + c анализировался как (a + b) + c , теперь он анализируется как a + (b + c) ].
Это не проблема для сложения и умножения, но это может быть проблема, например, для вычитания и деления.
В статье в Википедии более подробно рассказывается о процедуре удаления левой рекурсии и ее тонкостях.
Как отмечали другие, существует общая процедура замены левой рекурсии правой рекурсией. Другие ответы хорошо показывают, как использовать эту общую процедуру для удаления левой рекурсии в данной грамматике.
Вот решение, которое реструктурирует данную грамматику способом, специфичным для этой грамматики.
E= T+E|T
T= F*T|F
F= a|b|c
продукция
E = E+T
| T
T = T*F
| F
F = a|b|c
переходит в
E= T ('+' T)*
T= F ('*' F)*
F= a|b|c
Для поддержания той же обработки, где дизъюнкция кулака E обрабатывается с помощью A (E, T) . в новой версии используется:
ret = T1;
while(set.more()) ret = A(ret, set.pop_front().T);
Общая процедура, например, находится в Википедии . Я продемонстрирую для E = E + T | T :
E - леворекурсивный нетерминал.
+ T - это ненулевая последовательность (альфа).
T - это последовательность, которая не начинается с E (бета).
Создаем новый нетерминал для «отдыха», т.е. ненулевая последовательность. Это обрабатывает рекурсию.
E '= epsilon | + TE'
И мы модифицируем исходное правило, чтобы использовать новый нетерминал для обработки рекурсии.
E = TE '