Pratt parsing is a black box

For Pratt parsing as a component of a self-extensible language like this, it's worth checking out what Lean does.

Most dependently typed languages require explicit forward declarations and other things that already force them to run in a single pass at the top level. In Lean's case, the top-level granularity is one command-like item executed in a monad, which provides a natural synchronization boundary for an on-the-fly self-extensible language. You can read an overview with links to code here. Quoting the initial excerpt:

"The Lean parser was developed with the following primary goals in mind:

• flexibility: Lean's grammar is complex and includes indentation and other whitespace sensitivity. It should be possible to introduce such custom "tweaks" locally without having to adjust the fundamental parsing approach.
• extensibility: Lean's grammar can be extended on the fly within a Lean file, and with Lean 4 we want to extend this to cover embedding domain-specific languages that may look nothing like Lean, down to using a separate set of tokens.
• losslessness: The parser should produce a concrete syntax tree that preserves all whitespace and other "sub-token" information for the use in tooling.
• performance: The overhead of the parser building blocks, and the overall parser performance on average-complexity input, should be comparable with that of the previous parser hand-written in C++. No fancy optimizations should be necessary for this.

Given these constraints, we decided to implement a combinatoric, non-monadic, lexer-less, memoizing recursive-descent parser. Using combinators instead of some more formal and introspectible grammar representation ensures ultimate flexibility as well as efficient extensibility: there is (almost) no pre-processing necessary when extending the grammar with a new parser.

The lack of a dedicated lexer ensures we can modify and replace the lexical grammar at any point, and simplifies detecting and propagating whitespace. [...] Tokens also play a central role in the prattParser combinator, which selects a leading parser followed by zero or more trailing parsers based on the current token. [...] The Parser type is extended with additional metadata over the mere parsing function to propagate token information: collectTokens collects all tokens within a parser for registering. firstTokens holds information about the "FIRST" token set used to speed up parser selection in prattParser."

The language reference also has a chapter that goes into greater detail, including on macros and elaborators, which you can roughly think of as type-directed, context-directed macros that can access the semantic environment.

An interesting facet of so-called postponement in languages like this is that it lets you schedule elaborators to run out of syntactic order depending on their mutual dynamic data dependencies; they synchronize implicitly through so-called holes, which from an operational perspective are like dataflow variables. Because elaborators run encapsulated in a monad, you don't need to use suspend/resume scheduling or any other particular strategy. E.g. you can use abort/retry scheduling as described in the Build Systems á la Carte paper, which I believe is more or less what Lean does: you optimistically run an elaborator and if it tries to read the content of a hole then its partial execution is aborted and its re-run is postponed (until another elaborator can hopefully fill in that hole and let the postponed elaborator make progress when the scheduler gets back to it eventually).

I used Pratt parsing in the compiler for a macro-heavy language that I've been developing for almost a year before finally sitting down on my chair to write my thoughts on Pratt parsing. The code is closed right now because I don't want LLMs training on my code before the public release for 0.1, but what I can say is that Pratt fundamentally changed the design of my language by allowing metaprogramming stuff that I never dreamed of.

I'm glad to see more explorations of Pratt parsing :-) And thanks for referring to previous writing, including my own!

In the opening code snippet, I think a VERY important point is that both nud() and led() will typically call back into expression() (after the Pratt logic dispatches to the right one).

There's no getting around that languages are fundamentally not just recursive, but mutually recursive, so that is where it shows up.

---

Another useful observation is that it's like recursive descent, in that it's both recursive and "mutating".

That is, Pratt parsing and recursive descent are a different style of algorithm than "recursively count the nodes in a tree" e.g. 1 + count(left) + count(right), which is functional / immutable.

In contrast, they advance through the token stream at the same time -- they have a side effect. Hence the advance() in the opening code snippet. I like writing it self.advance() or self.Next() for that reason.

---

There are many ways to think of the algorithm, but I sometimes think of it as "recursive descent, except you want to control the output tree with a numeric precedence table".

In other words, Dragon Book parsing is not as focused on the output tree. It's focused mainly on recognition: is a string part of the (infinite) set that a grammar specifies? That is a boolean yes/no.

The Dragon book also says that you can construct a CST (concrete syntax tree) from the parsing process, i.e. with LR or LL parsing. The CST is a tree that mirrors the structure of the grammar.

With Pratt, you construct a more concise tree (that's not a CST) more "directly" and efficiently. It's NOT grammatical; it's more focused on the tree structure / traversal order.

A useful exercise is to join all these styles together with the SAME lexer: recursive descent, Pratt, grammars. Oils does this, and the different algorithms all become mutually recursive with each other!

I don't know what could possibly be causing this, but in Firefox's reading mode the contents of every code block are repeated four times.

I still wish to know: what would people categorize BABLR as? Is it a pratt parser? https://github.com/bablr-lang/language-en-json/blob/trunk/lib/grammar.js