Re: NFA and negation/conjunction

On Thu, May 13, 2010 at 8:42 PM, Stefan Monnier
<monnier@iro.umontreal.ca> wrote:
> I'm looking for any work that tries to provide negation and/or
> conjunction operations in regexps without using a DFA (or at least
> while avoiding the DFA state explosion problem).
>
> My search has currently come up empty (actually I pretty much haven't
> seen mention of conjunction and negation in regexps other than in
> Brzozowski's derivatives). B So any pointer would be welcome,


Torben Cgidius Mogensen's mail makes a pretty good case that
one can't avoid a lot of effort in the general case. However,
derivatives are a great way to avoid unnecessary effort, because
that formalism can model the concepts directly (in contrast to the
NFA formalism). http://www.ccs.neu.edu/home/turon/re-deriv.pdf
is a recent paper worth looking at. If I needed to implement support
for those concepts, I would start there.


Russ

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