Pratt Parsers: Expression Parsing Made Easy

• npeg

  2 320 5.1 Nim

  PEGs for Nim, another take

Ha, nice to see this on HN: this article was pretty helpful to me to understand the concept a few years back when extending my PEG parsing library [1] with a Pratt parser; this mitigates the problem of PEG parsers not allowing left recursion and allows for a much more concise notation of grammars with operator precedence. Thank you Bob:

1. https://github.com/zevv/npeg

• WebBS

  1 50 10.0 JavaScript

  A toy language that compiles to WebAssembly

A few years back I had to implement a new parser for a custom expression language to replace an old parser that didn’t giving very good errors and was hard to extend. I never did the traditional CS track so parsers were kind of mysterious black magic so naturally first thing I did was search HN.

I stumbled on an older parsing thread [1] with a link to a toy Prayt implementation [2] made by an HNer… and shamelessly ripped it off to write my own Pratt parser implementation.

Great success! Writing a Pratt parser by hand is a lot easier than I thought and like the comment says, adding type information was trivial.

[1] https://news.ycombinator.com/item?id=24480504

[2] https://github.com/mx-scissortail/WebBS

• WorkOS

  workos.com sponsored

  The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.

  

• expr

  1 5 6.1 Rust

  Simple integer expression parser (by Timmmm)

I had to write an expression parser recently and found the number of names for essentially the same algorithm very confusing. There's Pratt parsing, precedence climbing, and shunting yard. But really they're all the same algorithm.

Pratt parsing and precedence climbing are the same except one merges left/right associativity precedence into a single precedence table (which makes way more sense). Shunting yard is the same as the others except it's iterative instead of recursive, and it seems like common implementations omit some syntax checking (but there's no reason you have to omit it).

Here's what I ended up with:

https://github.com/Timmmm/expr

I had to write that because somewhat surprisingly I couldn't find an expression parser library that supports 64-bit integers and bools. Almost all of them only do floats. Also I needed it in C++ - that library was a prototype that I later translated into C++ (easier to write in Rust and then translate).

• pratt-parser-blog-code

  2 26 0.0 TypeScript

  The code to illustrate the pratt parser blog post for the desmos engineering blog.

  

Some time ago I went down a fascinating rabbit hole on Pratt parsers while writing a math expression evaluator. In addition to the OP and above-linked article, I found the following helpful.

- How Desmos Uses Pratt Parsers (2018) - TypeScript - https://engineering.desmos.com/articles/pratt-parser/ - Source: https://github.com/desmosinc/pratt-parser-blog-code

- Simple But Powerful Pratt Parsing (2020) - Rust - https://matklad.github.io/2020/04/13/simple-but-powerful-pra... - Source: https://github.com/matklad/minipratt

• minipratt

  2 175 10.0 Rust

Some time ago I went down a fascinating rabbit hole on Pratt parsers while writing a math expression evaluator. In addition to the OP and above-linked article, I found the following helpful.

- How Desmos Uses Pratt Parsers (2018) - TypeScript - https://engineering.desmos.com/articles/pratt-parser/ - Source: https://github.com/desmosinc/pratt-parser-blog-code

- Simple But Powerful Pratt Parsing (2020) - Rust - https://matklad.github.io/2020/04/13/simple-but-powerful-pra... - Source: https://github.com/matklad/minipratt

• fur

  2 0 8.8 C

I found this Rust tutorial[1] on Pratt parsers to be really easy to follow as well. I'm not a Rustacean but I didn't find not knowing Rust to be a barrier. I used that as a guide to write the parser for my experimental programming language Fur[2].

However, I'll caution anyone writing their own programming languages to read some wisdom from someone who has written a production-quality programming language[3]. Most programming language developers get bogged down in writing the parser and never even get into solving the real hard problems of language development, which are things like bytecode generation and garbage collection. The fact is, a naive recursive descent parser with some low lookahead number to handle left recursion will be performant and can be written in an afternoon for 99% of parsable languages. I'm not sure what it is about parsers that makes them susceptible to yak shaving, but it seems to be a trap a lot of people fall into (including myself!).

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

[2] https://github.com/kerkeslager/fur/blob/main/parser.c

[3] https://craftinginterpreters.com/compiling-expressions.html#...

Suggest a related project