3 ms·
> Naively implemented directly-executed parser-combinators aren't any more powerful than recursive-descent. Parser combinators are recursive descent, as in, th
by ookdatnog 6y ago
> Naively implemented directly-executed parser-combinators aren't any more powerful than recursive-descent.
Parser combinators are recursive descent, as in, they are just a neat way to write down a recursive descent parser using a compositional style. The reason they're popular is because they compose well and feel more declarative than traditional recursive descent.
- thechao 6y agoNaively implemented directly-executed parser-combinators are recursive-descent. More sophisticated parser-combinators are usually lowered to PEGs, GLRs, or PEPs.
- MaxBarraclough 6y ago'PEP'?
- thechao 6y agoPractical Earley Parsers. If you memoize the algorithm I presented you get the Earley parser; if you convert the itemsets of an Earley parser into tables you get a PEP. PEPs are as fast as other LL/LR/LALR table parsers, but also accept all CFGs. They’ve lost the “mental space war” to YACCen, PEGs, and parsecs.