Riley Williams wrote:
>Hi all.
>
> >> I take it back, it is regular (kinda) but you can't to
> >> it with a deterministic finite automaton. If there is a
> >> cycle in pattern1, off of which pattern2 has a branch,
> >> then you would need to count how many times you have gone
> >> around the cycle to know where to jump to in pattern2 if
> >> it fails to match pattern1 (which you can't do, pumping
> >> lemma and all that.) If you use a non-deterministic FA,
> >> you should be able to just go through each pattern until
> >> both crash or one matches and declare that the winner.
>
> > Anyone here interested by doing a regexp compiler ? I can
> > help for details or libqsearch internals, but I won't find
> > enough time to do all that quickly enough.
>
>Why reinvent the wheel? Have a look at flex which is designed
>to create routines to do precisely that. Just give it details
>of the patterns you require and it'll write out code that will
>recognise those patterns in the input.
>
>
well, for at least our application we need to give it the patterns at
runtime, so flex isn't an option. We didn't reinvent the wheel, either
though, and used Henry Spencer's regexp lib, which seems to work quite
well...
Ethan
-
To unsubscribe from this list: send the line "unsubscribe linux-net" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
This archive was generated by hypermail 2b29 : Fri May 23 2003 - 22:00:03 EST