Removing left recursion in the context of Free Grammar

Question

Trying to figure out how to remove left recursion in the context of free grammars. I'm used to certain forms, but I have a little dazed.

S --> S {S} S | (A) | a
A --> {S} A | epsilon

I also need to develop a decent parser that I can do. However, figuring out this left recursion (especially on the first), I got confused.

Answer 1

There is an interesting Wikipedia article on left recursion. It also has a section on deleting left recursion for non-contextual grammars.

http://en.wikipedia.org/wiki/Left_recursion

Answer 2

Try the following:

S --> a [ { S } S ]
    | ( [ A ] ) [ {S} S ]


A --> { S } [ A ]