[Haskell-cafe] regex-applicative library needs your help! (algorithmic challenge)

[Anton Tayanovskyy]

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 at 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>



-- 
Kind Regards,
Anton Tayanovskyy

WebSharper™ - type-safe JavaScript in F#
http://intellifactory.com