Re: How to do this odd kind of regex match?

Tony Finch wrote:
> Can anyone point me in the direction of literature on matching regexes
> with capturing brackets (as in sed) efficiently, i.e. without using a
> backtracking NFA. Is it possible to do with a DFA?


I'm not sure what you mean - if what you want to know which parts of the
regex matched what part of the input, Henry Spencer's regex engine will
do fine. AFAIK it's doing all the pattern matching with a DFA, so you
should be just fine.


> I'd also like to be able to match several regexes against the same
> text in parallel, preferably without running N regex engines in
> parallel. This is different from the standard tokenization problem
> because the several matches may overlap rather than occurring one
> after the other.


I think this isn't too difficult to do, but you'll probably have to roll
your own engine - I don't think the Spencer engine can to this.


I'd start constructing an NFA, with start and accept states for the
subexpressions that interest you.
The DFA might have to encode many substart and subaccept states in its
states, and you might end up assigning the same input text to many
different parts of the RE. For pathological cases, this might be worse
than exponential: think '(A|AA)*', applied to a string of a million As...
But these caveats don't touch the NFA->DFA transformation, so this
should work.


HTH
Joachim

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