So you want to encode priorities efficiently as far as I understand from [1]? Could bit-packing combined with prefix elimination do the trick? Choice boils down to binary choice. Attach a number N to every execution thread that sits in a given NFA state. When the thread moves through a binary choice state, it splits into two threads with N_{left} = 2 * N + 1 and N_{right} = 2 * N. When two threads arrive at the same NFA state, the machine picks one with greater N and discards the other, thus giving priority to early over late and left over right. This makes these numbers grow quickly, but at any point in the simulation one can identify the common binary prefix of all the thread numbers and remove it, because it will not be relevant for comparison. If this is too costly, amortize and do it every K steps instead of on every step. Anton [1] https://github.com/feuerbach/regex-applicative/wiki/Call-For-Help On Tue, Sep 13, 2011 at 1:40 AM, Roman Cheplyaka <roma@ro-che.info> wrote:
Please help make the regex-based parsing library efficient!
https://github.com/feuerbach/regex-applicative/wiki/Call-For-Help
-- Roman I. Cheplyaka :: http://ro-che.info/
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
-- Kind Regards, Anton Tayanovskyy WebSharper™ - type-safe JavaScript in F# http://intellifactory.com