Re: Looking for a design pattern
On Aug 14, 10:47 pm, Jerry Coffin <jerryvcof...@yahoo.com> wrote:
In article <dab1e3aa-9b9b-43fc-be49-ef2da07d4f27
@r18g2000yqd.googlegroups.com>, james.ka...@gmail.com says...
[ ... ]
It's not so much the move itself, but all of the necessary
additional logic to manage it.
If you supported REs that included newlines, I'd agree -- I
wouldn't advocate this technique in such a case. I doubt the
speed gain would be worth the extra complexity.
Since we're talking about editors here:-): all regular
expression implementations I'm familiar with support newlines in
the expression. The data structure of some editors (ed, vi,
vim), and some other programs like those in the grep family, is
such, however, that they will only apply the regular expression
to the text one line at a time, to text which doesn't contain a
new line. (It's possible to create a regular expression in vim
which will only match if there is a newline in the text. Such a
regular expression will never match anything, however.)
[ ... ]
Note too that editors normally use extended regular
expressions which allow capture of sub-strings. To my
knowledge, those can't be implemented as a pure DFA, which
means that the actual processing of each character probably
overwhelms the additional checking. Off hand, and this is
just my basic intuition, and not a result of any
measurements, I would expect such a regular expression to
take about ten times more time scanning a large range as it
takes to copy it. (My own regular expression class will
take less time to scan than it takes to copy, because it
uses a DFA. But it doesn't support capture.)
Offhand, it seems like that _would_ probably justify the
complexity of scanning the RE to see if a DFA can be used or
not, and using it if possible. Then again, unless I had a
really good reason to do otherwise, I'd probably just use the
regex class in TR1.
Exactly. Typically, editors are not scanning millions of lines
of text; the amount of text being scanned is relatively small,
and the time to compile the regular expression is usually a
significant part of the time necessary for the command using it.
In such cases, building a complete DFA is counter productive
(because it is a fairly expensive operation); using lazy
construction of the DFA might be acceptable, but it does
introduce the added complexity of having to handle out of memory
in the middle of the search. But IMHO, tr1::regex should work
just fine, unless you need some special features.
(FWIW: I wouldn't use my own RegularExpression class in an
editor. It's not designed for that. On the other hand, it has
some nice features that boost::regex doesn't: you can define
your accept code, and or existing regular expressions, along the
lines of:
RegularExpression decimal ( "[1-9][0-9]*" , 10 ) ;
RegularExpression octal ( "0[0-7]*" , 8 ) ;
RegularExpression hexadecimal( "0[xX][a-fA-F0-9]+", 16 ) ;
RegularExpression number( decimal | octal | hexadecimal ) ;
and then:
StringMatch< std::string::const_iterator >
match( number.match( s.begin(), s.end() ) ) ;
if ( match ) {
int i
= convert( s.begin(), match.endOfMatch(), match.acceptCode
() ) ;
// ...
}
where the last argument to convert is the base. And the class
has a function "dumpAsCpp", which outputs the tables as C++, so
you can compile them into a StaticRegularExpression, which has
pretty much the same interface as RegularExpression for the
non-mutating functions, but is statically initialized. And
finally, the class(es) exist in two variants, supporting either
single byte encodings or UTF-8---although complex regular
expressions in UTF-8 can rapidly become very, very large---I use
the single byte variant a lot even when working with UTF-8.)
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34