Trying to figure out re开发者_JS百科moving 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.
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
Try this:
S --> a [ { S } S ]
| ( [ A ] ) [ {S} S ]
A --> { S } [ A ]
精彩评论