Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
memoized parsers in CPS
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment