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

Question

Я понимаю, что для того, чтобы исключить немедленную левую рекурсию из грамматики, содержащей произведение формы A⇒Aα, мне нужно заменить ее на A⇒βA'and A'⇒αA / ∈

У меня есть следующие производства, мне нужно устранить немедленную левую рекурсию

E⇒E + T / T

E⇒E + T / T

T⇒T * Ф / Т

F⇒ (Е) / (ID)

Я вижу, что после ликвидации первая продукция становится

E⇒TE"

E'⇒ + TE '/ t∈

Может кто-нибудь объяснить, как это происходит

Answer 1

Это действительно просто следование алгоритму. Давайте посмотрим на общий случай. По алгоритму правило вида:

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