Removing Left Recursion in a Context Free Grammar

问题:

Trying to figure out removing left recursion in context free grammars. I'm used to certain forms, but this one has me a bit boggled.

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

I also have to design a decent parser, which I can do. However, figuring out this left recursion (especially on the first one) has me confused.

回答1:

There is an interesting Wikipedia article on left-recursion. It also has a section about removing left-recursion for non-context grammars.

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

回答2:

Try this:

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


A --> { S } [ A ]