Regular Expression

Regular expressions are essentially search patterns defined by a sequence of characters. Let's say, we wish to search for the substring 'grey' in a text document. This is a simple string search. What if we wish to search for both 'grey' and 'gray'? With simple string searches, we would need to do two separate searches and collate the results. With regular expressions, we can define a single search pattern that will give us matches for either of the two substrings.

In the above example, any of these patterns will work: gr[ae]y, gr(a|e)y, (gray|grey), gray|grey

Regular expression is commonly known as regex. Although regex has a history going back to the 1950s, it was popularized in computer science in the 1990s by the Perl programming language. Apart from Perl's regex, many other variants exist.

Discussion

  • Could you give examples where regular expressions are used?
    A regex to match email addresses. Source: Computer Hope 2017.
    A regex to match email addresses. Source: Computer Hope 2017.

    Regex is useful typically when the format or syntax of data is known. It's to this expected syntax that a regex is written. For example, email addresses are of the form username@domainname.tld. We can make a regex to extract all emails coming from a specific domain.

    A common use of regex is for search-and-replace. For example, developers can use regex to quickly change the order of arguments across hundreds of source code files.

    Regex can be used to process log files and filter log messages that match a particular signature. It can be used to filter reports on Google Analytics Dashboard.

    Regex can also be used within database commands, say, to obtain usernames that contain non-alphanumeric characters in them.

    Suppose we've reorganized the file structure in a web application. In web servers, regex can be used to match requested URL patterns and redirect them to new locations. Regex is also useful in web scraping tasks.

  • What are the basic building blocks of regular expressions?
    Regex basics. Source: Upscene 2015.
    Regex basics. Source: Upscene 2015.

    A regex has these basic building blocks:

    • Anchor: A regex is processed by a regex engine. Anchors make assertions about the current position of the engine. Common anchors are ^ (beginning of line) and $ (end of line). For a multiline input, we can use \A and \z to match beginning and end of string respectively.
    • Character: . matches any character; \s matches any whitespace; [12a-c] matches the set of characters '1 2 a b c'; (a|e)s matches 'a' or 'e' followed by 's'.
    • Group: A sequence of characters grouped within ().
    • Quantifier: Specify how many matches of the character or group are allowed. For zero or more matches, use *; + for one or more matches; ? for zero or one match; {m,n} for m to n matches.
    • Modifier/Flag: Modify the regex in specific ways. Use i for case insensitive match; m is for multiline match; s for single line match so that . matches newlines as well.

    For example, /^model{1,2}(ing)? /i will match any line starting with 'model ', 'modell ', 'modeling ', 'modelling ', and their lowercase versions.

  • Which are the special characters in regex?

    Regex special characters are often called metacharacters. The common ones include \ ^ $ . * + ? [ { ( ) | characters.

    Note that characters } ] have special meaning too when used with their counterparts { [; but on their own, they are treated literally. For example, a(b{2,})?c will match 'ac', 'abbc', 'abbbbc' and more; ab}?c will match exactly either 'abc' or 'ab}c', and nothing else.

    Since metacharacters have special meaning, to use them literally, we would have to escape them with the backslash \ character. For example, to match the dollar value in string 'This costs $22.50 after discount', the regex would be \$(\d+(?:\.\d+)?), where the dollar symbol is escaped. It's treated literally and not as end of the string.

    Metacharacter pair [] defines a character class. When range is specified, such as [0-6], hyphen character is a special character. However, if hyphen occurs without either start or end, such as [-6], it's interpreted literally. Likewise, other metacharacters are interpreted literally within a character class. This is therefore an alternative to escaping with backslash.

  • What are regex groups and how are they useful?

    Parts of a regex can be grouped within parentheses, (). A quantifier can be applied to an entire group. Thus, ab+ will match 'abb' but (ab)+ will match 'ab' and 'abab' but not 'abb'. Groups are also useful to restrict alternation. Thus, cat|dogs will match either 'cat' or 'dogs' but (cat|dog)s will match either 'cats' or 'dogs'.

    Groups are generally of three types:

    • Numbered Capturing Group: Each group within a regex is given a number starting from 1. The number 0 is reserved for the entire regex. This number can later be used within the regex for subsequent matches or in a replacement string. These are called backreferences.
    • Named Capturing Group: First introduced in Python, naming the groups make it easier to backreference. For example, we match one or more digits into a named group called 'score' using (?P<score>\d+) and backreference it as (?P=score).
    • Non-Capturing Group: Sometimes we wish to match a group but we're not going to backreference it later. Therefore, there's no need to capture the group. For example, here we match one or more word characters without capture, (?:\w+).
  • Could you explain the concepts of lookahead and lookbehind in regex?
    Illustrating regex lookaround assertions. Source: Adapted from Jain 2017, slide 16.
    Illustrating regex lookaround assertions. Source: Adapted from Jain 2017, slide 16.

    Sometimes we wish to match a string but only if it occurs in a certain context. For example, we wish to match all dark versions of colours that start with 'g': darkgreen, darkgrey, darkgray, etc. While dark(g[a-z]+) will do the job, an alternative is to match the base colour and look behind to see if it's dark: (?<=dark)g[a-z+]. The full match will return only the colour without the 'dark' prefix.

    Looking before or after a particular match is called lookaround assertion. It's called an assertion because it doesn't consume characters from the input. They only declare if there's a match or not. We illustrate examples of the four lookaround assertions:

    • Positive lookahead: Match 'q' that's followed by 'u', q(?=u).
    • Negative lookahead: Match 'q' that's not followed by 'u', q(?!u).
    • Positive lookbehind: Match 'b' that follows 'a', (?<=a)b.
    • Negative lookbehind: Match 'b' that doesn't follow 'a', (?<!a)b.
  • What are some other advanced regex features?

    Some advanced regex features include the following:

    • Laziness: A regex such as .*, is greedy. It will match as many characters as possible preceding a comma. A lazy or non-greedy match is achieved using '?', such as .*?,. This will match only till the first comma.
    • Possessive Quantifier: Using '+', such as .*+, we can tell the regex engine to avoid unnecessary backtracking. This can be seen as a notational convenience for atomic grouping.
    • Atomic Grouping: These are special non-capturing groups to prevent unnecessary backtracking. Use of atomic grouping improves performance. An example of this is (?>his|this). If 'his' is not present, obviously we don't need to backtrack and look for 'this'.
    • Conditionals: We can use lookaround assertions for specifying conditions. Depending on condition's result (true or false), other parts of the regex can be processed.
    • Recursion: Use (?R) to match nested constructs.
  • Do regular expressions differ across programming languages?

    Regular expressions are processed by regex engines, of which there are many flavours. A programming language typically adopts one of these engines. Differences across these flavours are not easy to remember. Programmers should be aware that migrating regex from one engine to another must be accompanied with proper testing.

    Some of these flavours include JGsoft, .NET, Perl, PHP, R, JavaScript, Python, Tcl ARE, POSIX BRE, POSIX ERE, GNU BRE and GNU ERE. The oldest of these is the Basic Regular Expression (BRE) that has limited power and expressiveness. BRE was later extended to the Extended Regular Expression (ERE). To study how these various engines differ, take a look at Roger Qiu's comparison chart or Wikipedia's entry.

    As an example, sed tool uses BRE by default, where + matches literal plus sign. But with option -E it uses ERE, where \+ must be used for literal match.

    Since Perl popularized regex, one of the popular engines that came about is called Perl Compatible Regular Expression (PCRE). PCRE was later updated to PCRE2. PCRE and its variants have been adopted by many programming languages.

  • What are some tips or best practices for using regex?

    For readable and maintainable regex, use the flag x to ignore whitespace. Thus, a complex regex can be expanded with useful comments.

    To find match in the right place, use anchors. The use of .* can make the engine backtrack often. Construct a more specific regex. Likewise, the use of lazy quantifier {.*?} can be inefficient. Instead, say what you don't want to match, {[^}]*}. Also, atomic groups can save on backtracking. However, lazy quantifiers can be better in some simple scenarios: *?'s is faster than *'s.

    Regex must be designed to fail fast. For example, (?=.*fleas).* does a lot of backtracking on lines that don't contain 'fleas'. On the other hand, ^(?=.*fleas).* has a lookahead anchored at the start of the string and will fail faster.

    Use contrast, that is, what characters to match and what not to match. For example, to match 'ABC123' the regex ^.+\d{3}$ won't work since . and \d are not mutually exclusive. Instead, use ^\D+\d{3}$.

    When using alternations (use of |), put the more common patterns earlier.

  • Where should I not use regular expressions?

    While regex is useful, it can be overused and abused. An extreme example is a 6343-character long regex to match an email address. Here's a quote from 1997, attributed to Jamie Zawinski,

    Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.

    While URL paths and email addresses can be parsed using regex, there are dedicated and mature libraries to do these. You should prefer to use them instead. Regex is also not the best choice for parsing HTML or code since there are better tools to generate tokenized outputs.

    Humans write in a number of different ways. A regex will not adequately capture all the different variations. In general, when code is read and maintained by many developers, complex regex will be problematic. Regex is generally not descriptive enough to match balanced parenthesis, such as, (aa (bbb) (bbb) aa).

  • Could you point me to useful resources for working with regex?
    Debuggex helps in visualizing your regex. Source: Debuggex 2019.
    Debuggex helps in visualizing your regex. Source: Debuggex 2019.

    Among the places to learn regex are RegexOne, RexEgg, Regex Crossword and Jan Goyvaerts' Regular-Expressions.info. Beginners might like Net Ninja's series of sixteen videos on regex.

    For absolute basics, consider reading Mike Malone's blog post from 2007.

    A classic book on regex is Mastering Regular Expressions by Jeffrey Friedl. Another good book is Regular Expressions Cookbook by Jan Goyvaerts and Steven Levithan. Dave Child has published a handy regex cheatsheet.

    There are many websites that help with debugging and visualizing regex patterns and their matches. A few recommended ones include Regex101, Debuggex and RegExr. These typically support multiple regex flavours. Regex Storm is particular to .NET regex flavour; Rubular is for Ruby regex. You can also read a comparison of some online regex testers.

Milestones

1956

Mathematician Stephen Cole Kleene coins the term regular expressions as a notation for expressing the algebra of regular sets. The regex metacharacter * is named Kleene star in his honour.

1967

Ken Thompson at Bell Labs writes a new version of QED text editor for the MIT CTSS system. He introduces regular expressions to QED, thus bringing regex from the world of mathematics to computer science for the first time. Regex in QED is also compiled on the fly, for which Thompson receives a US patent.

1970

In this decade, regex makes its way into some Unix programs and utilities such as sed, awk and grep. It's been said that awk is the first language to make regex a first class programming construct. In 1975, Al Aho creates egrep command with a much more expressive syntax that the basic one supported by grep.

1986

Henry Spencer expands the regex syntax and provides an engine for the same. His regex library could be freely included in other programs. He later goes on to create an even better regex engine for Tcl.

1992
POSIX character classes mapped to equivalent regex. Source: Goyvaerts 2018d.
POSIX character classes mapped to equivalent regex. Source: Goyvaerts 2018d.

IEEE defines POSIX BRE and POSIX ERE as part the standard IEEE Std 1003.1-1992.

1997

Philip Hazel releases the PCRE regex library. This is later adopted by PHP, Apache and many others. This follows the syntax and semantics of Perl5. In 2015, PCRE2 is released.

1998

In the 1990s, Larry Wall, the creator of Perl, adopts and expands on Spencer's library. Perl 5.005 is released in 1998 and it includes enhancements to the regex engine. Perl's innovation on regex include lazy quantifiers, non-capturing parentheses, inline mode modifiers, lookahead, and a readability mode. ColdFusion, Java, JavaScript, the .NET Framework, PHP, Python, and Ruby are some of the languages that have since adopted Perl's regex syntax and features.

References

  1. Atwood, Jeff. 2005. "Regex use vs. Regex abuse." Coding Horror, February 15. Accessed 2019-05-08.
  2. Atwood, Jeff. 2008. "Regular Expressions: Now You Have Two Problems." Coding Horror, June 27. Accessed 2019-05-04.
  3. Bennett, Liz. 2015. "Five Invaluable Techniques to Improve Regex Performance." Loggly Blog, June 30. Accessed 2019-05-04.
  4. Bezroukov, Nikolai. 2019. "Perl Regex History." Softpanorama, March 12.Accessed 2019-05-04.
  5. Byington, Ryan. 2005. ".NET Regular Expressions: Regex and Balanced Matching." MSDN Blog, Microsoft, March 15. Accessed 2019-05-08.
  6. Chanut, Frederic. 2016. "Regex Characters Explained." In Marketing We Trust, August 01. Updated 2017-08-29. Accessed 2019-05-04.
  7. Computer Hope. 2017. "Regex." Computer Hope, April 26. Accessed 2019-05-04.
  8. Debuggex. 2019. "Homepage." Debuggex. Accessed 2019-05-08.
  9. DevDojo. 2018. "5 Online Resources for Learning Regex." DevDojo, February 07. Accessed 2019-05-04.
  10. Engineer Man. 2018. "Python Web Scraping with Beautiful Soup and Regex." YouTube, September 23. Accessed 2019-05-04.
  11. FSF. 2018. "GNU sed, a stream editor." Version 4.7, GNU, Free Software Foundation. Accessed 2019-05-12.
  12. Friedl, Jeffrey. 2006. "Source of the famous “Now you have two problems” quote." September 15. Accessed 2019-05-04.
  13. Goyvaerts, Jan. 2016a. "Regular Expressions Quick Start." Regular-Expressions.info, December 08. Accessed 2019-05-04.
  14. Goyvaerts, Jan. 2016b. "Named Capturing Groups and Backreferences." Regular-Expressions.info, December 08. Accessed 2019-05-04.
  15. Goyvaerts, Jan. 2016c. "If-Then-Else Conditionals in Regular Expressions." Regular-Expressions.info, November 25. Accessed 2019-05-04.
  16. Goyvaerts, Jan. 2016d. "Possessive Quantifiers." Regular-Expressions.info, November 30. Accessed 2019-05-04.
  17. Goyvaerts, Jan. 2017a. "Literal Characters and Special Characters." Regular-Expressions.info, December 25. Accessed 2019-05-04.
  18. Goyvaerts, Jan. 2017b. "POSIX Basic Regular Expressions." Regular-Expressions.info, June 30. Accessed 2019-05-04.
  19. Goyvaerts, Jan. 2017c. "The PCRE Open Source Regex Library." Regular-Expressions.info, June 30. Accessed 2019-05-04.
  20. Goyvaerts, Jan. 2018a. "Regular Expressions Reference." Regular-Expressions.info, May 18. Accessed 2019-05-04.
  21. Goyvaerts, Jan. 2018b. "Lookahead and Lookbehind Zero-Length Assertions." Regular-Expressions.info, September 11. Accessed 2019-05-04.
  22. Goyvaerts, Jan. 2018c. "Use Parentheses for Grouping and Capturing." Regular-Expressions.info, July 01. Accessed 2019-05-04.
  23. Goyvaerts, Jan. 2018d. "POSIX Bracket Expressions." Regular-Expressions.info, November 30. Accessed 2019-05-04.
  24. IEEE. 1993. "1003.2-1992 - IEEE Standard for Information Technology--Portable Operating System Interfaces (POSIX(R))--Part 2: Shell and Utilities." IEEE, June 23. Accessed 2019-05-08.
  25. Jain, Neha. 2017. "Advanced regular expressions." SlideShare, September 29. Accessed 2019-05-08.
  26. Kuchling, A.M. 2019. "Regular Expression HOWTO." Python HOWTOs, Python Docs v3.7.3, May 03. Accessed 2019-05-04.
  27. Levithan, Steven. 2008. "Regex Legends: The People Behind the Magic." Flagrant Badassery, January 13. Accessed 2019-05-04.
  28. Malone, Mike. 2007. "The absolute bare minimum every programmer should know about regular expressions." April 06. Accessed 2019-05-08.
  29. Mourzenko, Arseni. 2011. "When you should NOT use Regular Expressions?" Software Engineering, StackExchange, October 09. Accessed 2019-05-04.
  30. PCRE. 2019. "PCRE - Perl Compatible Regular Expressions." Accessed 2019-05-08.
  31. RegexOne. 2019. " Problem 7: Extracting information from a log file." RegexOne. Accessed 2019-05-04.
  32. RexEgg. 2015a. "Is a Regex the Same as a Regular Expression?" Accessed 2019-05-04.
  33. RexEgg. 2015b. "The Many Uses of Regex." Accessed 2019-05-04.
  34. RexEgg. 2015c. "The Elements of Good Regex Style." Accessed 2019-05-04.
  35. RexEgg. 2015d. "Regex Anchors." Accessed 2019-05-08.
  36. Ritchie, Dennis. 2019. "An incomplete history of the QED Text Editor." Accessed 2019-05-08.
  37. Rualthanzauva, Benjamin. 2014. "“grep was a private command of mine for quite a while before i made it public.” -Ken Thompson." Medium, February 05. Accessed 2019-05-08.
  38. Upscene. 2015. "Regular Expressions." FB TraceManager Docs, v3.5.4.9, Upscene Productions, October 17. Accessed 2019-05-04.
  39. Viswanathan, Karthik. 2009. "Crucial Concepts Behind Advanced Regular Expressions." Smashing Magazine, May 06. Accessed 2019-05-08.
  40. Wikipedia. 2019a. "Regular expression." Wikipedia, April 29. Accessed 2019-05-04.
  41. Wikipedia. 2019b. "Perl." Wikipedia, April 24. Accessed 2019-05-04.
  42. Wojciechowski, Jarek. 2018. "Regular Expressions Are Great… Sometimes." Atomic Object, February 21. Accessed 2019-05-04.

Further Reading

  1. Chanut, Frederic. 2016. "Regex Characters Explained." In Marketing We Trust, August 01. Updated 2017-08-29. Accessed 2019-05-04.
  2. Malone, Mike. 2007. "The absolute bare minimum every programmer should know about regular expressions." April 06. Accessed 2019-05-08.
  3. Engineer Man. 2018. "Regular Expressions - Enough to be Dangerous." YouTube, August 05. Accessed 2019-09-08.

Article Stats

Author-wise Stats for Article Edits

Author
No. of Edits
No. of Chats
DevCoins
7
0
2481
1
0
16
2175
Words
5
Likes
17K
Hits

Cite As

Devopedia. 2022. "Regular Expression." Version 8, February 15. Accessed 2024-06-25. https://devopedia.org/regular-expression
Contributed by
2 authors


Last updated on
2022-02-15 11:53:08
  • Regular Expressions in Python
  • Regular Expressions in Perl
  • Regex Engines
  • Regex Optimization
  • String Searching Algorithm
  • Pattern Matching