7 ms·

My understanding is Pest doesn't use packrat, and thus doesn't have the unbounded lookahead mentioned in the article. I figure that unbounded lookahead comes wi

My understanding is Pest doesn't use packrat, and thus doesn't have the unbounded lookahead mentioned in the article. I figure that unbounded lookahead comes with a lot of downsides, and my opinion is that Pest solves lookahead in an interesting way. It felt relevant given the focus on lookahead in the article.

chrisseaton 7y ago
Packrat isn't really a parsing algorithm - the PEG is the parsing algorithm. Packrat is instead an optimisation that can be transparently applied to a PEG. It's a common cause of confusion. And to make it more complicated some PEGs aren't really tractable without Packrat, so then that's sort of not an optimisation any more.
- strictfp 7y ago
  Ok, thank you for clarifying. If you don't mind me asking, is the manual approach to lookahead common to most PEG parsers? And if so, why would packrat be associated with infinite lookahead?
  - chrisseaton 7y ago
    The manual approach to lookahead is standard for PEG. You mean things like the negative predicate when you talk about lookahead, right? That's in Ford's 2002 thesis. And the operator precedence? I was doing that in my masters thesis in 2006. Packrat caches intermediate results so that you don't have to factor your rules out to avoid trying to parse the same thing repeatedly. PEGs can already do as much lookahead as you care fore and Packrat doesn't optimise that, except between multiple choices. So that allows you to write more natural grammars.
    - strictfp 7y ago
      I might have misread what Guido is writing in the article then; " So how does a PEG parser solve these annoyances? By using an infinite lookahead buffer! The typical implementation of a PEG parser uses something called “packrat parsing”, which not only loads the entire program in memory before parsing it, but also allows the parser to backtrack arbitrarily. While the term PEG primarily refers to the grammar notation, the parsers generated from PEG grammars are typically recursive-descent parsers with unlimited backtracking, " I read that as implying generating a typical recursive descent, with the classical degenerate branching cases that TDOP partially solves.
      - chrisseaton 7y ago
        I suppose you could call the packrat cache an 'infinite lookahead buffer'. Arbitrary backtracking is a property of PEGs though - you don't need Packrat for that. The original 1970s Ullman paper that this all goes back to is 'parsing algorithms with [arbitrary] backtrack'. Packrat made it linear. These differences probably aren't worth worrying about too much though.
  - pkd 7y ago
    The manual approach to lookahead is primarily what makes PEG, PEG and resolves the ambiguity in a CFG.
- cakoose 7y ago
  > Packrat isn't really a parsing algorithm - the PEG is the parsing algorithm. The way I've seen it presented, PEG is primarily a style of grammar (basically, prioritized choice instead of normal alternation) and Packrat is a parsing algorithm. http://bford.info/packrat/ http://bford.info/packrat/
  - chrisseaton 7y ago
    I'm listed in that bibliography. A PEG is imperative. It's already an 'algorithm' and already describes how to parse it. That's different to traditional declarative grammars that people are used to, which need an algorithm to go with the grammar.
    - mehrdadn 7y ago
      In your own thesis you point out that the naive recursive-descent algorithm has exponential runtime and that's why we use Packrat parsing instead? Meaning you have a choice of at least 2 algorithms that you need to pick between when parsing with your PEG, not just one? Or alternatively you could claim no CFG needs an algorithm either, since you could just use recursive descent on everything...
      - chrisseaton 7y ago
        'Risks exponential runtime', is what it literally says. Ford also said 'risk of exponential parse time'. PEG without Packrat can work for many grammars just fine. I was also talking in the context of PEG under composition, where the problem is at its worst. You don't need an extra algorithm to parse. You'd just like one to make sure it runs reasonably fast. You can't use recursive descent on everything - how do you build a reclusive descent parser for an ambiguous grammar? You'd have to introduce some extra rules. That's the parsing algorithm, distinct from the grammar.
        mehrdadn 7y ago
        Ambiguity shouldn't be relevant? If it's ambiguous then you can just keep going after the first match. The only thing you should need is to eliminate left recursion, which is a grammar transformation you can do before you run your recursive descent... I think left recursion elimination + recursive descent should cover recognition for all CFGs? I think you can probably also use GLR (or whatever) to parse a language described by a PEG too. All you should need to do is to just prune the extra branches. If I'm not mistaken it should get you a better worst-case complexity than Packrat too. So I really don't see how you can say PEG is an algorithm... you have plenty of options for what algorithm to use, it's just that people prefer a particular one.

