Eliminating Immediate Left Recursion

问题:

I understand that in order to eliminate an immediate left recursion from a grammar containing production of the form A⇒Aα i need to replace it by A⇒βA'and A'⇒αA/∈

Im having the following productions,i need to eliminate immediate left recursion

E⇒E+T/T

E⇒E+T/T

T⇒T*F/T

F⇒(E)/(id)

I can see that after elimination the first production becomes

E⇒TE'

E'⇒+TE'/T∈

Can somebody explain how this comes

回答1:

It's really just a matter of following the algorithm. Let's look at the general case. According to the algorithm a rule of the form:

A => A a1 | ... | A aN | b1 | .. | bN

where A a1, ..., A aN are nonzero left recursive sequences of terminals and nonterminals and b1, ..., bN are sequences of terminals and nonterminals that does not start with the terminal A.

The algorithm says we need to replace this by

A => b1 A' | ... | bN A'
A' => a1 A' | ... | aN A' | epsilon

Let's look at your case. Here we have

E => E + T | T

So you can think of a1 is the sequence + T since E + T is a left recursive sequence of terminals and nonterminals. Likewise you can think of B1 as T since this is a nonleft recursive sequence. We now use this to define the new nonterminal E as:

E => b1 E'

And since b1 is T this becomes

E => T E'

Defining E' we get

E' => a1 E' | epsilon

And since a1 is + T this becomes

E' => + T E' | epsilon 

Thus you end up with the grammar

E => T E'
E' => + T E' | epsilon