[TUHS] Short history of 'grep'
dot at dotat.at
Mon Feb 1 20:38:53 AEST 2016
John Cowan <cowan at mercury.ccil.org> wrote:
> 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 :-)
> 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.
Right. The relevant section in the article that started this thread says:
: Al Aho decided to put theory into practice, and implemented full regular
: expressions (including alternation and grouping which were missing from
: grep)and wrote egrep over a weekend. Fgrep, specialised for the case of
: multiple (alternate) literal strings, was written in the same weekend.
: Egrep was about twice as fast as grep for simplecharacter searches but was
: slower for complex search patterns (due to the high cost of build-ing the
: state machine that recognised the patterns).
The "putting theory into practice" refers to compiling the regex to a DFA,
rather than interpreting an NFA.
Russ Cox has a good summary of differing regex implementation techniques
This makes me wonder how well-known was the technique of compiling to a
DFA, and whether it was widely implemented before awk, egrep, and lex.
f.anthony.n.finch <dot at dotat.at> http://dotat.at/
Fair Isle, Faeroes: Southeast 6 to gale 8, veering southwest gale 8 to storm
10, becoming cyclonic later. Very rough, becoming high or very high. Rain or
squally showers. Moderate or poor.
More information about the TUHS