chrisseaton 7y ago

Packrat isn't really a parsing algorithm - the PEG is the parsing algorithm. Packrat is instead an optimisation that can be transparently applied to a PEG. It's a common cause of confusion. And to make it more complicated some PEGs aren't really tractable without Packrat, so then that's sort of not an optimisation any more.

strictfp 7y ago
Ok, thank you for clarifying. If you don't mind me asking, is the manual approach to lookahead common to most PEG parsers? And if so, why would packrat be associated with infinite lookahead?
- chrisseaton 7y ago
  The manual approach to lookahead is standard for PEG. You mean things like the negative predicate when you talk about lookahead, right? That's in Ford's 2002 thesis. And the operator precedence? I was doing that in my masters thesis in 2006. Packrat caches intermediate results so that you don't have to factor your rules out to avoid trying to parse the same thing repeatedly. PEGs can already do as much lookahead as you care fore and Packrat doesn't optimise that, except between multiple choices. So that allows you to write more natural grammars.
  - strictfp 7y ago
    I might have misread what Guido is writing in the article then; " So how does a PEG parser solve these annoyances? By using an infinite lookahead buffer! The typical implementation of a PEG parser uses something called “packrat parsing”, which not only loads the entire program in memory before parsing it, but also allows the parser to backtrack arbitrarily. While the term PEG primarily refers to the grammar notation, the parsers generated from PEG grammars are typically recursive-descent parsers with unlimited backtracking, " I read that as implying generating a typical recursive descent, with the classical degenerate branching cases that TDOP partially solves.
    - chrisseaton 7y ago
      I suppose you could call the packrat cache an 'infinite lookahead buffer'. Arbitrary backtracking is a property of PEGs though - you don't need Packrat for that. The original 1970s Ullman paper that this all goes back to is 'parsing algorithms with [arbitrary] backtrack'. Packrat made it linear. These differences probably aren't worth worrying about too much though.
- pkd 7y ago
  The manual approach to lookahead is primarily what makes PEG, PEG and resolves the ambiguity in a CFG.
cakoose 7y ago
> Packrat isn't really a parsing algorithm - the PEG is the parsing algorithm. The way I've seen it presented, PEG is primarily a style of grammar (basically, prioritized choice instead of normal alternation) and Packrat is a parsing algorithm. http://bford.info/packrat/ http://bford.info/packrat/
- chrisseaton 7y ago
  I'm listed in that bibliography. A PEG is imperative. It's already an 'algorithm' and already describes how to parse it. That's different to traditional declarative grammars that people are used to, which need an algorithm to go with the grammar.
  - mehrdadn 7y ago
    In your own thesis you point out that the naive recursive-descent algorithm has exponential runtime and that's why we use Packrat parsing instead? Meaning you have a choice of at least 2 algorithms that you need to pick between when parsing with your PEG, not just one? Or alternatively you could claim no CFG needs an algorithm either, since you could just use recursive descent on everything...
    - chrisseaton 7y ago
      'Risks exponential runtime', is what it literally says. Ford also said 'risk of exponential parse time'. PEG without Packrat can work for many grammars just fine. I was also talking in the context of PEG under composition, where the problem is at its worst. You don't need an extra algorithm to parse. You'd just like one to make sure it runs reasonably fast. You can't use recursive descent on everything - how do you build a reclusive descent parser for an ambiguous grammar? You'd have to introduce some extra rules. That's the parsing algorithm, distinct from the grammar.
      - mehrdadn 7y ago
        Ambiguity shouldn't be relevant? If it's ambiguous then you can just keep going after the first match. The only thing you should need is to eliminate left recursion, which is a grammar transformation you can do before you run your recursive descent... I think left recursion elimination + recursive descent should cover recognition for all CFGs? I think you can probably also use GLR (or whatever) to parse a language described by a PEG too. All you should need to do is to just prune the extra branches. If I'm not mistaken it should get you a better worst-case complexity than Packrat too. So I really don't see how you can say PEG is an algorithm... you have plenty of options for what algorithm to use, it's just that people prefer a particular one.