Idea: To support assertions, use a separate lookup table that says what assertions matched where.
If I thought it through correctly, this will work. The downside is O(n) space complexity, but yanno, maybe that's impossible to avoid, yeah?
Would create abstract program type similar to NFA, but generalized. This could then be executed directly through whatever means (including backtracking search).