4 ms·
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 dece
by sovande 12y ago
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.
- sklogic 12y agoHow 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.
- sovande 12y agoI was and also when scanning/lexing. My limited PEG parsing experience is with peg/leg by http://piumarta.com/software/peg/ http://piumarta.com/software/peg/ and http://pegjs.majda.cz http://pegjs.majda.cz which is a Javascript PEG parser. Both very cool projects.
- sklogic 12y agoLooks like they do not include the optimisations I mentioned. But for this sort of use cases that would have been an overkill anyway.
- BruceIV 12y agoI'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 http://arxiv.org/abs/1405.4841