Это действительно вопрос соблюдения алгоритма. Давайте посмотрим на общий случай. Согласно алгоритму правила следующего вида:
A => A a1 | ... | A aN | b1 | .. | bN
где A a1, ..., A aN
ненулевые левые рекурсивные последовательности терминалов и нетерминалов и b1, ..., bN
представляют собой последовательность терминалов и нетерминалов, которые не начинаются с терминалом A
.
алгоритм говорит, что мы должны заменить это на
A => b1 A' | ... | bN A'
A' => a1 A' | ... | aN A' | epsilon
Давайте посмотрим на ваш случай. Здесь мы имеем
E => E + T | T
Таким образом, вы можете думать о a1
является последовательностью + T
так E + T
является левой рекурсивной последовательностью терминалов и нетерминалов. Точно так же вы можете думать о B1
как T
, так как это нелеточная рекурсивная последовательность. Теперь мы используем это, чтобы определить новый нетерминал E
как:
E => b1 E'
И поскольку b1
является T
это становится
E => T E'
Определение E'
мы получаем
E' => a1 E' | epsilon
И поскольку a1
является + T
это становится
E' => + T E' | epsilon
Таким образом, вы в конечном итоге с грамматикой
E => T E'
E' => + T E' | epsilon
Выглядит очень похоже на [cs.se] вопрос (скорее всего, будет лучше подходит на этом сайте). – Dukeling