How to implement a left recursion eliminator?

Question

How can i implement an eliminator for this?

 A := AB |
      AC |
      D  |
      E  ;

Answer 1

This is an example of so called immediate left recursion, and is removed like this:

A := DA' |
     EA' ;

A' := ε   |
      BA' |
      CA' ;

The basic idea is to first note that when parsing an A you will necessarily start with a D or an E. After the D or an E you will either end (tail is ε) or continue (if we're in a AB or AC construction).

The actual algorithm works like this:

For any left-recursive production like this: A -> A a1 | ... | A ak | b1 | b2 | ... | bm replace the production with A -> b1 A' | b2 A' | ... | bm A' and add the production A' -> ε | a1 A' | ... | ak A'.

See Wikipedia: Left Recursion for more information on the elimination algorithm (including elimination of indirect left recursion).

Answer 2

Another form available is:

A := (D | E) (B | C)*

The mechanics of doing it are about the same but some parsers might handle that form better. Also consider what it will take to munge the action rules along with the grammar its self; the other form requires the factoring tool to generate a new type for the A' rule to return where as this form doesn't.