4 ms·
Packrat Parsing and Parsing Expression Grammars
- stormbrew 12y agoI kind of really dislike the tendency to conflate PEG and packrat parsing. Packrat parsing is not a required feature of PEGs, and many of them don't use it. Further, many implementations of packrat parsing are absolutely dog slow because they simply memoize every term, which is basically trading a high complexity in steps for a high complexity in space, so allocation pressure and cache pressure can both become very bad, especially for large inputs and/or large grammars. To me it's almost a defining case of complexity notation being utterly misleading in practice. This paper reflects my experience: https://mercurylang.org/documentation/papers/packrat.pdf https://mercurylang.org/documentation/papers/packrat.pdf
- lucio 12y agoI've used PEGs to create a compiler, and it results in clear, readable code, easy to maintain. Because the parser structure it's cleaner, it feels natural to write the parser manually with PEGs. The key is to handle parse-fail with exceptions. Instead of having a syntax-file and a generated parser, the code is clear enough to act as low-level documentation. see: https://github.com/luciotato/LiteScript https://github.com/luciotato/LiteScript