3 ms·
>Unlimited backtracking means it's really easy to accidentally end up with `O(2^n)` parsing behavior. Does this apply to all parser combinators? In Bennu (http
by AgentME 10y ago
>Unlimited backtracking means it's really easy to accidentally end up with `O(2^n)` parsing behavior.
Does this apply to all parser combinators? In Bennu (http://bennu-js.com/ http://bennu-js.com/), which I believe is based on Parsec, you only get backtracking at specific points where you explicitly choose to have it. Are most parser combinator libraries different from Bennu and always let you backtrack to any point implicitly? If you use that sparingly or stay away from it, does that mean you've avoided O(2^n) behavior, or is there some other kind of unavoidable backtracking behavior inherent to parser combinators?