2 ms·

And that's why the RE2 implementation has existed equally long! Oh, wait.

by kenko 13y ago

dlisboa 13y ago
Cox's work builds on Thompson's work from the 60s. He says so himself.
- mjn 13y ago
  The basic implementation methods are well-known and quasi-standard, but Cox did make some useful practical additions, in addition to writing up a clear and accessible exposition. The classic DFA engines, like in Thompson's version of grep, provide a fairly minimal regex language (later standardized as POSIX regexes), not much fancier than the regular-language syntax used in textbooks. Perl-style regular expressions get such widespread usage even outside of Perl in part because they have a more full-featured syntax, which provides conveniences people find useful. Cox implemented a significant subset of this functionality as syntactic sugar on top of a classic automaton regex engine, so RE2, unlike POSIX regexes, supports named matches, named character classes like \d (plus Unicode character classes), non-greedy matches, etc. Basically everything that can be done without making the language nonregular, so excluding lookahead, lookbehind, and backreferences. Since vim regexes (a custom dialect) support some of those supra-POSIX features, those implementation techniques were likely useful for them to look at. Indeed they link to Cox's article somewhere or other in the design docs. Vim does have lookahead/lookbehind syntax, though; I wonder how they supported that. Fallback to the backtracking engine?
danieldk 13y ago
There are many implementations the standard operations on finite state automata (determinization, minimization, intersection, concatenation, etc.) and nearly as many implementations of regular expressions[1]. Anyone who is in the trade (of text processing), including Bram Molenaar, will be aware that regular languages can be represented as finite state automata. However, the problem is that not all regular expressions 'dialects' (most notably Perl regexes) are not regular languages and cannot be represented as a finite state automata. For instance, the introduction of back-references makes regular expressions non-regular. So, it's not so much being enlightened by Russ Cox, but a trade-off between the convenience of some of the Perl extensions and the ability to apply matching in linear time. Also, for complex expressions, constructing the automaton can be slow. [1] A small selection: http://www.brics.dk/automaton/ http://www.brics.dk/automaton/ http://www.let.rug.nl/~vannoord/Fsa/ http://www.let.rug.nl/~vannoord/Fsa/ http://www.complang.org/ragel/ http://www.complang.org/ragel/ http://open.xerox.com/Services/fst-nlp-tools http://open.xerox.com/Services/fst-nlp-tools Some of the packages can also be used to construct transducers, weighted automata, etc.

And that's why the RE2 implementation has existed equally long! Oh, wait.

by kenko 13y ago

And that's why the RE2 implementation has existed equally long! Oh, wait.

dlisboa 13y ago

Cox's work builds on Thompson's work from the 60s. He says so himself.

mjn 13y ago
The basic implementation methods are well-known and quasi-standard, but Cox did make some useful practical additions, in addition to writing up a clear and accessible exposition. The classic DFA engines, like in Thompson's version of grep, provide a fairly minimal regex language (later standardized as POSIX regexes), not much fancier than the regular-language syntax used in textbooks. Perl-style regular expressions get such widespread usage even outside of Perl in part because they have a more full-featured syntax, which provides conveniences people find useful. Cox implemented a significant subset of this functionality as syntactic sugar on top of a classic automaton regex engine, so RE2, unlike POSIX regexes, supports named matches, named character classes like \d (plus Unicode character classes), non-greedy matches, etc. Basically everything that can be done without making the language nonregular, so excluding lookahead, lookbehind, and backreferences. Since vim regexes (a custom dialect) support some of those supra-POSIX features, those implementation techniques were likely useful for them to look at. Indeed they link to Cox's article somewhere or other in the design docs. Vim does have lookahead/lookbehind syntax, though; I wonder how they supported that. Fallback to the backtracking engine?

danieldk 13y ago

There are many implementations the standard operations on finite state automata (determinization, minimization, intersection, concatenation, etc.) and nearly as many implementations of regular expressions[1]. Anyone who is in the trade (of text processing), including Bram Molenaar, will be aware that regular languages can be represented as finite state automata. However, the problem is that not all regular expressions 'dialects' (most notably Perl regexes) are not regular languages and cannot be represented as a finite state automata. For instance, the introduction of back-references makes regular expressions non-regular. So, it's not so much being enlightened by Russ Cox, but a trade-off between the convenience of some of the Perl extensions and the ability to apply matching in linear time. Also, for complex expressions, constructing the automaton can be slow. [1] A small selection: http://www.brics.dk/automaton/ http://www.brics.dk/automaton/ http://www.let.rug.nl/~vannoord/Fsa/ http://www.let.rug.nl/~vannoord/Fsa/ http://www.complang.org/ragel/ http://www.complang.org/ragel/ http://open.xerox.com/Services/fst-nlp-tools http://open.xerox.com/Services/fst-nlp-tools Some of the packages can also be used to construct transducers, weighted automata, etc.