Linux 正则表达式（basic and extened）

正则表达式(Regular Expressions)，整理自：
https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap09.html
gred
sed

定义

Regular Expressions (REs) provide a mechanism to select specific strings from a set of character strings.
Regular expressions are a context-independent syntax that can represent a wide variety of character sets and character set orderings, where these character sets are interpreted according to the current locale.

什么是 “locale”?

参考自：Locale

A locale is the definition of the subset of a user’s environment that depends on language and cultural conventions.
It is made up from one or more categories.
Each category is identified by its name and controls specific aspects of the behavior of components of the system.
Category names correspond to the following environment variable names:

LC_CTYPE

Character classification and case conversion.

LC_COLLATE

Collation order.

LC_MONETARY

Monetary formatting.

LC_NUMERIC

Numeric, non-monetary formatting.

LC_TIME

Date and time formats.

LC_MESSAGES

Formats of informative and diagnostic messages and interactive responses.

我们常用的是：POSIX Locale

collating element

先回答一个比较容易混淆的概念：什么是collating element？

In many languages, collation (sorting like in a dictionary) is not only done per-character.
For instance, in Czech, ch doesn’t sort between cg and ci like it would in English, but is considered as a whole for sorting.
It is a collating element (we can’t refer to a character here, character are a subset of collating elements) that sorts in between h and i.

也就是说collating element是在某些语言系统中，多个字符组成一个字符的含义。这让我想起音标。

正则表达式中：
What does [[.ch.]] mean in a regex?

When you use [.ch.] in a regexp, you basically say:
“I expect a non-English input sequence with the digraph ch.
I want my regexp to match the single charachter ch.
My programming language/regex engine/keyboard does not allow me to write this digraph’s sign, so I type in [.ch.].
I don’t mean a c followed by an h. Please only find occurences of the digraph as a single charachter.”
[[.ch.]] means that the digraph is part of a a set of characters.
In this case only one character actually. Just standard regexp notation.

参考：https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap07.html#tag_07_03

multi-character collating element is that of “ch”.

Subject

1. Basic Regular Expression
2. Extended Regular Expression

Both BREs and EREs are supported by the Regular Expression Matching interface in the System Interfaces volume of POSIX.1-2017 under regcomp(), regexec(), and related functions.

Matched 定义

A sequence of zero or more characters shall be said to be matched by a BRE or ERE when the characters in the sequence correspond to a sequence of characters defined by the pattern.

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.

BRE (ERE) matching a single character 匹配一个字符

A BRE or ERE that shall match either a single character or a single collating element.

Only a BRE or ERE of this type that includes a bracket expression ( RE Bracket Expression) can match a collating element.

BRE (ERE) matching multiple characters 匹配多个字符

A BRE or ERE that shall match a concatenation of single characters or collating elements.

Such a BRE or ERE is made up from a BRE (ERE) matching a single character and BRE (ERE) special characters.

invalid

character class expression

[:alnum:]   [:cntrl:]   [:lower:]   [:space:]
[:alpha:]   [:digit:]   [:print:]   [:upper:]
[:blank:]   [:graph:]   [:punct:]   [:xdigit:]

对应的名字在下面：

LC_CTYPE Category in the POSIX Locale
The minimum character classifications for the POSIX locale follow; the code listing depicts the localedef input, and the table represents the same information, sorted by character. Implementations may add additional characters to the cntrl and punct classifications but shall not make any other additions.

LC_CTYPE
# The following is the minimum POSIX locale LC_CTYPE.
# "alpha" is by definition "upper" and "lower"
# "alnum" is by definition "alpha" and "digit"
# "print" is by definition "alnum", "punct", and the <space>
# "graph" is by definition "alnum" and "punct"
#
upper    <A>;<B>;<C>;<D>;<E>;<F>;<G>;<H>;<I>;<J>;<K>;<L>;<M>;\
         <N>;<O>;<P>;<Q>;<R>;<S>;<T>;<U>;<V>;<W>;<X>;<Y>;<Z>
