Making a Pratt Parser Generator | Hacker News Reader

Making a Pratt Parser Generator

robertjacobson.dev

60 pointstodsacerdoti12 comments

My go to article for Pratt parsing:

http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-e...

Pratt-parsers is a very underrated style of parsing.

Years ago when I was at Mozilla we built PrattParser utils in JS: https://github.com/taskcluster/json-e/blob/386ae415d807eb066...

It probably had short comings, because it's been rewritten since (I haven't kept up).

But with a few rules and simple functions a pratt parser is rather intuitive, and easy to write and port to other languages.

I'd be very curious to see the next article :)

Thorsten Ball’s “Writing an Interpreter in Go” has a very in-depth walkthrough of building a Pratt parser. It’s a very good read/tutorial.

Maybe it’s just me but it seems there’s a lot of language design coming out recently. E.g. Bob Nystrom has “Crafting Interpreters.” It really like that language design and parsing gets more attention, which is great because it’s fascinating stuff.

My favourite article on Pratt parsing, it’s in Rust but easy to port to any language:

https://matklad.github.io/2020/04/13/simple-but-powerful-pra...

Matklad follows Norvell's excellent exposition in these two articles pretty closely:

http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm

http://www.engr.mun.ca/~theo/Misc/pratt_parsing.htm

Matklad's stuff is really great. I wish he had cited Norvell, though.

Hopefully Robert Jacobson sees this, but, the TFA uses the word "donation" when Pratt used "denotation." Just a couple small typos.

I have easily read more than a dozen articles over the years on this parsing strategy, including Pratt's original paper, and in every case I have read "donation." But you are 100% right! All of my sources actually use denotation. MY MIND IS FREAKING BLOWN.

I am going to go meditate on the subjectivity of my reality. If I am wrong about this, what else am I wrong about?

LOL. I don't think it's that serious. Maybe it's the Berenstain Bears Effect, Mandela Effect, Glitch in the Matrix, or ... a slight lack of your favorite morning pick me up. :D In any case, looking forward to reading the next article.

Personally, at some point, I'd like to write a Pratt Parser in C99. I'd like to explore the one sentiment you had that OOP has a negative effect on understanding Pratt Parsers.

Off-topic, but I just have to ask: does "TFA" mean what I think it means? (i.e. the same as in "RTFA") I have seen that acronym used more and more lately, and I always trip up when I read it in a rather polite sentence.

You read me correctly. I did intend the politer version of TFA of RTFA ("Read/The Fine Article"). IMO, Robert does a great job of setting up Pratt Parsing and his intent to write a Pratt Parser Generator. As such, it is a "Fine Article" adding to the compendium of Pratt Parsing & Operator Precedence Parsing.

I hear you though, there are many that (overly) use passive-aggressive and/or aggressive language in the form of acronyms like STFU, GTFO, RTFA, IDC, WTH, WTF etc. Not my intent. I sometimes use TFA as a reference to the linked article. I'll reconsider next time.

Can anyone recommend the best parser for human language? Detecting natural suffixes, etc.

Google "natural language processing."

Natural languages are highly ambiguous. Using a naive approach like Early's algorithm can lead to thousands of parse trees for a single sentence. Probabilistic grammar parsing algorithms attempt to discover the "most likely" parse tree with respect to a particular statistical model of the language grammar. As with parsing algorithms for formal languages, different algorithms make different trade-offs. "Best" only makes sense with respect to a particular metric: "Best" in what sense?

I personally don't know much about this area beyond what I just said.

Reply on news.ycombinator.com