# Tips for Regex Golf

Similar to our threads for language-specific golfing tips: what are general tricks to shorten regular expressions?

I can see three uses of regex when it comes to golfing: classic regex golf ("here is a list that should match, and here is a list that should fail"), using regex to solve computational problems and regular expressions used as parts of larger golfed code. Feel free to post tips addressing any or all of these. If your tip is limited to one or more flavours, please state these flavours at the top.

As usual, please stick to one tip (or family of very closely related tips) per answer, so that the most useful tips can rise to the top via voting.

• Flagrant self-promotion: what category of regex-use does this fall into? codegolf.stackexchange.com/a/37685/8048 – Kyle Strand Mar 8 '15 at 8:53
• @KyleStrand "regular expressions used as parts of larger golfed code." – Martin Ender Mar 8 '15 at 12:42

# When not to escape

These rules apply to most flavours, if not all:

• ] doesn't need escaping when unmatched.

• { and } don't need escaping when they are not part of a repetition, e.g. {a} matches {a} literally. Even if you want to match something like {2}, you only need to escape one of them, e.g. {2\}.

In character classes:

• ] doesn't need escaping when it's the first character in a character set, e.g. []abc] matches one of ]abc, or when it's the second character after a ^, e.g. [^]] matches anything but ]. (Notable exception: ECMAScript flavour!)

