# Removing left recursion with terminals only

I have a grammar:

$$G → id > id$$
$$| id < id$$
$$| G and id$$

Does anybody know how I can do left recursive elimination on this one, when it doesn't have any extra non terminals?

• What follows the recursive non-terminal is irrelevant. It could be any non-empty sequence of terminals and non-terminals. However, I don't believe that grammar describes the language you're interested.in describing. – rici Feb 3 at 21:45
• @rici well the task of the exercise was to 1) remove left recursion (where possible) this creates grammar G' and 2) change G' to left factored grammar (where possible) this creates grammar G'' .I thought that you need to remove the left recursion because in the third or, it would never reach 'and' and 'id', no? i.e. how do I change it so that the third part wouldn't be endless recursion? Thanks! – Samuel V. Feb 4 at 14:17
• There's a simple algorithm to remove direct left recursion, here on Wikipedia. I'm sure that same algorithm is in your course materials. It is not affected by the rest of the production whose left recursion you are removing. – rici Feb 4 at 15:58

## 1 Answer

You'll need to introduce a new non-terminal to factor this, like:

\begin{align*} G &\to id A \\ A &\to < id \mid > id \end{align*}

Then you'll need to get rid of the left recursion.