[TUHS] Short history of 'grep'

John Cowan cowan at mercury.ccil.org
Sun Jan 31 12:37:00 AEST 2016

Dave Horsfall scripsit:

> I'm still trying to get my around about how a program such as "egrep" 
> which handles complex patterns can be faster than one that doesn't...  It 
> seems to defeat all logic :-)

Actually, it just appears to be that way.  Many egrep things like + and ?
are supported in grep too, you just have to enter them as \+ and \?, at
least now that we have Posix regular expressions.  What egrep does not
support that grep does is backreferences, and that allows it to use highly
efficient deterministic (i.e. non-backtracking) finite state automata.
Classic grep uses backtracking, which makes it much slower on problematic
expressions like "a*b" where there is no b in the input.  On the other
hand, creating a deterministic automaton has higher setup costs.

 John Cowan          http://www.ccil.org/~cowan        cowan at ccil.org
               Si hoc legere scis, nimium eruditionis habes.

More information about the TUHS mailing list