Return to the
comp.compilers page.
Search the
comp.compilers archives again.
| Related articles |
|---|
| Regular expression search algorithm harvinder.singh@patni.com (Harry) (2002-07-15) |
| Re: Regular expression search algorithm joachim_d@gmx.de (Joachim Durchholz) (2002-07-21) |
| Re: Regular expression search algorithm ralph@inputplus.co.uk (Ralph Corderoy) (2002-07-21) |
| Re: Regular expression search algorithm peter.tillier@btinternet.com (Peter S Tillier) (2002-07-24) |
| Re: Regular expression search algorithm arnold@skeeve.com (Aharon Robbins) (2002-09-03) |
| regular expression search algorithm forsyth@minster.york.ac.uk (1993-03-18) |
| Re: regular expression search algorithm pardo@cs.washington.edu (1993-03-19) |
| Reg. expr. character class compression dmr@research.att.com (1993-03-21) |
| Newsgroups: | comp.compilers |
| From: | forsyth@minster.york.ac.uk |
| 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
`sam'.
[FYI, it's the same K. Thompson that later wrote most of Unix. -John]
--
Return to the
comp.compilers page.
Search the
comp.compilers archives again.