[?] equivalence of regular expressions

"Quinn Tyler Jackson" <qjackson@wave.home.com>
5 Aug 1998 22:23:48 -0400

          From comp.compilers

Related articles
[?] equivalence of regular expressions qjackson@wave.home.com (Quinn Tyler Jackson) (1998-08-05)
Re: [?] equivalence of regular expressions bromage@cs.mu.OZ.AU (1998-08-10)
| List of all articles for this month |

From: "Quinn Tyler Jackson" <qjackson@wave.home.com>
Newsgroups: comp.compilers
Date: 5 Aug 1998 22:23:48 -0400
Organization: Compilers Central
Keywords: lex, theory, question


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

        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

Post a followup to this message

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