开发者

Removing Left Recursion in a Context Free Grammar

开发者 https://www.devze.com 2023-01-18 07:37 出处:网络
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.

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 ]
0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号