|Looking for code to quickly build DFSAs from Reg Exprs jhummel@esp.ICS.UCI.EDU (Joseph Edward Hummel) (1992-12-04)|
|Re: Looking for code to quickly build DFSAs from Reg Exprs email@example.com (1992-12-05)|
|From:||Joseph Edward Hummel <jhummel@esp.ICS.UCI.EDU>|
|Date:||Fri, 4 Dec 1992 07:04:34 GMT|
|Keywords:||DFA, lex, question, comment|
Hello. I'm looking for code that builds FSAs from regular expressions.
However, I also need to perform intersection and complementation
of regular expressions, which seems to imply that DFSAs are ultimately
needed. I actually never need to "run" the resulting DFSA, instead
I need to perform e.g. intersections and checks to see if the language
accepted is empty or not. Thus, speed of machine execution is not
important, but speed of construction and operations such as intersection
is crucial. I was ruling out lex/flex, since they build machines designed
to run fast, while I need fast construction of machines whose format is
also easy to manipulate. Any ideas? (Anyone know what kind of machines
the grep/egrep/fgrep family build? Probably not appropriate for the same
reasons as lex).
Thanks in advance for whatever leads you can offer,
Dept of ICS
Irvine, CA 92717
[Last time I checked, egrep used a DFA, grep used an NFA, and fgrep used
a hack. -John]
Return to the
Search the comp.compilers archives again.