Why do regex engines allow / automatically attempt matching at the end of the input string?

Question

<sup>Note:
* Python is used to illustrate behaviors, but this question is language-agnostic.
* For the purpose of this discussion, assume single-line input only, because the presence of newlines (multi-line input) introduces variations in behavior of $ and . that are incidental to the questions at hand.</sup>

Most regex engines:

• accept a regex that explicitly tries to match an expression after the end of the input string^[1].

  $ python -c "import re; print(re.findall('$.*', 'a'))"
  [''] # !! Matched the hypothetical empty string after the end of 'a'
  

• when finding / replacing globally, i.e., when looking for all non-overlapping matches of a given regex, and having reached the end of the string, unexpectedly try to match again^[2], as explained in this answer to a related question:

  $ python -c "import re; print(re.findall('.*$', 'a'))"
  ['a', ''] # !! Matched both the full input AND the hypothetical empty string
  

Perhaps needless to say, such match attempts succeed only if the regex in question matches the empty string (and the regex by default / is configured to report zero-length matches).

These behaviors are at least at first glance counter-intuitive, and I wonder if someone can provide a design rationale for them, not least because:

• it's not obvious what the benefit of this behavior is.
• conversely, in the context of finding / replacing globally with patterns such as .* and .*$, the behavior is downright surprising.^[3]
  • To ask the question more pointedly: Why does functionality designed to find multiple, non-overlapping matches of a regex - i.e., global matching - decide to even attempt another match if it knows that the entire input has been consumed already, irrespective of what the regex is (although you'll never see the symptom with a regex that doesn't at least also match the empty string)
  • The following languages/engines exhibit the surprising behavior: .NET, Python (both 2.x and 3.x)^[2], Perl (both 5.x and 6.x), Ruby, Node.js (JavaScript)

---

Note that regex engines vary in behavior with respect to where to continue matching after a zero-length (empty-string) match.

Either choice (start at the same character position vs. start at the next) is defensible - see the chapter on zero-length matches at www.regular-expressions.info.

By contrast, the .*$ case discussed here is different in that, with any non-empty input, the first match for .*$ is not a zero-length match, so the behavior difference does not apply - instead, the character position should advance unconditionally after the first match, which of course is impossible if you're already at the end.
Again, my surprise is at the fact that another match is attempted nonetheless, even though there's by definition nothing left.

---

^{[1] I'm using $ as the end-of-input marker here, even though in some engines, such as .NET's, it can mark the end the end of the input optionally followed by a trailing newline. However, the behavior equally applies when you use the unconditional end-of-input marker, \z.}

^{[2] Python 2.x and 3.x up to 3.6.x seemingly special-cased replacement behavior in this context: python -c "import re; print(re.sub('.*$', '[\g<0>]', 'a'))" used to yield just [a] - that is, only one match was found and replaced.
Since Python 3.7, the behavior is now like in most other regex engines, where two replacements are performed, yielding [a][].}

^{[3] You can avoid the problem by either (a) choosing a replacement method that is designed to find at most one match or (b) use ^.* to prevent multiple matches from being found via start-of-input anchoring.
(a) may not be an option, depending on how a given language surfaces functionality; for instance, PowerShell's -replace operator invariably replaces all occurrences; consider the following attempt to enclose all array elements in "...":
'a', 'b' -replace '.*', '"$&"'. Due to matching twice, this yields elements "a""" and "b""";
option (b), 'a', 'b' -replace '^.*', '"$&"', fixes the problem.}

Answer 1

I am giving this answer just to demonstrate why a regex would want to allow any code appearing after the final $ anchor in the pattern. Suppose we needed to create a regex to match a string with the following rules:

• starts with three numbers
• followed by one or more letters, numbers, hyphen, or underscore
• ends with only letters and numbers

We could write the following pattern:

^\d{3}[A-Za-z0-9\-_]*[A-Za-z0-9]$

But this is a bit bulky, because we have to use two similar character classes adjacent to each other. Instead, we could write the pattern as:

^\d{3}[A-Za-z0-9\-_]+$(?<!_|-)

or

^\d{3}[A-Za-z0-9\-_]+(?<!_|-)$

Here, we eliminated one of the character classes, and instead used a negative lookbehind after the $ anchor to assert that the final character was not underscore or hyphen.

Other than a lookbehind, it makes no sense to me why a regex engine would allow something to appear after the $ anchor. My point here is that a regex engine may allow a lookbehind to appear after the $, and there are cases for which it logically makes sense to do so.

Answer 2

Recall several things:

1. ^ and $ are zero width assertions - they match right after the logical start of the string (or after each line ending in multiline mode with the m flag in most regex implementations) or at the logical end of string (or end of line BEFORE the end of line character or characters in multiline mode.)

2. .* is potentially a zero length match of no match at all. The zero length only version would be $(?:end of line){0} DEMO (which is useful as a comment I guess...)

3. . does not match \n (unless you have the s flag) but does match the \r in Windows CRLF line endings. So $.{1} only matches Windows line endings for example (but don't do that. Use the literal \r\n instead.)

There is no particular benefit other than simple side effect cases.

1. The regex $ is useful;
2. .* is useful.
3. The regex ^(?a lookahead) and (?a lookbehind)$ are common and useful.
4. The regex (?a lookaround)^ or $(?a lookaround) are potentially useful.
5. The regex $.* is not useful and rare enough to not warrant implementing some optimization to have the engine stop looking with that edge case. Most regex engines do a decent job of parsing syntax; a missing brace or parenthesis for example. To have the engine parse $.* as not useful would require parsing meaning of that regex as different than $(something else)
6. What you get will be highly dependent on the regex flavor and the status of the s and m flags.

For examples of replacements, consider the following Bash script output from some major regex flavors:

#!/bin/bash

echo "perl"
printf  "123\r\n" | perl -lnE 'say if s/$.*/X/mg' | od -c
echo "sed"
printf  "123\r\n" | sed -E 's/$.*/X/g' | od -c
echo "python"
printf  "123\r\n" | python -c "import re, sys; print re.sub(r'$.*', 'X', sys.stdin.read(),flags=re.M) " | od -c
echo "awk"
printf  "123\r\n" | awk '{gsub(/$.*/,"X")};1' | od -c
echo "ruby"
printf  "123\r\n" | ruby -lne 's=$_.gsub(/$.*/,"X"); print s' | od -c

Prints:

perl
0000000    X   X   2   X   3   X  \r   X  \n                            
0000011
sed
0000000    1   2   3  \r   X  \n              
0000006
python
0000000    1   2   3  \r   X  \n   X  \n                                
0000010
awk
0000000    1   2   3  \r   X  \n                                        
0000006
ruby
0000000    1   2   3   X  \n                                            
0000005

Answer 3

What is the reason behind using .* with global modifier on? Because someone somehow expects an empty string to be returned as a match or he / she isn't aware of what * quantifier is, otherwise global modifier shouldn't be set. .* without g doesn't return two matches.

it's not obvious what the benefit of this behavior is.

There shouldn't be a benefit. Actually you are questioning zero-length matches existence. You are asking why does a zero-length string exist?

We have three valid places that a zero-length string exists:

• Start of subject string
• Between two characters
• End of subject string

We should look for the reason rather than the benefit of that second zero-length match output using .* with g modifier (or a function that searches for all occurrences). That zero-length position following an input string has some logical uses. Below state diagram is grabbed from debuggex against .* but I added epsilon on the direct transition from start state to accept state to demonstrate a definition:

_{(source: pbrd.co)}

That's a zero-length match (read more about epsilon transition).

These all relates to greediness and non-greediness. Without zero-length positions a regex like .?? wouldn't have a meaning. It doesn't attempt the dot first, it skips it. It matches a zero-length string for this purpose to transit the current state to a temporary acceptable state.

Without a zero-length position .?? never could skip a character in input string and that results in a whole brand new flavor.

Definition of greediness / laziness leads into zero-length matches.

Answer 4

^Note:

• My question post contains two related, but distinct questions, for which I should have created separate posts, as I now realize.
• The other answers here focus on one of the questions each, so in part this answer provides a road map to what answers address which question.

---

As for why patterns such as $<expr> are allowed (i.e., matching something after the input's end) / when they make sense:

• dawg's answer argues that nonsensical combinations such as $.+ probably aren't prevented for pragmatic reasons; ruling them out may not be worth the effort.

• Tim's answer shows how certain expressions can make sense after $, namely negative lookbehind assertions.

• The second half of ivan_pozdeev's answer answer cogently synthesizes dawg's and Tim's answers.

---

As for why global matching finds two matches for patterns such as .* and .*$:

• revo's answer contains great background information about zero-length (empty-string) matching, which is what the problem ultimately comes down to.

Let me complement his answer by relating it more directly to how the behavior contradicts my expectations in the context of global matching:

• From a purely common-sense perspective, it stands to reason that once the input has been fully consumed while matching, there is by definition nothing left, so there is no reason to look for further matches.

• By contrast, most regex engines consider the character position after the last character of the input string - the position known as end of subject string in some engines - a valid starting position for a match and therefore attempt another one.

  • If the regex at hand happens to match the empty string (produces a zero-length match; e.g., regexes such as .*, or a?), it matches that position and returns an empty-string match.

  • Conversely, you won't see an extra match if the regex doesn't (also) match the empty string - while the additional match is still attempted in all cases, no match will be found in this case, given that the empty string is the only possible match at the end-of-subject-string position.

While this provides a technical explanation of the behavior, it still doesn't tell us why matching after the last character was implemented.

The closest thing we have is an educated guess by Wiktor Stribiżew in a comment (emphasis added), which again suggests a pragmatic reason for the behavior:

... as when you get an empty string match, you might still match the next char that is still at the same index in the string. If a regex engine did not support it, these matches would be skipped. Making an exception for the end of string was probably not that critical for regex engine authors.

The first half of ivan_pozdeev's answer explains the behavior in more technical detail by telling us that the void at the end of the [input] string is a valid position for matching, just like any other character-boundary position.
However, while treating all such positions the same is certainly internally consistent and presumably simplifies the implementation, the behavior still defies common sense and has no obvious benefit to the user.

---

Further observations re empty-string matching:

^{Note: In all code snippets below, global string replacement is performed to highlight the resulting matches: each match is enclosed in [...], whereas non-matching parts of the input are passed through as-is.}

In summary, 3 different, independent behaviors apply in the context of empty(-string) matches, and different engines use different combinations:

• Whether the POSIX ERE spec's longest leftmost rule^{Thanks, revo.} is obeyed.

• In global matching:

  • Whether or not the character position is advanced after an empty match.
  • Whether or not another match is attempted for the by-definition empty string at the very end of the input (the 2nd question in my question post).

Matching at the end-of-subject-string position is not limited to those engines where matching continues at the same character position after an empty match.

For instance, the .NET regex engine does not do so (PowerShell example):

PS> 'a1' -replace '\d*|a', '[$&]'
[]a[1][]

That is:

• \d* matched the empty string before a
• a itself then did not match, which implies that the character position was advanced after the empty match.
• 1 was matched by \d*
• The end-of-subject-string position was again matched by \d*, resulting in another empty-string match.

Perl 5 is an example of an engine that does resume matching at the same character position:

$ "a1" | perl -ple "s/\d*|a/[$&]/g"
[][a][1][]

Note how a was matched too.

Interestingly, Perl 6 not only behaves differently, but exhibits yet another behavior variant:

$ "a1" | perl6 -pe "s:g/\d*|a/[$/]/"
[a][1][]

Seemingly, if an alternation finds both and empty and a non-empty match, only the non-empty one is reported.

Perl 6's behavior appears to be following the longest leftmost rule.

While sed and awk do as well, they don't attempt another match at the end of the string:

sed, both the BSD/macOS and GNU/Linux implementations:

$ echo a1 | sed -E 's/[0-9]*|a/[&]/g'
[a][1]

awk - both the BSD/macOS and GNU/Linux implementations as well as mawk:

$ echo a1 | awk '1 { gsub(/[0-9]*|a/, "[&]"); print }'
[a][1]

Answer 5

"Void at the end of the string" is a separate position for regex engines because a regex engine deals with positions between input characters:

|a|b|c|   <- input line

^ ^ ^ ^
positions at which a regex engine can "currently be"

All other positions can be described as "before Nth character" but for the end, there's no character to refer to.

As per Zero-Length Regex Matches -- Regular-expressions.info, it's also needed to support zero-length matches (which not all regex flavors support):

• E.g. a regex \d* over string abc would match 4 times: before each letter, and at the end.

---

$ is allowed anywhere in the regex for uniformity: it's treated the same as any other token and matches at that magical "end of string" position. Making it "finalize" the regex work would lead to an unnecessary inconsistency in engine work and prevent other useful things that can match there, like e.g. lookbehind or \b (basically, anything that can be a zero-length match) -- i.e. would be both a design complication and a functional limitation with no benefit whatsoever.

---

Finally, to answer why a regex engine may or may not try to match "again" at the same position, let's refer to Advancing After a Zero-Length Regex Match -- Zero-Length Regex Matches -- Regular-expressions.info:

Say we have the regex \d*|x, the subject string x1

The first match is a blank match at the start of the string. Now, how do we give other tokens a chance while not getting stuck in an infinite loop?

The simplest solution, which is used by most regex engines, is to start the next match attempt one character after the end of the previous match

This may give counterintuitive results -- e.g. the above regex will match '' at start, 1 and '' at the end -- but not x.

The other solution, which is used by Perl, is to always start the next match attempt at the end of the previous match, regardless of whether it was zero-length or not. If it was zero-length, the engine makes note of that, as it must not allow a zero-length match at the same position.

Which "skips" matches less at the cost of some extra complexity. E.g. the above regex will produce '', x, 1 and '' at the end.

The article goes on to show that there aren't established best practices here and various regex engines are actively trying new approaches to try and produce more "natural" results:

One exception is the JGsoft engine. The JGsoft engine advances one character after a zero-length match, like most engines do. But it has an extra rule to skip zero-length matches at the position where the previous match ended, so you can never have a zero-length match immediately adjacent to a non-zero-length match. In our example the JGsoft engine only finds two matches: the zero-length match at the start of the string, and 1.

Python 3.6 and prior advance after zero-length matches. The gsub() function to search-and-replace skips zero-length matches at the position where the previous non-zero-length match ended, but the finditer() function returns those matches. So a search-and-replace in Python gives the same results as the Just Great Software applications, but listing all matches adds the zero-length match at the end of the string.

Python 3.7 changed all this. It handles zero-length matches like Perl. gsub() does now replace zero-length matches that are adjacent to another match. This means regular expressions that can find zero-length matches are not compatible between Python 3.7 and prior versions of Python.

PCRE 8.00 and later and PCRE2 handle zero-length matches like Perl by backtracking. They no longer advance one character after a zero-length match like PCRE 7.9 used to do.

The regexp functions in R and PHP are based on PCRE, so they avoid getting stuck on a zero-length match by backtracking like PCRE does. But the gsub() function to search-and-replace in R also skips zero-length matches at the position where the previous non-zero-length match ended, like gsub() in Python 3.6 and prior does. The other regexp functions in R and all the functions in PHP do allow zero-length matches immediately adjacent to non-zero-length matches, just like PCRE itself.

Answer 6

I don't know where the confusion comes from.
Regex engines are basically stupid.
They're like Mikey, they'll eat anything.

$ python -c "import re; print(re.findall('$.*', 'a'))"
[''] # !! Matched the hypothetical empty string after the end of 'a'

You could put a thousand optional expressions after $ and it will still match the
EOS. Engines are stupid.

$ python -c "import re; print(re.findall('.*$', 'a'))"
['a', ''] # !! Matched both the full input AND the hypothetical empty string

Think of it this way, there are two independent expressions here
.* | $. The reason is the first expression is optional.
It just happens to butt against the EOS assertion.
Thus you get 2 matches on a non-empty string.

Why does functionality designed to find multiple, non-overlapping matches of a regex - i.e., global matching - decide to even attempt another match if it knows that the entire input has been consumed already,

The class of things called assertions don't exist at character positions.
They exist only BETWEEN character positions.
If they exist in the regex, you don't know if the entire input has been consumed.
If they can be satisfied as an independent step, but only once, they will match
independently.

Remember, regex is a left-to-right proposition.
Also remember, engines are stupid.
This is by design.
Each construct is a state in the engine, it's like a pipeline.
Adding complexity will surely doom it to failure.

As an aside, does .*a actually start from the beginning and check each character ?
No. .* immediately starts at the end of string (or line, depending) and starts
backtracking.

Another funny thing. I see a lot of novices using .*? at the end of their
regex, thinking it will get all the remaining kruft from the string.
It's useless, it will never match anything.
Even a standalone .*? regex will always match nothing for as many characters
there are in the string.

Good luck! Don't fret it, regex engines are just ... well, stupid.