With tokens another nice thing to note is there is longest token matching and the concept of "proto" tokens and regexes. This lets you have simple decision making between similarly defined tokens without backtracking. For example the grammar I have for biological sequences can simultaneously identify and parse DNA/RNA/Protein without back tracking. Even if a file has a mixture of data I can instantiate the correct subclasses on the fly whilst parsing! https://github.com/MattOates/BioInfo/blob/master/lib/BioInfo...
And yeah, proto regexes are pretty sweet, and they seem to be a natural fit for what you're doing. I'm always surprised by how popular Perl seems to be in biology / life sciences, and projects like BioInfo (and BioPerl, of course) are a great reminder as to why that happens to be.
Basically: Perl 6 tokens and rules imply :ratchet, which means no backtracking. You can use raw regexes if for some reason you do need backtracking, but otherwise it looks like a Perl 6 grammar is backtracking-free (and grammars in the real world hopefully use tokens/rules exclusively).
So it might actually be at least tolerable for the problems you need to solve (though it's hard for me to say without knowing the problems in the first place (: ). The main remaining question is the exact algorithm in use; I'd be very surprised if Perl 6 grammars didn't compile down to at least some variation on packrat parsers, which would mean linear complexity, but this is probably - again - implementation-dependent in the "we don't care what you do so long as it passes the Perl 6 test suite" sense. I've yet to find a definitive answer by spelunking through Rakudo's code, but it's reassuring that even Rakudo's grammar for Perl 6 itself seems to be devoid of backtracking (meaning that it's clearly possible to do without it; there are quite a few generic subs/methods in there, though, which could prove me wrong here).