Article URL: https://www.npopov.com/2012/06/15/The-true-power-of-regular-expressions.html Comments URL: https://news.ycombinator.com/item?id=49152973 Points: 16 # Comments: 5

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. 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: 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. 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).