Getting started with Regular Expressions
For many programmers the regex is some sort of magical sword that they throw to solve any kind of text parsing situation. But this tool is nothing magical, and even though it's great at what it does, it's not a full featured programming language (i.e. it is not Turing-complete).
What does 'regular expression' mean?
Regular expressions express a language defined by a regular grammar that can be solved by a nondeterministic finite automaton (NFA), where matching is represented by the states.
A regular grammar is the most simple grammar as expressed by the Chomsky Hierarchy.
Simply said, a regular language is visually expressed by what an NFA can express, and here's a very simple example of NFA:
And the Regular Expression language is a textual representation of such an automaton. That last example is expressed by the following regex:
Which is matching any string beginning with
1, repeating 0 or more times, that ends with a
1. In other words, it's a regex to match odd numbers from their binary representation.
Are all regex actually a regular grammar?
Actually they are not. Many regex engines have improved and are using push-down automata, that can stack up, and pop down information as it is running. Those automata define what's called context-free grammars in Chomsky's Hierarchy. The most typical use of those in non-regular regex, is the use of a recursive pattern for parenthesis matching.
A recursive regex like the following (that matches parenthesis) is an example of such an implementation:
For more information on the theory behind Regular Expressions, you can refer to the following courses made available by MIT:
- Automata, Computability, and Complexity
- Regular Expressions & Grammars
- Specifying Languages with Regular Expressions and Context-Free Grammars
When you're writing or debugging a complex regex, there are online tools that can help visualize regexes as automatons, like the debuggex site.
Note that some syntax elements have different behavior depending on the expression.
|Match the preceding character or subexpression 0 or 1 times. Also used for non-capturing groups, and named capturing groups.|
|Match the preceding character or subexpression 0 or more times.|
|Match the preceding character or subexpression 1 or more times.|
|Match the preceding character or subexpression exactly n times.|
|Match the preceding character or subexpression min or more times.|
|Match the preceding character or subexpression max or fewer times.|
|Match the preceding character or subexpression at least min times but no more than |
|When included between square brackets indicates |
|Start of string (or start of line if the multiline |
|End of string (or end of a line if the multiline |
|Groups subexpressions, captures matching content in special variables (|
|Groups subexpressions, and captures them in a named group|
|Groups subexpressions without capturing|
|Matches any character except line breaks (|
|Any character between these brackets should be matched once. NB: |
|Escapes the following character. Also used in meta sequences - regex tokens with special meaning.|
|dollar (i.e. an escaped special character)|
|open parenthesis (i.e. an escaped special character)|
|close parenthesis (i.e. an escaped special character)|
|asterisk (i.e. an escaped special character)|
|dot (i.e. an escaped special character)|
|question mark (i.e. an escaped special character)|
|left (open) square bracket (i.e. an escaped special character)|
|backslash (i.e. an escaped special character)|
|right (close) square bracket (i.e. an escaped special character)|
|caret (i.e. an escaped special character)|
|left (open) curly bracket / brace (i.e. an escaped special character)|
|pipe (i.e. an escaped special character)|
|right (close) curly bracket / brace (i.e. an escaped special character)|
|plus (i.e. an escaped special character)|
|start of a string|
|end of a string|
|absolute of a string|
|word (alphanumeric sequence) boundary|
|back-references to previously matched subexpressions, grouped by |
|backspace - when |
|word (i.e. alphanumeric character)|
|named character set|
|or; i.e. delineates the prior and preceding options.|