Re: Help making an automat...

Jonathan Neve <jonathan@microtec.fr> wrote:


>the book only searched for one string at a time, I'd like to be able to
>check a whole list of keywords for possible match before proceding
>futher in the file. I'd like to create an automat of the type:
> A?-YES->N?-YES->D?-YES--->MATCH!!
>NO MATCH!!<-NO D? <-NO
> -YES-> D?-YES--->MATCH!!
> <-NO <-NO
>for the keywords AND and ADD.
>That is, I'd like the automat to check the first letter, and then fork
>out to check all the possible keywords starting with that letter, and so
>on recursively.


>[The usual approach is to treat the set of strings as a regular expression
>and translate it to an NFA or DFA. -John]


Actually this can be done more efficiently (as this'll result
in a very special DFA):


Ricardo Baeza-Yates and Gaston H. Gonnet
A New Approach to Text Searching
October 1992/Vol.35, No.10/COMMUNICATIONS OF THE ACM


Sun Wu and Udi Manber
Fast Text Searching Allowing Errors
October 1992/Vol.35, No.10/COMMUNICATIONS OF THE ACM


    Br,
    Andras Erdei
    ccg@freemail.c3.hu

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