Can confirm; yes it was helpful! I've never thought seriously about parsing and I've read occasionally (casually) about Pratt parsing, but this is the first time it seemed like an intuitive idea I'll remember.
(Then I confused myself by following some references and remembering the term "precedence climbing" and reading e.g. https://www.engr.mun.ca/~theo/Misc/pratt_parsing.htm by the person who coined that term, but nevermind — the original post here has still given me an idea I think I'll remember.)
There's also the "shunting yard" algorithm, which is basically the iterative version of these algorithms (instead of recursive). It is usually presented with insufficient error checking, so it allows invalid input, but there's actually no reason you have to do it like that.
Not to step on anyone's toes, I just don't feel that formal grammar theory is that important in practice. :^)
It was probably decent when all you had was something like Pascal and you wanted to write a C compiler.
Parsing and compiling and interpreting etc are all much more at home in functional languages. Much easier to understand there. And once you do, then you can translate back into imperative.
For parsing: by default you should be using parser combinators.
Need to parse * before +? Begin at add, have it call parse_mul for its left and right sides, and so on.
parse_mul() {
left = parse_literal()
while(is_mul_token()) { // left associative
right = parse_literal()
make_mul_node(left, right)
}
}
parse_add() {
left = parse_mul()
while(is_add_token()) { // left associative
right = parse_mul()
make_add_node(left, right)
}
}
exactly this ! a thousand times this !
Out of curiosity, what do you mean by this? Do you mean you like the prose, or the typesetting, or...?
The symbols "·" and "|" don't mean anything - I've chosen them to be visually intuitive: The "|" is supposed to look like a physical divider. Also, bracketed expressions "(...)" or "{...}" should be parsed first.
Wikipedia mentions that a variant of this got used in FORTRAN I. You could also speed up my naive O(n^2) approach by using Cartesian trees, which you can build using something suspiciously resembling precedence climbing.
As far as I can tell, parser combinators are just one way that promises to let "write a compiler without understanding abstract languages" but all these methods actually wind-up being libraries that are far complicated than gp's "recursive descent + pratt parsing", which is easy once you understand the idea of an abstract language.
parse_left_to_right(with(), is_token()) {
left = with()
while(is_token()) {
right = with()
left = operate(left, right, operator)
}
ret left;
}
p0() { ret lex digit or ident; };
p1() { ret parse_left_right(p0, is_mul); };
p2() { ret parse_left_right(p1, is_add); };
The need for NFA/DFA/derivative models is mostly unnecessary because ultimately, REG is just DSPACE(O(1)). That's it. Thinking in any other way is confusing the map with the territory. Furthermore, REG is extremely robust, because we also have REG = DSPACE(o(log log n)) = NSPACE(o(log log n)) = 1-DSPACE(o(log n)). For help with the notation, see here: https://en.wikipedia.org/wiki/DSPACE
The style is very good and fun to read for someone who also reads other more boring papers.
Well, it depends how formal you're talking about. I have to say that the standard you mention, recursive descent parsing + Pratt for expressions. actually requires you to understand what a formal language is - that it's a "thing" that can't (or shouldn't) be an object or a data structure but exists abstractly before any objects created by the program.
Moreover, the standard way of producing a recursive descend parser is to begin with your language in Chomsky normal form or some human understandable format and then convert to Greibach Normal form and that specification converts readily to your series of recursive functions. So all language transforms are useful to know (though you can skip steps if you have a good intuition of your language).
In the end, all the hard work in a compiler is in the back-end optimization phases. Put your mental energy there.
Consider if you had functions called parse_user_ops_precedence_1, parse_user_ops_precedence_2, etc. These would simply take a table of user-defined operators as an argument (or reference some shared/global state), and participate in the same recursive callstack as all your other parsing functions.
Btw, I mentioned parser combinators: those are basically just a front-end. Similar to regular expressions. The implementation can be all kinds of things, eg could be recursive descent or a table or backtracking or whatever. (Even finite automata, if your combinators are suitably restricted.)
It does make me wonder though about why grammars have to be so complicated that such high-powered tools are needed. Isn't the gist of LR/LALR that the states of an automaton that can parse CFGs can be serialised to strings, and the set of those strings forms a regular language? Once you have that, many desirable "infinitary" properties of a parsing automaton can be automatically checked in finite time. LR and LALR fall out of this, in some way.
2026-03-26
You already know that a + b * c + d is calculated as a + (b * c) + d. But how do you encode that knowledge precisely enough for a machine to act on it?
The most common solution employed by compilers is to make use of a tree known as an abstract syntax tree. In an AST, each operator sits above its operands, and evaluation works bottom-up: resolve the children, then apply the operation.
+
/ \
+ d
/ \
a *
/ \
b c
This tree encodes the desired ordering (a + (b * c)) + d in a format that is very convenient to work with programmatically.
But of course, people (for the most part) don’t write programs as trees. This means we face the problem of deriving this structure from flat text.
This is known as parsing. It has been the focus of decades of computer science research. It has also, in many cases, been wildly overcomplicated.
The difficulty in parsing lies with mixed precedence. To be precise, cases where precedence changes direction. Let’s imagine our users only ever wrote programs of either increasing or decreasing precedence. What would that mean for our tree representation?
In the case of decreasing precedence, we repeatedly evaluate the leftmost operator as it is higher precedence - multiplication before addition, addition before comparison, and so on. The first operator sits deepest in the tree, the last the shallowest. The resulting tree is left-leaning.
Decreasing
<
/ \
+ d
/ \
* c
/ \
a b
You can imagine what happens when precedence is increasing. It’s the exact opposite: the leftmost operator is now the shallowest and the rightmost the deepest, as each operator depends on the result to its right. The tree is right-leaning.
Increasing
>
/ \
a +
/ \
b *
/ \
c d
Now, what is the most reasonable encoding of equal precedence?
It depends on the operation. Convention favours a left-to-right evaluation for arithmetic, known as left associativity. Some language features favour the opposite: assignment in C, for instance, is right associative.
Let’s suppose (for now) that all operators are left associative. This is represented by a left-leaning tree, as the leftmost operator must be evaluated earlier and therefore rests deeper in the tree.
We should refine our definitions accordingly. Given a sequence of operators, let x_i be the precedence of the ith operator:
x_i >= x_{i+1}. This now includes the case of equal precedence.x_i < x_{i+1}.This means any two equal-precedence operators are encoded exactly like two decreasing ones.
A natural continuation is to consider expressions with exactly one change in direction. We’ll focus on the more interesting of the two resulting cases: a transition from increasing to decreasing precedence. The reverse simply continues a right-leaning tree from the tip of the existing left-leaning.
Consider the expression I = (a > b + c * d), given by the tree below.
>
/ \
a +
/ \
b *
/ \
c d
The tree is right-leaning, as expected for increasing precedence. Now, suppose we extend I with a new operator whose precedence is equal to or less than *. This would mean the increasing property no longer holds, and so continuing a right-leaning tree would produce an incorrect encoding.
We need a left-leaning tree somewhere, but where? The visualisation of each possible precedence level for the new operator begins to reveal a pattern:
[I] * e:
>
/ \
a +
/ \
b *
/ \
* e
/ \
c d
[I] + e:
>
/ \
a +
/ \
+ e
/ \
b *
/ \
c d
[I] == e:
==
/ \
> e
/ \
a +
/ \
b *
/ \
c d
The left-leaning tree starts at the first place it can: at an operator of equal or lesser precedence. This lower precedence operator must evaluate later than at least the current one, but there could be several prior operators that also must evaluate first. Those operators are found along the spine of the right-leaning tree.
The
==case is the clearest example. All previous operators are higher precedence than==, so the entire spine of the tree must evaluate first, and therefore must be its left child.
The observation is as follows: when we encounter a transition operator, we must walk back up the spine, collecting every operator that evaluates first. That collected chain - a right-leaning subtree - becomes the left child of the new operator, which starts a left-leaning tree of its own.
Since any expression is just a sequence of these transitions, this is all we need. This walk-back procedure is Pratt parsing.
We can hopefully make things a little more concrete with some pseudocode, extending the right-leaning case to handle a transition as we did earlier.
A right-leaning tree can be built by recursing onto ourselves and then building the tree bottom up.
def parse():
left = leaf()
if peek() is not None:
op = advance()
right = parse()
return Node(op, left, right)
return left
parse() first defers to leaf() to handle a literal such as a, consuming it from the token stream before checking the next token with peek(). The next token (an operator for a valid program) is consumed by advance() which moves the parser to the next token. parse() finally calls itself for the right-hand side.
The parser advances through the tokens as it recurses, and constructs the tree as it returns. For our earlier tree [I]:
-- Down: advance
(1) parse(0)
a [>] b + c * d
(2) parse(prec(>))
a > b [+] c * d
(3) parse(prec(+))
a > b + c [*] d
(4) parse(prec(*))
a > b + c * d [None]
-- Up: build
(4) d
(3) [*]
/ \
c d
(2) [+]
/ \
b *
/ \
c d
(1) [>]
/ \
a +
/ \
b *
/ \
c d
The use of recursion is how we will backtrack to find a continuation point.
Until then, our parser produces incorrect trees for decreasing precedence. To prevent parsing tokens we shouldn’t, we can forward the current precedence to the recursive child call:
def parse(prev_prec=0):
left = leaf()
if peek() is not None and prec(peek()) > prev_prec:
op = advance()
right = parse(prec(op))
return Node(op, left, right)
return left
This works, but we can simplify by giving end-of-file its own token with the lowest precedence - peek() would cause the condition to fail naturally, letting us drop the null check:
def parse(prev_prec=0):
left = leaf()
if prec(peek()) > prev_prec:
op = advance()
right = parse(prec(op))
return Node(op, left, right)
return left
As parse() recurses, it pushes a frame onto the call stack with the left child and minimum precedence. The call stack, representing the yet-to-be-built spine, is always of increasing precedence.
This means that when unwinding, we visit each level in decreasing order. So, the first level where peek() can bind is also the correct level: every level above is strictly lower in precedence, and we already know it can’t go deeper because parse() wouldn’t have returned. The greedy choice is the only correct choice.
But if is only capable of taking that greedy choice once - we need to take it every time, because anything else is incorrect. So, we replace if with while:
def parse(prev_prec=0):
left = leaf()
while prec(peek()) > prev_prec:
op = advance()
right = parse(prec(op))
left = Node(op, left, right)
return left
This is the complete Pratt parser. The while loop is the walkback procedure we described earlier: when a transition operator appears, parse() returns up the call stack until it finds the right level, then the loop consumes it and continues with the left-leaning subtree.
Here’s the trace [I] * e, where I = a > b + c * d:
-- Down: advance
(1) a [>] b + c * d * e
(2) a > b [+] c * d * e
(3) a > b + c [*] d * e
(4) a > b + c * d [*] e FAIL
-- Up: build
(4) d
(3) iteration 1:
[*]
/ \
c d
iteration 2:
[*]
/ \
* e
/ \
c d
(2) [+]
/ \
b *
/ \
* e
/ \
c d
(1) [>]
/ \
a +
/ \
b *
/ \
* e
/ \
c d
The left-leaning subtree (c * d) * e is built entirely within frame 3’s while loop.
In practice every operator has two types of precedence: left and right. Pratt refers to this as left and right binding power, or LBP and RBP. All of our operators so far have an equal LBP and RBP.
An operator’s LBP determines how strongly it attracts the expression to its left - this is what peek() checks in the while condition. Its RBP determines how strongly it attracts the expression to its right - this is what gets passed as prev_prec to the recursive call.
For left-associative operators, LBP and RBP are equal. When two * operators meet, the second *’s LBP is not greater than the first *’s RBP, so parse() does not recurse but instead loops at the same level to build left.
We want the opposite for right-associative operators. a = b = c should parse as a = (b = c). The second = should be consumed by the recursive call, not by the loop. We can achieve this by setting RBP lower than LBP - the recursive child’s precedence threshold is low enough that a consecutive operator still passes the > check and gets consumed deeper.
def parse(prev_prec=0):
left = leaf()
while lbp(peek()) > prev_prec:
op = advance()
right = parse(rbp(op))
left = Node(op, left, right)
return left
To ensure this, we set rbp = lbp for left-associative operators, and rbp = lbp - 1 for right-associative.
I’ve often found Pratt parsing to be presented as if it were a clever trick. Well, it is, but with a very simple geometric intuition: trees are either left-leaning or right-leaning depending on precedence. When precedence drops, walk back up the spine until you find where the new operator belongs.
I’ve read many articles on the same topic but never found it presented this way - hopefully N + 1 is of help to someone.