4 ms·

> What kind of PEG are you talking about? I’m talking about the Packrat algorithm which, as far as I know, is the only practically used PEG algorithm. The memo

by klmr 9y ago

> What kind of PEG are you talking about? I’m talking about the Packrat algorithm which, as far as I know, is the only practically used PEG algorithm. The memory requirement comes from the fact that the algorithm handles partial match failures without having to recompute intermediate steps. By comparison, a bog-standard recursive descent parser without memoisation has exponential worst-case runtime [1]. [1] https://stackoverflow.com/a/16897246/1968 https://stackoverflow.com/a/16897246/1968

loup-vaillant 9y ago
Last time I checked Packrat had nothing to do with memoization. Packrat parsing is the same as precedence climbing, very similar to the shunting yard algorithm, except it leverages the call stack to simplify the code. And last time I checked, PEG was syntax sugar above recursive descent, just like parser combinators. I implemented¹ the damn thing, so I think I know what I'm talking about. Somewhat. Memoization is just a way to go beyond LL(1), and handle left recursive grammars, it's not not mandatory. [1]: http://loup-vaillant.fr/projects/metacompilers/ http://loup-vaillant.fr/projects/metacompilers/
- klmr 9y ago
  The original Packrat parser explicitly defines it as using memoisation: > Packrat parsing provides the simplicity, elegance, and generality of the backtracking model, but eliminates the risk of super-linear parse time, by saving all intermediate parsing results as they are computed and ensuring that no result is evaluated more than once.[1] And just to get a potential misunderstanding out of the way: I’m not claiming that PEGs are formally distinct from recursive descent: According to my understanding (but unlike you I’ve never implemented the packrat algorithm itself … though I’ve written plenty of recursive descent parsers and some PEG-based parsers) there’s a 1:1 correspondence between nonterminals in PEG, and a function in the recursive descent parser. The difference is that one is a formal grammar for describing parsers, while the other is the actual parser implementation. [1] https://paperpile.com/app/p/3c6d20f0-ab15-0b13-b809-1fdf4ac758b1 https://paperpile.com/app/p/3c6d20f0-ab15-0b13-b809-1fdf4ac7...

by klmr 9y ago

loup-vaillant 9y ago

Last time I checked Packrat had nothing to do with memoization. Packrat parsing is the same as precedence climbing, very similar to the shunting yard algorithm, except it leverages the call stack to simplify the code. And last time I checked, PEG was syntax sugar above recursive descent, just like parser combinators. I implemented¹ the damn thing, so I think I know what I'm talking about. Somewhat. Memoization is just a way to go beyond LL(1), and handle left recursive grammars, it's not not mandatory. [1]: http://loup-vaillant.fr/projects/metacompilers/ http://loup-vaillant.fr/projects/metacompilers/

klmr 9y ago
The original Packrat parser explicitly defines it as using memoisation: > Packrat parsing provides the simplicity, elegance, and generality of the backtracking model, but eliminates the risk of super-linear parse time, by saving all intermediate parsing results as they are computed and ensuring that no result is evaluated more than once.[1] And just to get a potential misunderstanding out of the way: I’m not claiming that PEGs are formally distinct from recursive descent: According to my understanding (but unlike you I’ve never implemented the packrat algorithm itself … though I’ve written plenty of recursive descent parsers and some PEG-based parsers) there’s a 1:1 correspondence between nonterminals in PEG, and a function in the recursive descent parser. The difference is that one is a formal grammar for describing parsers, while the other is the actual parser implementation. [1] https://paperpile.com/app/p/3c6d20f0-ab15-0b13-b809-1fdf4ac758b1 https://paperpile.com/app/p/3c6d20f0-ab15-0b13-b809-1fdf4ac7...