I will never forget the amusing attention I got from the professor when this topic was covered during my undergrad. It's only happened once, sadly, but this is only seconded by the time I was assisting a junior engineer with a related problem and was able to say "Oh, that's just a Pratt Parser. Let me show you."
Intuiting Pratt Parsing
31–40 of 51 posts
Re: Intuiting Pratt Parsing
#32"I’ve read many articles on the same topic but never found it presented this way" it reminds me a lot of a description I saw in a video with Jonathan Blow talking about precedence and parsing with Casey Muratori.
The video is 3 hours long though, and I'm not sure the text he shows is available.
At this point he's talking about left leaning vs right leaning trees, after having already talked about one of them: https://youtu.be/fIPO4G42wYE?t=2256&si=aanthLGe-q8ntZez
Re: Intuiting Pratt Parsing
#33Love Pratt parsing! Not a compiler guy, but I've spent way too many hours reflecting on parsing. I remember trying to get though the dragon book so many times and reading all about formal grammar etc. Until I landed on; recursive descent parsing + Pratt for expressions. Super simple technique, and for me is sufficient. I'm sure it doesn't cover all cases, but just for toy languages it feels like we can usually do eve…
I am a compiler guy, and I completely agree. Parsing is not that hard and not that important. Recursive descent + pratt expressions is almost always the practical choice.
Re: Intuiting Pratt Parsing
#34Love Pratt parsing! Not a compiler guy, but I've spent way too many hours reflecting on parsing. I remember trying to get though the dragon book so many times and reading all about formal grammar etc. Until I landed on; recursive descent parsing + Pratt for expressions. Super simple technique, and for me is sufficient. I'm sure it doesn't cover all cases, but just for toy languages it feels like we can usually do eve…
It's not for toy languages. Most big compilers use recursive descent parsing.
Language design benefits from parser generators that can point out ambiguities and verify a language is easy to parse.
Re: Intuiting Pratt Parsing
#35Love Pratt parsing! Not a compiler guy, but I've spent way too many hours reflecting on parsing. I remember trying to get though the dragon book so many times and reading all about formal grammar etc. Until I landed on; recursive descent parsing + Pratt for expressions. Super simple technique, and for me is sufficient. I'm sure it doesn't cover all cases, but just for toy languages it feels like we can usually do eve…
Quick other one: To parse infix expressions, every time you see "x·y | (z | w)", find the operator of least binding power: In my example, I've given "|" less binding power than "·". Anyway, this visually breaks the expression into two halves: "x·y" and "(z | w)". Recursively parse those two subexpressions. Essentially, that's it. The symbols "·" and "|" don't mean anything - I've chosen them to be visually intuitive:…
An even easier approach is to give all infix operators the same precedence and force the programmer to group subexpressions.
Re: Intuiting Pratt Parsing
#36The latest implementation of Picol has a Tcl-alike [expr] implemented in 40 lines of code that uses Pratt-style parsing: https://github.com/antirez/picol/blob/main/picol.c#L490
Love Picol, and love this! When I first revisited Tcl, I was a bit miffed about needing [expr] but now really appreciate both it and the normal Tcl syntax.
Re: Intuiting Pratt Parsing
#37Also discussed in detail in Crafting Interpreters.[0]
Re: Intuiting Pratt Parsing
#38I can recommend anyone reading pratts original paper. Its written in a very cool and badass style. https://dl.acm.org/doi/epdf/10.1145/512927.512931
> Its written in a very cool and badass style. Out of curiosity, what do you mean by this? Do you mean you like the prose, or the typesetting, or...?
He is a bit offensive towards traditional academia that favors BNF and parser generators. It's been a while since a read it but I remember e.g. a rhetoric question (not exactly cited but by meaning): "Has anyone learned a programming language by reading the BNF?"
The style is very good and fun to read for someone who also reads other more boring papers.
Re: Intuiting Pratt Parsing
#39Love Pratt parsing! Not a compiler guy, but I've spent way too many hours reflecting on parsing. I remember trying to get though the dragon book so many times and reading all about formal grammar etc. Until I landed on; recursive descent parsing + Pratt for expressions. Super simple technique, and for me is sufficient. I'm sure it doesn't cover all cases, but just for toy languages it feels like we can usually do eve…
The Dragon book is not very good, to be honest. It was probably decent when all you had was something like Pascal and you wanted to write a C compiler. Parsing and compiling and interpreting etc are all much more at home in functional languages. Much easier to understand there. And once you do, then you can translate back into imperative. For parsing: by default you should be using parser combinators.
The Dragon book wasn't good for me either but I'd disagree about using parser combinators. The problem that I'd see the Dragon book having is basically starting to use concepts (phases of compilation) before it introduces and motivates them in the abstract. I can see how people who already know these concepts can look at the Dragon book and say "oh, that's a good treatment of this" so perhaps it's good reference but it's problematic for a class and terrible to pick up and try to read as a stand alone (which I did back in Berkeley in the 80s).
As far as I can tell, parser combinators are just one way that promises to let "write a compiler without understanding abstract languages" but all these methods actually wind-up being libraries that are far complicated than gp's "recursive descent + pratt parsing", which is easy once you understand the idea of an abstract language.
Re: Intuiting Pratt Parsing
#40Earlier quoted context omitted.
It's not for toy languages. Most big compilers use recursive descent parsing.
Language design benefits from parser generators that can point out ambiguities and verify a language is easy to parse.
It does not follow that a generated parser would make sense in production code.