dg@lakart.UUCP (David Goodenough) (06/09/89)
I am looking for code, comments, suggestions on how to create a FSA that will recognise regular expressions, when handed a stream of text (i.e. a file). Ignoring the setup time, I'm basically after a linear time grep algorithm. Comments on what can be done and what can't, and how to do it, will be welcome, as will any source or anything. -- dg@lakart.UUCP - David Goodenough +---+ IHS | +-+-+ ....... !harvard!xait!lakart!dg +-+-+ | AKA: dg%lakart.uucp@xait.xerox.com +---+
bill@twwells.com (T. William Wells) (06/11/89)
In article <564@lakart.UUCP> dg@lakart.UUCP writes:
: I am looking for code, comments, suggestions on how to create a FSA that
: will recognise regular expressions, when handed a stream of text (i.e.
: a file). Ignoring the setup time, I'm basically after a linear time grep
: algorithm. Comments on what can be done and what can't, and how to do it,
: will be welcome, as will any source or anything.
You might pick up _Compilers: Principles, Techniques, and Tools_ by
Aho, Sethi, and Ullman. It has all the information you'll need, though
no source code. And yes, you can do a linear time grep, though both
the setup time and memory use can be awful on occasion.
---
Bill { uunet | novavax } !twwells!bill