Because of back references PCRE regular expressions can match non-regular languages as well.
"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"...
You can think of this as the languages that can be matched with an algorithm that is bounded (i.e., O(1) ) in memory, no matter what is the string to be matched.
The following pseudocode is not bounded in memory -- can you guess why?
bool is_prime(Number n)
{
for (Number i = 2; i < n; ++i) {
if (n % i == 0) {
return false;
}
}
return true;
}It should be noted, so can the value n, but in defining regular languages in this way, we allow our O(1) memory algorithms to be fed the characters of an a priori unbounded input string one by one sequentially.
You can also do a separate test for 2, then start at 3 and use i+=2 instead of i++, that cuts the test time in half. Once you've done that, you can observe that all primes are 6k +/- 1 except 2 and 3, which makes your code 3 times faster than the naive version.
At this point, you've basically got a simple wheel primality testing algorithm going, so why not go all the way?
I don't think the parent poster was making the point that his was the most efficient algorithm for testing primes. I think his point was that regular numbers are O(log n) in CS terms, not O(1), which is not obvious at first.
You can invent a variety of notations to describe a DFA. But you can't change the formal definition of a DFA, or what kinds of things a DFA can match without making it not a DFA.
I'm not actually a fan of using "regular expressions" in a sense broader than that of Kleene's regular, DFA-accepted languages, to be clear. That is exactly what I've been questioning.
I'm not actually a fan of using "regular expressions" in a sense broader than that of Kleene's regular, DFA-accepted languages, to be clear. That is exactly what I've been questioning.
On the other hand, backreferences can allow matching non-regular languages.
However, most programmers are not mathematicians or computer scientists, and so are effectively using lay terminology which is similar to but not precisely the same as the mathematical terminology. Most programmers only care that their regex library allows them to concisely match strings, not that it allows them to match regular languages.
Thus there are two standards you could follow: the precise mathematical definition of "regular", or the lay definition.
(And this is part of why I find it confusing terminology and would prefer "regular expression" only to mean specifications of regular languages in the original formal sense. But, of course, I'm not the king of language, and it's natural that people would speak the way they speak, given the circumstances.)
And surely you don't think those implementing the regular expression engine are lay people. They should know better.
The point here is that users of (colloquial) regular expressions, however professional they are or aren't, are just engaging with the surface of a deeper set of mathematical principles that require greater nuances of meaning to discuss than their applications do.
What? No. Many programmers out there are just working on fun projects in their spare time. I'm sure there exist some aerospace engineers doing that, but it's not many. I don't see why your average bedroom open source programmer should be treated like an aerospace engineer.
Considering this writeup leads with a giant headline saying "Regular Expressions - The Theory"... I think the complaints about how it's not actually a regular expression are even more valid than usual.
Understanding REs (a little more) formally, one can exploit their properties for e.g. performance and/or concision. For an example of what that understanding gives you, I'd recommend checking out the Ragel state machine compiler.
The difference isn't academical. It has huge practical implications, from software that is just annoyingly slow to DoS attacks.
People need to understand that. And stop using non-regular regexes (or better yet: regex in general) in production code. It increases world-suck.
The same features have also been implemented independently many times. For example Ruby, Java and Python all have independent implementations of regular expressions with a lot of the same features.
> Grouping and backreferences: All versions of sed support grouping and backreferences on the LHS and backreferences only on the RHS.
If the former, then it predated perl by quite a bit, of course.
I've tried finding some source for early versions but all the links I've found are dead. It's an interesting question!
Perl used that as a starting place and began adding extensions such as the difference between .* and .*?.
So using "non-regular thing" as a regular expression predates Perl. But the dialect we standardized on with the features people now expect is due to Perl's influence.
The sad thing is that the libraries use the same algorithms even if the expression doesn't contain backreferences. A while ago, Stack Overflow had a brief outage because of regular expression performance, although the expression that caused it didn't even use backreferences or other non-regular features:
http://stackstatus.net/post/147710624694/outage-postmortem-j...
In contrast, Google Code Search - when it still existed - supported regular expression searches over world's public codebases. One key ingredient making this possible was to only use proper regular expressions:
I'd argue that this is useful, even if you use it as part of a parser that doesn't just parse regular languages, as you'll have a slightly easier time reasoning about the time and space complexity of the construction.
There's an interesting book that covers some unusual aspects of automata and regular expressions: https://www.amazon.com/Finite-Automata-Regular-Expressions-S...
But that won't get you a primality checker. You can't get a primality checker. Primes don't comprise a regular language, neither in unary nor in any nontrivial base.
The regexp in the article is perfectly compatible with UNIX grep:
$ s=.; for i in `seq 50`; do echo $s | grep -qE '^.?$|^(..+)\1+$' || echo -n $i\ ; s=$s.; done; echo
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
In this case, bashing PCRE is completely off-topic.
>but they are definitely part of the traditional (UNIX) definition of regular expressions.
This is not exactly true. In 1968 or ealier Ken Thompson wrote first grep implementation using NFA simulation, an algorithm which is now known as Thompson Construction [1][2] There were no back-references in that grep.
In 1975 Al Aho wrote an egrep which used DFA instead of NFA [3] (both NFA and DFA accepts regular languages, but in some cases DFA will have exponentially more states than the same regular language accepting NFA automata [4]) This added features such as alternation and grouping which was not supported by grep, but it not supported back-references.
Current GNU grep have -E switch which accepts extended regular expressions as described in Posix standard. Theses extended regular expressions supports back-references as do PCRE available in grep with -P switch
So no, back-references are not in traditional Unix definition of regular language.
[1] https://en.wikipedia.org/wiki/Thompson%27s_construction
[2] http://dl.acm.org/citation.cfm?doid=363347.363387
[3] http://dl.acm.org/citation.cfm?id=55333
[4] http://cs.stackexchange.com/questions/3381/nfa-with-exponent...