Build a Pratt Parser (Top-Down Operator Precedence)

Pratt Parsing for Expressions

Vaughan Pratt's top-down operator precedence parsing handles infix, prefix, and postfix operators with uniform binding-power logic. JavaScript engines, Rust's old parser, and many embedded DSL compilers use Pratt because it avoids left-recursion rewriting and handles mixed precedence cleanly.

Binding Power

Each token has left and right binding power. Parse a prefix expression, then while the next token's left power exceeds the current minimum, consume it as infix and parse the right side with appropriate right power.

cCopy
Loading…

• Prefix: numbers, identifiers, unary -, ( expr )
• Infix: +, *, ==, function-call ()
• Higher binding power binds tighter: * before +
• One loop replaces mutual recursion between expression levels

Connecting to real compilers

Production compilers embed this step inside a longer pipeline. GCC flows through cpp, cc1, assembly, and ld; Clang uses the driver, Sema, LLVM IR passes, and a target backend. LLVM bitcode, JVM bytecode, and WASM are other familiar IRs at the same layer. The exercise isolates one pass so you can test it alone before chaining it to the next stage.

Why for this exercise

You will build a Pratt parser for expressions with correct operator precedence. This exercise requires assigning binding powers to tokens and implementing the parse loop that produces binary and unary AST nodes.