Удаление левой рекурсии

Question

Следующая грамматика вышла из рекурсии

E= E+T|T
T= T*F|F
F= a|b|c

Как это убрать? Есть ли какая-нибудь общая процедура для этого?

Answer 1

Да, есть общая процедура, см., Например, википедия .

E = TE'
E'= (e) | +TE'
T = FT'
T'= (e) | *FT'
F = a | b | c

Следует отметить, что это изменяет ассоциативность + и * слева направо. То есть, если раньше a + b + c был проанализирован как (a + b) + c, теперь он проанализирован как a + (b + c).

Это не проблема сложения и умножения, но, например, проблема вычитания и деления.

Статья в Википедии содержит более подробную информацию о процедуре удаления левой рекурсии и ее тонкостях.

Answer 2

Общая процедура находится в Википедии , например. Я покажу за E = E+T|T:

E - леворекурсивный нетерминал. +T - ненулевая последовательность (альфа). T - это последовательность, которая не начинается с E (бета).

Мы создаем новый нетерминал для «остальных», т.е. ненулевая последовательность. Это обрабатывает рекурсию.

E' = epsilon|+TE'

И мы модифицируем исходное правило, чтобы использовать новый нетерминал для обработки рекурсии.

E = TE'

Answer 3

Как уже отмечали другие, существует общая процедура замены левой рекурсии на правую рекурсию. Другие ответы хорошо показывают, как использовать эту общую процедуру для удаления левой рекурсии в данной грамматике.

Вот решение, которое реструктурирует данную грамматику способом, специфичным для этой грамматики.

E= T+E|T
T= F*T|F
F= a|b|c

Answer 4

производство

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);