3

From what I've read online, it's hard to understand the behaviour of a non-greedy match (lazy match) in sed. I am puzzled by what seems to be a lazy match.

In ~/tmp/tmp.txt, I have one line with 3 alphanumeric strings separated by 2 tabs: TheQuick<TAB>BrownFox<TAB>JumpedOver. If I issue sed -n -E '/^.+\t.+\t.+$/p' ~/tmp/tmp.txt, the line prints out.

It seems to me like it shouldn't because even though the regular expression matches 3 strings separated by 2 tabs, the strings are not alphanumeric. So the first string should greedily gobble up all the characters on the line, leaving nothing to match the first tab.

How can I understand this behaviour so that I can craft reliable regular expressions? I am using GNU sed.

8
  • It does this by repeated backtracking I think - see for example In regular expressions, what is a backtracking / back referencing? and also Runaway Regular Expressions: Catastrophic Backtracking Mar 7, 2023 at 16:42
  • So it's not intended behaviour according to the documentation? That means it's hard to use the documented intended behaviour to craft regular expressions. Mar 7, 2023 at 16:46
  • No, it is entirely intended behavior.
    – terdon
    Mar 7, 2023 at 16:54
  • I tried to explain in my answer but I think I might not quite understand what is confusing you. Could you clarify why "alphanumeric" is relevant here? Did you think that . only matches alphanumeric characters?
    – terdon
    Mar 7, 2023 at 17:00
  • @terdon that's what I thought at first too but now I think the OP is confused that the regexp .+\t can match anything\t because they think that .+ should match the whole line and so how could it match \t in the input when in their mind the \t should be consumed by the .+. All the stuff about "alphanumeric" in the question is IMHO just a red herring and it's just "how can .+X match fooX when .+ alone matches fooX"?.
    – Ed Morton
    Mar 7, 2023 at 17:15

1 Answer 1

4

A greedy matching system just means it will try to find the largest matching string (meaning the first largest, it will stop searching at the first match for the whole regex), not that it will stop at a non-matching string even if matching strings exist. Think of it as the order to "find me the largest possible match, but do find me a match!". Since allowing the first .\+ to eat up the entire string would mean that the regex doesn't match, the engine will go back and try something else.

In your case, it is even simpler since you are anchoring the regex to the beginning and end of the line (^ and $), so the .+ can never reach the end of the line because there are other things in the regular expression after it.

Here's an example that might help explain greedy matching:

$ echo aaaaaaa | sed 's/a*/B/'
B

Here, since the regular expression a* means "match 0 or more consecutive a characters", the greedy match will find the largest possible matching string. A non-greedy match, using PCRE for example, would return:

$ echo aaaaaaa | perl -pe 's/a*?/B/'
Baaaaaaa

That's because non-greedy will find the shortest matching string instead of the longest.

I don't understand why you mention alphanumeric or how that is relevant. Perhaps you have misunderstood . and think that only matches alphanumeric strings, but it doesn't; . will match everything (depending on which flavor of regular expressions you are using and what options you give it, it can even match newline characters). If you want alphanumeric strings, you can use the POSIX character class [[:alnum:]] which matches [a-zA-Z0-9].

3
  • I referred to alphanumeric because I wanted to emphasize my visualization of the regex engine as not confining a dot to an alphanumeric character, wherein lies the problem, as I mistakenly pictured it. Thank you for dispelling that wrong picture. Mar 7, 2023 at 20:01
  • Clarification: a greedy match finds the largest match among those starting closest to the beginning of the region, not necessarily the largest overall. So ` sed 's/a*/B/' <<<'aaayaaaaa'` prints Byaaaaa, not aaayB. Mar 8, 2023 at 1:11
  • You may want to mention perl's *+ one that matches as much as possible and doesn't give anything back which would match what the OP was thinking greedy matching does Mar 8, 2023 at 9:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .