4 ms·

Sure! I didn't mention them in the post because it was already getting a bit long, but here are a few: - Unlimited backtracking means it's really easy to accid

by lihaoyi 10y ago

Sure! I didn't mention them in the post because it was already getting a bit long, but here are a few: - Unlimited backtracking means it's really easy to accidentally end up with `O(2^n)` parsing behavior. Most real-life languages you parse won't be like that, but there's nothing in-the-framework that's stopping you from becoming exponential. In this way, it's just like recursive descent. - Performance isn't as good as code-gen or hand-written; it's basically a grammar-interpreter rather than a grammar-compiler. We're looking at (depending on grammar) 4-10x slower than the most optimized hand-written parser, e.g. in the same benchmark, the FastParse JSON parser runs at ~2 million lines of JSON a second, vs ~8 million lines/second for "industry standard" parsers on the same platform (JVM) like Jackson. Whether this is a problem for you is an empirical question. - They take some initialization time at-runtime. A hand-rolled or code-gen parser is ready almost immediately, whereas a parser-combinator parser takes a bit of time instantiating `Parser[T]` objects and plumbing them around. This is a one time cost, since the parsers are immutable and can be re-used, but it's still a cost nonetheless if you're trying to shave milliseconds off your startup time.

catnaroek 10y ago
> there's nothing in-the-framework that's stopping you from becoming exponential. Recursive-descent parsing is executing a logic program, so couldn't you prevent backtracking by adding a `cut` operator? That's essentially what LL(1) parsing gives you: an implicit `cut` after successfully selecting a branch.
- lihaoyi 10y ago
  Yes, there is a `cut` operator, and it does exactly what you expect. It's heavily documented here http://www.lihaoyi.com/fastparse/#Cuts http://www.lihaoyi.com/fastparse/#Cuts Just because there's a `cut` operator doesn't mean people will use it though =P
  - catnaroek 10y ago
    Oh, very nice. :-)
jhpriestley 10y ago
It's worth mentioning that, except for the initialization time, these are not inherent downsides of parser combinators. Any parsing strategy can be implemented using combinators, for example the "earley" package for haskell produces Earley parsers using combinators. Writing combinators for an algorithm which needs to analyze the whole grammar does require explicit fixpoints (`A -> aA` has to be encoded as something like `fix(lambda A. aA)`, or in Haskell with `MonadFix` syntax), and unsafe type casts.
- lihaoyi 10y ago
  Yes, you are right. These are limitations of the PEG/recursive-descent style of parser-combinators, which FastParse is a member of. If you use a set of parser combinators that use a different execution model (e.g. https://github.com/djspiewak/gll-combinators https://github.com/djspiewak/gll-combinators) then the API will be similar, but the performance and runtime characteristics will be totally different.
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?

by lihaoyi 10y ago

catnaroek 10y ago

> there's nothing in-the-framework that's stopping you from becoming exponential. Recursive-descent parsing is executing a logic program, so couldn't you prevent backtracking by adding a `cut` operator? That's essentially what LL(1) parsing gives you: an implicit `cut` after successfully selecting a branch.

lihaoyi 10y ago
Yes, there is a `cut` operator, and it does exactly what you expect. It's heavily documented here http://www.lihaoyi.com/fastparse/#Cuts http://www.lihaoyi.com/fastparse/#Cuts Just because there's a `cut` operator doesn't mean people will use it though =P
- catnaroek 10y ago
  Oh, very nice. :-)

jhpriestley 10y ago

It's worth mentioning that, except for the initialization time, these are not inherent downsides of parser combinators. Any parsing strategy can be implemented using combinators, for example the "earley" package for haskell produces Earley parsers using combinators. Writing combinators for an algorithm which needs to analyze the whole grammar does require explicit fixpoints (`A -> aA` has to be encoded as something like `fix(lambda A. aA)`, or in Haskell with `MonadFix` syntax), and unsafe type casts.

lihaoyi 10y ago
Yes, you are right. These are limitations of the PEG/recursive-descent style of parser-combinators, which FastParse is a member of. If you use a set of parser combinators that use a different execution model (e.g. https://github.com/djspiewak/gll-combinators https://github.com/djspiewak/gll-combinators) then the API will be similar, but the performance and runtime characteristics will be totally different.

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?