4 ms·

Why are parser combinators not given any attention in traditional academic treatments of parsing? Is there some drawback compared to other popular methods? (And

Why are parser combinators not given any attention in traditional academic treatments of parsing? Is there some drawback compared to other popular methods? (And why are they relatively more popular on HN and in functional programming communities?) For instance, in the book of Grune and Jacobs on parsing techniques, they are presented as essentially a curiosity (with 2.5 pages of description in a 600+ page book).

Joker_vD 5y ago
They have an exponential complexity in general case, I guess that's the reason. There is a way to make them be of polynomial complexity in the worst case, but it requires quite an ingenious memoization technique, coupled with lazy evaluation.
- ahelwer 5y ago
  Do you have any reading about this or terms I could search to learn more?
  - spekcular 5y ago
    This paper gives the best algorithm I know of, and a sketch of its complexity: http://dinhe.net/~aredridel/.notmine/PDFs/Parsing/SPIEWAK,%20Daniel%20(2010)%20-%20Generalized%20Parser%20Combinators.pdf http://dinhe.net/~aredridel/.notmine/PDFs/Parsing/SPIEWAK,%2....
    - deleted 5y ago
      [deleted]
Athas 5y ago
From an academic point of view, most parser combinator libraries are basically LL parsers with backtracking. This is eminently practical (especially if the backtracking part is done well), but from an academic point of view that means they're not very interesting - really just a nicer way of implementing recursive descent parsers. There is of course plenty of academic work specifically on how to implement parser combinator libraries efficiently, how to make them invertible (so they can also produce prettyprinters), provide good error messages, etc.
marcosdumay 5y ago
As people said, they are simpler, less strict (what means you can get bad performance if you use them wrong), and just an abstraction over the very general concept of recursive context-dependent parsing. There isn't much to cover about them, they are just very ergonomic. Even guaranteeing a good performance is covered on the theory of other types of parser, that is them trivial to replicate on them, but it's not about them.
auggierose 5y ago
There is the PEG paper [1], which is basically a formalisation of parser combinators. But really, otherwise there is not much to say about parser combinators, as they are just code. The cool thing about parsing is that usually you can give much nicer descriptions of the grammar than via parser combinators, and you can analyse these descriptions (uniqueness, for example), und generate optimised code. [1] https://dl.acm.org/doi/10.1145/964001.964011 https://dl.acm.org/doi/10.1145/964001.964011
kccqzy 5y ago
Parser combinators are just a nicer syntax for implementing recursive descent parsing†. That's not enough academic content for the subset of academia focused on Algorithm and Data Structures. But of course if you are interested in another subset interested in Programming Languages and Types, you'll find plenty of people interested not in the algorithm (which is easy) but also the way it's written in a real programming language, and leveraging type systems to make the code nice; that's where you'll find most of the academic discussions on it. Also, higher-kinded types are pretty much required to make parser combinators nice, so that restricts the appeal of parser combinators to just Haskell and a few other niche languages. Yet another reason is that like all recursive descent parsing with backtracking, it's easy to accidentally make your parser run in exponential time. It certainly requires discipline and deliberation to avoid that. †: I only know of one library in Haskell that has a parser-combinator-like interface without recursive descent parsing, and that's https://github.com/ollef/Earley https://github.com/ollef/Earley but I'll quote from its README the difference between that and typical parser combinators: > The grammar language is similar to that of many parser combinators (Parsec, Attoparsec, parallel parsing processes, etc.), providing an applicative interface, but the parser gracefully handles all finite CFGs, including those with left-recursion. On the other hand, its productions are not monadic meaning that it does not support context-sensitive or infinite grammars, which are supported by many parser combinator libraries.
chowells 5y ago
Most replies to this are making a category error. Parser combinators aren't a parsing technology, they're a library interface. You can use any parsing technology as a backend to an interface that is built in terms of combinators. That most of them are essentially recursive-descent is a result of common implementation decisions, not a requirement of the interface. And that's why parsing research doesn't pay much attention to it - it's an interface, not a different approach to handling data while parsing. It's all about ergonomics of using a parser, not about the capability and performance characteristics of parsing. Should more research pay attention to that? Probably. BISON/YACC/ANTLR are all hell to use. Combinator-based libraries are easier, but current designs lack things like extending parsers without modifying them. There's a lot of research that could be done that would care about this aspect of parsers, but it doesn't seem to be for now.

Joker_vD 5y ago

They have an exponential complexity in general case, I guess that's the reason. There is a way to make them be of polynomial complexity in the worst case, but it requires quite an ingenious memoization technique, coupled with lazy evaluation.

ahelwer 5y ago
Do you have any reading about this or terms I could search to learn more?
- spekcular 5y ago
  This paper gives the best algorithm I know of, and a sketch of its complexity: http://dinhe.net/~aredridel/.notmine/PDFs/Parsing/SPIEWAK,%20Daniel%20(2010)%20-%20Generalized%20Parser%20Combinators.pdf http://dinhe.net/~aredridel/.notmine/PDFs/Parsing/SPIEWAK,%2....
  - deleted 5y ago
    [deleted]

Athas 5y ago

From an academic point of view, most parser combinator libraries are basically LL parsers with backtracking. This is eminently practical (especially if the backtracking part is done well), but from an academic point of view that means they're not very interesting - really just a nicer way of implementing recursive descent parsers. There is of course plenty of academic work specifically on how to implement parser combinator libraries efficiently, how to make them invertible (so they can also produce prettyprinters), provide good error messages, etc.

marcosdumay 5y ago

As people said, they are simpler, less strict (what means you can get bad performance if you use them wrong), and just an abstraction over the very general concept of recursive context-dependent parsing. There isn't much to cover about them, they are just very ergonomic. Even guaranteeing a good performance is covered on the theory of other types of parser, that is them trivial to replicate on them, but it's not about them.

auggierose 5y ago

There is the PEG paper [1], which is basically a formalisation of parser combinators. But really, otherwise there is not much to say about parser combinators, as they are just code. The cool thing about parsing is that usually you can give much nicer descriptions of the grammar than via parser combinators, and you can analyse these descriptions (uniqueness, for example), und generate optimised code. [1] https://dl.acm.org/doi/10.1145/964001.964011 https://dl.acm.org/doi/10.1145/964001.964011

kccqzy 5y ago

Parser combinators are just a nicer syntax for implementing recursive descent parsing†. That's not enough academic content for the subset of academia focused on Algorithm and Data Structures. But of course if you are interested in another subset interested in Programming Languages and Types, you'll find plenty of people interested not in the algorithm (which is easy) but also the way it's written in a real programming language, and leveraging type systems to make the code nice; that's where you'll find most of the academic discussions on it. Also, higher-kinded types are pretty much required to make parser combinators nice, so that restricts the appeal of parser combinators to just Haskell and a few other niche languages. Yet another reason is that like all recursive descent parsing with backtracking, it's easy to accidentally make your parser run in exponential time. It certainly requires discipline and deliberation to avoid that. †: I only know of one library in Haskell that has a parser-combinator-like interface without recursive descent parsing, and that's https://github.com/ollef/Earley https://github.com/ollef/Earley but I'll quote from its README the difference between that and typical parser combinators: > The grammar language is similar to that of many parser combinators (Parsec, Attoparsec, parallel parsing processes, etc.), providing an applicative interface, but the parser gracefully handles all finite CFGs, including those with left-recursion. On the other hand, its productions are not monadic meaning that it does not support context-sensitive or infinite grammars, which are supported by many parser combinator libraries.

chowells 5y ago

Most replies to this are making a category error. Parser combinators aren't a parsing technology, they're a library interface. You can use any parsing technology as a backend to an interface that is built in terms of combinators. That most of them are essentially recursive-descent is a result of common implementation decisions, not a requirement of the interface. And that's why parsing research doesn't pay much attention to it - it's an interface, not a different approach to handling data while parsing. It's all about ergonomics of using a parser, not about the capability and performance characteristics of parsing. Should more research pay attention to that? Probably. BISON/YACC/ANTLR are all hell to use. Combinator-based libraries are easier, but current designs lack things like extending parsers without modifying them. There's a lot of research that could be done that would care about this aspect of parsers, but it doesn't seem to be for now.