Nick Pisarro wrote:
Wikimedia developers <wikitech-l(a)Wikipedia.org>
writes:
Really? All the regular expressions I've seen
should be possible in O(N)
time.
I had to think about this for a few days:
Doing the scan is linear, however putting together the output string, is
not.
You're probably right, and our current parser does turn out to be O(n^2).
I have to go do my "day" job now, but
I'll try out some of these things
the next time I get, unless someone gets to this before I do. Please let
me know if one of you starts trying these ideas out before I can get to it.
It would probably be wiser to just simply write a new parser that does
it the "correct" way (lexing, parse tree generation, translation).
Timwi