memoized parsers in CPS

gistfile1.lua

function fail(reason)
    return { status = "failure", reason = reason }
end

function success(ret, idx)
    return { status = "success", token = ret, new_idx = idx }
end

function token(tok)
    return function (stream, idx, cont)
        print("token parser {" .. tok .. "} called")
        local ret
        if idx > #stream then
            ret = fail("unexpected end of stream")
        else
            local tok_s = stream[idx]
            if tok_s == tok then
                ret = success(tok_s, idx + 1)
            else
                ret = fail("expected " .. tok .. " found " .. tok_s)
            end
        end
        cont(ret)
    end
end

function seq(parser1, parser2)
    return function (stream, idx, cont)
        print "seq parser called"
        _ENV[parser1](stream, idx, function (parse_result)
            if parse_result.status == "success" then
               _ENV[parser2](stream, parse_result.new_idx, cont)
            else
                cont(parse_result)
            end
        end)
    end
end

function alt(parser1, parser2)
    return function (stream, idx, cont)
        print "alt parser called"
        _ENV[parser1](stream, idx, cont)
        _ENV[parser2](stream, idx, cont)
    end
end

function memo(parser)
    -- WARNING: this function is badly implemented in the sense that
    -- if you parser generated by this function on two different streams
    -- it will generate wrong results
    local tbl = {}
    return function (stream, idx, cont)
        if tbl[idx] == nil then
            tbl[idx] = { results = {}, conts = {} }
            table.insert(tbl[idx].conts, cont)
            parser(stream, idx, function (parse_result)
                -- check if same parse_result is already in the table
                local exists = false
                for _, result in ipairs(tbl[idx].results) do
                    if result == parse_result then -- TODO: this equality is probably wrong
                        exists = true
                        break
                    end
                end

                if not exists then
                    table.insert(tbl[idx].results, parse_result)
                    for _, cont in ipairs(tbl[idx].conts) do
                        cont(parse_result)
                    end
                end
            end)
        else
            table.insert(tbl[idx].conts, cont)
            for _, result in ipairs(tbl[idx].results) do
                cont(result)
            end
        end
        return tbl[idx]
    end
end

test_stream = { "int", "+", "int" }

int_parser = token("int")
plus_parser = token("+")
seq_parser1 = seq("plus_parser", "sum_parser")
seq_parser = seq("sum_parser", "seq_parser1")
alt_parser = alt("seq_parser", "int_parser")

sum_parser = memo(alt("seq_parser", "int_parser"))
sum_parser(test_stream, 1, function (ret)
    print(ret.status)
end)