Nobody is bashing PCRE. >but they are definitely part of the traditional (UNIX) definition of regular expressions. This is not exactly true. In 1968 or ealier

Nobody is bashing PCRE. >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 https://en.wikipedia.org/wiki/Thompson%27s_construction [2] http://dl.acm.org/citation.cfm?doid=363347.363387 http://dl.acm.org/citation.cfm?doid=363347.363387 [3] http://dl.acm.org/citation.cfm?id=55333 http://dl.acm.org/citation.cfm?id=55333 [4] http://cs.stackexchange.com/questions/3381/nfa-with-exponential-number-of-states-when-deteminized http://cs.stackexchange.com/questions/3381/nfa-with-exponent...