regular expressions -- syntax for regular expressions

A regular expression is a string that specifies a pattern that describes a set of matching subject strings. Typically the string is compiled into a deterministic finite automaton whose execution, guided by the subject string, determines whether there is a match.

Characters match themselves, except for the following special characters.

.  [  {  }  (  )  \  *  +  ?  |  ^  $

Regular expressions are constructed inductively as follows: the empty regular expression matches the empty string; a concatenation of regular expressions matches the concatenation of the corresponding matching strings. Regular expressions separated by the character | match strings matched by any of them. Parentheses can be used for grouping, except that now, with the use of the Boost library, their insertion may alter the matching of subexpressions of ambiguous expressions. Additionally, the substrings matched by parenthesized subexpressions are captured for later use in replacement strings.

Syntax for special characters

• Wildcard
  • . -- match any character except the newline character
• Anchors
  • ^ -- match the beginning of the string or the beginning of a line
  • $ -- match the end of the string or the end of a line
• Sub-expressions
  • (...) -- marked sub-expression, may be referred to by a back-reference
  • \i -- match the same string that the i-th parenthesized sub-expression matched
• Repeats
  • * -- match previous expression 0 or more times
  • + -- match previous expression 1 or more times
  • ? -- match previous expression 1 or 0 times
  • {m} -- match previous expression exactly m times
  • {m,n} -- match previous expression at least m and at most n times
  • {,n} -- match previous expression at most n times
  • {m,} -- match previous expression at least m times
• Alternation
  • | -- match expression to left or expression to right
• Word and buffer boundaries
  • \b -- match word boundary
  • \B -- match within word
  • \< -- match beginning of word
  • \> -- match end of word
  • \` -- match beginning of string
  • \' -- match end of string
• Character sets
  • [...] -- match any single character that is a member of the set
    • [abc] -- match either a, b, or c
    • [A-C] -- match any character from A through C
  • [^...] -- match non-listed characters, ranges, or classes
• Character classes
  • [:alnum:] -- any alphanumeric character
  • [:alpha:] -- any alphabetic character
  • [:blank:] -- any whitespace or tab character
  • [:cntrl:] -- any control character
  • [:digit:] -- any decimal digit
  • [:graph:] -- any graphical character (same as [:print:] except omits space)
  • [:lower:] -- any lowercase character
  • [:print:] -- any printable character
  • [:punct:] -- any punctuation character
  • [:space:] -- any whitespace, tab, carriage return, newline, vertical tab, and form feed
  • [:unicode:] -- any unicode character with code point above 255 in value
  • [:upper:] -- any uppercase character
  • [:word:] -- any word character (alphanumeric characters plus the underscore
  • [:xdigit:] -- any hexadecimal digit character
• "Single character" character classes
  • \d -- same as [[:digit:]]
  • \l -- same as [[:lower:]]
  • \s -- same as [[:space:]]
  • \u -- same as [[:upper:]]
  • \w -- same as [[:word:]]
  • \D -- same as [^[:digit:]]
  • \L -- same as [^[:lower:]]
  • \S -- same as [^[:space:]]
  • \U -- same as [^[:upper:]]
  • \W -- same as [^[:word:]]

The special character \ may be confusing, as inside a string delimited by quotation marks ("..."), you type two of them to specify a special character, whereas inside a string delimited by triple slashes (///...///), you only need one. Thus regular expressions delimited by triple slashes are more readable. To match \ against itself, double the number of backslashes.

In order to match one of the special characters itself, precede it with a backslash or use regexQuote.

Flavors of Regular Expressions

The regular expression functions in Macaulay2 are powered by calls to the Boost.Regex C++ library, which supports multiple flavors, or standards, of regular expression.

Since Macaulay2 v1.17 (missing documentation) , the Perl flavor is the default. In general, the Perl flavor supports all patterns designed for the POSIX Extended flavor, but allows for more fine-tuning in the patterns. Alternatively, the POSIX Extended flavor can be chosen by passing the option POSIX => true. One key difference is what happens when there is more that one way to match a regular expression:

• Perl -- the "first" match is arrived at by a depth-first search.
• POSIX -- the "best" match is obtained using the "leftmost-longest" rule;

If there's a tie in the POSIX flavor, the rule is applied to the first parenthetical subexpression.

Additional Perl Regular Expression Syntax

The Perl flavor adds the following, non-backward compatible constructions:

Non-marking grouping; i.e., a grouping that does not generate a sub-expression

• (?#...) -- ignored and treated as a comment
• (?:...) -- non-marked sub-expression, may not be referred to by a back-reference
• (?=...) -- positive lookahead; consumes zero characters, only if pattern matches
• (?!...) -- negative lookahead; consumes zero characters, only if pattern does not match
• (?<=..) -- positive lookbehind; consumes zero characters, only if pattern could be matched against the characters preceding the current position (pattern must be of fixed length)
• (?<!..) -- negative lookbehind; consumes zero characters, only if pattern could not be matched against the characters preceding the current position (pattern must be of fixed length)
• (?>...) -- match independently of the surrounding pattern and the expression will never backtrack into the pattern

Non-greedy repeats

• *? -- match the previous atom 0 or more times, while consuming as little input as possible
• +? -- match the previous atom 1 or more times, while consuming as little input as possible
• ?? -- match the previous atom 1 or 0 times, while consuming as little input as possible
• {m,}? -- match the previous atom m or more times, while consuming as little input as possible
• {m,n}? -- match the previous atom at between m and n times, while consuming as little input as possible

Possessive repeats

• *+ -- match the previous atom 0 or more times, while giving nothing back
• ++ -- match the previous atom 1 or more times, while giving nothing back
• ?+ -- match the previous atom 1 or 0 times, while giving nothing back
• {m,}+ -- match the previous atom m or more times, while giving nothing back
• {m,n}+ -- match the previous atom at between m and n times, while giving nothing back

Back references

• \g1 -- match whatever matched sub-expression 1
• \g{1} -- match whatever matched sub-expression 1
• \g-1 -- match whatever matched the last opened sub-expression
• \g{-2} -- match whatever matched the last but one opened sub-expression
• \g{that} -- match whatever matched the sub-expression named "that"
• \k<that> -- match whatever matched the sub-expression named "that"
• (?<NAME>...) -- named sub-expression, may be referred to by a named back-reference
• (?'NAME'...) -- named sub-expression, may be referred to by a named back-reference

See references below for more in depth syntax for controlling the backtracking algorithm.

String Formatting Syntax

The replacement string in replace(String,String,String) and select(String,String,String) supports additional syntax for escape sequences as well as inserting captured sub-expressions:

Using Perl regular expression syntax (default)

• Syntax for inserting captured sub-expressions:
  • $& -- outputs what matched the whole expression
  • $` -- outputs the text between the end of the last match (or beginning if no previous match was found) and the start of the current match
  • $' -- outputs the text following the end of the current match
  • $+ -- outputs what matched the last marked sub-expression in the regular expression
  • $^N -- outputs what matched the last sub-expression to be actually matched
  • $n -- outputs what matched the n-th sub-expression
  • ${n} -- outputs what matched the n-th sub-expression
  • $+{NAME} -- outputs what matched the sub-expression named NAME (Perl syntax only)
  • $$ -- outputs a literal $
• Syntax for manipulating the captured groups:
  • \l -- converts the next character to be outputted to lower case
  • \u -- converts the next character to be outputted to upper case
  • \L -- converts all subsequent characters to be outputted to lower case, until it reaches \E
  • \U -- converts all subsequent characters to be outputted to upper case, until it reaches \E
  • \E -- terminates a \U or \L sequence
  • \ -- specifies an escape sequence (e.g. \\)

Using POSIX Extended syntax (POSIX => true)

• Syntax for inserting captured groups:
  • & -- outputs what matched the whole expression
  • \0 -- outputs what matched the whole expression
  • \n -- if n is in the range 1-9, outputs what matched the n-th sub-expression
  • \ -- specifies an escape sequence (e.g. \&)

For the complete list, including characters escape sequences, see the Boost.Regex manual on format string syntax.

String processing functions that accept regular expressions

• match -- regular expression matching
• regex -- evaluate a regular expression search
• separate -- split a string into substrings using a regular expression
• select(String,String,String) -- select and reformat substrings matching a regular expression
• replace(String,String,String) -- replace substrings matching a regular expression

Other functions that accept regular expressions

• about -- search the documentation
• apropos -- symbols matching a pattern
• findFiles -- find files recursively
• copyDirectory
• symlinkDirectory -- make symbolic links for all files in a directory tree

Complete References

For complete documentation on regular expressions supported in Macaulay2, see the Boost.Regex manual on Perl and Extended flavors, or read the entry for regex in section 7 of the unix man pages.

In addition to the functions mentioned below, regular expressions appear in about, apropos, findFiles, copyDirectory, and symlinkDirectory.