Applicative Parsing
jobjo.github.io
jobjo.github.io
"Higher-Order Functions for Parsing", Graham Hutton - parser combinators before monadic parsing
"Monadic parser combinators", Graham Hutton and Erik Meijer - the discovery of monadic parsing, which is now the standard for parser combinators
My best stab at representing something like EBNF in JS looked like this:
class ArrayGrammar { //e.g: [1, 2, 3, [4, 5,],]
array =()=> ['[', this.entries, ']'];
entries =()=> many(this.entry);
entry =()=> [either(this.array, this.number, ''), /\s*,\s*/];
number =()=> /\d+/;
}
---
Edit: Not much to look at, but here is the source code of the toy implementation if anyone is interested:
https://jsfiddle.net/306jrnt9/1/
The only "cool" part about it is that the parser implementation is close to 100 lines of code.
https://tree-sitter.github.io/tree-sitter/creating-parsers#t...
Is it because the papers are hard to understand? All those symbols make no sense to the uninitiated. I definitely struggled to gain an understanding of how it works.
The other answer is also correct, that it's Yes.
In other words, the question is wrong.
Applicative parser combinators are an interface. The backing implementation is pretty open. It might be recursive descent. It might be the Earley algorithm. It might be a packrat parser.
The interesting thing about Applicative parser combinators is that the way they are composed is amenable to static analysis. That allows a wide variety of implementation strategies, all behind a simple uniform interface...
... So long as you ignore that there are still things left unspecified by the interface, especially related to backtracking behavior. (I really hate how much mindspace Parsec-like libraries have in Haskell. They have the worst backtracking behavior.)
The one that auto-backtracks on Alternative is attoparsec (IIRC), parsec and megaparsec don't unless you use `try`. Is your problem with the attoparsec style or with all of them, and if the latter what do you prefer instead?
Let's say I want to match the strings "a" or "aa" followed by "ab". Let's just go ahead and write that the most trivially obviously correct way:
thing = (string "a" <|> string "aa") <> string "ab"
Yes, this example is artificial, but that makes it easy to understand. The broader issue of which this is one example is that you cannot apply distributive laws in parsec or its derivatives.
(a <*> c) <|> (b <*> c)
(a <|> b) <*> c
(a <*> b) <|> (a <*> c)
a <*> (b <|> c)
There are two notion of backtracking at play here. One is backtracking out of a failing first branch of <|> even though it's consumed some input. The megaparsec authors consider this a form of backtracking (see https://hackage.haskell.org/package/megaparsec-9.0.1/docs/Te...).
The other is backtracking from a failure in the second argument to <> or <*>.
I agree that none of the libraries being considered do the latter. But the effect on memory use wouldn't just be slightly inefficient, it would mean keeping the entire input following a <|> in memory until the whole thing completes. Do you think this is the best way to do things in general, or just for specialized situations like parsing things with a fixed size such as config files?
None of that changes the fact that Parsec-like designs are especially obnoxious when it comes to backtracking. You need to be aware of their limitations and design the structure of your grammar around them.
As an idea for a design somewhere in between, maybe try taking inspiration from Prolog. Add a cut combinator for limiting the scope of backtracking explicitly. It still solves the size issues on large inputs, but it allows more freedom in refactoring as long as you don't cross one of those explicit boundaries.
The former[1] is monadic rather than Applicative, but it has a lot of interesting properties related to error correction and producing online results. Sometimes it feels magical to watch the error correction at work, and the online nature makes it good for memory use if your parser is constructed to take advantage of it.
The latter[2] is strictly applicative, though it's inside an environment monad for making shared productions explicit. Because the grammar portions are strictly applicative, it actually supports turning a grammar around and producing a list of possible outputs from the parser associated with the input sequence that would produce them. It shows off the introspection capabilities nicely, but sometimes you really just want to write a context-sensitive parser, and the applicative interface doesn't give you that power. (Nor does the underlying algorithm support it, so it's nice to match the interface expressiveness to the algorithm power.)
[1] https://hackage.haskell.org/package/uu-parsinglib [2] https://hackage.haskell.org/package/Earley
Functional recursion is just looping. "Recursive Descent" is a very specific parsing algorithm.
You keep talking about "functional recursion".
These are not the same words, nor do they mean the same thing. I do not understand your underlying question, or what point you might be trying to make if the question is intended to be rhetorical.