4 ms·
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 t
by 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 agoI 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.