#
lower    <a>;<b>;<c>;<d>;<e>;<f>;<g>;<h>;<i>;<j>;<k>;<l>;<m>;\
         <n>;<o>;<p>;<q>;<r>;<s>;<t>;<u>;<v>;<w>;<x>;<y>;<z>
#
digit    <zero>;<one>;<two>;<three>;<four>;<five>;<six>;\
         <seven>;<eight>;<nine>
#
space    <tab>;<newline>;<vertical-tab>;<form-feed>;\
         <carriage-return>;<space>
#
cntrl    <alert>;<backspace>;<tab>;<newline>;<vertical-tab>;\
         <form-feed>;<carriage-return>;\
         <NUL>;<SOH>;<STX>;<ETX>;<EOT>;<ENQ>;<ACK>;<SO>;\
         <SI>;<DLE>;<DC1>;<DC2>;<DC3>;<DC4>;<NAK>;<SYN>;\
         <ETB>;<CAN>;<EM>;<SUB>;<ESC>;<IS4>;<IS3>;<IS2>;\
         <IS1>;<DEL>
#
punct    <exclamation-mark>;<quotation-mark>;<number-sign>;\
         <dollar-sign>;<percent-sign>;<ampersand>;<apostrophe>;\
         <left-parenthesis>;<right-parenthesis>;<asterisk>;\
         <plus-sign>;<comma>;<hyphen-minus>;<period>;<slash>;\
         <colon>;<semicolon>;<less-than-sign>;<equals-sign>;\
         <greater-than-sign>;<question-mark>;<commercial-at>;\
         <left-square-bracket>;<backslash>;<right-square-bracket>;\
         <circumflex>;<underscore>;<grave-accent>;<left-curly-bracket>;\
         <vertical-line>;<right-curly-bracket>;<tilde>
#
xdigit   <zero>;<one>;<two>;<three>;<four>;<five>;<six>;<seven>;\
         <eight>;<nine>;<A>;<B>;<C>;<D>;<E>;<F>;<a>;<b>;<c>;<d>;<e>;<f>
#
blank    <space>;<tab>
#
toupper (<a>,<A>);(<b>,<B>);(<c>,<C>);(<d>,<D>);(<e>,<E>);\
        (<f>,<F>);(<g>,<G>);(<h>,<H>);(<i>,<I>);(<j>,<J>);\
        (<k>,<K>);(<l>,<L>);(<m>,<M>);(<n>,<N>);(<o>,<O>);\
        (<p>,<P>);(<q>,<Q>);(<r>,<R>);(<s>,<S>);(<t>,<T>);\
        (<u>,<U>);(<v>,<V>);(<w>,<W>);(<x>,<X>);(<y>,<Y>);(<z>,<Z>)
#
tolower (<A>,<a>);(<B>,<b>);(<C>,<c>);(<D>,<d>);(<E>,<e>);\
        (<F>,<f>);(<G>,<g>);(<H>,<h>);(<I>,<i>);(<J>,<j>);\
        (<K>,<k>);(<L>,<l>);(<M>,<m>);(<N>,<n>);(<O>,<o>);\
        (<P>,<p>);(<Q>,<q>);(<R>,<r>);(<S>,<s>);(<T>,<t>);\
        (<U>,<u>);(<V>,<v>);(<W>,<w>);(<X>,<x>);(<Y>,<y>);(<Z>,<z>)
END LC_CTYPE

Regular Expression General Requirements

The requirements in this section shall apply to both basic and extended regular expressions.

The use of regular expressions is generally associated with text processing.
REs (BREs and EREs) operate on text strings, that is, zero or more characters followed by an end-of-string delimiter (typically NUL). Some utilities employing regular expressions limit the processing to lines; that is, zero or more characters followed by a <newline>.

上面提到两个特别的符号NUL和 newline

In the functions processing regular expressions described in System Interfaces volume of POSIX.1-2017, the <newline> is regarded as an ordinary character and both a <period> and a non-matching list can match one.
其实就是一个"."
在 POSIX.1-2017系统接口中 newline是一个常规字符串，同时period 以及 non-matching list都能字面匹配

