Исключение левой рекурсии для E := EE+|EE-|id
Вопрос
Как устранить левую рекурсию для следующей грамматики?
E := EE+|EE-|id
Используя общую процедуру:
A := Aa|b
переводится как:
A := b|A'
A' := ϵ| Aa
Применяя это к исходной грамматике, мы получаем:
A = E, a = (E+|E-) and b = id
Следовательно:
E := id|E'
E' := ϵ|E(E+|E-)
Но эта грамматика кажется неверной, потому что
ϵE+ -> ϵ id +
было бы допустимо но это неправильное постфиксное выражение.
Решение
Ваша “обычная процедура” процитирована неправильно.Взяв это из Книги о Драконах:
A := Aα | β
становится
A := βA′
A′ := αA′ | ϵ
... что дает:
E := id E′
E′ := (E + | E -) E′ | ϵ
Не связан с StackOverflow