5 ms·
Understanding Parser Combinators (2015)
- MaxGabriel 8y agoThis is a pretty in-depth look into parser combinators in F#. If you’d like something higher level/easier, I wrote an intro to using them in TypeScript/JavaScript: https://medium.com/mercury-bank/a-magic-date-input-using-parser-combinators-in-typescript-3c779741bf4c https://medium.com/mercury-bank/a-magic-date-input-using-par...
- gameswithgo 8y agoI'm curious about the performance of parser combinator approaches to other parsing methods. It seems that generally they are slower, but is this an innate problem, or could clever techniques improve on this? Anyone done work/research in this area?
- convolvatron 8y agoI use higher-order parser combinators in a few different languages and its not really that noticable on a modern machine assuming you're parsing human-written source and not gigabytes of json. but if you look at it, the real cost is in closure creation and control transfers (function indirection). functional compilers are already trying really hard to make those costs disappear. there is some really interesting work lately in manual vectorization of traditionally control flow laden tasks like parsing. i would fully expect some clever people in an appropriate linguistic framework to make frameworks for automating that transformation. but for me personally I find the parser combinator approach: o a pretty direct translation of a model you might see in BNF o considerably easier to maintain/extend/reuse than either external parser generator or recursive descent o more straightforward in the construction of output values than the traditional approach of a parser generator language o amenable to a flexible decomposition of layers rather than the traditional scanner/parser split (alot of simple languages dont really need that distinction) o self contained - removes a big external dependency o simplifies the build its a really good default in the absence of other constraints
- thedufer 8y agoA lot of the closure creation costs can be eliminated by writing the library in a continuation-passing style, which shoves all of the data into proper arguments, bypassing the need for the closure. Of course, the user of the library is still likely to generate closures. The implementation of this I'm most familiar with is OCaml's angstrom library.
- Tarean 8y agoSo the main performance penalty is that you want to parse foobar | foobaz As fooba(r|z) But this requires you to analyse your parsers. Virtually all parser combinator libraries in haskell are monadic and most others follow suit. This means you can parse turing complete languages and parsers are very pleasant to write but also all predicates are undecidable and therefore you can't optimize well. There are a couple ways around this: - rewrite into non-turing-complete parsers when possible using heuristics. Ghc supports this, the original motivation was implicit parallelism for facebooks anti-abuse infrastructure - use a non-monadic dsl. This either makes coding more awkward or forces you to reimplement a bunch of things like if statements - if you really need performance and error messages use a parser generator instead of an embedded dsl Ghc inlines functions incredibly aggressively so the higher order combinators don't have a huge cost. Doing this in a jit compiled language will be more expensive. There are also tradeoffs in the primitives you use - you could only have a primitive to check a single char and then use it in a loop to check strings. But even when inlined you won't beat a fine tuned string comparison function this way.
- abecedarius 8y agoRight, I think you only need monadic bind for semantic predicates. Ordinary semantic actions (i.e. ones that don't feed back into deciding how to parse the rest of the input) can fit smoothly into a parser combinator design without monads, but AFAIK that's not how it's usually done.
- zzzcpan 8y agoThey can be as fast as hand written recursive descent parsers, which is what they are under the hood anyway. But of course this way of writing parsers is like compiling without optimization passes. It can be fast for a lot of things, but not as fast if you can do some optimizations, like moving shared prefixes out of strings to match them only once or use lookup tables instead of iterating over a lot of choices, etc. It requires generating an AST with combinators, not parsing functions directly. Which nullifies the whole point of using parser combinators in the first place.
- profquail 8y agoParser combinators are generally slower than a hand-written or code-generated parser. That’s somewhat innate due to the overhead of “threading” (for lack of a better word) your control flow through many function calls. There are some techniques for improving the performance though — some at the compiler level (by having your language compiler fuse some function calls together where feasible) and some by providing additional, specialized function overloads for developers to use. There’s also an elegant technique described in the paper “Parser Derivative Combinators: A functional Pearl” which seems like it should improve performance but never seemed to gain widespread usage. There was an HN discussion of the paper last year: https://news.ycombinator.com/item?id=17391071 https://news.ycombinator.com/item?id=17391071
- naasking 8y ago> Parser combinators are generally slower than a hand-written or code-generated parser. That’s somewhat innate due to the overhead of “threading” (for lack of a better word) your control flow through many function calls Using functions is an implementation detail. If you had something like MetaOCaml, or some other quasi-quotations, you can generate optimized code at runtime.
- zzzcpan 8y agoWithout functions you have a compiler, not combinator. Functions is what makes it a nice usable thing.
- naasking 8y agoExcept the functions being composed don't have to operate directly on domain values, they can work on quotations, code fragments, data structures, etc. which themselves then operate on the domain values. Are you going to argue that this isn't a combinator library: https://yanniss.github.io/streams-popl17.pdf https://yanniss.github.io/streams-popl17.pdf
- zzzcpan 8y ago
- nixpulvis 8y agohttps://en.m.wikipedia.org/wiki/Parser_combinator https://en.m.wikipedia.org/wiki/Parser_combinator Read under shortcomings for some insight here. I'm personally more interested in the ambiguities than performance. But obviously both are critical.
- necubi 8y agoThey can be fast (see for example the Rust parser-combinator library Nom [0] which benchmarks competitively with hand-written parsers). However you likely need some level of metaprogramming to make them fast, as the way they're implemented in, say, Haskell has a lot of function call overhead that's hard to optimize. Nom uses macros, and the generated code tends to look a lot like the sort of state machine you'd write by hand. That said, the main benefit of parser combinators for me are that they're super easy and fast to write, and easy to modify. So I tend to use a PC library for prototyping, then if I need more performance I'll rewrite it by hand. [0] https://github.com/Geal/nom https://github.com/Geal/nom
- nybble41 8y ago> ...as the way they're implemented in, say, Haskell has a lot of function call overhead that's hard to optimize. GHC inlines aggressively (when you use -O) so there shouldn't be much function call overhead. As others have commented, the bigger issue is that monadic parsers are generally unable to perform static analysis of the full parse tree and thus identify the aspects which parallel branches have in common, which implies more backtracking and redundant parsing. Some of this can be improved heuristically with rewrite rules, or by explicitly using applicative combinators (which can be statically analyzed) instead of monadic ones.
- nixpulvis 8y agoShameless repost of a parser combinator I wrote for a JSON lab back when I was a TA at Northeastern. If you like parsers and Racket this may interest you. I've been wanting to write up a post kinda like this myself, but haven't found the time. https://github.com/nixpulvis/parser-combinator https://github.com/nixpulvis/parser-combinator
- nixpulvis 8y agoThe beauty of parser combinators is how closely they can follow the description of languages like JSON. Just compare https://json.org https://json.org to https://github.com/nixpulvis/parser-combinator/blob/master/json.rkt https://github.com/nixpulvis/parser-combinator/blob/master/j... for example.
- gnufx 8y agoit's a long time since I read it, but I remember the treatment in Burge's 1975 "Recursive Programming Techniques" being clear, along with other techniques, if you can find a library copy. As far as I know, combinator parsing was introduced there, and I find it's normally worth reading the original literature on a topic. Burge is a classic generally as a follow-on to "The Next 700 Programming Languages".
- vlowrian 8y agoAnyone interested in that matter might enjoy these two blog posts by a colleague of mine: 1. https://medium.com/@armin.heller/using-parser-combinators-in-go-e63b3ad69c94 https://medium.com/@armin.heller/using-parser-combinators-in... 2. https://medium.com/@armin.heller/parser-combinator-gotchas-2792deac4531 https://medium.com/@armin.heller/parser-combinator-gotchas-2... They highlight the typical pitfalls of implementing your own parser combinators and I found them very helpful for my understanding of parser combinators.
- LeanderK 8y agoI would really recommend anyone who want's to get a taste of "real" function programming to develop some parser with parser combinators (I developed a java-parser). I started to understand a great deal of functional-programming concepts by using them...and they are so awesome! They are, in my optinion, a prime example where functional programming shines. I think they really had an impact on my journy through programming languages. I am just not sure about f#, but that's probably because I am so used to haskell.
- nuclx 8y agoVery good tutorial. Could easily follow, although I don't know F#, just some Haskell.