No, PEG is prone to exactly this in its default form. Parser combinator usually means something PEG-ish anyway. If you memoize (packrat), it improves to polyno

No, PEG is prone to exactly this in its default form. Parser combinator usually means something PEG-ish anyway. If you memoize (packrat), it improves to polynomial time (not sure what, but it's not linear; that's false advertising and a fraudulent claim), but you're still stuck with the vulnerability to bugs in the grammar. A better idea is to create a parser-combinator-style API on top of an LL or LR backend, for guaranteed linear time and only enough stack space for the deepest part of the AST.