10
$\begingroup$

Motivation

There seems to be something popular in the rust community called parser combinators.

I temporarily use a traditional recursive descent parser, my syntax is not yet stable, composition means flexible, I am considering whether to use the parser combinator library to rewrite.

Question

I'm wondering if there is a mainstream language or compiler front end using parser combinators?

What are the advantages over traditional hand-written recursive descent parsers? Such as runtime speed, maintainability, traceability of semantic errors, etc.

$\endgroup$
8
  • $\begingroup$ I don't know thoroughly, but Haskell chose readPrec :: Read a => ReadPrec a over readsPrec :: Read a => Int -> ReadS a because "backtracking parsers become inefficient easily." $\endgroup$ Jul 10, 2023 at 3:15
  • 2
    $\begingroup$ You're asking 2 questions here: does anyone use them, and what are the advantages. I'd suggest editing your question to focus on the 2nd, because the first is not that interesting (the answer is: The main disadvantage of parser combinators is that they can easily cause your parser to take exponential time due to the backtracking. For this reason, you probably won't find any production compiler using them. There are ways around this, but AFAIK they can only reduce time complexity to cubic at best, so it's just easier to switch to a faster parsing method) $\endgroup$
    – pxeger
    Jul 10, 2023 at 10:31
  • $\begingroup$ Rust community primarily uses parser generators for programming languages, not parser combinators, IE Pest things like Nom are used for small domain specific languages. $\endgroup$
    – Krupip
    Jul 10, 2023 at 19:01
  • $\begingroup$ @Krupip Another parser combinator crate chumsky has been gaining traction lately. It has built-in support for error reporting and error recovery, which is super handy when you want decent error messages. $\endgroup$
    – Bubbler
    Jul 12, 2023 at 7:27
  • $\begingroup$ @pxeger: "exponential time due to the backtracking" — I don't know about its time complexity, but combine does LL(1) by default, so minimal backtracking. $\endgroup$
    – user570286
    Jul 12, 2023 at 7:42

2 Answers 2

10
$\begingroup$

"Parser combinators" and "recursive descent parsers" are complementary. In fact, "parser combinators" are what you get if you try to write a recursive descent parser in Haskell without going mad.

The main difference is that a traditional recursive descent parser involves writing new parser functions that use the usual control structures of the underlying language to explicitly invoke lower-level parsers, coordinate their execution, and combine their results. The parser combinator approach involves calling functions that take parsers (i.e., parser functions) as arguments and return a parser (i.e., a parser function) that invokes the argument parsers, coordinates their execution, and combines their results.

If you like, you can think of parser combinators as "templates" for recursive descent parser functions that themselves can be composed into larger "templates".

The advantages primarily have to do with reusability of the combinators. As a concrete example, if you are writing a traditional recursive descent parsing function to parse a sequence of statements separated by semicolons, you'll probably write a function that tries to parse statements in a loop, stopping when it fails to parse an intervening semicolon. When it comes time to write a parsing function to parse a sequence of expressions separated by commas, you'll probably write another function that tries to parse expressions in a loop, stopping when it fails to parse an intervening comma.

If you're using parser combinators, you'll probably define these parsing functions with a couple of one-liners:

let program = sep_by(statement, semicolon);
let arglist = sep_by(expression, comma);

(If your approach to writing recursive descent parsers allows you to achieve this level of code reuse, congratulations, you've independently implemented parser combinators.)

Anyway, the resulting parser code tends to be easier to read and easier to maintain by virtue of the reusability of combinator components. With well named components, the definition of a parser can read a lot like a high-level grammar, which is also appealing. However, in practice, this works really well in Haskell and less well in other languages that don't share Haskell's curried functions, applicative operators, and "call by juxtaposition" syntax. I'd still say that parser combinators are a net win for maintainability in non-Haskell languages, but the syntax may be ugly and distracting.

With respect to runtime speed, parser combinators should perform similarly to recursive descent parsers, because they're basically doing the same thing. There's nothing intrinsic to parser combinators that causes exponential performance problems or inefficient backtracking. It will depend on the library. Some libraries don't backtrack by default , and you must use a try combinator on a case-by-case basis to enable backtracking. For these libraries, you must learn and understand their method of implementing backtracking (which usually boils down to the difference between "failing without consuming input" and "failing after consuming input") or you will create fragile, buggy parsers that you'll never be able to get right.

Some libraries (e.g., nom, I think, unless I'm misunderstanding the documentation) do backtrack by default, and you must become skilled at using the cut combinator to curb backtracking, or you're likely to create a disastrously slow parser by accident.

That's the main disadvantage of the parser combinator approach -- it involves a complicated contract between parsers and combinators, and the details of that contract are often not entirely clear in the library documentation. You can write "toy" parsers without really understanding what you're doing, but when you make the switch to real world parsers, a firm understanding of the details of parser behavior is absolutely essentially, and you'll probably need to read some library code to really understand what's going on. (This is really bad in the Haskell community, where "types are documentation", ha ha. A well documented Rust crate might avoid this problem.)

With respect to traceability of semantic errors, I assume you're talking about errors in parse input that can only be detected after parsing is complete and some semantic analysis has been performed -- can you then trace them back to specific bits of code? Most libraries will have a method of retrieving position information and attaching it to the parser abstract syntax tree. It's usually not an automatic process, and you'll have to decide exactly how you want to attach that position information to your AST. I note that "nom" has a "nom_locate" crate specifically designed to help you attach location "span" data to your AST.

That brings us to another disadvantage of parser combinators. They're generally part of a library that you yourself will not have written. So, unless you want to dig into library code, you'll be dealing with a lot of abstract concepts and opaque functions and types. If the library doesn't provide a feature that you need, you'll have to dig in and implement it, and it'll probably be harder than if you'd written a traditional recursive descent parser yourself. You'll want to pick a well-maintained, "serious" parser library here. I think "nom" might fit the bill, but I don't have any first hand experience with it. Working through some tutorials and studying some example parsers might be worthwhile.

$\endgroup$
2
$\begingroup$

To add to the good and long answer:

If your language definition uses denotational semantics, your code will reflect that or show errors in your language definition.

From my experience, they are horrible when it comes to good input error handling and they tempt you to make bad decisions in your language design as most of these libraries are, like handwritten recursive decent, turing-complete and not LL(1) or similar.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .