why GNU grep is fast

[Dag-Erling Smørgrav]

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