Re: How to rewrite a regexp without word boundaries?

I think Hallvard B Furuseth and Hans Aberg are close to a solution,
since the intersection of 2 regular expressions is a regular
expression (at least for automata theoretic ones), for Perl ones with
captures and backreferences I don't know if that holds (or not).
However, since you are generating an FA, you're dealing with automata
theoretic ones and are safe.


However, if I were attacking this problem, and I might have reason to
over the next year (so I would be glad to correspond further on it), I
would do some case-analysis to prune off easy cases. So, we'll call
our original RE A\bB, such that A & B are both regular expressions.


If your analysis of A or B can tell you what characters A can end with
or B can begin with (and if you are making an FA, you should be able
to get that information), since there has to be a set of states that
correspond to where the \b is to be matched. The edges into and out of
that state will be labelled with the valid characters upon which the
transition can occur. If the ones leading in have characters in the
\w set, the ones leading out must have characters in the \W set and
vice-versa. Note, if one or the other side has characters from both
sets \w and \W, split the state into 2 states, with the \W characters
leading to 1 state and the \w characters leading to the other. I'll
leave the rest of this idea as an exercise to the reader. I'm sure
there are some thorny details that I haven't worked out.


Hope this helps,
-Chris


******************************************************************************
Chris Clark Internet: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. or: compres@world.std.com
23 Bailey Rd Web Site: http://world.std.com/~compres
Berlin, MA 01503 voice: (508) 435-5016
USA fax: (978) 838-0263 (24 hours)
------------------------------------------------------------------------------

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