The Shell and Utilities volume of POSIX.1-2017 specifies within the individual descriptions of those standard utilities employing regular expressions whether they permit matching of <newline> characters; if not stated otherwise, the use of literal <newline> characters or any escape sequence equivalent in either patterns or matched text produces undefined results.

如果是使用正则匹配的工具，就要自己说明是否允许匹配newline。
在有些工具中，一般不处理<newline>，出现<newline>在patterns或者在需要匹配的字符串中，都是为undefined results.
比如说在grep中就不能处理<newline>，grep

If the final byte of an input file is not a newline, grep silently supplies one.
Since newline is also a separator for the list of patterns, there is no way to match newline characters in a text.

Those utilities (like grep) that do not allow <newline> characters to match are responsible for eliminating any <newline> from strings before matching against the RE.
The regcomp() function in the System Interfaces volume of POSIX.1-2017, however, can provide support for such processing without violating the rules of this section.

The interfaces specified in POSIX.1-2017 do not permit the inclusion of a NUL character in an RE or in the string to be matched.
If during the operation of a standard utility a NUL is included in the text designated to be matched, that NUL may designate the end of the text string for the purposes of matching.

下面一段说明要允许有大小写不敏感的匹配。
When a standard utility or function that uses regular expressions specifies that pattern matching shall be performed without regard to the case (uppercase or lowercase) of either data or patterns, then when each character in the string is matched against the pattern, not only the character, but also its case counterpart (if any), shall be matched.

This definition of case-insensitive processing is intended to allow matching of multi-character collating elements as well as characters, as each character in the string is matched using both its cases.
For example, in a locale where “Ch” is a multi-character collating element and where a matching list expression matches such elements, the RE "[[.Ch.]]" when matched against the string “char” is in reality matched against “ch”, “Ch”, “cH”, and “CH”.

The implementation shall support any regular expression that does not exceed 256 bytes in length.

Basic Regular Expression BRE

BREs Matching a Single Character or Collating Element

• A BRE ordinary character, a special character preceded by a
  <backslash>, or a <period> shall match a single character.
• A bracke expression shall match a single character or a single collating
  element.

什么是ordinary character

An ordinary character is a BRE that matches itself: any character in the supported character set, except for the BRE special characters listed in BRE Special Characters.

The interpretation of an ordinary character preceded by an unescaped ( ‘\’ ) is undefined, except for:

