Understanding Regular Expressions and Formal Language Theory

The Misconception of Regular Expressions

A common statement in programming discussions, particularly regarding HTML parsing, is that "You cannot parse HTML with regular expressions, because HTML isn’t regular." This article addresses this statement, arguing it is often misleading or incorrect in the context of specific parsing needs. It aims to demonstrate the capabilities of modern regular expressions.

Defining "Regular" in Formal Language Theory

In formal language theory, a language is considered "regular" if its grammar adheres to specific production rules. These rules are B -> a, B -> aC, or B -> ε. Here, 'B' and 'C' represent non-terminals (symbols that can be further broken down), and 'a' represents a terminal (a symbol that cannot be broken down further), while 'ε' denotes an empty string.

Example: Natural Numbers as a Regular Grammar

The article provides an example using the grammar for natural numbers to illustrate a regular grammar. This grammar defines a natural number (N) as either a digit from 0 to 9, or a digit from 0 to 9 followed by another natural number. This structure fits the criteria for a regular grammar, with digits acting as terminals and 'N' as the non-terminal.

Regular Expressions for Conciseness

While the grammar for natural numbers is regular, its formal definition can be verbose. Regular expressions offer a more concise way to express such grammars. The example grammar for natural numbers is equivalent to the regular expression [0-9]+, which is significantly simpler and more compact.