regular expression search algorithm
Thu, 18 Mar 1993 15:05:52 GMT

          From comp.compilers

Related articles
Regular expression search algorithm (Harry) (2002-07-15)
Re: Regular expression search algorithm (Joachim Durchholz) (2002-07-21)
Re: Regular expression search algorithm (Ralph Corderoy) (2002-07-21)
Re: Regular expression search algorithm (Peter S Tillier) (2002-07-24)
Re: Regular expression search algorithm (Aharon Robbins) (2002-09-03)
regular expression search algorithm (1993-03-18)
Re: regular expression search algorithm (1993-03-19)
Reg. expr. character class compression (1993-03-21)
| List of all articles for this month |

Newsgroups: comp.compilers
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
%V 11
%N 6
%D June 1968
%P 419-
%K 68

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]

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.