12

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
  • 2
    This doesn't make sense. You have a working solution in Perl, but you want to use Sed, why? – Kusalananda Jul 23 '16 at 6:44
10

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

Obviously 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, of course, 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.

  • I just edited your answer to add a lengthy explanation; feel free to trim it or roll it back. – G-Man Jul 23 '16 at 5:33
  • @G-Man That is an excellent explanation! Very nicely done. Thank you. – John1024 Jul 23 '16 at 6:51
  • You can echo or printf an `\000' just fine in bash (or the input could come from a file). But in general, a string of text is of course not likely have NULs. – ilkkachu Jul 23 '16 at 14:39
  • @ilkkachu You are right about that. What I should have written is that no shell variable or parameter can contain NULs. Answer updated. – John1024 Jul 23 '16 at 19:24
  • Wouldn't this be a whole lot safer if you changed AC to AC@ and back again? – Michael Vehrs Jul 25 '16 at 8:52
7

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

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

AT&T ast sed has conjunction and negation when using augmented regexps:

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

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/g; # 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/g;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).

5

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.

  • @ilkkachu No, it doesn't. s/\n//g removes all newlines. – Gilles Jul 24 '16 at 19:28
  • asdf. Right, my bad. – ilkkachu Jul 24 '16 at 20:06
2

sed - non greedy matching by Christoph Sieghart

The trick to get non greedy matching in sed is to match all characters excluding the one that terminates the match. I know, a no-brainer, but I wasted precious minutes on it and shell scripts should be, after all, quick and easy. So in case somebody else might need it:

Greedy matching

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

Non greedy matching

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

  • 2
    The term “no-brainer” is ambiguous.  In this case, it is not clear that you (or Christoph Sieghart) thought this through.  In particular, it would have been nice if you had showed how to solve the specific problem in the question (where the zero-of-more-of- expression is followed by more than one character).  You may find that this answer doesn’t work well in that case. – Scott Oct 12 '17 at 22:14
  • The rabbit hole is much deeper than it seemed to me at first glance. You are right, that workaround doesn't work well for multi-character regular expression. – gresolio Oct 15 '17 at 20:15
0

In your case you can just negate closing char this way:

echo 'ssABteAstACABnnACss' | sed 's/AB[^C]*AC/XXX/'
  • 2
    The question says, “I want replace anything between the first AB and the first occurrence of AC with XXX …,” and gives ssABteAstACABnnACss as an example input. This answer works for that example, but doesn’t answer the question in general.  For example, ssABteCstACABnnACss should also yield the output aaXXXABnnACss, but your command passes this line through unchanged. – G-Man Jul 23 '16 at 5:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.