[?] equivalence of regular expressions

Hello:


In version 2.0 of LPM, I have introduced prefiltering through parent
patterns, roughly equivalent to:


        parent RE: c.{2}[ed]
        child RE: (care|cave|card|cold)


What I want to be able to do during the compilation phase is determine
whether a given child rule satisfies a parent rule, to prevent rules that
could never match anything, such as:


        parent RE: c.{2}[ed]
        child RE: (dog|cat|fish)


One idea I have for this is to have the compiler generate a minimal literal
string that satisfies the child RE, and then apply the parent RE to that
minimal string, and see if they match. For instance, suppose we have the
RE's:


        parent RE: c.{2}[ed]
        child RE: c[a-z][A-Z]d


The child rule minimal literal would be "caAd" and would match parentRE, and
therefore, this inheritance would be allowed. This is a hack dreamed up in
a caffeine enhanced stupor, however, and I would like to do it "right."


Any pointers?


--
Quinn Tyler Jackson


email: qjackson@wave.home.com
url: http://www.qtj.net/~quinn/
ftp: qtj.net
--

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