How to Write a Pratt Parser | Writing a Custom Language Parser in Golang

This is the 3rd video in my series covering modern parsing techniques for language & compiler development. This is probably the most important video in the entire series, as this guides you through the required components for writing a pratt parser. I will guide you step by step with how to define proper AST nodes, setup the parser struct and implement the binding power lookup handlers. By the end of this video we will be able to parse binary expressions like Relational, Comparison, Multiplicative and Additive operations.

⭐⭐ GitHub Repo ⭐⭐

🔔 JOIN THE COMMUNITY 🔔
----------------------------------------

-- Social Links --

[TheSimpleEngineer]

Maybe it's getting too late, but if we look at L30 at 46:25, we continue to pass `bp` down the callstack. However, bp is never changing so if we begin parsing a subexpression with a binding power of 0, we curry 0 through in each iteration.

For this to work, wouldn't bp need to continue to change by passing in `bp_lu[p.currentTokenKind()]` instead to each recursive call of `led_fn` like:

`led_fn(p, left,

Evaluating the call stack with a more complex example like: 3 + 5 * 7 + 9 - 2 tells me the parser gets confused and sees:

3 + (
5 * (
7 + (
9 -
( 2 )
)
)
)

which would look like: 3 + (5 * (7 + (9-2))). Your example works, but I think it's maybe too simplified to expose the issue:

10 + ( 6 * (2)) unravels to be accidentally correct.

[thedevconnor]

Amazing job explaining everything! You have made it very straightforward and easy to understand, why better then reading papers

[vaelix-dev]

I'm new to Go but you've taught me so much in just 3 videos. Love this series. Keep it up.

[brajbabua]

Thank you SOO MUCH! i was writing my language in C++ but there was basically nothing for AST and parser in low-level languages but you came in clutch

[eug.bondarev]

Very helpful, thank you for your high quality content!

[kubikaugustyn]

12:48 Yes, show us how to handle parsing soft and hard errors! Pls pls pls

[sanjeetsingh]

This was a pretty straight-forward explanation to Pratt-Parsing. Great Work!! Could you also go through the grammar for the language and show how it ties up with the parsing algo?

[tmanley]

I'd absolutely like to see how errors are handled. I'm trying to learn in public by creating dsls, and this is very helpful. Once I get through this series I feel like I could be the hero of the day at any job I go to once I figure out this dsl stuff. If I could suggest a video, maybe do a kind of "lay of the land" video when it comes to different types of parsers. Almost like a mindmap to get a birds-eye view. Great video as always.

[TheSimpleEngineer]

Amazing explanation. One thing I've not been a fan of is the pedagogical lexicon used in the Pratt parsing original paper such as NUD and LED. Definitely less intuitive to me than something like infix and prefix, which for some reason is easier to reason about when rereading my parsing code.

Edit: After reading the Top Down Operator Precedence article, I don't mind it much anymore haha.

[devaughntimoll]

Ohh yeah this is better than the typescript one for sure! But I’m kinda struggling because I’m writing the compiler in python(it’s slow ik) I do have go installed but I’ve already made the lexer in python and I would have to learn go. Anyways great series as usual