3 ms·
What type of parser does this produce?
by DC-3 9y ago
What type of parser does this produce?
- jmcomets 9y ago"Parsing expression grammars (PEGs) are an alternative to context free grammars for formally specifying syntax" [1] Basically, you have tools for context free grammars such as GNU Bison or Yacc. This is an alternative, but with PEG. For more in-depth info, there's the original PEG paper. [2] [1]: http://bford.info/packrat http://bford.info/packrat [2]: http://bford.info/pub/lang/peg http://bford.info/pub/lang/peg
- yellowapple 9y agoThat's the grammar, not the parser resulting from the grammar. The README doesn't say, but most PEGs in the wild (AFAICT) compile down to / are implemented by packrat parsers.
- yellowapple 9y agoWith PEGs (like Pest), it's probably going to be a packrat parser (which would also make sense given the project's name).
- DC-3 9y agoThank you for the actual answer. Funny how some people are so excited to give an RTFM answer that they forget to read the question. E: turns out this is wrong anyway.
- dragostis 9y agoFor now, it produces a recursive descent parser. Packrat parsing is an open-question since I'm afraid that adding a memoization layer all throughout the parser will lead to a consistent general slowdown.
- DC-3 9y agoInteresting. I'll try and find some time to read the source - am interested to see how this is implemented.
- dragostis 9y agoA good place to start would be in the manually written example. [1] My current plan is to try and limit the the use of memoization such that it still guarantees linear parsing, but it doesn't memoize unless necessary. [1]: https://github.com/pest-parser/pest/blob/master/pest/examples/parens.rs#L20 https://github.com/pest-parser/pest/blob/master/pest/example...
- DC-3 9y agoI appreciate the link - I'm teaching myself about parsers right now and like the rest of HN I like Rust programs ;)