in reply to Why aren't perl regular expressions really regular expressions?
To expound on the answers you've already received -- the word "regular" in "regular expression" comes from regular languages, a certain kind of formal language (as described by formal grammars).
There are a number of different kinds of these languages that arise fairly naturally; the most important ones are collected in the so-called Chomsky hierarchy. They're characterized by increasingly strict conditions imposed on their grammars' production rules; the most general kind of language (recursively enumerable) has no restrictions, context-sensitive and context-free languages have some, regular languages have the most stringent. (The most stringent in this hierarchy, that is: there are languages that would rank below regular languages still, e.g. star-free languages.)
Interestingly, all these languages are computed by certain kinds of formal machines, from Turing machines (or equivalent notions of computation, e.g. μ-recursive functions) for recursively enumerable languages to finite automata (deterministic or non-deterministic, it makes no difference) for regular languages.
Regular expressions, in the theoretical sense (rather than Perl's), directly describe finite automata. The only things you need there are concenation, alternation ((...|...) in Perl) and the Kleene star ((...)* in Perl).
This is what Perl's regular expressions are based on, but in practice, when you're more interested in solving problems than researching formal languages (as fascinating a subject as they are), you'll need more tools in your toolbox, and Perl gained a lot of tools to make your job easier, from references to look-around assertions to non-backtracking subpatterns to pattern interpolation to match-time code evaluation to... well, you get the idea.
That's the sense in which Perl's regular expression are, in fact, irregular -- or, perhaps equivalently, "Perl-compatible". They go far beyond what "regular expressions" originally were, and as a result they're vastly more useful in practice.
(On that note, BTW, it's also worth adding that when you encounter "Perl-compatible" regular expressions in any other language, it's pretty much a safe bet that they aren't in fact.)
|
|---|
| Replies are listed 'Best First'. | |
|---|---|
|
Re^2: Why aren't perl regular expressions really regular expressions?
by LanX (Saint) on Mar 17, 2015 at 15:28 UTC | |
by AppleFritter (Vicar) on Mar 17, 2015 at 18:51 UTC | |
by LanX (Saint) on Mar 17, 2015 at 20:35 UTC | |
by Dumu (Monk) on Mar 18, 2015 at 10:32 UTC | |
by Dumu (Monk) on Mar 18, 2015 at 10:09 UTC | |
by LanX (Saint) on Mar 19, 2015 at 01:23 UTC |
