Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: