Which Match You Actually Get, and Why Two Engines Disagree
Last timeThe Parts That Are Not Really Patterns
One pattern, one line and four different answers, worked out position by position: greedy against lazy, leftmost first against leftmost longest, and where a captured group comes from.
A pattern that matches is only half an answer. A line of text usually offers
several positions where a pattern could start and several lengths it could run
for, and something has to pick one. That choice is not made by the pattern on
its own. It is made by a rule the engine follows, and the two rules in wide use
are genuinely different rules, so one pattern on one line gives a four character
answer in one language and a six character answer in another.
Everything below is worked on one line of text, nineteen characters long, with
positions numbered from zero:
say "a\"b" then "c"
Position 0 holds the letter s and position 18 holds the final quote. Four quote
characters sit in the line, at positions 4, 7, 9 and 18, and the one at position
7 is not a real quote at all. It has a backslash in front of it, so it is part
of the quoted text rather than the end of it. Any engine that treats it as the
end has gone wrong, and two of the four patterns below do exactly that.
A match is two numbers, and a rule chooses between them
A match is a starting position and a length. Both families of engine agree on
the starting position and take it as early as the pattern allows, which is what
leftmost means in both of their names. They disagree about what to do once that
position is fixed.
Leftmost first returns the first match the engine's own search order
reaches. That search order is written into the pattern. Branches of a choice are
tried left to right. A greedy repetition tries the longest run it can and gives
characters back only when forced. A lazy repetition tries the shortest run first
and takes more only when forced. Once any complete match is found the engine
stops looking. Perl, PCRE and therefore PHP and nginx, Python, Java, JavaScript
and .NET in its default mode all work this way.
Leftmost longest returns the longest match that exists at that starting
position, whatever order the pattern was written in. It is what POSIX requires
of its tools, so awk, the POSIX grep and the standard library matching functions
behave this way.
import re
line = 'say "a\\"b" then "c"' # 19 characters, positions 0 to 18
loose = r'".*"' # a quote, anything at all, a quote
lazy = r'".*?"' # same set, shortest run preferred
careful = r'"(\\.|[^"\\])*"' # an escape pair, or an ordinary character
branches = r'"[^"]*"|"(\\.|[^"\\])*"' # two descriptions, in this order
def answer(p):
m = re.search(p, line)
return m.span(), m.end() - m.start(), m.group(0)
print(answer(loose)) # ((4, 19), 15, '"a\\"b" then "c"')
print(answer(lazy)) # ((4, 8), 4, '"a\\"')
print(answer(careful)) # ((4, 10), 6, '"a\\"b"')
print(answer(branches)) # ((4, 8), 4, '"a\\"')Greedy and lazy, and the line that defeats both
The loose pattern asks for a quote, then any characters at all, then a quote.
Its repetition is greedy, so the engine takes the whole rest of the line first
and then hands characters back one at a time until a quote can be matched. The
last quote on the line is at 18, so the match runs from 4 to 18 and its length
is 18 minus 4 plus 1, which is 15. It has swallowed two separate quoted strings
and the four words between them.
The lazy pattern asks for exactly the same set of strings. The question mark on
its repetition changes nothing about what may be consumed and only changes which
length is tried first, so the engine now takes nothing and extends one character
at a time until a quote can be matched. The first quote after position 4 is at
7, so the match runs from 4 to 7 and its length is 7 minus 4 plus 1, which is 4.
It has stopped at the escaped quote.
The careful pattern asks for something narrower. Between the two quotes it
allows only two kinds of piece: a backslash followed by any single character, or
one character that is neither a quote nor a backslash. That stops the match at
position 9 and its length is 9 minus 4 plus 1, which is 6.
The lesson stops here
7 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents