Re: Wanted: Regular Expression -> Finite Automata C code =-

megatest!plethorax!djones@uu2.psi.com (Dave Jones) writes:
>Also, every time a final state is encountered, you will want to remember
>the number of characters that have been processed at that point. The last
>number remembered will be the length of the longest match.


Unfortunately, this doesn't generalize to most real-life applications,
where the match is not anchored at the start of the string. It's easy to
generalize the matching algorithm so you still make only one pass, by
considering the possibility of a fresh start at each character, and this
is definitely the way to do it -- you don't want to retry the match at
each possible starting position! Alas, the bookkeeping for longest match
falls apart. You don't know when the particular match that corresponds to
a new final state started. Consider the RE "(abcde|cd|ef)" and the string
"xabcdefy". You reach a final state after seeing the "d", another after
the "e", and another after the "f", but the last one is not the longest.
--
Henry Spencer @ U of Toronto Zoology, henry@zoo.toronto.edu utzoo!henry
--

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