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

Question

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

Im имеющие следующие постановки, мне нужно устранить Немедленное леворекурсивные

E⇒E + T/T

E⇒E + T/T

T⇒T * F/T

F⇒ (E)/(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