• Subject: list-lpeg and capture stack overflow
• From: Wesley Smith <wesley.hoke@...>
• Date: Thu, 17 Jun 2010 10:08:58 -0700

```I'm trying to figure out why a listlpeg pattern I've written is
generating so many captures.  Below is a vastly simplified script that
generates a stack of 15 captures when only 1 is returned by the
pattern.  When the subject of the match is larger, I easily get in
excess of 9000 captures.  It seems that the pattern is capturing every
singly sub-table and I have absolutely no idea why.  Is there
something about recursive grammar rules that implicitly generates
captures?  Is it possibly a bug where the stack isn't being properly
cleared after going down a level in the tree of tables?

There's no way to see what's going on from within Lua itself unless
you hit the stack overflow limit, so to test, put a printf in the
pushcapture function and watch.

static int pushcapture (CapState *cs) {
printf("push_capture top %d\n", lua_gettop(cs->L));
luaL_checkstack(cs->L, 4, "too many captures)");
....

}

Thanks for any hints.  I've been at it for a few days now and haven't
been able to figure it out.
wes

local listlpeg = require("listlpeg")

local Ct = listlpeg.Ct
local Cc = listlpeg.Cc
local Cg = listlpeg.Cg
local Cmt = listlpeg.Cmt
local C = listlpeg.C
local V = listlpeg.V
local P = listlpeg.P
local S = listlpeg.S
local R = listlpeg.R
local P = listlpeg.P
local L = listlpeg.L

function print_table(t, name, lvl)
lvl  = lvl or 1

local tab = string.rep("   ", lvl)
print(tab..(name and (name .. " = {") or "{"))
for k, v in pairs(t) do
if(type(v) == "table") then
print_table(v, k, lvl+1)
else
print(tab..tab..tostring(k).." = "..tostring(v)..",")
end
end
print(tab.."}")
end

function print_match(t)
if(type(t) == "table") then
print_table(t)
else
print(t)
end
end

function compress(t)
local tt = {}
local maxidx = 0
for k, v in pairs(t) do
maxidx = max(maxidx, k)
end

for i=1, maxidx do
tt[#tt+1] = t[i]
end

return tt
end

local
ast_token = function(patt, name)
return Cmt(L(P(1)), function(s, i)
if(s[i].token == name) then
return i, nil
end
end
)
end

local
function ret(i, t)
if(#t == 0) then
return i, nil
else
return i, unpack(t)
end
end

local
ast_rule = function(patt, name)
return Cmt(L(patt), function(s, i, ...)
if(s[i].rule == name) then
-- propagate any captures
return ret(i, compress{...})
end
end
)
end

local
function apply_depth_first(grammar, p)
local rules = {
_patt = p,
-- (the pattern) + (the pattern down one level in the list) + (look
in the next element)
_depth_first = (V"_patt" + L(V"_depth_first") + P(1))^0
}
for k, v in pairs(grammar) do
rules[k] = v
end

rules[1] = V"_depth_first"

return P(rules)
end

local grammar = {
[1] = "A",
A = ast_rule(V"B" * V"C", "A"),

B = ast_token("B", "B"),
C = ast_token("C", "C"),
}

--patt = P(grammar)
patt = apply_depth_first(grammar, V"B")

local ast = {
{
"B",
token = "B",
},
{
"C",
token = "C",
},
rule = "A",
}

print_match( patt:match{ast} )

```