• The characters ‘)’, ‘(’, ‘{’, and ‘}’
• The digits 1 to 9 inclusive (see BREs Matching Multiple Characters)
• A character inside a bracket expression.

BRE Special Characters

A BRE special character has special properties in certain contexts.
Outside those contexts, or when preceded by a <backslash>, such a character is a BRE that matches the special character itself.
The BRE special characters and the contexts in which they have their special meaning are as follows:

Note that:
A <period> ( '.' ), a BRE that shall match any character in the supported character set except NUL or <newline> \r\n.

注意上面需要加backslash\的地方，有些地方需要加，有些地方不需要加
如果你需要匹配上面的特殊字符，就需要转义字符

Special Backslash Expressions

The ‘\’ character followed by a special character is a regular expression that matches the special character. The ‘\’ character, when followed by certain ordinary characters, takes a special meaning:

For example, ‘\brat\b’ matches the separate word ‘rat’, ‘\Brat\B’ matches ‘crate’ but not ‘furry rat’.

The behavior of grep is unspecified if a unescaped backslash is not followed by a special character, a nonzero digit, or a character in the above list. Although grep might issue a diagnostic and/or give the backslash an interpretation now, its behavior may change if the syntax of regular expressions is extended in future versions.

RE Bracket Expression

A bracket expression (an expression enclosed in square brackets, “[]” ) is an RE that shall match a specific set of single characters, and may match a specific set of multi-character collating elements, based on the non-empty set of list expressions contained in the bracket expression.

The following rules and definitions apply to bracket expressions:

1. A bracket expression is either a matching list expression or a non-matching list expression.
2. It consists of one or more expressions: ordinary characters, collating elements, collating symbols, equivalence classes, character classes, or range expressions.
3. The <right-square-bracket> ( ']' ) shall lose its special meaning and represent itself in a bracket expression if it occurs first in the list (after an initial ( ‘^’ ), if any).Otherwise, it shall terminate the bracket expression, unless it appears in a collating symbol (such as “[.].]” ) or is the ending for a collating symbol, equivalence class, or character class.
4. The special characters '.', '*', '[', and '\\' ( <period>, <asterisk>, <left-square-bracket>, and <backslash>, respectively) shall lose their special meaning within a bracket expression.
5. The character sequences "[.", "[=", and "[:" ( <left-square-bracket> followed by a <period>, <equals-sign>, or <colon>) shall be special inside a bracket expression and are used to delimit collating symbols, equivalence class expressions, and character class expressions. These symbols shall be followed by a valid expression and the matching terminating sequence ".]", "=]", or ":]", as described in the following items.
6. A matching list expression specifies a list that shall match any single character that is matched by one of the expressions represented in the list.
7. The first character in the list cannot be the <circumflex>.
8. An ordinary character in the list should only match that character, but may match any single character that collates equally with that character; for example, “[abc]” is an RE that should only match one of the characters ‘a’, ‘b’, or ‘c’.
9. A non-matching list expression begins with a <circumflex> ( '^' ), and the matching behavior shall be the logical inverse of the corresponding matching list expression (the same bracket expression but without the leading ). For example, if the RE "[abc]" only matches 'a', 'b', or 'c', then "[^abc]" is an RE that matches any character except 'a', 'b', or 'c'. It is unspecified whether a non-matching list expression matches a multi-character collating element that is not matched by any of the expressions.
10. 10.The <circumflex> shall have this special meaning only when it occurs first in the list, immediately following the<left-square-bracket>.
11. A collating symbol is a collating element enclosed within bracket-period ( “[.” and “.]” ) delimiters. Collating elements are defined as described in Collation Order.
    Conforming applications shall represent multi-character collating elements as collating symbols when it is necessary to distinguish them from a list of the individual characters that make up the multi-character collating element. For example, if the string “ch” is a collating element defined using the line:collating-element <ch-digraph> from "<c><h>"
12. in the locale definition, the expression “[[.ch.]]” shall be treated as an RE containing the collating symbol ‘ch’, while “[ch]” shall be treated as an RE matching ‘c’ or ‘h’.
    Collating symbols are recognized only inside bracket expressions. If the string is not a collating element in the current locale, the expression is invalid.
13. An equivalence class expression shall represent the set of collating elements belonging to an equivalence class, as described in Collation Order.
    Only primary equivalence classes shall be recognized.
    The class shall be expressed by enclosing any one of the collating elements in the equivalence class within bracket-equal ( “[=” and “=]” ) delimiters.
    For example, if ‘a’, ‘à’, and ‘â’ belong to the same equivalence class, then “[[=a=]b]”, “[[=à=]b]”, and “[[=â=]b]” are each equivalent to “[aàâb]”. If the collating element does not belong to an equivalence class, the equivalence class expression shall be treated as a collating symbol.
14. A character class expression shall represent the union of two sets:
    The set of single characters that belong to the character class, as defined in the LC_CTYPE category in the current locale.
    An unspecified set of multi-character collating elements.
    All character classes specified in the current locale shall be recognized.
    A character class expression is expressed as a character class name enclosed within bracket- <colon> ( "[:" and ":]" ) delimiters.

The following character class expressions shall be supported in all locales:

[:alnum:]   [:cntrl:]   [:lower:]   [:space:]
[:alpha:]   [:digit:]   [:print:]   [:upper:]
[:blank:]   [:graph:]   [:punct:]   [:xdigit:]

