3 ms·

> 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,

> 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

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.