6

I would like to know if, for instance, \{x,y\} in sed will try to match as much or as little as possible characters.

Also, can someone explain to me the bellow unexpected behaviour of sed?

echo "baaab" | sed 's/a\{1,2\}//'
bab

echo "baaab" | sed 's/a\{0,2\}//'
baaab

In the first line, sed becomes greedy, in the second apparently it doesn't, is there a reason for that?

I'm using GNU sed version 4.2.1.

  • Your first example by itself demonstrates that it is greedy. – Wildcard Nov 19 '15 at 0:16
  • If you watch closely, you'll notice that there are actually two examples, with two seemingly different behaviours. However thanks to those useful and constructive answers, I can know understand this behaviour ;) – Kira Nov 19 '15 at 14:54
15

a\{0,2\} will match the empty string at the start of the line (actually, any empty string, but g wasn't specified):

$ echo "baaab" | sed 's/a\{0,2\}/y/' 
ybaaab

Since GNU sed does matching from left to right, and a global replacement wasn't specified, only the start of the line matched. If you'd used g:

$ echo "baaab" | sed 's/a\{0,2\}/y/g'
ybyyby

The empty strings at the start and end matched, and the aa, and the remaining a.

6

Yes, it's greedy.

In POSIX compliant system, not only sed but also all tools which use Basic Regular Expression, the matched pattern will always be greedy:

The search for a matching sequence starts at the beginning of a string and stops when the first sequence matching the expression is found, where "first" is defined to mean "begins earliest in the string". If the pattern permits a variable number of matching characters and thus there is more than one such sequence starting at that point, the longest such sequence is matched. For example, the BRE "bb*" matches the second to fourth characters of the string "abbbc", and the ERE "(wee|week)(knights|night)" matches all ten characters of the string "weeknights".

Consistent with the whole match being the longest of the leftmost matches, each subpattern, from left to right, shall match the longest possible string. For this purpose, a null string shall be considered to be longer than no match at all. For example, matching the BRE "(.)." against "abcdef", the subexpression "(\1)" is "abcdef", and matching the BRE "(a*)*" against "bc", the subexpression "(\1)" is the null string.

The pattern a\{0,2\} matched any occurrence of character a between zero and two. Zero occurrence means the empty string, which is considered to be longer than no match as the spec indicated above.

The problem with your usage is that you did not use the global flag for sed substitution command. Without global flag, sed stop doing substitution as soon as it found the first match, which is the empty string at the beginning of the line.


The general form is \{m,n\} with 0 <= m <= n <= RE_DUP_MAX, with RE_DUP_MAX is 32767 in most platform:

$ getconf RE_DUP_MAX
32767

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.