Re: Lexer and syntax highlighter powered by LPeg

[Gé Weijers <ge@...>]

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é

--

Gé Weijers

ge@weijers.org