Build a Pratt Parser (Top-Down Operator Precedence)

Topic Overview

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.

Your Task

Write a Pratt parser (top-down operator precedence): instead of one function per precedence level, a single parse_expr(min_bp) loop driven by a table of binding powers. Print each parsed expression as an S-expression.

Input

One expression per line; blank lines are ignored. Tokens: numbers, identifiers ([A-Za-z_][A-Za-z0-9_]*), + - * / ^ ( ) [ ] ,. Spaces and tabs are ignored.

Binding powers

The core loop: parse a prefix expression, then while the next token's left binding power is greater than min_bp, consume it and parse its right operand with min_bp = lbp for left-associative operators and lbp - 1 for ^. Call arguments and index expressions are parsed with min_bp = 0. Consequences worth checking: -2^2 is (neg (^ 2 2)), but -a*b is (* (neg a) b).

Output

• leaves print as themselves; (OP LEFT RIGHT) for + - * / ^; (neg X) for prefix minus
• calls: (call CALLEE ARG1 ARG2 ...): the callee may itself be any expression, e.g. f(1)(2) is (call (call f 1) 2)
• indexing: (index TARGET INDEX)

On error print only the first one, error at column C: MESSAGE (C is where the offending token starts; line length + 1 at the end):

• unexpected character 'X': a character that starts no token
• expected expression: no valid prefix token where an operand is needed
• expected ')' / expected ']': an unclosed group, call or index
• unexpected token 'TEXT': tokens left over after a complete expression

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. One parse_expr(int min_bp) function containing the prefix step and the infix loop, plus a binding-power lookup (lbp(token)): no separate function per precedence level.
2. Build a tree, print it, free it.

Hidden tests cover left vs right associativity, unary minus against every operator, calls with zero and several arguments, chained calls and indexes, and each error.