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
- : 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
