0
$\begingroup$

For all regular expressions, is it possible to pre-determine the set of possible positions in which any given sub-expression may be found? If so, is there any existing research on this subject?

Here's some examples of what I have in mind:

  1. For the expression /^f/, we can determine that f must be found as the first character in the input.
  2. For the expression /b$/, we can determine that b must be found as the last character in the input.
  3. For the expression /c.....b/, we cannot determine a fixed position for b, but we can pre-determine that once a c is encountered, a b must be found 6 characters later.

What I've got in mind is the notion of a "guided" regex. E.g. consider example 3 above. Given a regex implementation that can be streamed its input, and an input which can be randomly accessed, we should be able to do better than current implementations by having the regex implementation skip 6 characters ahead once it encounters a c.

Improve this question
$\endgroup$
3
  • $\begingroup$ Do you have in mind something like the Boyer-Moore string-matching algorithm, but generalized to handle regular expressions? $\endgroup$
    – Neal Young
    Dec 19, 2021 at 20:07
  • $\begingroup$ Yes I think so. Do you know of any such algorithms? $\endgroup$
    – eatnumber1
    Dec 19, 2021 at 23:53
  • $\begingroup$ No. But maybe asking if anybody knows of extensions of the Boyer-Moore algorithm to regular expressions (or DFAs, or some restriction thereof) would be a more specific way to ask your question. As worded currently, your aim ("skip characters") is a little vague. $\endgroup$
    – Neal Young
    Dec 20, 2021 at 2:04

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.