I was thinking that maybe a packrat parser need not memoise every single
state previously encountered but just use a limited size cache of states.
That way, there would be a certain probability of an expensive backtrack
when a rule fails but this probability would reduce if a larger cache was
available. On desktop machines, you might get near linear time compilation
but on Lego Mindstorms (where the source text is presumably short) you
would get much worse performance. This would seem to make Lua more
"scalable" across a wide variety of target machines. I haven't found any
research into this subject, though, which isn't a good sign.