Re: Help making an automat...

Andras Erdei <>
28 Mar 2000 01:04:19 -0500

          From comp.compilers

Related articles
Help making an automat... (Jonathan Neve) (2000-03-25)
Re: Help making an automat... (Andras Erdei) (2000-03-28)
| List of all articles for this month |

From: Andras Erdei <>
Newsgroups: comp.theory,comp.compilers
Date: 28 Mar 2000 01:04:19 -0500
Organization: Compilers Central
Distribution: inet
References: 00-03-135
Keywords: lex

Jonathan Neve <> 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!!
> -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

    Andras Erdei

Post a followup to this message

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