6

Using, for example, the tools on a Debian or Debian-derived system, a regex like N*, which could match the empty string, could result in a match in sed:

$ echo 'Hello' | sed 's/N*/ xx&xx /g'
  xxxx H xxxx e xxxx l xxxx l xxxx o xxxx

Which is the correct result of an empty match (thus the xxxx strings, no character in the middle xx&xx) before each string character (6 times in Hello. The trailing newline doesn't count, it is not matched).

And, if any character (or group of characters) would match it would appear between the xx and xx:

$ echo  'Hello' | sed 's/e*/ xx&xx /g'
 xxxx H xxexx l xxxx l xxxx o xxxx

However, the same regex in grep would not match the empty string:

$ echo 'Hello' | grep -o 'N*'

But will print only non-empty matches:

$ echo 'Hello' | grep -o 'e*'
e

Is there an additional internal rule in grep to avoid empty regex matches?

3
  • 5
    grep regexps find empty matches alright, but GNU grep -o as documented, doesn't report them. You'll find that echo a | grep 'x*' outputs nothing but succeeds. ast-open's grep outputs empty matches and runs in infinite loop when there are some. Aug 9, 2022 at 6:59
  • 1
    Using debian grep, the echo a | grep 'x*' command from your comment does output a. I assume that you meant echo a | grep -o 'x*' which, yes has no output but an exit code of success, yes, while echo a | grep 'xd*' has a failure exit code. How does that help? @StéphaneChazelas Aug 9, 2022 at 8:07
  • Yes, sorry, I did mean each a | grep -o 'x*' indeed. Aug 9, 2022 at 8:19

3 Answers 3

7

grep -o is documented in grep --help as

  -o, --only-matching       show only nonempty parts of lines that match

and in the manual as

Print only the matched (non-empty) parts of matching lines, with each such part on a separate output line.

So yes, there is an additional rule in grep -o: matches are only output if they are non-empty.

In echo 'Hello' | grep -o 'N*', the regular expression matches (as can be seen by looking at the return code, or with echo 'Hello' | grep 'N*'), but because the matches are empty, nothing is output.

4

The behavior of 0-length string matches can be special cased in the code, or not. For instance the sed but not perl

$ echo aabb | sed 's/a*/X/g'
XbXbX
$ echo aabb | gsed 's/a*/X/g'
XbXbX
$ echo aabb | perl -ple 's/a*/X/g'
XXbXbX

behavior probably comes from how vi behaved historically as seen in the depths of ex/ex_subst.c:

    /*
     * !!!
     * It's possible to match 0-length strings -- for example, the
     * command s;a*;X;, when matched against the string "aabb" will
     * result in "XbXbX", i.e. the matches are "aa", the space
     * between the b's and the space between the b's and the end of
     * the string.  There is a similar space between the beginning
     * of the string and the a's.  The rule that we use (because vi
     * historically used it) is that any 0-length match, occurring
     * immediately after a match, is ignored.  Otherwise, the above
     * example would have resulted in "XXbXbX".  Another example is
     * incorrectly using " *" to replace groups of spaces with one
     * space.

(A different problem can be a zero-width matches that match forever; I'm pretty sure there's "just move to the next character..." code to prevent that, probably added after someone's CPU went to 100% a few times and a palm met a forehead.)

Both BSD and GNU ed fail on the s/a*/X/g expression, so the special behavior might be an ex-vi era change that escaped into sed?

$ echo aabb > foo
$ ed foo
5
s/a*/X/g
?
s/a*/X
Xbb
Q
5
  • See also the sed 's/\<ab/X/g' which turns abab into XX with some sed implementations (not easily avoidable when using the standard regex API). Aug 9, 2022 at 7:33
  • Strange interpretation to ignore the "0-length match, occurring immediately after a match". Matches are non-overlapping, so there is no 0-length match which wouldn't already have been included in the previous match. With their logic you could as well say you find as many 0-length matches as you like between two matches …
    – Philippos
    Aug 9, 2022 at 9:30
  • @StéphaneChazelas, wait what, how does that work? I could see it with s/\<ab/:/g, if the first ab turned into a :, giving :ab and there'd now be a word boundary before the second ab. But there shouldn't be one between an X and ab...? Right? I got XX with Busybox, so yeah, there must be some logic, but I can't see what it is...
    – ilkkachu
    Aug 9, 2022 at 9:39
  • 1
    @ilkkachu, after finding the first ab, sed resumes searching for the next occurrence of \<ab in what's after that: ab. At that point, ab is at the start so matching a word boundary. You don't get the same problem with s/^ab/X/ because, there's a REG_NOTBOL flag in the standard regexp API for that, but no equivalent REG_NOTBOW. Aug 9, 2022 at 10:17
  • @StéphaneChazelas, oh, yes, right, of course it has to move over past the replaced part and not look at it again. Thanks again. IIRC \< isn't standard anyway, so it's perhaps not surprising there's no corresponding flag for it, and if there was a non-standard one, the tools wouldn't know to use it.
    – ilkkachu
    Aug 9, 2022 at 10:22
1
$ echo 'Hello' | grep -o 'N*'
$ echo $?
0

It does match an empty substring of that input line, as shown by the exit status. (With a different pattern like N, we still get nothing on stdout, but an exit status of 1, failure.)

-o makes it not print empty matches, but that's separate from whether the regex matches any input lines. (And yes, we can distinguish that; if it had printed an empty-string match, it would output a newline after it each match, so there'd be a blank line before the prompt. Or 6, one for each match.)

Without -o, it prints the whole matching line:

$ echo 'Hello' | grep  'N*'          # same as grep '' empty pattern
Hello
1
  • 1
    or there would be six blank lines, assuming the same behavior sed showed: that the zero-length match would be found once in every possible position
    – ilkkachu
    Aug 9, 2022 at 16:30

You must log in to answer this question.

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