Non-greedy match with SED regex (emulate perl's .*?)

Question

I want to use sed to replace anything in a string between the first AB and the first occurrence of AC (inclusive) with XXX.

For example, I have this string (this string is for a test only):

ssABteAstACABnnACss

and I would like output similar to this: ssXXXABnnACss.

---

I did this with perl:

$ echo 'ssABteAstACABnnACss' | perl -pe 's/AB.*?AC/XXX/'
ssXXXABnnACss

---

but I want to implement it with sed. The following (using the Perl-compatible regex) does not work:

$ echo 'ssABteAstACABnnACss' | sed -re 's/AB.*?AC/XXX/'
ssXXXss

Answer 1

Sed regexes match the longest match. Sed has no equivalent of non-greedy.

What we want to do is match

1. AB,
   followed by
2. any amount of anything other than AC,
   followed by
3. AC

Unfortunately, sed can’t do #2 — at least not for a multi-character regular expression.  Of course, for a single-character regular expression such as @ (or even [123]), we can do [^@]* or [^123]*.  And so we can work around sed’s limitations by changing all occurrences of AC to @ and then searching for

1. AB,
   followed by
2. any number of anything other than @,
   followed by
3. @

like this:

sed 's/AC/@/g; s/AB[^@]*@/XXX/; s/@/AC/g'

The last part changes unmatched instances of @ back to AC.

But this is a reckless approach because the input could already contain @ characters. So, by matching them, we could get false positives.  However, since no shell variable will ever have a NUL (\x00) character in it, NUL is likely a good character to use in the above work-around instead of @:

$ echo 'ssABteAstACABnnACss' | sed 's/AC/\x00/g; s/AB[^\x00]*\x00/XXX/; s/\x00/AC/g'
ssXXXABnnACss

The use of NUL requires GNU sed. (To make sure that GNU features are enabled, the user must not have set the shell variable POSIXLY_CORRECT.)

If you are using sed with GNU's -z flag to handle NUL-separated input, such as the output of find ... -print0, then NUL will not be in the pattern space and NUL is a good choice for the substitution here.

Although NUL cannot be in a bash variable it is possible to include it in a printf command. If your input string can contain any character at all, including NUL, then see Stéphane Chazelas' answer which adds a clever escaping method.

Answer 2

To do a non-greedy match on a single character, match all characters excluding the one that terminates the match.

Greedy matching:

$ echo "<b>foo</b>bar" | sed 's/<.*>//g'
bar

Non greedy matching:

$ echo "<b>foo</b>bar" | sed 's/<[^>]*>//g'
foobar

Source: sed - non greedy matching by Christoph Sieghart

Answer 3

Some sed implementations have support for that. ssed has a PCRE mode:

ssed -R 's/AB.*?AC/XXX/'

AT&T ast sed supports the *? operator as a non-greedy version of * in its extended (with -E) and augmented (with -A regexps).

sed -E 's/AB.*?AC/XXX/'
sed -A 's/AB.*?AC/XXX/'

In that implementation and those -E/-A modes, more generally, perl-like regexps can be used inside (?P:perl-like regexp here), though as seen above, it's not necessary for the *? operator.

Its augmented regexps also have conjunction and negation operators:

sed -A 's/AB(.*&(.*AC.*)!)AC/XXX/'

Portably, you can use this technique: replace the end string (here AC) with a single character that doesn't occur in either the beginning or end string (like : here) so you can do s/AB[^:]*://, and in case that character may appear in the input, use an escaping mechanism that doesn't clash with the begin and end strings.

An example:

sed 's/_/_u/g; # use _ as the escape character, escape it
     s/:/_c/g; # escape our replacement character
     s/AC/:/g; # replace the end string
     s/AB[^:]*:/XXX/; # actual replacement
     s/:/AC/g; # restore the remaining end strings
     s/_c/:/g; # revert escaping
     s/_u/_/g'

With GNU sed, an approach is to use newline as the replacement character. Because sed processes one line at a time, newline never occurs in the pattern space, so one can do:

sed 's/AC/\n/g;s/AB[^\n]*\n/XXX/;s/\n/AC/g'

That generally doesn't work with other sed implementations because they don't support [^\n]. With GNU sed you have to make sure that POSIX compatibility is not enabled (like with the POSIXLY_CORRECT environment variable).

Answer 4

No, sed regexes don't have non-greedy matching.

You can match all text up to the first occurrence of AC by using “anything not containing AC” followed by AC, which does the same as Perl's .*?AC. The thing is, “anything not containing AC” cannot be expressed easily as a regular expression: there is always a regular expression that recognizes the negation of a regular expression, but the negation regex gets complicated fast. And in portable sed, this isn't possible at all, because the negation regex requires grouping an alternation which is present in extended regular expressions (e.g. in awk) but not in portable basic regular expressions. Some versions of sed, such as GNU sed, do have extensions to BRE that make it able to express all possible regular expressions.

sed 's/AB\([^A]*\|A[^C]\)*A*AC/XXX/'

Because of the difficulty of negating a regex, this doesn't generalize well. What you can do instead is to transform the line temporarily. In some sed implementations, you can use newlines as a marker, since they can't appear in an input line (and if you need multiple markers, use newline followed by a varying character).

sed -e 's/AC/\
&/g' -e 's/AB[^\
]*\nAC/XXX/' -e 's/\n//g'

However, beware that backslash-newline doesn't work in a character set with some sed versions. In particular, this doesn't work in GNU sed, which is the sed implementation on non-embedded Linux; in GNU sed you can use \n instead:

sed -e 's/AC/\
&/g' -e 's/AB[^\n]*\nAC/XXX/' -e 's/\n//g'

In this specific case, it's enough to replace the first AC by a newline. The approach I presented above is more general.

A more powerful approach in sed is to save the line into the hold space, remove all but the first “interesting” part of the line, exchange the hold space and the pattern space or append the pattern space to the hold space and repeat. However, if you start doing things that are this complicated, you should really think about switching to awk. Awk doesn't have non-greedy matching either, but you can split a string and save the parts into variables.

Answer 5

The solution is quite simple. .* is greedy, but it is not absolutely greedy. Consider matching ssABteAstACABnnACss against the regexp AB.*AC. The AC that follows .* must actually have a match. The problem is that because .* is greedy, the subsequent AC will match the last AC rather than the first one. .* eats up the first AC while the literal AC in the regexp matches the last one in ssABteAstACABnnACss. To prevent this from happening, simply replace the first AC with something ridiculous to differentiate it from the second one and from anything else.

echo ssABteAstACABnnACss | sed 's/AC/-foobar-/; s/AB.*-foobar-/XXX/'
ssXXXABnnACss

The greedy .* will now stop at the foot of -foobar- in ssABteAst-foobar-ABnnACss because there is no other -foobar- than this -foobar-, and the regexp -foobar- MUST have a match. The previous problem was that the regexp AC had two matches, but because .* was greedy, the last match for AC was selected. However, with -foobar-, only one match is possible, and this match proves that .* is not absolutely greedy. The bus stop for .* occurs where only one match remains for the rest of the regexp following .*.

Note that this solution will fail if an AC appears before the first AB because the wrong AC will be replaced with -foobar-. For example, after the first sed substitution, ACssABteAstACABnnACss becomes -foobar-ssABteAstACABnnACss; therefore, a match cannot be found against AB.*-foobar-. However, if the sequence is always ...AB...AC...AB...AC..., then this solution will succeed.

Answer 6

One alternative is to change the string so you want the greedy match

echo "ssABtCeCAstACABnnACss" | rev | sed -E "s/(.*)CA.*BA(.*)/\1CA+-+-+-+-BA\2/" | rev

Use rev to reverse the string, reverse your match criteria, use sed in the usual fashion and then reverse the result....

ssAB-+-+-+-+ACABnnACss

Answer 7

It doesn't appear that typical/vanilla sed supports non-greedy RegEx repetitions (aka Minimal Repetitions), so our solution cannot rely on that if portability matters. With that sed however (pun intended), re_format(7) does appear to document it as a potential feature achievable by appending ? to a repetition operator.

Anyway, albeit perhaps a bit hard to understand, I believe that the following is a concise and straightforward solution. I am going to avoid the use of injecting special delimiters (such as NUL characters or unique strings) as other answers have already exercised that strategy.

sed -E 's/ABA*(C|([^CA]+C*A)+C)/XXX/g' <<< 'ssABteAstACABnnACss'

Some things to note here:

1. There's no use of makeshift delimiters (e.g. injecting null chars/bytes, unique strings, etc.) here.

2. This solution assumes that the input isn't broken across multiple lines (i.e. the input is a single line), as otherwise our sed script would first need to concatenate every line of the input into the pattern space verbatim before doing anything else. This is a mandatory first step if it is possible for a line break to appear between an AB and a following AC, or between A and B or A and C itself (as in A\nB or A\nC). Just to be extra safe, we'd also want to ensure that patterns like [^CA], . or [[:space:]] are going to match end of line characters given the: end-of-line character(s) of the input, version of sed in use, and the locale in use, when our sed program is run. [^CA] should match any character though (except C or A of course) including control and EOL characters, just beware of input containing NUL characters or multibyte characters (plus locale, encoding, etc.). Lastly, keep in mind that the pattern space is likely limited to a fixed number of bytes, therefore the following may error/overflow on large inputs.

   sed -n -E \
       -e ':start' \
       -e '$!N' \
       -e '$!bstart' \
       -e 's/ABA*(C|([^CA]+C*A)+C)/XXX/g' \
       -e 'p' <<\EOF
   ssABteAstACABnnACss
   ssABteAstACABnnACss
   ssABteA
   stACABnnACss
   EOF
   

3. There's no special handling or consideration for an AB that occurs between an AB and the very next AC, or, an AC occurring after an AC with no AB in between them (if such cases are even possible in your input?).

4. This solution uses the -E flag in order to enable extended regex patterns, which is required for alternation (i.e. |). This flag may not be very portable when it comes to older sed's, however, it should be available on any modern BSD, GNU, or macOS sed. Here's what the GNU sed manual has to say about it:

   -E

   -r

   --regexp-extended

   Use extended regular expressions rather than basic regular expressions. Extended regexps are those that egrep accepts; they can be clearer because they usually have fewer backslashes.

   Historically this was a GNU extension, but the -E extension has since been added to the POSIX standard, so use -E for portability. GNU sed has accepted -E as an undocumented option for years, and *BSD seds have accepted -E for years as well, but scripts that use -E might not port to other older systems. See Extended regular expressions.

P.S I'm fairly certain that this can also be solved/accomplished just by utilizing multiple "sed commands" (i.e. utilizing multiple s commands, the hold space, conditional branching via the t command, etc.), and such an alternative solution would probably be more readable, understandable, and less error-prone than this is (maybe I'll add it to my answer sometime in the future if I find the time 🙂).