Why Pratt Parsing Finally Clicked
I started this project for a very practical reason: I wanted to write a C expression parser with a long runway. First, a calculator. Later, maybe a real compiler if I didn’t lose my patience or accidentally invent a new dialect of nonsense along the way.
That goal changed the way I looked at expression parsing. I’d already built a calculator with the shunting yard algorithm, so I had a working baseline and a healthy respect for how much can be done with a stack and a bit of discipline. But once I began thinking about growth, the cracks in that approach became harder to ignore. A calculator is one thing. A parser that needs to live inside a compiler is another.
Pratt parsing kept turning up in compiler-development material as the cleaner answer, but it was never part of the usual classroom path I’d seen. In ordinary computer science courses, you’re much more likely to meet LR parsing, or a straightforward recursive descent parser, than Pratt’s method. That makes sense. Courses have limited time, and Pratt parsing tends to get filed away as “nice to know” rather than “will probably save you time later.” It took me a while to understand why.
The thing that makes Pratt parsing click is not the syntax. It’s realizing that precedence can live inside the parser’s control flow instead of outside it.
What finally helped was reading two kinds of material side by side. One was compiler-development writing, the sort that explains expression parsing from the ground up instead of assuming you already speak fluent grammar. The other was Pratt’s original paper, which is short in a way that almost feels rude at first, but gets to the point with unusual confidence. Put together, they gave me a mental model that stuck.
The appeal wasn’t that Pratt parsing does something magical. It’s that it makes expression handling feel less like a pile of special cases and more like a system you can extend without grimacing every time you add a new operator. That matters if the parser is just the first piece of a larger compiler, where every awkward decision tends to come back later with interest.
So this article is partly for anyone else who has looked at Pratt parsing and thought, “I’m sure this is clever, but why does it keep showing up in parser discussions?” It’s also for me, frankly. The goal is to write down the model while it’s still fresh, before it slips back into the fog and I have to relearn it the hard way again.
Shunting Yard: The Familiar Starting Point
Before Pratt parsing shows up and starts tidying the room, shunting yard is the baseline worth understanding. It’s the old reliable method for expression parsing: simple, a little fussy, and very good at one job. You feed it an infix expression like 2 + 3 * 4, and it quietly turns that into a postfix sequence that a later evaluator can read without worrying about parentheses or precedence.
At the center of the algorithm are two structures. One is an output stream, which holds the numbers and, later, the operators in the order they should be applied. The other is an operator stack, which temporarily parks symbols like +, -, *, and / until the parser knows what to do with them. Numbers don’t need much discussion. They go straight to the output as soon as they appear. Operators, though, have opinions. Some need to wait.
Numbers leave immediately. Operators wait their turn. That’s the whole trick.
The reason they wait is binding power, which is just a plain way of saying how tightly an operator wants to stick to the numbers around it. Multiplication and division bind tighter than addition and subtraction. In 2 + 3 * 4, the * should attach itself to 3 and 4 before the + gets involved. If the parser treated every operator the same, the expression would come out wrong, and arithmetic would start looking a bit too democratic for its own good.
Shunting yard handles that with a small rule set. When a number arrives, it goes directly to the output stream. When an operator arrives, the parser looks at the operator sitting on top of the stack. If the new operator has lower precedence, or equal precedence in the usual left-associative case, the parser pops the older operator off the stack and sends it to output first. Then it compares again, working downward until the stack is empty or it finds an operator that should stay put. Only then does it push the new operator onto the stack.
That last part matters more than it sounds. The “equal precedence” rule is what makes the basic version behave as though operators are left-associative. So if you parse 8 - 3 - 2, the first minus gets popped before the second one goes on top, which means the expression is read as (8 - 3) - 2, not 8 - (3 - 2). Same idea with division. The parser isn’t making a philosophical statement about subtraction. It’s just following the stack rules.
A tiny mixed example makes the whole thing easier to see. Take 2 + 3 * 4. The parser reads 2 and emits it. Then it sees + and pushes it on the operator stack. Next comes 3, so that goes straight to output too. When * arrives, it compares itself with the + already on the stack. Since multiplication binds tighter than addition, + stays where it is and * gets pushed above it. Then 4 goes to output. At the end of the input, there are still operators sitting on the stack, so the parser flushes them in order. The result is postfix: 2 3 4 * +.
That final flush is easy to miss, but it’s doing a lot of work. The stack empties only after the input ends, which is why shunting yard is often described as a postfix conversion machine. It doesn’t evaluate the expression itself. It rearranges the tokens so another step can evaluate them without needing a pile of precedence rules. Pretty neat, honestly. A little bureaucratic, but neat.
If you want to compare the classic idea with the later operator-precedence approach that builds on similar logic, the original Top Down Operator Precedence paper is still the historical anchor, and this concise Pratt parsing walkthrough gives a modern sketch of where the method goes next. The overlap is the point. Once you see how shunting yard uses a stack to manage precedence, Pratt parsing starts to look less like magic and more like a different way of doing the same accounting.
Where the Stack Starts to Fray
The shunting yard algorithm is tidy when the grammar stays close to arithmetic homework. Feed it numbers, a few binary operators, and maybe a pair of parentheses, and it behaves like a polite clerk. The trouble starts when an expression parser has to deal with the sort of syntax a real language uses every day.
A parser can look elegant right up until the grammar asks it to remember one more special case.
Parentheses are the first place the neatness slips. In the textbook version, an opening parenthesis gets pushed onto the operator stack and a closing one tells the parser to pop operators until that matching delimiter appears. That works, but only because the parser is now carrying a hidden rule just for grouping. It is no longer treating every token with the same small set of behaviors. It has to know that ( means “store this marker and wait,” while ) means “unwind everything until you find the marker, then throw the marker away.” That is manageable, but it already feels like a patch on top of the core operator precedence logic.
Unary operators make the situation less pleasant. A minus sign can mean subtraction, or it can mean negation. Those are different operations with different arity, different precedence, and different places where they are allowed to appear. The shunting yard algorithm has to inspect context to decide whether - is binary or unary, which means the parser must remember what came before. Was the previous token an operator, a left parenthesis, the start of the input, or a completed expression? Each answer changes how the next token is handled. Once that rule is in place, another one usually follows. A plus sign might be unary too. A language might add a prefix increment operator. Suddenly the tidy operator table has branches on branches.
Right-associative operators add another wrinkle. Exponentiation is the usual example. In 2 ^ 3 ^ 2, most languages read the expression as 2 ^ (3 ^ 2), not (2 ^ 3) ^ 2. The basic shunting yard algorithm was built around popping operators of higher or equal precedence, which works well for left-associative operators like addition and multiplication. For right-associative operators, that simple rule has to bend. Now the parser has to ask whether the operator on the stack should stay put or come off based on associativity, not just precedence. That is still possible, of course, but the rule set gets longer and less obvious with every new operator family.
Function calls complicate things in a different way. A function like max(1, 2, 3) is not just one expression wrapped in parentheses. It may contain a variable number of arguments, each of which can itself be a full expression. The parser must count commas, track when an argument ends, and know when the closing parenthesis belongs to the call rather than to some nested group inside one of the arguments. The control flow starts to look crowded. A small calculator can live with that. A language parser usually can’t.
That is the real limitation here. The shunting yard algorithm has no natural recursive notion of subexpressions. Everything has to be simulated through the stack, so nested structure is represented indirectly instead of directly. A grouped expression, a unary prefix operator, a function call, and a binary operator all end up sharing the same machinery, with extra flags and special cases sprinkled on top. The clean version that handles 2 + 3 * 4 feels compact because it only has to solve one narrow problem. Once you want parentheses, prefix operators, right-associative operators, and variadic calls in the same parser, the method starts to look less like a model and more like a set of exceptions that happen to work.
That is why the next step usually points toward a different shape of parser altogether, one where nested expressions are handled as nested calls instead of as tricks with a stack. The older expression-parsing literature spends a lot of time on exactly this kind of tension, and the recursive alternative gets a cleaner treatment in top-down operator precedence notes and in an older paper on expression parsing. The math hasn’t changed. The way you organize the control flow has.
How Pratt Parsing Replaces the Stack
Once you stop thinking of operator precedence as a pile of symbols waiting their turn, Pratt parsing starts to look much less mysterious. The trick is that the parser does not keep a separate operator stack at all. Instead, it calls itself again when it reaches an operator that needs a right-hand expression. That recursive call handles the next chunk of input, and the call stack quietly does the bookkeeping that shunting yard used to do by hand.
That shift sounds small, but it changes the feel of the whole parser. In shunting yard, an incoming operator gets compared with the thing already sitting on top of the stack. In Pratt parsing, the current call keeps reading tokens until it meets an operator with a lower left binding power than the one it is currently allowed to consume. At that point, it stops, returns to its caller, and lets the outer expression pick up the rest. The behavior is the same in spirit. Higher-precedence work gets handled first. The difference is where the memory lives.
Pratt parsing replaces the explicit operator stack with a simple rule: keep going until the next operator no longer belongs to this expression.
That stopping rule is where left binding power earns its keep. A token’s left binding power tells the parser how strongly it wants to bind to what came before it. If the next operator’s left binding power is lower than the current context allows, the parser returns. If it is high enough, the parser stays in the current call and keeps building the expression. You can think of that return as the recursive version of “pop the stack until the precedence order makes sense again.” The same precedence logic is still there. It just shows up as a series of returns rather than a series of stack pops.
That is also why Pratt parsing feels cleaner than a classic recursive descent parser for expressions. Traditional recursive descent often walks through precedence levels one by one. You get one function for addition and subtraction, another for multiplication and division, maybe another for comparisons, and so on. It works, but the code can end up looking like a small bureaucratic office, with each function stamped to handle only one narrow slice of the grammar. Pratt parsing skips that parade of levels. One loop, plus a couple of token-specific handlers, can deal with the whole expression.
The structure usually breaks into two halves. The first half is prefix handling, sometimes called nud parsing in Pratt jargon. This runs when the parser sees the first token of an expression, or any token that begins a subexpression. A number returns itself. A prefix operator like unary minus consumes the token that follows it and builds a prefix expression node. A left parenthesis, in more complete parsers, starts a grouped expression. In all of those cases, the parser is dealing with a token that appears at the front of an expression.
The second half handles infix and postfix behavior after that first token has already been consumed. Once the parser has a left-hand expression in hand, it asks whether the next token can continue it. If the answer is yes, it keeps going. If the next token is an infix operator, the parser recurses to read the right-hand side with the proper binding power. If the token is postfix, the parser attaches it directly to the expression it already has. Same machinery, different point of entry.
That split matters because it explains why Pratt parsing handles awkward cases without extra ceremony. Prefix minus and binary minus can share a token if their handlers differ. A postfix operator does not need a separate parsing phase. It just slots into the infix/postfix side after the left expression exists. The parser does not need to march through every precedence layer before it reaches the operator that actually matters.
If you want the original form, Pratt’s 1973 paper is still there, and it reads like a compact blueprint rather than a modern tutorial: Pratt’s 1973 paper on top-down operator precedence. For a more hands-on walkthrough, this Pratt parsing introduction lays out the same ideas in a more approachable form.
Once you see it this way, Pratt parsing stops looking like a separate species of parser and starts looking like a neater expression of the same precedence rules you already know. The stack is still doing the work. It just lives in the call stack now, where recursion gets to do the heavy lifting and the code gets to look less like a juggling act.
From Theory to a Parser You Can Maintain
Once the recursion model makes sense, Pratt parsing stops feeling clever for its own sake and starts looking practical. The nice part is that each token type gets a small, local job. A number can return itself. A prefix operator can read what follows and build a unary node. An infix operator can grab a left-hand expression, decide how tightly it binds, then ask for the right-hand side. Those little entry points are usually called nud and led. The names sound like something a compiler engineer made up over coffee, which is only half a joke, but they map cleanly to what the parser actually does.
A Pratt parser stays small because each token knows only the rules it needs.
Parentheses fit that model without much drama. When the parser sees an opening parenthesis, it can recurse into a grouped expression, keep reading until it reaches the matching closing parenthesis, and then return the inner result as one unit. No special stack choreography. No separate case that has to rummage around for a delimiter while hoping nobody misplaced a token. The grouping rule lives right next to the token that introduces it, which makes the code easier to read six months later when you’ve forgotten half your own cleverness.
That same structure is what makes new operators less painful to add. Instead of rewriting the whole parser every time the grammar grows a new quirk, you give the operator a binding power and the routine it needs. A prefix operator gets a nud. An infix operator gets a led. A postfix operator gets its own little handler. The parser doesn’t need to know ahead of time whether the language will use the operator for one thing or two things. It just calls the right function at the right time.
A more realistic expression parser might support unary plus and minus alongside a postfix factorial operator. So -3! can mean the negation of 3!, while +4 stays legal even if it doesn’t do much beyond confirming the parser isn’t confused. That mix sounds fiddly when described in a grammar table, but in Pratt form it usually comes down to a few focused routines and some binding-power checks. The code grows in the same places the language grows, which is a far nicer relationship than the usual “one new feature, three new hacks” arrangement.
In the end, that’s the real appeal. The parser stays compact even as the expression language picks up more behavior. Parentheses, unary operators, binary operators, postfix operators. They all slot into the same mechanism without forcing a tangle of special cases. If you’re heading toward compiler work, that kind of structure matters more than looking elegant on paper. It’s the difference between a parser you can keep extending and one you start avoiding because every edit feels like poking a sleeping cat.
