How greedy is sed in matching patterns?

Question

I know sed is greedy when matching patterns. But, how greedy is it?

Consider these examples.

$ echo 'foobar123' | sed 's/[0-9]*/(&)/'
()foobar123
$ echo 'foobar123' | sed 's/[0-9][0-9]*/(&)/'
foobar(123)

Why doesn't the second example print foobar(1)23 and instead prints foobar(123)?

Answer 1

It's as greedy as it can.

The first pattern ("any digit zero or more times") matches everywhere, but only does once in your example because there's no g flag.

Compare:

$ echo foobar123 | sed 's/[0-9]*/(&)/g'
()f()o()o()b()a()r(123)

Note how it does become greedy as soon as it can, i.e., there are digits of which more than zero can be consumed.

Same thing for the second pattern ("any single digit, plus any digit zero or more times"). It can't match anywhere before the 123. Once there, it consumes as many as possible.

Answer 2

The reason for the confusion is

1) sed matches as early as possible (hence 1st example)
2) sed * is as greedy as possible (hence second example)

In single-match mode, once it has found a match, sed doesn't look for later matches where it could be greedier.