How to recursively replace characters with sed?

Is it possible to replace occurrences of a character sequence recursively without iterating over the same sequence again?

By performing a sed as in the following scenarios I can get the mentioned output.

$ echo XX | sed -e 's/XX/XoX/g'
XoX  
$ echo XXX | sed -e 's/XX/XoX/g'
XoXX  
$ echo XXXX | sed -e 's/XX/XoX/g'
XoXXoX  

However, I'm expecting the output to follow the following behavior.

Input:

XX
XXX
XXXX

Expected output:

XoX
XoXoX
XoXoXoX

Is it possible to achieve the expected behavior with sed alone?

Solution 1:

You can do:

> echo XXXX | sed -e ':loop' -e 's/XX/XoX/g' -e 't loop'
XoXoXoX

With:

• -e ':loop' : Create a "loop" label
• -e 't loop' : Jump to the "loop" label if previous substitution was successful

Solution 2:

In this particular case look-ahead or look-behind would be useful. I think GNU sed doesn't support these. With perl:

perl -ne 's/X(?=X)/Xo/g; print;'

You could also use lookbehind and lookahead like:

s/(?<=X)(?=X)/o/g

Where:

(?<=X) is a positive lookbehind, a zero-length assertion that make sure we have an X before the current position
(?=X) is a positive lookahead, a zero-length assertion that make sure we have an X after the current position

Using in a perl one-liner:

perl -pe 's/(?<=X)(?=X)/o/g' inputfile

Where:

-p causes Perl to assume a loop around the program with an implicit print of the current line