6 ms·
Parsing is hard. I've worked at several companies where I was literally the only person who understood how to write a recursive descent parser and similarly the
by joe_the_user 8y ago
Parsing is hard. I've worked at several companies where I was literally the only person who understood how to write a recursive descent parser and similarly the only person who understood how maintain or modify parsers of any sort.
The thing is, recursive descent, already fairly hard, seems several steps easier to me than a construct like function-derivatives (or parser-combinators).
And as far as I call follow this paper, the process seems similar to recursive descent except instead of generating code, you generate a bunch of the insides of the code and apply it as an array or something.
And that's thing. The view of process is nice and regular for someone who likes to look at languages abstractly but you have to be leveraging a lot of the laziness of functional languages to make this work.
So altogether, I tend to question whether approaches are really worth the effort.
- actsasbuffoon 8y agoHaving worked with both recursive descent and parser combinators, I can say that I strongly prefer parser combinators. Haskell has some libraries that are fast, easy to use, and have good documentation. I've never managed to find a parser combinator library that I love outside of the Haskell family of languages. I'm not sure why that is.
- afranchuk 8y agoIt might have something to do with most parsing libraries having a Monad/Monoid and Alternative type. Those two together give a truly excellent programmer experience for writing pragmatic, readable, and correct parsers.
- ufo 8y agoParser combinators are basically just libraries for writing recursive descent parsers, aren't they?
- pygy_ 8y agoMostly, yes. They can be applied with a different formalism though. See https://github.com/pygy/compose-regexp.js https://github.com/pygy/compose-regexp.js which uses a parser combinator API with regexps as backend.
- codebje 8y agoI don't think I'd call that a parser combinator, it's a regex DSL - it's just a more verbose way of writing out a regular expression, with a 1:1 translation between the DSL and a regex.
- pygy_ 8y agoA parser combinator is a function that takes one or more parser as argument and returns a parser with the same API as result. combine-regexp is a parser combinator lib backed by regexps. Traditional parser combinators are just a recursive descent parser DSL, with a 1:1 translation between both representations.
- codebje 8y ago"A parser for a thing is a function from a string to a list of pairs of strings and things." > Traditional parser combinators are just a recursive descent parser DSL, with a 1:1 translation between both representations. Yes, exactly - a recursive descent _parser_ recognises a grammar and produces the parse result for the grammar. Parser combinators take little parsers and make bigger parsers. combine-regexp doesn't make parsers, it makes regular expression grammars, that you then feed to some _other_ parser that actually does the parsing based on that grammar.
- pygy_ 8y agoThe line is blurrier in my eyes. The library combines regular grammars that need an interpreter (the `match` method, which is bundled with the regexp object), whereas parser combinators work on code written in the same language (that is ultimately interpreted by the CPU). Edit: the parser in this case is a `(Regexp.prototype.match, regex.source)` tuple, whereas in the case of a praser combinator lib in a language that compiles to machine code, it would be `(call instruction, instructions list)`.
- seanmcdirmid 8y agoA lot of parsing techniques have specialized contexts where they are useful. Hand written recursive descent dominates for production languages because it is one file and error reporting and recovery is very important. Parsing combinatory are great for small embedded languages, parsing generators are great when efficiency or concenience is desired, and so on.
- carapace 8y agoIn my opinion Brzozowski’s derivatives of regular expressions are worth the effort. I think it's a historical fluke that it was overshadowed by other parsing techniques. I have some crude Python code that (kind of) illustrates the brevity and elegance of the idea: https://gist.github.com/calroc/ad4321dc4c43d5f3e09d39283461b8fe https://gist.github.com/calroc/ad4321dc4c43d5f3e09d39283461b...