15. In the POSIX locale, a range expression shall be expressed as the starting point and the ending point separated by a <hyphen-minus> ( '-' ).
    In the following, all examples assume the POSIX locale.
    eated as invalid.
    The interpretation of range expressions where the ending range point is also the starting range point of a subsequent range expression (for example, "[a-m-o]" ) is undefined.

16. The character shall be treated as itself if it occurs first (after an initial ‘^’, if any) or last in the list, or as an ending range point in a range expression.
    As examples, the expressions “[-ac]” and “[ac-]” are equivalent and match any of the characters 'a', 'c', or '-';
    "[^-ac]" and "[^ac-]" are equivalent and match any characters except 'a', 'c', or '-';

17. the expression "[%--]" matches any of the characters between ‘%’ and ‘-’ inclusive;

18. the expression “[–@]” matches any of the characters between ‘-’ and ‘@’ inclusive;

19. and the expression "[a--@]" is either invalid or equivalent to ‘@’, because the letter ‘a’ follows the symbol ‘-’ in the POSIX locale.

20. To use a <hyphen-minus> as the starting range point, it shall either come first in the bracket expression or be specified as a collating symbol; for example, "[][.-.]-0]", which matches either a <right-square-bracket> or any character or collating element that collates between <hyphen-minus> and 0, inclusive.

21. If a bracket expression specifies both ‘-’ and ‘]’, the ‘]’ shall be placed first (after the ‘^’, if any) and the ‘-’ last within the bracket expression.

Note:
A future version of this standard may require that an ordinary character in the list only matches that character.
It is unspecified whether a matching list expression matches a multi-character collating element that is matched by one of the expressions.

Anchoring

The caret ‘^’ and the dollar sign ‘$’ are special characters that respectively match the empty string at the beginning and end of a line. They are termed anchors, since they force the match to be “anchored” to beginning or end of a line, respectively.

Back-references and Subexpressions

The back-reference ‘\n’, where n is a single nonzero digit, matches the substring previously matched by the nth parenthesized subexpression of the regular expression.
For example, ‘(a)\1’ matches ‘aa’. If the parenthesized subexpression does not participate in the match, the back-reference makes the whole match fail; for example, ‘(a)*\1’ fails to match ‘a’. If the parenthesized subexpression matches more than one substring, the back-reference refers to the last matched substring; for example, ‘^(ab*)*\1$’ matches ‘ababbabb’ but not ‘ababbab’. When multiple regular expressions are given with -e or from a file (‘-f file’), back-references are local to each expression.

Basic vs Extended Regular Expressions

Basic regular expressions differ from extended regular expressions in the following ways:

