From mboxrd@z Thu Jan 1 00:00:00 1970 From: scj@yaccman.com (scj@yaccman.com) Date: Mon, 1 Feb 2016 11:26:10 -0800 Subject: [TUHS] Short history of 'grep' In-Reply-To: References: <20160130030012.GB9762@minnie.tuhs.org> <56AD0AB7.40701@mhorton.net> <56AD1B28.4010908@mhorton.net> <20160131023700.GB7917@mercury.ccil.org> Message-ID: <4dda350d543908e59a54dc0ea356dc6c.squirrel@webmail.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