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

Рет қаралды 2,266

2 ай бұрын

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 ⭐⭐
- github.com/tlaceby/parser-series
🔔 JOIN THE COMMUNITY 🔔
/ @tylerlaceby
----------------------------------------
-- Social Links --
Discord - / discord
GitHub - github.com/tlaceby/

Пікірлер: 10

@TheSimpleEngineer 2 ай бұрын

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, bp_lu[p.currentTokenKind()])`? 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 2 ай бұрын

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

@DoubleDotStudio 2 ай бұрын

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

@sanjeetsingh4743 2 ай бұрын

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?

@eug.bondarev 2 ай бұрын

Very helpful, thank you for your high quality content!

@TheSimpleEngineer 2 ай бұрын

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.

@tylerlaceby 2 ай бұрын

I get that. But postfix is handled the same as an infix expression. Hence NUD means null denotation and LED meaning left denotation. Simply something is expected to the left it’s LED if the token does not expect anything to left it’s NUD .

@TheSimpleEngineer 2 ай бұрын

@@tylerlaceby Fair point!

@tmanley1985 2 ай бұрын

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.

@tylerlaceby 2 ай бұрын

With errors it’s a good idea to keep a list of found errors so you can display them later. Then if something fails you can either go back to the parse_stmt() level or continue with a soft error. Then at the end you can just iterate over the errors and display them