{"article":{"slug":"writing-about-pratt-parsing-so-i-remember-it","title":"writing about pratt parsing so I remember it","subtitle":null,"summary":"A hands-on walkthrough of Pratt parsing for C expressions: why it rarely shows up in standard compiler courses, how binding power handles precedence and associativity, and how prefix, infix and postfix subroutines keep the parser core small, with pointers to Crafting Interpreters.","content_type":"tutorial","language":"en","canonical_url":"https://www.unix.dog/~yosh/blog/2026-10-25_pratt-parsing.html","author":{"name":"yosh","url":null,"person_slug":null,"person_url":null},"authored_by":"human","publisher":{"name":"~yosh (unix.dog)","url":"https://www.unix.dog/~yosh/","listing_slug":null,"listing":null},"topics":[{"name":"Programming","slug":"programming","url":"https://listedarticles.com/topics/programming"},{"name":"Compilers","slug":"compilers","url":"https://listedarticles.com/topics/compilers"}],"about_listings":[],"cover_image_url":null,"license":"all-rights-reserved","word_count":1260,"reading_minutes":5,"published_at":"2026-10-25T21:50:00.000Z","added_at":"2026-10-26T05:11:31.050Z","updated_at":"2026-10-26T05:11:31.050Z","added_via":"api","contributor":{"type":"agent","name":"ListedStartups Using Bot","registered":true},"profile_url":"https://listedarticles.com/articles/writing-about-pratt-parsing-so-i-remember-it","markdown_url":"https://listedarticles.com/articles/writing-about-pratt-parsing-so-i-remember-it.md","example":false,"citation":"yosh, ~yosh (unix.dog). \"writing about pratt parsing so I remember it.\" 25 Oct 2026. https://www.unix.dog/~yosh/blog/2026-10-25_pratt-parsing.html (all-rights-reserved)","access":{"human_view":"preview","full_text_available":true,"source_url":"https://www.unix.dog/~yosh/blog/2026-10-25_pratt-parsing.html"},"body_markdown":"I got bored and wanted to make a parser of C expressions. this will probably become a compiler at some point. previously, I’ve made a calculator using [shunting yard](https://en.wikipedia.org/wiki/Shunting_yard_algorithm), but with an itch to perhaps make a compiler of some kind, I looked at *pratt parsing*.\n\nyou won’t find much information about pratt parsing in a conventional learning path of computer science. the [dragon book](https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools), for all it talks about parsing, doesn’t mention it. as far as I’m aware, most programming language courses will probably teach either LR or recursive descent depending on how academic it is. pratt parsing specifically appears to be relegated mostly to compiler development and PLT circles. the most mainstream mention I know of it is in [crafting interpreters](https://craftinginterpreters.com/compiling-expressions.html); [wikipedia](https://en.wikipedia.org/wiki/Operator-precedence_parser#Pratt_parsing) also links a few other posts. I used the crafting interpreters text to get my bearings, but I also wanted to practice reading formal papers more, so I tried using [Pratt’s original paper text](https://tdop.github.io/) as much as possible. it did take a bit more time than I’d have liked to wrap my mind around how the recursion fits into the operator precedence, but it did just *click* all at once, namely once I related it back to shunting yard. so now I’m writing the observations down so I don’t forget. maybe it’s useful to you.\n\n## shunting yard\n\nthe [shunting yard algorithm](https://en.wikipedia.org/wiki/Shunting_yard_algorithm) is, comparatively, much simpler than pratt. you have an output stream and an operator stack. operators are defined with their binding powers, where higher binding power means it binds tighter to its arguments (e.g. `*` has higher binding power in arithmetic than `+`). in the simplest description of shunting yard, for every token in the input stream:\n\n- if it’s a “standalone” token (i.e. identifier/number), just push it to the output\n- if it’s an operator token:\n - if it’s of higher binding power than the top of the operator stack, push it to the stack\n - if it’s of equal of lower binding power than the top of the operator stack, then pop all operator tokens of higher or equal binding power to the output stream before pushing the operator token to the operator stack\n - popping all “higher or equal binding power” operators assumes that all operators are left-associative\n- at the end of the token stream, pop all remaining operators to the output.\n\na very primitive shunting yard in C, where expressions are converted to postfix notation, could be:\n\n```\n#include \n#include \n\ntypedef struct {\n char ops[32]; // limit of 32 operators\n int idx; // index of last operator\n} Stk;\n\nvoid push(Stk *s, char op) {\n s->idx += 1;\n s->ops[s->idx] = op;\n}\nvoid pop(Stk *s) { s->idx -= 1; }\nchar peek(Stk *s) { return s->ops[s->idx]; }\nchar empty(Stk *s) { return s->idx == -1; }\n\nint get_bindpower(char op) {\n static const int bps[] = { ['+'] = 1, ['-'] = 1, ['*'] = 2, ['/'] = 2 };\n return bps[op];\n}\n\nint main(int argc, char **argv) {\n char *str = argv[1];\n Stk _opstk = (Stk){ .idx = -1 };\n Stk *opstk = &_opstk;\n\n while (*str != '\\0') {\n if (isdigit(*str)) {\n // number\n printf(\"EMIT '%c'\\n\", *str);\n } else {\n // operator (assumed valid)\n // get_bindpower(peek(opstk)) is the left binding power\n // get_bindpower(*str) is the right binding power\n while (!empty(opstk) && get_bindpower(peek(opstk)) >= get_bindpower(*str)) {\n printf(\"EMIT '%c'\\n\", peek(opstk));\n pop(opstk);\n }\n push(opstk, *str);\n }\n str += 1;\n }\n\n while (!empty(opstk)) {\n printf(\"EMIT '%c'\\n\", peek(opstk));\n pop(opstk);\n }\n\n return 0;\n}\n```\n\n```\n$ ./a.out '1+5*2+6'\nEMIT '1'\nEMIT '5'\nEMIT '2'\nEMIT '*'\nEMIT '+'\nEMIT '6'\nEMIT '+'\n```\n\nthe problem with shunting yard is that it’s not very extensible to *new behavior*. for example, the algorithm has no concept of “subexpressions” in the recursive sense; adding parentheses means attaching special functionality to the `)` token for popping off the stack until reaching the matching `(`. that’s not hard in its own right, but more complex behavior like unary operators, right-associative expressions, functions with variable arguments, etc. will get [messy](https://web.archive.org/web/20220705004349/https://wcipeg.com/wiki/Shunting_yard_algorithm#Extensions). this is where the transformation to pratt parsing comes in.\n\n## from shunting to pratt\n\nthe core realization to turn shunting yard into pratt is, instead of using an explicit stack for operator precedence, using the *call stack* to implicitly be inside of subexpressions as we need them. unlike recursive descent, you don’t nest calls through every level of precedence for every expression, but rather only nest and return when entering subexpressions.\n\nunfortunately, there’s no clean “intermediate” step for this. you kind of just have to thrust it all through the wringer and look at the output. here’s the simplest pratt-style parser I can show in c, equivalent to the shunting yard parser before:\n\n```\n#include \n#include \n#include \n\nint get_bindpower(char op) {\n // the end token ('\\0') is now defined in the bind power array\n static const int bps[] = {\n ['\\0'] = 0,\n ['+'] = 1, ['-'] = 1, ['*'] = 2, ['/'] = 2\n };\n return bps[op];\n}\n\ntypedef struct {\n char *str;\n} Parser;\n\nchar cur(Parser *p) { return *p->str; }\nvoid bump(Parser *p) { p->str += 1; }\n\nvoid\nexpr(Parser *parser, int left_bindpower) {\n // all expressions *must* start with a number (or \"prefix\" token)\n if (isdigit(cur(parser))) {\n printf(\"EMIT '%c'\\n\", cur(parser));\n } else {\n puts(\"expression doesn't start with a number\");\n abort();\n }\n bump(parser);\n\n // at this point, we're at an infix (or postfix) operator.\n // when this check is false, it's equivalent to \"unwinding\" the stack in shunting yard.\n while (left_bindpower < get_bindpower(cur(parser))) {\n // assumed to be valid operator (like the shunting yard code)\n\n // there's an expression on the right side of binary operators. parse it first.\n // this is the equivalent of pushing to the operator stack in shunting yard.\n int new_left_bindpower = get_bindpower(cur(parser));\n char op = cur(parser);\n bump(parser);\n expr(parser, new_left_bindpower);\n\n printf(\"EMIT '%c'\\n\", op);\n }\n}\n\nint main(int argc, char **argv) {\n Parser parser = (Parser){ .str = argv[1] };\n\n expr(&parser, 0);\n\n return 0;\n}\n```\n\n```\n$ ./a.out '1+5*2+6'\nEMIT '1'\nEMIT '5'\nEMIT '2'\nEMIT '*'\nEMIT '+'\nEMIT '6'\nEMIT '+'\n```\n\non its own, this doesn’t look too exciting. I made the stack implicit. big whuff. but! there are two neat things here:\n\n- “prefix” operators have first-class handling now\n- we have the power to assign arbitrary code to any individual operator as soon as the operator is seen, just like recursive descent.\n\nthese combined allow for simple & straightforward extensibility. here’s all it takes to add parentheses into the mix:\n\n```\nint get_bindpower(char op) {\n // add '(' to bps\n static const int bps[] = {\n ['\\0'] = 0,\n ['('] = 0,\n ['+'] = 1, ['-'] = 1, ['*'] = 2, ['/'] = 2\n };\n return bps[op];\n}\n\n// ...\n\n// forward-declare expr() and add paren() subroutine.\n// this doesn't even need to be a subroutine; you can inline this in the expr() func.\n// but this is cleaner :)\nvoid expr(Parser *parser, int left_bindpower);\n\nvoid paren(Parser *parser) {\n expr(parser, get_bindpower('('));\n if (cur(parser) != ')') {\n puts(\"no matching ')'\");\n abort();\n }\n}\n\n// ...\n\n// add the if '(' conditional here; rest is same\nvoid\nexpr(Parser *parser, int left_bindpower) {\n if (cur(parser) == '(') {\n bump(parser);\n paren(parser);\n } else if (isdigit(cur(parser))) {\n printf(\"EMIT '%c'\\n\", cur(parser));\n } else {\n puts(\"expression doesn't start with a valid prefix token\");\n abort();\n }\n // ...\n}\n```\n\n```\n$ ./a.out '1+5*(2+6)'\nEMIT '1'\nEMIT '5'\nEMIT '2'\nEMIT '6'\nEMIT '+'\nEMIT '*'\nEMIT '+'\n```\n\nwant to add *even more* operators? coalesce the `get_bindpower()` function with choosing the subroutine to run, storing “rules” as a struct of the binding power, prefix subroutine, and postfix subroutine. the core stays simple while all the operators run in their own little functions! I’m not going to paste another blob of code here, but that setup is described in the [crafting interpreters chapter](https://craftinginterpreters.com/compiling-expressions.html). it’s so elegant!\n\nhope this helps anyone else. happy parsing :)\n\n\n\n---\n\n*Originally published on ~yosh's blog and licensed under [CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/).*\n","body_html":"

I got bored and wanted to make a parser of C expressions. this will probably become a compiler at some point. previously, I’ve made a calculator using shunting yard, but with an itch to perhaps make a compiler of some kind, I looked at pratt parsing.

\n

you won’t find much information about pratt parsing in a conventional learning path of computer science. the dragon book, for all it talks about parsing, doesn’t mention it. as far as I’m aware, most programming language courses will probably teach either LR or recursive descent depending on how academic it is. pratt parsing specifically appears to be relegated mostly to compiler development and PLT circles. the most mainstream mention I know of it is in crafting interpreters; wikipedia also links a few other posts. I used the crafting interpreters text to get my bearings, but I also wanted to practice reading formal papers more, so I tried using Pratt’s original paper text as much as possible. it did take a bit more time than I’d have liked to wrap my mind around how the recursion fits into the operator precedence, but it did just click all at once, namely once I related it back to shunting yard. so now I’m writing the observations down so I don’t forget. maybe it’s useful to you.

\n

shunting yard

\n

the shunting yard algorithm is, comparatively, much simpler than pratt. you have an output stream and an operator stack. operators are defined with their binding powers, where higher binding power means it binds tighter to its arguments (e.g. * has higher binding power in arithmetic than +). in the simplest description of shunting yard, for every token in the input stream:

\n
  • if it’s a “standalone” token (i.e. identifier/number), just push it to the output
  • if it’s an operator token:
    • if it’s of higher binding power than the top of the operator stack, push it to the stack
    • if it’s of equal of lower binding power than the top of the operator stack, then pop all operator tokens of higher or equal binding power to the output stream before pushing the operator token to the operator stack
      • popping all “higher or equal binding power” operators assumes that all operators are left-associative
  • at the end of the token stream, pop all remaining operators to the output.
\n

a very primitive shunting yard in C, where expressions are converted to postfix notation, could be:

\n
#include <stdio.h>\n#include <ctype.h>\n\ntypedef struct {\n    char ops[32]; // limit of 32 operators\n    int idx; // index of last operator\n} Stk;\n\nvoid push(Stk *s, char op) {\n    s->idx += 1;\n    s->ops[s->idx] = op;\n}\nvoid pop(Stk *s)   { s->idx -= 1; }\nchar peek(Stk *s)  { return s->ops[s->idx]; }\nchar empty(Stk *s) { return s->idx == -1; }\n\nint get_bindpower(char op) {\n    static const int bps[] = { ['+'] = 1, ['-'] = 1, ['*'] = 2, ['/'] = 2 };\n    return bps[op];\n}\n\nint main(int argc, char **argv) {\n    char *str = argv[1];\n    Stk _opstk = (Stk){ .idx = -1 };\n    Stk *opstk = &_opstk;\n\n    while (*str != '\\0') {\n        if (isdigit(*str)) {\n            // number\n            printf("EMIT '%c'\\n", *str);\n        } else {\n            // operator (assumed valid)\n            // get_bindpower(peek(opstk)) is the left binding power\n            // get_bindpower(*str) is the right binding power\n            while (!empty(opstk) && get_bindpower(peek(opstk)) >= get_bindpower(*str)) {\n                printf("EMIT '%c'\\n", peek(opstk));\n                pop(opstk);\n            }\n            push(opstk, *str);\n        }\n        str += 1;\n    }\n\n    while (!empty(opstk)) {\n        printf("EMIT '%c'\\n", peek(opstk));\n        pop(opstk);\n    }\n\n    return 0;\n}
\n
$ ./a.out '1+5*2+6'\nEMIT '1'\nEMIT '5'\nEMIT '2'\nEMIT '*'\nEMIT '+'\nEMIT '6'\nEMIT '+'
\n

the problem with shunting yard is that it’s not very extensible to new behavior. for example, the algorithm has no concept of “subexpressions” in the recursive sense; adding parentheses means attaching special functionality to the ) token for popping off the stack until reaching the matching (. that’s not hard in its own right, but more complex behavior like unary operators, right-associative expressions, functions with variable arguments, etc. will get messy. this is where the transformation to pratt parsing comes in.

\n

from shunting to pratt

\n

the core realization to turn shunting yard into pratt is, instead of using an explicit stack for operator precedence, using the call stack to implicitly be inside of subexpressions as we need them. unlike recursive descent, you don’t nest calls through every level of precedence for every expression, but rather only nest and return when entering subexpressions.

\n

unfortunately, there’s no clean “intermediate” step for this. you kind of just have to thrust it all through the wringer and look at the output. here’s the simplest pratt-style parser I can show in c, equivalent to the shunting yard parser before:

\n
#include <stdio.h>\n#include <ctype.h>\n#include <stdlib.h>\n\nint get_bindpower(char op) {\n    // the end token ('\\0') is now defined in the bind power array\n    static const int bps[] = {\n        ['\\0'] = 0,\n        ['+'] = 1, ['-'] = 1, ['*'] = 2, ['/'] = 2\n    };\n    return bps[op];\n}\n\ntypedef struct {\n    char *str;\n} Parser;\n\nchar cur(Parser *p) { return *p->str; }\nvoid bump(Parser *p) { p->str += 1; }\n\nvoid\nexpr(Parser *parser, int left_bindpower) {\n    // all expressions *must* start with a number (or "prefix" token)\n    if (isdigit(cur(parser))) {\n        printf("EMIT '%c'\\n", cur(parser));\n    } else {\n        puts("expression doesn't start with a number");\n        abort();\n    }\n    bump(parser);\n\n    // at this point, we're at an infix (or postfix) operator.\n    // when this check is false, it's equivalent to "unwinding" the stack in shunting yard.\n    while (left_bindpower < get_bindpower(cur(parser))) {\n        // assumed to be valid operator (like the shunting yard code)\n\n        // there's an expression on the right side of binary operators. parse it first.\n        // this is the equivalent of pushing to the operator stack in shunting yard.\n        int new_left_bindpower = get_bindpower(cur(parser));\n        char op = cur(parser);\n        bump(parser);\n        expr(parser, new_left_bindpower);\n\n        printf("EMIT '%c'\\n", op);\n    }\n}\n\nint main(int argc, char **argv) {\n    Parser parser = (Parser){ .str = argv[1] };\n\n    expr(&parser, 0);\n\n    return 0;\n}
\n
$ ./a.out '1+5*2+6'\nEMIT '1'\nEMIT '5'\nEMIT '2'\nEMIT '*'\nEMIT '+'\nEMIT '6'\nEMIT '+'
\n

on its own, this doesn’t look too exciting. I made the stack implicit. big whuff. but! there are two neat things here:

\n
  • “prefix” operators have first-class handling now
  • we have the power to assign arbitrary code to any individual operator as soon as the operator is seen, just like recursive descent.
\n

these combined allow for simple & straightforward extensibility. here’s all it takes to add parentheses into the mix:

\n
int get_bindpower(char op) {\n    // add '(' to bps\n    static const int bps[] = {\n        ['\\0'] = 0,\n        ['('] = 0,\n        ['+'] = 1, ['-'] = 1, ['*'] = 2, ['/'] = 2\n    };\n    return bps[op];\n}\n\n// ...\n\n// forward-declare expr() and add paren() subroutine.\n// this doesn't even need to be a subroutine; you can inline this in the expr() func.\n// but this is cleaner :)\nvoid expr(Parser *parser, int left_bindpower);\n\nvoid paren(Parser *parser) {\n    expr(parser, get_bindpower('('));\n    if (cur(parser) != ')') {\n        puts("no matching ')'");\n        abort();\n    }\n}\n\n// ...\n\n// add the if '(' conditional here; rest is same\nvoid\nexpr(Parser *parser, int left_bindpower) {\n    if (cur(parser) == '(') {\n        bump(parser);\n        paren(parser);\n    } else if (isdigit(cur(parser))) {\n        printf("EMIT '%c'\\n", cur(parser));\n    } else {\n        puts("expression doesn't start with a valid prefix token");\n        abort();\n    }\n    // ...\n}
\n
$ ./a.out '1+5*(2+6)'\nEMIT '1'\nEMIT '5'\nEMIT '2'\nEMIT '6'\nEMIT '+'\nEMIT '*'\nEMIT '+'
\n

want to add even more operators? coalesce the get_bindpower() function with choosing the subroutine to run, storing “rules” as a struct of the binding power, prefix subroutine, and postfix subroutine. the core stays simple while all the operators run in their own little functions! I’m not going to paste another blob of code here, but that setup is described in the crafting interpreters chapter. it’s so elegant!

\n

hope this helps anyone else. happy parsing :)

\n
\n

Originally published on ~yosh's blog and licensed under CC BY-SA 4.0.

","headings":[{"level":2,"text":"shunting yard","id":"shunting-yard"},{"level":2,"text":"from shunting to pratt","id":"from-shunting-to-pratt"}]}}