What are Interval Regular Expression and Tagged Regular Expression?

Question

I was recently reading about sed when I encountered this topic. I need examples to understand the topic better.

Answer 1

The interval regular expression operator in Basic Regular Expressions (BRE) as supported by standard sed would refer to \{x,y\}.

The equivalent ERE (extended) or PCRE (perl compatible) operators (with -r/-E, -R/-P with some sed implementations) would be {x,y}.

They're used to specify a range of repeat count for a regexp.

sed 's/<a\{3,12\}>/<b>/'

Would replace the first occurrence of < followed by from 3 to 12 as followed by > with <b>.

On an input like <a> <aa> <aaaa> <aaaaaaaa>, it would replace <aaaa> with <b>.

Tagged regular expressions is more commonly refered as capture groups.

In BRE, that's with \(...\) and with ERE/PCRE with (...). They're used to capture the text that was matched by a regex to use it either as a back-reference or in substitutions. Those can also be used for grouping (as in \(foo\)* for any number of foos).

In:

sed 's/\(.\)\(.\)\(.*\)\2\1/\1\2<\3>\2\1/'

We have 3 tagged expressions aka capture groups, the character (. is to match a single character) matched by the first \(.\) will be tagged with 1, and is referred to as \1 later on in the regexp (so if the first \(.\) captured a x, \1 will match on x only), and is also called back in the replacement.

On an input like whatever -+foobar+-, the regexp will find: (1:-)(2:+)(3:foobar)(2:+)(1:-) and the s command will replace it with -+<foobar>+-.

Standard (POSIX) EREs don't support back references (that \1 in the regexp above) so the (...) there is only for grouping (like in (foo|bar) or (foo){1,3}), though some implementations support it as an extension. The next major release of the POSIX specification will specify the -E option for sed regexps to use EREs. \1 in the regexp (back references) will still not be supported, but \1 in the s replacement to expand to what was matched by the corresponding tagged expression will be.

python, perl, PCRE or compatible regular expressions also let you give arbitrary names to tagged expressions (instead of just 1, 2... numbered left to right). See their manual for details.