You can either use the stack in an intuitive way, or you can change the tree directly in a somewhat less intuitive way without recursion. Essentially either DF or BF. I don’t see how it matters much anymore with stacks that grow automatically, but it’s good to understand.
Intuiting Pratt Parsing
11–20 of 51 posts
Re: Intuiting Pratt Parsing
#12> I’ve read many articles on the same topic but never found it presented this way - hopefully N + 1 is of help to someone.
Can confirm; yes it was helpful! I've never thought seriously about parsing and I've read occasionally (casually) about Pratt parsing, but this is the first time it seemed like an intuitive idea I'll remember.
(Then I confused myself by following some references and remembering the term "precedence climbing" and reading e.g. https://www.engr.mun.ca/~theo/Misc/pratt_parsing.htm by the person who coined that term, but nevermind — the original post here has still given me an idea I think I'll remember.)
Re: Intuiting Pratt Parsing
#13Love 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.
Re: Intuiting Pratt Parsing
#14Also if you're looking into this area you'll find there is another algorithm called "Precedence climbing", which is really the same thing with some insignificant differences in how precedence is encoded.
There's also the "shunting yard" algorithm, which is basically the iterative version of these algorithms (instead of recursive). It is usually presented with insufficient error checking, so it allows invalid input, but there's actually no reason you have to do it like that.
Re: Intuiting Pratt Parsing
#15I 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
For some reason I struggled to get my head around Pratt parsing. Then I read an offhand comment on Reddit that said to start with a recursive descent parser and add table parsing to that. Once I did that it all clicked.
Re: Intuiting Pratt Parsing
#16I 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...?
Re: Intuiting Pratt Parsing
#17The 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
Re: Intuiting Pratt Parsing
#18Love 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.
Is there a production compiler out there that doesn't use recursive descent, preferably constructed from combinators? Table-driven parsers seem now to be a "tell" of an old compiler or a hobby project.
Re: Intuiting Pratt Parsing
#19Earlier quoted context omitted.
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.
Is there a production compiler out there that doesn't use recursive descent, preferably constructed from combinators? Table-driven parsers seem now to be a "tell" of an old compiler or a hobby project.
Some people appreciate that an LR/LALR parser generator can prove non-ambiguity and linear time parse-ability of a grammar. A couple of examples are the creator of the Oil shell, and one of the guys responsible for Rust.
It does make me wonder though about why grammars have to be so complicated that such high-powered tools are needed. Isn't the gist of LR/LALR that the states of an automaton that can parse CFGs can be serialised to strings, and the set of those strings forms a regular language? Once you have that, many desirable "infinitary" properties of a parsing automaton can be automatically checked in finite time. LR and LALR fall out of this, in some way.
Re: Intuiting Pratt Parsing
#20Earlier quoted context omitted.
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.
Is there a production compiler out there that doesn't use recursive descent, preferably constructed from combinators? Table-driven parsers seem now to be a "tell" of an old compiler or a hobby project.
Oh, I was talking much more about how you can first learn how to write a compiler. I wasn't talking about how you write a production industry-strength compiler.
Btw, I mentioned parser combinators: those are basically just a front-end. Similar to regular expressions. The implementation can be all kinds of things, eg could be recursive descent or a table or backtracking or whatever. (Even finite automata, if your combinators are suitably restricted.)