| ▲ | giraffe_lady 9 days 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? | ||
| ▲ | o11c 9 days ago | parent | next [-] | |
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. | ||
| ▲ | yen223 9 days ago | parent | prev | next [-] | |
PEGs 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) | ||
| ▲ | vrighter 8 days ago | parent | prev [-] | |
Only if a packrat parser is implemented, which requires a lot of memory. | ||