3 ms·
PEGs don't have this problem right? Linear time over length of input? Though I guess most peg libraries probably aren't "pure" pegs to get around its limitation
by giraffe_lady 2y ago
PEGs don't have this problem right? Linear time over length of input? Though I guess most peg libraries probably aren't "pure" pegs to get around its limitations and may reintroduce this issue?
- yen223 2y agoPEGs don't have this problem only because they place restrictions on the grammar. In practice, this isn't a problem, but it does require you write grammar rules in a specific way (e.g. no left-recursion)
- o11c 2y agoNo, 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.
- vrighter 2y agoOnly if a packrat parser is implemented, which requires a lot of memory.