Pratt Parsers: Expression Parsing Made Easy

This page summarizes the projects mentioned and recommended in the original post on news.ycombinator.com

InfluxDB - Power Real-Time Data Analytics at Scale
Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.
www.influxdata.com
featured
SaaSHub - Software Alternatives and Reviews
SaaSHub helps you find the best software and product alternatives
www.saashub.com
featured
  • npeg

    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

  • InfluxDB

    Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.

    InfluxDB logo
  • WebBS

    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

  • expr

    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

    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

    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

    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#...

NOTE: The number of mentions on this list indicates mentions on common posts plus user suggested alternatives. Hence, a higher number means a more popular project.

Suggest a related project

Related posts

  • Using Nom - a parser combinator library

    3 projects | dev.to | 27 Aug 2021
  • Rust is the second most used language for Advent of Code, after Python

    1 project | /r/rust | 31 Dec 2020
  • Lelwel: A resilient LL(1) parser generator for Rust

    1 project | news.ycombinator.com | 12 Jul 2024
  • Trip C++Now 2024 – think-cell

    4 projects | news.ycombinator.com | 10 May 2024
  • nom > regex

    10 projects | /r/rust | 6 Dec 2023

Did you konow that Rust is
the 5th most popular programming language
based on number of metions?