• [ doesn't need escaping at all. Together with the above tip, this means you can match both brackets with the horribly counter-intuitive character class [][].

• ^ doesn't need escaping when it's not the first character in a character set, e.g. [ab^c].

• - doesn't need escaping when it's either the first (second after a ^) or last character in a character set, e.g. [-abc], [^-abc] or [abc-].

• No other characters need escaping inside a character class, even if they are meta characters outside of character classes (except for backslash \ itself).

# Recursion for pattern reuse

A handful of flavours support recursion (to my knowledge, Perl, PCRE and Ruby). Even when you're not trying to solve recursive problems, this feature can save a lot of bytes in more complicated patterns. There is no need to make the call to another (named or numbered) group inside that group itself. If you have a certain pattern that appears several times in your regex, just group it and refer to it outside that group. This is no different from a subroutine call in normal programming languages. So instead of

...someComplexPatternHere...someComplexPatternHere...someComplexPatternHere...


in Perl/PCRE you could do:

...(someComplexPatternHere)...(?1)...(?1)...


or in Ruby:

...(someComplexPatternHere)...\g<1>...\g<1>...


provided that is the first group (of course, you can use any number in the recursive call).

Note that this is not the same as a backreference (\1). Backreferences match the exact same string that the group matched last time. These subroutine calls actually evaluate the pattern again. As an example for someComplexPatternHere take a lengthy character class:

a[0_B!$]b[0_B!$]c[0_B!$]d  This would match something like aBb0c!d  Note that you cannot use backreferences here while preserving the behaviour. A backreference would fail on the above string, because B and 0 and ! are not the same. However, with subroutine calls, the pattern is actually reevaluated. The above pattern is completely equivalent to a([0_B!$])b(?1)c(?1)d


### Capturing in subroutine calls

One note of caution for Perl and PCRE: if group 1 in the above examples contains further groups, then the subroutine calls will not remember their captures. Consider this example:

(\w(\d):)\2 (?1)\2 (?1)\2


This will not match

x1:1 y2:2 z3:3


because after the subroutine calls return, the new capture of group 2 is discarded. Instead, this pattern would match this string:

x1:1 y2:1 z3:1


This is different from Ruby, where subroutine calls do retain their captures, so the equivalent Ruby regex (\w(\d):)\2 \g<1>\2 \g<1>\2 would match the first of the examples above.

• You can use \1 for Javascript. And PHP too (I guess). – Ismael Miguel Mar 5 '15 at 23:13
• @IsmaelMiguel This is not a backreference. This actually evaluates the pattern again. For instance (..)\1 would match abab but fail on abba whereas (..)(?1) will match the latter. It's actually a subroutine call in the sense that the expression is applied again, instead of literally matching what it matched last time. – Martin Ender Mar 5 '15 at 23:16
• Wow, I had no idea! Learning something new everyday – Ismael Miguel Mar 5 '15 at 23:22
• In .NET (or other flavors without this feature): (?=a.b.c)(.[0_B!$]){3}d – jimmy23013 Mar 13 '15 at 8:45 • @user23013 that seems very specific to this particular example. I'm not sure that's applicable if I reuse a certain subpattern in various lookarounds. – Martin Ender Mar 13 '15 at 9:19 # Causing a match to fail When using regex to solve computational problems or match highly non-regular languages, it is sometimes necessary to make a branch of the pattern fail regardless of where you are in the string. The naive approach is to use an empty negative lookahead: (?!)  The contents (the empty pattern) always matches, so the negative lookahead always fails. But more often than not, there is a much simpler option: just use a character you know will never appear in the input. E.g. if you know your input will always consist only of digits, you can simply use !  or any other non-digit, non-meta character to cause failure. Even if your input could potentially contain any substrings whatsoever, there are shorter ways than (?!). Any flavour which allows anchors to appear within a pattern as opposed to the end, could use either of the following 2-character solutions: a^$a


Note however that some flavours will treat ^ and $ as literal characters in these positions, because they obviously don't actually make sense as anchors. In the ECMAScript flavour there is also the rather elegant 2-character solution []  This is an empty character class, which tries to make sure that the next characters is one of those in the class - but there are no characters in the class, so this always fails. Note that this won't work in any other flavour, because character classes can't usually be empty. # Optimize you OR's Whenever you have 3 or more alternatives in your RegEx: /aliceblue|antiquewhite|aquamarine|azure/  Check to see if there's a common start: /a(liceblue|ntiquewhite|quamarine|zure)/  And maybe even a common ending? /a(liceblu|ntiquewhit|quamarin|zur)e/  Note: 3 is just the start and would account for the same length, 4+ would make a difference But what if not all of them have a common prefix? (whitespace only added for clarity) /aliceblue|antiquewhite|aqua|aquamarine|azure |beige|bisque|black|blanchedalmond|blue|blueviolet|brown|burlywood |cadetblue|chartreuse|chocolate|coral|cornflowerblue|cornsilk|crimson|cyan/  Group them, as long as the 3+ rule makes sense: /a(liceblue|ntiquewhite|qua|quamarine|zure) |b(eige|isque|lack|lanchedalmond|lue|lueviolet|rown|urlywood) |c(adetblue|hartreuse|hocolate|oral|ornflowerblue|ornsilk|rimson|yan)/  Or even generalise if the entropy satisfies your usecase: /\w(liceblue|ntiquewhite|qua|quamarine|zure |eige|isque|lack|lanchedalmond|lue|lueviolet|rown|urlywood |adetblue|hartreuse|hocolate|oral|ornflowerblue|ornsilk|rimson|yan)/  ^ in this case we're sure we don't get any clue or crown slack Ryan This "according to some tests" also improves performance, as it provides an anchor to start at. • If the common start or end is longer than one character, even grouping two can make a difference. Like aqua|aquamarineaqua(|marine) or aqua(marine)?. – Paŭlo Ebermann Mar 8 '15 at 11:16 This one is fairly simple, but worth stating: If you find yourself repeating the character class [a-zA-Z] you can probably just use [a-z] and append the i (case-insensitive modifier) to your regex. For example, in Ruby, the following two regexes are equivalent: /[a-zA-Z]+\d{3}[a-zA-Z]+/ /[a-z]+\d{3}[a-z]/i - 7 bytes shorter For that matter, the other modifiers can shorten your total length as well. Instead of doing this: /(.|\n)/ which matches ANY character (because dot doesn't match newline), use the single-line modifier s, which makes dot match newlines. /./s - 3 bytes shorter In Ruby, there are a ton of built-in Character Classes for regex. See this page and search for "Character Properties". A great example is the "Currency Symbol". According to Wikipedia there are a ton of possible currency symbols, and to put them in a character class would be very expensive ([$฿¢₡Ð₫€.....]) whereas you can match any of them in 6 bytes: \p{Sc}

• Excepting JavaScript, where s modifier is not supported. :( But there you can use JavaScript's proprietary /[^]/ trick. – manatwork Mar 5 '15 at 15:08
• Note that (.|\n) doesn't even work in some flavours, because . often also doesn't match other types of line separators. However, the customary way to do this (without s) is [\s\S] which is the same bytes as (.|\n). – Martin Ender Mar 5 '15 at 23:55
• @MartinBüttner, my idea was to keep it together with the other line ending related tips. But if you feel this answer is more about modifiers, I have no objections if you repost it. – manatwork Mar 6 '15 at 8:40
• @manatwork done (and added a related non-ES specific trick as well) – Martin Ender Mar 6 '15 at 9:07

# A simple language parser

You can build a very simple parser with an RE like \d+|\w+|".*?"|\n|\S. The tokens you need to match are separated with the RE 'or' character.

Each time the RE engine tries to match at the current position in the text, it will try the first pattern, then the second, etc. If it fails (on a space character here for example), it moves on and tries the matches again. Order is important. If we placed the \S term before the \d+ term, the \S would match first on any non-space character which would break our parser.

The ".*?" string matcher uses a non-greedy modifier so we only match one string at a time. If your RE doesn't have non-greedy functions, you can use "[^"]*" which is equivalent.

### Python Example:

text = 'd="dogfinder"\nx=sum(ord(c)*872 for c in "fish"+d[3:])'
pat = r'\d+|\w+|".*?"|\n|\S'
print re.findall(pat, text)

['d', '=', '"dogfinder"', '\n', 'x', '=', 'sum', '(', 'ord', '(', 'c', ')',
'*', '872', 'for', 'c', 'in', '"fish"', '+', 'd', '[', '3', ':', ']', ')']


### Golfed Python Example:

# assume we have language text in A, and a token processing function P
map(P,findall(r'\d+|\w+|".*?"|\n|\S',A))


You can adjust the patterns and their order for the language you need to match. This technique works well for JSON, basic HTML, and numeric expressions. It has been used successfully many times with Python 2, but should be general enough to work in other environments.

# \K instead of positive lookbehind

PCRE and Perl support the escape sequence \K, which resets the beginning of the match. That is ab\Kcd will require your input string to contain abcd but the reported match will only be cd.

If you are using a positive lookbehind at the start of your pattern (which is probably the most likely place), then in most cases, you can use \K instead and save 3 bytes:

(?<=abc)def
abc\Kdef


This is equivalent for most purposes, but not entirely. The differences bring both advantages and disadvantages with them:

• Upside: PCRE and Perl don't support arbitrary-length lookbehinds (only .NET does). That is, you can't do something like (?<=ab*). But with \K you can put any sort of pattern in front of it! So ab*\K works. This actually makes this technique vastly more powerful in the cases where it's applicable.
• Upside: Lookarounds don't backtrack. This is relevant if you want to capture something in the lookbehind to backreference later, but there are several possible captures which all lead to valid matches. In this case, the regex engine would only ever try one of those possibilities. When using \K that part of the regex is being backtracked like everything else.
• Downside: As you probably know, several matches of a regex cannot overlap. Often, lookarounds are used to partially work around this limitation, since the lookahead can validate a portion of the string that was already consumed by an earlier match. So if you wanted to match all the characters that followed ab you might use (?<=ab).. Given the input

ababc


this would match the second a and the c. This cannot be reproduced with \K. If you used ab\K., you would only get the first match, because now the ab is not in a lookaround.

• If a pattern uses the \K escape sequence within a positive assertion, the reported start of a successful match can be greater than the end of the match. – hwnd Mar 7 '15 at 4:03
• @hwnd My point is that given ababc, there is no way to match both the second a and the c with \K. You'll only get one match. – Martin Ender Mar 7 '15 at 4:07
• You're correct, not with the feature itself. You would have to anchor with \G – hwnd Mar 7 '15 at 4:08
• @hwnd Ah I see your point now. But I guess at that point (from a golfing perspective) you're better off with a negative lookbehind, becaue you actually might even need it anyway since you can't be sure that the . from the last match was actually an a. – Martin Ender Mar 7 '15 at 4:12
• Interesting use of \K =) – hwnd Mar 7 '15 at 15:57

# Matching any character

The ECMAScript flavour is lacking the s modifiers which makes . match any character (including newlines). This means there is no single-character solution to matching completely arbitrary characters. The standard solution in other flavours (when one doesn't want to use s for some reason) is [\s\S]. However, ECMAScript is the only flavour (to my knowledge) which supports empty character classes, and hence has a much shorter alternative: [^]. This is a negated empty character class - that is, it matches any character whatsoever.

Even for other flavours, we can learn from this technique: if we don't want to use s (e.g. because we still need to usual meaning of . in other places), there can still be a shorter way to match both newline and printable characters, provided there is some character we know doesn't appear in the input. Say, we're processing numbers delimited by newlines. Then we can match any character with [^!], since we know that ! won't ever be part of the string. This saves two bytes over the naive [\s\S] or [\d\n].

• In Perl, \N means exactly what . means outside of /s mode, except it isn't affected by a mode. – Konrad Borowski Mar 6 '15 at 17:48

# Use atomic groups and possessive quantifiers

I found atomic groups ((?>...)) and possessive quantifiers (?+, *+, ++, {m,n}+) sometimes very useful for golfing. It matches a string and disallows backtracking later. So it will only match the first matchable string which is found by the regex engine.

For example: To match a string with odd number of a's at the beginning, which is not followed by more a's, you can use:

^(aa)*+a
^(?>(aa)*)a


This allows you to use things like .* freely, and if there is an obvious match, there won't be another possibility matching too many or too few characters, which may break your pattern.

In .NET regex (which doesn't have possessive quantifiers), you can use this to pop group 1 the greatest multiple of 3 (with maximum 30) times (not golfed very well):

(?>((?<-1>){3}|){10})

• ECMAscript is also missing possessive quantifiers or atomic groups :( – CSᵠ Mar 6 '15 at 23:24

# Forget a captured group after a subexpression (PCRE)

For this regex:

^((a)(?=\2))(?!\2)


If you want to clear the \2 after group 1, you can use recursion:

^((a)(?=\2)){0}(?1)(?!\2)


It will match aa while the previous one won't. Sometimes you can also use ?? or even ? in place of {0}.

This might be useful if you used recursions a lot, and some of the backreferences or conditional groups appeared in different places in your regex.

Also note that atomic groups are assumed for recursions in PCRE. So this won't match a single letter a:

^(a?){0}(?1)a


I didn't try it in other flavors yet.

For lookaheads, you can also use double negatives for this purpose:

^(?!(?!(a)(?=\1))).(?!\1)


## Optional expressions

It is sometimes useful to remember that

(abc)?


is mostly the same as

(abc|)


There is a small difference though: in the first case, the group either captures abc or doesn't capture at all. The latter case would make a backreference fail unconditionally. In the second expression, the group will either capture abc or an empty string, where the latter case would make a backreference match unconditionally. To emulate the latter behaviour with ? you'd need to surround everything in another group which would cost two bytes:

((abc)?)


The version using | is also useful when you want to wrap the expression in some other form of group anyway and don't care about the capturing:

(?=(abc)?)
(?=abc|)

(?>(abc)?)
(?>abc|)


Finally, this trick can also be applied to ungreedy ? where it saves a byte even in its raw form (and consequently 3 bytes when combined with other forms of groups):

(abc)??
(|abc)


# Capturing groups hold the last value matched

(REGEX)* will hold in capturing group 1 the last match of REGEX. (REGEX) can be combined with any such repeaters.

For getting the last character of a string, there is the straightforward 5-byter

.*(.)


which captures the last character in capturing group 1. Another byte can be saved by noting the point in the title of this post, giving the 4-byter

(.)*


Another example, getting the penultimate character

.*(.).        # 6 bytes
(.)*.         # 5 bytes


# Multiple lookaheads that always match (.NET)

If you have 3 or more lookahead constructs that always match (to capture subexpressions), or there is a quantifier on a lookahead followed by something else, so they should be in a not necessarily captured group:

(?=a)(?=b)(?=c)
((?=a)b){...}


These are shorter:

(?(?(?(a)b)c))
(?(a)b){...}


where a should not be the name of a captured group. You can't use | to mean the usual thing in b and c without adding another pair of parentheses.

Unfortunately, balancing groups in the conditionals seemed buggy, making it useless in many cases.