help with a fast pattern matching utility requested

mike <>
10 Apr 2002 00:26:10 -0400

          From comp.compilers

Related articles
help with a fast pattern matching utility requested (mike) (2002-04-10)
| List of all articles for this month |

From: mike <>
Newsgroups: comp.compilers
Date: 10 Apr 2002 00:26:10 -0400
Organization: Cornell University
Keywords: lex, question, comment
Posted-Date: 10 Apr 2002 00:26:10 EDT

I'm writing a Go program that needs to match a given subsection of the
board to a list of predefined patterns. Both are converted to strings,
so it becomes a 1-d problem. The program is in C/C++.

A DFA is really the only option I see, but the question is how to
construct it? I considered using flex, but its not quite what i need -
instead of matching multiple tokens on one input, i need to match the
whole input string to one or several patterns (each time from the
beginning of the input). Flex/lex is much too big for what I need -
ie much slower, and I was hoping for a way to add/subtract patterns
from the DFA w/o completely rebuilding it, if possible.

If anyone knows of a utility to do this in C, I would greatly
appreciate letting me know. Please email directly to

[I'd start with the Henry Spencer's popular regex library which as I
recall turns the patterns into NFAs and see if it's really too slow
for this application. If it is, take a look at egrep, some versions
of which build DFAs. -John]

Post a followup to this message

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