The true power of regular expressions

As someone who frequents the PHP tag on StackOverflow I pretty often see questions about how to parse some particular aspect of HTML using regular expressions. A common reply to such a question is: You cannot parse HTML with regular expressions, because HTML isn’t regular. Use an XML parser instead. This statement - in the context of the question - is somewhere between very misleading and outright wrong. What I’ll try to demonstrate in this article is how powerful modern regular expressions really are. What does “regular” actually mean? In the context of formal language theory, something is called “regular” when it has a grammar where all production rules have one of the following forms: B -> a B -> aC B -> ε You can read those -> rules as “The left hand side can be replaced with the right hand side”. So the first rule would be “B can be replaced with a”, the second one “B can be replaced with aC” and the third one “B can be replaced with the empty string” (ε is the symbol for the empty string). So what are B, C and a? By convention, uppercase characters denote so called “non-terminals” - symbols which can be broken down further - and lowercase characters denote “terminals” - symbols which cannot be broken down any further. All that probably sounds a bit abstract, so let’s look at an example: Defining the natural numbers as a grammar. N -> 0 N -> 1 N -> 2 N -> 3 N -> 4 N -> 5 N -> 6 N -> 7 N -> 8 N -> 9 N -> 0N N -> 1N N -> 2N N -> 3N N -> 4N N -> 5N N -> 6N N -> 7N N -> 8N N -> 9N What this grammar says is: A natural number (N) is ... one of the digits 0 to 9 or ... one of the digits 0 to 9 followed by another natural number (N) In this example the digits 0 to 9 would be terminals (as they can’t be broken down any further) and N would be the only non-terminal (as it can be and is broken down further). If you have another look at the rules and compare them to the definition of a regular grammar from above, you’ll see that they meet the criteria: The first ten rules are of the form B -> a and the second ten rules follow the form B -> aC. Thus the grammar defining the natural numbers is regular. Another thing you might notice is that even though the above grammar defines such a simple thing, it is already quite bloated. Wouldn’t it be better if we could express the same concept in a more concise manner? And that’s where regular expressions come in: The above grammar is equivalent to the regex [0-9]+ (which is a hell lot simpler). And this kind of transformation can be done with any regular grammar: Every regular grammar has a corresponding regular expression which defines all its valid strings. What can regular expressions match? Thus the question arises: Can regular expressions match only regular grammars, or can they also match more? The answer to this is both yes and no: Regular expressions in the formal grammar sense can (pretty much by definition) only parse regular grammars and nothing more. But when programmers talk about “regular expressions” they aren’t talking about formal grammars. They are talking about the regular expression derivative which their language implements. And those regex implementations are only very slightly related to the original notion of regularity. Any modern regex flavor can match a lot more than just regular languages. How much exactly, that’s what the rest of the article is about. To keep things simple, I’ll focus on the PCRE regex implementation in the following, simply because I know it best (as it’s used by PHP). Most other regex implementations are quite similar though, so most stuff should apply to them too. The language hierarchy In order to analyze what regular expressions can and cannot match, we first have to look at what other types of languages there are. A good starting point for this is the Chomsky hierarchy: Chomsky hierarchy: /-------------------------------------------\ | | | Recursively enumerable languages | Type 0 | | | /-----------------------------------\ | | | | | | | Context-sensitive languages | | Type 1 | | | | | | /---------------------------\ | | | | | | | | | | | Context-free languages | | | Type 2 | | | | | | | | | /-------------------\ | | | | | | | Regular languages | | | | Type 3 | | | \-------------------/ | | | | | \---------------------------/ | | | \-----------------------------------/ | \-------------------------------------------/ As you can see the Chomsky hierarchy divides formal languages into four types: Regular languages (Type 3) are the least-powerful, followed by the context-free languages (Type 2), the context-sensitive languages (Type 1) and at last the all-mighty recursively enumerable languages (Type 0). The Chomsky hierarchy is a containment hierarchy, so the smaller boxes in the above image are fully contained in the larger boxes. For example every regular language is also a context-free language (but not the other way around!) So, let’s move one step up in that hierarchy: We already know that regular expressions can match any regular language. But can they also match context-free languages? (Reminder: When I say “regular expression” here I obviously mean it in the programmer sense, not the formal language theory sense.) Matching context-free languages The answer to this is yes, they can! Let’s take the classical example of a context-free language, namely {a^n b^n, n>0}, which means “A number of a characters followed by the same number of b characters”. The (PCRE) regex for this language is: /^(a(?1)?b)$/ The regular expression is very simple: (?1) is a reference to the first subpattern, namely (a(?1)?b). So basically you could replace the (?1) by that subpattern, thus forming a recursive dependency: /^(a(?1)?b)$/ /^(a(a(?1)?b)?b)$/ /^(a(a(a(?1)?b)?b)?b)$/ /^(a(a(a(a(?1)?b)?b)?b)?b)$/ # and so on From the above expansions it should be clear that this expression can match any string with the same number of as and bs. Thus regular expressions can match at least some non-regular, context-free grammars. But can they match all? To answer that, we first have to look at how context-free grammars are defined. In a context-free grammar all production rules take the following form: A -> β Here A once again is a non-terminal symbol and β is an arbitrary string of terminals and non-terminals. Thus every production rule of a context-free grammar has a non-terminal on the left hand side and an arbitrary symbol string on the right hand side. As an example, have a look at the following grammar: function_declaration -> T_FUNCTION is_ref T_STRING '(' parameter_list ')' '{' inner_statement_list '}' is_ref -> '&' is_ref -> ε parameter_list -> non_empty_parameter_list parameter_list -> ε non_empty_parameter_list -> parameter non_empty_parameter_list -> non_empty_parameter_list ',' parameter // ... ... ... What you see there is an excerpt from the PHP grammar (just a few sample rules). The syntax is slightly different from what we used before, but should be easy to understand. One aspect worth mentioning is that the uppercase T_SOMETHING names here also are terminal symbols. These symbols which are usually called tokens encode more abstract concepts. E.g. T_FUNCTION represents the function keyword and T_STRING is a label token (like getUserById or some_other_name). I’m using this example to show one thing: Context-free grammars are already powerful enough to encode quite complex languages. That’s why pretty much all programming languages have a context-free grammar. In particular this also includes well-formed HTML. Now, back to the actual question: Can regular expressions match all context-free grammars? Once again, the answer is yes! This is pretty easy to prove as regular expressions (at least PCRE and similar) provide a syntax very similar to the above for constructing grammars: / (?(DEFINE) (?<addr_spec> (?&local_part) @ (?&domain) ) (?<local_part> (?&dot_atom) | (?&quoted_string) | (?&obs_local_part) ) (?<domain> (?&dot_atom) | (?&domain_literal) | (?&obs_domain) ) (?<domain_literal> (?&CFWS)? \[ (?: (?&FWS)? (?&dtext) )* (?&FWS)? \] (?&CFWS)? ) (?<dtext> [\x21-\x5a] | [\x5e-\x7e] | (?&obs_dtext) ) (?<quoted_pair> \\ (?: (?&VCHAR) | (?&WSP) ) | (?&obs_qp) ) (?<dot_atom> (?&CFWS)? (?&dot_atom_text) (?&CFWS)? ) (?<dot_atom_text> (?&atext) (?: \. (?&atext) )* ) (?<atext> [a-zA-Z0-9!#$%&'*+/=?^_`{|}~-]+ ) (?<atom> (?&CFWS)? (?&atext) (?&CFWS)? ) (?<word> (?&atom) | (?&quoted_string) ) (?<quoted_string> (?&CFWS)? " (?: (?&FWS)? (?&qcontent) )* (?&FWS)? " (?&CFWS)? ) (?<qcontent> (?&qtext) | (?&quoted_pair) ) (?<qtext> \x21 | [\x23-\x5b] | [\x5d-\x7e] | (?&obs_qtext) ) # comments and whitespace (?<FWS> (?: (?&WSP)* \r\n )? (?&WSP)+ | (?&obs_FWS) ) (?<CFWS> (?: (?&FWS)? (?&comment) )+ (?&FWS)? | (?&FWS) ) (?<comment> \( (?: (?&FWS)? (?&ccontent) )* (?&FWS)? \) ) (?<ccontent> (?&ctext) | (?&quoted_pair) | (?&comment) ) (?<ctext> [\x21-\x27] | [\x2a-\x5b] | [\x5d-\x7e] | (?&obs_ctext) ) # obsolete tokens (?<obs_domain> (?&atom) (?: \. (?&atom) )* ) (?<obs_local_part> (?&word) (?: \. (?&word) )* ) (?<obs_dtext> (?&obs_NO_WS_CTL) | (?&quoted_pair) ) (?<obs_qp> \\ (?: \x00 | (?&obs_NO_WS_CTL) | \n | \r ) ) (?<obs_FWS> (?&WSP)+ (?: \r\n (?&WSP)+ )* ) (?<obs_ctext> (?&obs_NO_WS_CTL) ) (?<obs_qtext> (?&obs_NO_WS_CTL) ) (?<obs_NO_WS_CTL> [\x01-\x08] | \x0b | \x0c | [\x0e-\x1f] | \x7f ) # character class definitions (?<VCHAR> [\x21-\x7E] ) (?<WSP> [ \t] ) ) ^(?&addr_spec)$ /x What you see above is a regular expression for matching email addresses as per RFC 5322. It was constructed simply by transforming the BNF rules from the RFC into a notation that PCRE understands. The syntax is quite simple: