Re: RE's to CFG's

"Philip Fortomas" <>
20 Dec 2000 17:23:13 -0500

          From comp.compilers

Related articles
RE's to CFG's (Clive Minnican) (2000-12-18)
Re: RE's to CFG's (Chris F Clark) (2000-12-19)
Re: RE's to CFG's (Philip Fortomas) (2000-12-20)
| List of all articles for this month |

From: "Philip Fortomas" <>
Newsgroups: comp.compilers
Date: 20 Dec 2000 17:23:13 -0500
Organization: Virgin Net Usenet Service
References: 00-12-070
Keywords: lex, DFA
Posted-Date: 20 Dec 2000 17:23:13 EST


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

Post a followup to this message

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