<p>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?</p>
<p>Here's some examples of what I have in mind:</p>
<ol>
<li>For the expression <code>/^f/</code>, we can determine that <code>f</code> must be found as the first character in the input.</li>
<li>For the expression <code>/b$/</code>, we can determine that <code>b</code> must be found as the last character in the input.</li>
<li>For the expression <code>/c.....b/</code>, we cannot determine a fixed position for <code>b</code>, but we can pre-determine that once a <code>c</code> is encountered, a <code>b</code> must be found 6 characters later.</li>
</ol>
<p>What I've got in mind is the notion of a &quot;guided&quot; 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 <code>c</code>.</p>

CC BY-SA 4.0
2021-12-19T20:07:01.573Z
Do you have in mind something like the [Boyer-Moore string-matching algorithm](https://en.wikipedia.org/wiki/Boyer–Moore_string-search_algorithm), but generalized to handle regular expressions?
Neal Young
CC BY-SA 4.0
2021-12-19T23:53:47.203Z
Yes I think so. Do you know of any such algorithms?
eatnumber1
CC BY-SA 4.0
2021-12-20T02:04:30.540Z
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.
Neal Young
<regular-expressions>
Regex: Pre-determining the position of matching characters
eatnumber1
# Regex: Pre-determining the position of matching characters

(Asked by: username_0 on 2021-12-19)

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`.

**Tags:** regular-expressions

> **Comments:**
> **username_1**: Do you have in mind something like the [Boyer-Moore string-matching algorithm](https://en.wikipedia.org/wiki/Boyer–Moore_string-search_algorithm), but generalized to handle regular expressions?  
> **username_0**: Yes I think so. Do you know of any such algorithms?  
> **username_1**: 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.  

---

## 0 answers

