Re: Looking for a DFA implementation (please help)

"Dmitry A. Kazakov" <>
12 Nov 2002 14:07:36 -0500

          From comp.compilers

Related articles
Looking for a DFA implementation (please help) (mike) (2002-11-08)
Re: Looking for a DFA implementation (please help) (Dmitry A. Kazakov) (2002-11-12)
Re: Looking for a DFA implementation (please help) (Clint Olsen) (2002-11-12)
Re: Looking for a DFA implementation (please help) (Burak Emir) (2002-12-01)
| List of all articles for this month |

From: "Dmitry A. Kazakov" <>
Newsgroups: comp.compilers
Date: 12 Nov 2002 14:07:36 -0500
Organization: At home
References: 02-11-039
Keywords: DFA
Posted-Date: 12 Nov 2002 14:07:36 EST

mike wrote:

> I'm working on an AI project and one part of it requires an
> implementation of fast string matching.
> Specifically I need a DFA (or an analog) that can match a string against
> a set of others and give a
> different output depending on which string it matched (not just that a
> match was found)
> for example, i have a set of strings
> xoo?.?$ (1)
> ?$?x.? (2)
> o$?.. (3)
> (where ? [xo.] and $ is [xo])
> and I need to if another string C, for example 'xxo?' matches anything
> in the set, and if so, what is the number of the string that it matches


If correctly understand the above, what do you need is a table of
topics, which can be matched against a string to find the longest
topic in the table that matches a string prefix. If so there is a
GMGPL-ed software for this (in Ada 95):

In worst case matching time is linear. However, usually it is logarithmic.

Alternatively, if topics are not strings, but patterns then you need a
sort of pattern matching and little could be said about speed. There
is a GMGPL-ed pattern matching software (in C, C++):

It supports SNOBOL-like immediate assignment, i.e. setting/resetting
variables during matching process. This can be used to note which part of
the pattern (=topic) was actually matched.

Dmitry A. Kazakov

Post a followup to this message

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