Problem over Context Free Grammar Transitive Closure Algorithm

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

Problem over Context Free Grammar Transitive Closure Algorithm

imanewbie
Folks this is a parser for Context Free Grammars, for some reason when I go simplify the grammar trying to remove productions that substitute variables like in the case:
S -> A, A -> B, B -> a, it works perfectly and returns S -> a, the problem is when the root symbol is on the listthat must be replaced as in:
S -> aXa | bXb , X -> a | b | S | £(empty)
instead of returning
S -> aXa | bXb, X -> a | b | £ | aXa | bXb

it ruturns X as
X -> a | b | £ | S <- this S is wrong! it should return X -> a | b | £ | aXa | bXb! Im not sure about where is the mistake. If you can give me hints it would be grat. I will be checking the mail and also hanging over #haskell at freenode ifyou want to contact me directly. Thanks in advance for the help!

Victor

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

CFG.hs (6K) Download Attachment