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 only found/stopped to read/paid attention to your blogposts on the topic of Pratt parsing after my project/language was already deep on “Pratt rails”, but I must say... from any person alive, I think you're the one with the parsing mindset closest to my own (when it comes to parsing problems). This time I'll probably copy your design on eggexes instead of going on the route of designing something of my own from scratch just to find out in the end that whatever I come up with would be incredibly similar to something you already designed earlier anyways.
There are in fact four complete copies of each code block as it looks the typst html styling in use seems to use four separate divs each containing the full text content and then do some selective display or something of them for color schemes and stuff.
Chrome reading mode also behaves the same rendering all four copies.
No. Briefly skimming that file (I spent a few minutes trying to chase definitions across repos before I gave up), it looks like a conventional recursive-descent pull parser, where pulling is implemented via generators. You could also be using the generators for backtracking but I don't see any evidence of that in this file. Both ideas, i.e. using generators in a recursive-descent parser for backtracking and pulling, are standard; neither of them have anything to do with Pratt parsing except insofar as they're all examples of recursive-descent parsing.
Since generator frames are heap allocated in JavaScript VMs, generators are also an easy way to avoid fixed-depth stack overflows in recursive-descent parsing for adversarial inputs like "((((...." where the recursion depth is linear in the size of the input. It comes at a high price in efficiency and memory usage; goroutine-style stacks are a much more efficient VM implementation technique for supporting pulling and unbounded recursion.
It's actually a push parser though! The thread of control is held by the grammar not the core. Wherever you see eatMatch parsing can backtrack, but otherwise it's LR. It uses a special shift instruction to handle infix grammars.
pervognsen | 15 hours ago
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:
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).
[OP] vinipsmaker | 16 hours ago
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.
andyc | 13 hours ago
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()andled()will typically call back intoexpression()(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 itself.advance()orself.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!
[OP] vinipsmaker | 13 hours ago
I only found/stopped to read/paid attention to your blogposts on the topic of Pratt parsing after my project/language was already deep on “Pratt rails”, but I must say... from any person alive, I think you're the one with the parsing mindset closest to my own (when it comes to parsing problems). This time I'll probably copy your design on eggexes instead of going on the route of designing something of my own from scratch just to find out in the end that whatever I come up with would be incredibly similar to something you already designed earlier anyways.
hjvt | 14 hours ago
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.
abeyer | 14 hours ago
There are in fact four complete copies of each code block as it looks the typst html styling in use seems to use four separate divs each containing the full text content and then do some selective display or something of them for color schemes and stuff.
Chrome reading mode also behaves the same rendering all four copies.
conartist6 | 13 hours ago
Looks like something to do with Typst and its "zebraw" package: https://github.com/hongjr03/typst-zebraw
conartist6 | 13 hours ago
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
pervognsen | 9 hours ago
No. Briefly skimming that file (I spent a few minutes trying to chase definitions across repos before I gave up), it looks like a conventional recursive-descent pull parser, where pulling is implemented via generators. You could also be using the generators for backtracking but I don't see any evidence of that in this file. Both ideas, i.e. using generators in a recursive-descent parser for backtracking and pulling, are standard; neither of them have anything to do with Pratt parsing except insofar as they're all examples of recursive-descent parsing.
Since generator frames are heap allocated in JavaScript VMs, generators are also an easy way to avoid fixed-depth stack overflows in recursive-descent parsing for adversarial inputs like "((((...." where the recursion depth is linear in the size of the input. It comes at a high price in efficiency and memory usage; goroutine-style stacks are a much more efficient VM implementation technique for supporting pulling and unbounded recursion.
conartist6 | 8 hours ago
It's actually a push parser though! The thread of control is held by the grammar not the core. Wherever you see
eatMatchparsing can backtrack, but otherwise it's LR. It uses a special shift instruction to handle infix grammars.