4 ms·
Abstract makes this seem interesting, but the title is odd. packrat parsing is already a dynamic programming algorithm. The reformulation is to parse bottom-t
by aidenn0 6y ago
Abstract makes this seem interesting, but the title is odd. packrat parsing is already a dynamic programming algorithm. The reformulation is to parse bottom-to-top, right-to-left.
bottom-to-top is fairly common for parsing (e.g. pretty much any LR based parser will do so), but right-to-left is not something I've encountered before. The very right-most terminal is the first thing matched with this technique.
- thechao 6y agoI'm also a little unnerved by the author's dismissal of Earley as not practical, when Aycock & Horspool (who are big in this field) literally have a paper called "Practical Earley Parsing", which does exactly what it says on the tin. The other thing I wasn't a fan of is he doesn't give an recursive descent (RD) algorithm, even though it's trivial to describe RD using a pair of functions (parse-alt; parse-rule) over a grammer. When RD is expressed as a grammar, almost every parsing algorithm falls out as a "memoization" hack for one part of the algorithm, or another.