|Regular expression search algorithm email@example.com (Harry) (2002-07-15)|
|Re: Regular expression search algorithm firstname.lastname@example.org (Joachim Durchholz) (2002-07-21)|
|Re: Regular expression search algorithm email@example.com (Ralph Corderoy) (2002-07-21)|
|Re: Regular expression search algorithm firstname.lastname@example.org (Peter S Tillier) (2002-07-24)|
|Re: Regular expression search algorithm email@example.com (Aharon Robbins) (2002-09-03)|
|regular expression search algorithm firstname.lastname@example.org (1993-03-18)|
|Re: regular expression search algorithm email@example.com (1993-03-19)|
|Reg. expr. character class compression firstname.lastname@example.org (1993-03-21)|
|Keywords:||lex, bibliography, comment|
|Organization:||Department of Computer Science, University of York, England|
|Date:||Thu, 18 Mar 1993 15:05:52 GMT|
The CACM paper that first described the construction and use of the NFA
for regular expression search mentioned the explosive nature of the lists
if duplicates aren't eliminated, and discusses the difficulties (and
correct handling) of a**.
%T Regular Expression Search Algorithm
%A Thompson, K.
%J Communications of the ACM
%D June 1968
It's worth reading in any case. The paper includes a program that
compiles the regular expression into machine code that emulates the NFA.
(It's a good exercise in puzzling out 7094 assembly code.) The compiling
variant has been used in several editors and even a version of grep. An
interpretive variant can be seen in the source code to Rob Pike's editor
[FYI, it's the same K. Thompson that later wrote most of Unix. -John]
Return to the
Search the comp.compilers archives again.