Hacker News Reader

Comment by sovande | Hacker News Reader

Another issue is that it uses at least the same memory as the the input. Not that I'm a PEG expert, but it also basically feels like a formalised recursive decent parser. Nothing wrong with that, but changing the grammar afterwards can have a rippling effect and require much more work than with a traditional LALR parser.

View on HN

How is it so? If you're referring to the Packrat memoisation (which is not the only possible PEG implementation), you can do a lot of memory optimisation, like discarding memoised entries based on some rules (e.g., once a top-level entry, like a function or a class definition is parsed, all the alternative interpretations can be thrown away). You can memoise complex entries but re-parse simple tokens. And many, many more.

I was and also when scanning/lexing. My limited PEG parsing experience is with peg/leg by http://piumarta.com/software/peg/ and http://pegjs.majda.cz which is a Javascript PEG parser. Both very cool projects.

Looks like they do not include the optimisations I mentioned. But for this sort of use cases that would have been an overkill anyway.

So do you have an example of a PEG parser that uses these so called memorisation optimisation techniques then?

https://github.com/combinatorylogic/mbase/blob/master/src/l/...

I've been working on a derivative parsing algorithm for PEGs; it only uses memory proportional to the amount of backtracking and grammar nesting (i.e. about the same as recursive descent), but still gives a polynomial worst-case bound on time. An early draft of my paper on it is at [1]; this turned out to be about 6x slower than packrat when I actually built and tested it, but I've come up with a substantial simplification to the algorithm that I'm quite optimistic will have better performance results once I finish debugging my code.

[1] http://arxiv.org/abs/1405.4841

Reply on news.ycombinator.com