Patterns For Non-regular Languages
Many features found in modern regular expression libraries provide an expressive power that far exceeds the regular languages. For example, many implementations allow grouping subexpressions with parentheses and recalling the value they match in the same expression (backreferences). This means that a pattern can match strings of repeated words like "papa" or "WikiWiki", called squares in formal language theory. The pattern for these strings is (.*)\1.
The language of squares is not regular, nor is it context-free. Pattern matching with an unbounded number of back references, as supported by numerous modern tools, is NP-complete.
However, many tools, libraries, and engines that provide such constructions still use the term regular expression for their patterns. This has led to a nomenclature where the term regular expression has different meanings in formal language theory and pattern matching. For this reason, some people have taken to using the term regex or simply pattern to describe the latter. Larry Wall, author of the Perl programming language, writes in an essay about the design of Perl 6:
| “ | 'Regular expressions' are only marginally related to real regular expressions. Nevertheless, the term has grown with the capabilities of our pattern matching engines, so I'm not going to try to fight linguistic necessity here. I will, however, generally call them "regexes" (or "regexen", when I'm in an Anglo-Saxon mood). | ” |
Read more about this topic: Regular Expression
Famous quotes containing the words patterns for, patterns and/or languages:
“For the man who should loose me is dead,
Fighting with the Duke in Flanders,
In a pattern called a war.
Christ! What are patterns for?”
—Amy Lowell (1874–1925)
“Persons grouped around a fire or candle for warmth or light are less able to pursue independent thoughts, or even tasks, than people supplied with electric light. In the same way, the social and educational patterns latent in automation are those of self- employment and artistic autonomy.”
—Marshall McLuhan (1911–1980)
“It is time for dead languages to be quiet.”
—Natalie Clifford Barney (1876–1972)