lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

On Apr 10, 2007, at 4:43 PM, Andy Stark wrote:

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.

One thing: if your grammar is written in such a way that it only needs limited lookahead (the C parser uses two lexical symbols) you would not really need packrat parsing, because a simple backtracking parser will already perform in linear time. The downside of using backtracking parsers is that your semantic actions must be reversible, so you need to store even more backtracking information, which is pretty much equivalent memory-wise to storing the AST. That will not work too well on a Lego Mindstorms embedded system with limited memory.

Gé Weijers