NFA.Compiler.fs

module NFA =

    let Compile regex =
        let k = ref 0
        let next () =
            incr k
            !k
        let rec compile regex matched =
            match regex with
            | Choose (a, b) ->
                let y = compile b matched
                let x = compile a matched
                Branch { k = next (); x = x; y = y }
            | Concat (a, b) ->
                matched
                |> compile b
                |> compile a
            | Empty ->
                matched
            | Filter f ->
                Read (next (), f, matched)
            | Star x ->
                let p = {
                    k = 0
                    x = Unchecked.defaultof<_>
                    y = matched
                }
                let r = Branch p
                p.x <- compile x r
                p.k <- next ()
                r
        compile regex Match