Is an expensive DFA something that could be mitigated with source code hints? An 80% solution might do the trick.