1. The characters ‘?’, ‘+’, ‘{’, ‘|’, ‘(’, and ‘)’ lose their special meaning; instead use the backslashed versions ‘?’, ‘+’, ‘{’, ‘|’, ‘(’, and ‘)’. Also, a backslash is needed before an interval expression’s closing ‘}’.
2. An unmatched ‘)’ is invalid.
3. If an unescaped ‘^’ appears neither first, nor directly after ‘(’ or ‘|’, it is treated like an ordinary character and is not an anchor.
4. If an unescaped ‘$’ appears neither last, nor directly before ‘|’ or ‘)’, it is treated like an ordinary character and is not an anchor.
5. If an unescaped ‘*’ appears first, or appears directly after ‘(’ or ‘|’ or anchoring ‘^’, it is treated like an ordinary character and is not a repetition operator.

Problematic Regular Expressions

Some strings are invalid regular expressions and cause grep/sed to issue a diagnostic and fail. For example, ‘xy\1’ is invalid because there is no parenthesized subexpression for the back-reference ‘\1’ to refer to.

Also, some regular expressions have unspecified behavior and should be avoided even if grep does not currently diagnose them. For example, ‘xy\0’ has unspecified behavior because ‘0’ is not a special character and ‘\0’ is not a special backslash expression (see Special Backslash Expressions). Unspecified behavior can be particularly problematic because the set of matched strings might be only partially specified, or not be specified at all, or the expression might even be invalid.

The following regular expression constructs are invalid on all platforms conforming to POSIX, so portable scripts can assume that grep rejects these constructs:

1. A basic regular expression containing a back-reference ‘\n’ preceded by fewer than n closing parentheses. For example, ‘(a)\2’ is invalid.
2. A bracket expression containing ‘[:’ that does not start a character class; and similarly for ‘[=’ and ‘[.’. For example, ‘[a[:b]’ and ‘[a[:ouch:]b]’ are invalid.

GNU grep treats the following constructs as invalid. However, other grep implementations might allow them, so portable scripts should not rely on their being invalid:

1. Unescaped ‘\’ at the end of a regular expression.
2. Unescaped ‘[’ that does not start a bracket expression.
3. A ‘{’ in a basic regular expression that does not start an interval expression.
4. A basic regular expression with unbalanced ‘(’ or ‘)’, or an extended regular expression with unbalanced ‘(’.
5. In the POSIX locale, a range expression like ‘z-a’ that represents zero elements. A non-GNU grep might treat it as a valid range that never matches.
6. An interval expression with a repetition count greater than 32767. (The portable POSIX limit is 255, and even interval expressions with smaller counts can be impractically slow on all known implementations.)
7. A bracket expression that contains at least three elements, the first and last of which are both ‘:’, or both ‘.’, or both ‘=’. For example, a non-GNU grep might treat ‘[:alpha:]’ like ‘[[:alpha:]]’, or like ‘[:ahlp]’.

The following constructs have well-defined behavior in GNU grep. However, they have unspecified behavior elsewhere, so portable scripts should avoid them:

1. Special backslash expressions like ‘\b’, ‘<’, and ‘]’. See Special Backslash Expressions.
2. A basic regular expression that uses ‘?’, ‘+’, or ‘|’.
3. An extended regular expression that uses back-references.
4. An empty regular expression, subexpression, or alternative. For example, ‘(a|bc|)’ is not portable; a portable equivalent is ‘(a|bc)?’.
5. In a basic regular expression, an anchoring ‘^’ that appears directly after ‘(’, or an anchoring ‘$’ that appears directly before ‘)’.
6. In a basic regular expression, a repetition operator that directly follows another repetition operator.
7. In an extended regular expression, unescaped ‘{’ that does not begin a valid interval expression. GNU grep treats the ‘{’ as an ordinary character.
8. A null character or an encoding error in either pattern or input data. See Character Encoding.
9. An input file that ends in a non-newline character, where GNU grep silently supplies a newline.

The following constructs have unspecified behavior, in both GNU and other grep implementations. Scripts should avoid them whenever possible.

1. A backslash escaping an ordinary character, unless it is a back-reference like ‘\1’ or a special backslash expression like ‘<’ or ‘\b’. See Special Backslash Expressions. For example, ‘\x’ has unspecified behavior now, and a future version of grep might specify ‘\x’ to have a new behavior.
2. A repetition operator that appears directly after an anchor, or at the start of a complete regular expression, parenthesized subexpression, or alternative. For example, ‘+|^*(+a|?-b)’ has unspecified behavior, whereas ‘+|^*(+a|?-b)’ is portable.
3. A range expression outside the POSIX locale. For example, in some locales ‘[a-z]’ might match some characters that are not lowercase letters, or might not match some lowercase letters, or might be invalid. With GNU grep it is not documented whether these range expressions use native code points, or use the collating sequence specified by the LC_COLLATE category, or have some other interpretation. Outside the POSIX locale, it is portable to use ‘[[:lower:]]’ to match a lower-case letter, or ‘[abcdefghijklmnopqrstuvwxyz]’ to match an ASCII lower-case letter.

If a bracket expression contains at least three list elements, where the first and last list elements are the same single-character element of , , or , then it is unspecified whether the bracket expression will be treated as a collating symbol, equivalence class, or character class, respectively; treated as a matching list

Extended Regular Expression ERE