[TUHS] Short history of 'grep'

[scj@yaccman.com (scj@yaccman.com)]

: 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 simple character searches but
: was slower for complex search patterns (due to the high cost of building
: the state machine that recognised the patterns).

I remember talking to Al about his programming experiences not long after
he wrote egrep.  His focus was theory, and he wrote far more books and
papers than programs.  He said something like: "I never realized that you
had to write so many different algorithms to get something to work.  I
thought I just needed to write one!"

Also, as a practical example of exponential blowup doing an fgrep-like
problem, use lex to recognize a bunch of reserved words ("if","for","else",
"while","int",... and such) and follow it with lnu* to recognize
identifier names (where lnu recognizes letters, numbers, and underscore). 
I gave up on lex for PCC when the lexer got bigger than all the rest of
the compiler...

Steve