Hacker News Reader

Comment by jbangert | Hacker News Reader

One issue with PEG's (and other parsers) is that it doesn't address (unbounded) count fields (or bounded count fields in an elegant manner) or offsets. This means a pure PEG can't express e.g. PDF or ZIP files. To address this, we built a PEG-based parser generator with a few new features, Nail (paper at OSDI 14, github.com/jbangert/nail)

View on HN

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.

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

I like this idea! Mind if I steal it for my PEG generator?

This is probably the best property of PEGs, they're extremely extensible and flexible, you can add features not possible in any other parsing technology, including high order parsers, dynamic extensibility, etc.

Reply on news.ycombinator.com