Re: why GNU grep is fast

From: Dag-Erling Smørgrav <des_at_des.no>
Date: Sun, 22 Aug 2010 22:44:13 +0200
Mike Haertel <mike_at_ducky.net> writes:
> For example if your regex is /foo.*bar/, the initial Boyer-Moore search
> is (probably) searching for foo.
>
> If the initial search succeeds, GNU grep isolates the containing line,
> and then runs the full regex matcher on that line to make sure.

You don't really need to "isolate the containing line" unless you have
an actual match, do you?  There are two cases:

 1) The regexp does not use any character classes, including /./, so the
    FSA will stop if it hits EOL before it reaches an accepting state.

 2) The regexp uses character classes, and you rewrite them to exclude
    \n: /[^bar]/ becomes /[^bar\n]/, /./ becomes /[^\n]/, etc., and the
    FSA will stop if it hits EOL before it reaches an accepting state.

DES
-- 
Dag-Erling Smørgrav - des_at_des.no
Received on Sun Aug 22 2010 - 18:44:15 UTC

This archive was generated by hypermail 2.4.0 : Wed May 19 2021 - 11:40:06 UTC