Hacker News Reader

Comment by chrisseaton | Hacker News Reader

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.

View on HN

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?

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.

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.

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.

The manual approach to lookahead is primarily what makes PEG, PEG and resolves the ambiguity in a CFG.

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

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.

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

'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.

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.

Reply on news.ycombinator.com