Re: RE's to CFG's

Clive,


As John suggests, RegExps (or, better, Regular Grammars defining the
corresponding RegExps) are a pure subset of CFGs. There are ways that
you can use a sample set of regular expressions to derive the Regular
Grammar that will parse all of them in their entirety. I used the
technique while doing a BSc. The process is quite lengthy (and not
absolutely error-free). If you are interested, I will find the
lecture notes and post a further message. I remember that from the
regular grammar that was derived, by using suitable branch merging and
a bit of recursion you could end up with a CFG that would parse all of
the RegExps that were in the sample set and (obviously) more that were
not included in the original specification.


Best Regards
Philip Fortomas
philip.fortomas@virgin.net

Return to the comp.compilers page.
Search the comp.compilers archives again.