Parsing Math with Pratt Parsing
A few weeks ago I decided to start a challenge to build a Lox interpreter in order to learn C++. In the process, I learned about a technique for parsing called Pratt Parsing, one that is not very mainstream and thus not very well taught or documented. In this post, I'll try to teach you the basics of parsing using Pratt and by the end of it we should be able to parse and interpret relatively complicated math expressions.
I'll assume you know a thing or two about C++, but the code here is simple enough that someone coming from Java or C# could also read it. If you are from C++: some correctness and ceremonies were sacrificed for the sake of education.
This post is also a little beginner-friendly, so if you already understand what a lexer and ASTs are, you might feel like it's a little too slow. If not, have fun reading.
Understanding the pipeline
First of all, let's have an overview of what we'll be doing. Parsing is the process of transforming raw text into a representational state that can either be interpreted or compiled. In our case, we'll transform (parse) raw text into an Abstract Syntax Tree that can be interpreted by a piece of code. The pipeline looks like this:
raw text -> lexer -> parser -> Abstract Syntax Tree -> interpreter -> output
Raw text will be our math expressions, like "-5 * 10 + (25 / 5)". Then, we'll have a Lexer; a Lexer is a piece of code that transforms raw text into chunks of data, often referred to as Tokens. In our case, the tokens would be:
- (unary minus)
5 (number 5)
* (multiplication)
10 (number 10)
+ (plus)
( (opening parenthesis)
25 (number 25)
/ (division)
5 (number 5)
) (closing parenthesis)
Then, we'll feed all those tokens into a parser that will transform them into an Abstract Syntax Tree, which we'll refer to as "AST" from now on for brevity. Our AST would look like this:
(+)
/ \
/ \
(*) (/)
/ \ / \
(-) 10 25 5
|
5From here, we'll (hopefully) have already learned Pratt's technique, but we'll keep going and have it interpreted just so we can view the output of our parser.
The Lexer
The Lexer is almost the simplest part of our project, second only to Pratt's algorithm main loop. Some people do not enjoy writing lexers by hand, but we'll write one anyway for the sake of education. Before we get into the lexer, let's first define Token, as it is the output of a lexer:
enum class TokenType {
NUMBER,
PLUS,
MINUS,
DIVISION,
MULTIPLICATION,
LEFT_PARENTHESIS,
RIGHT_PARENTHESIS,
END_OF_FILE
};
struct Token {
TokenType type;
std::string value;
};The more complex your project becomes the more complex these two become. For example, the Token could also have fields to save where it was seen - like which line and column; there could be more token types too, were we parsing a programming language we would probably have token types like "IF" and "WHILE" to represent those tokens.
Next, the lexer's interface:
struct Lexer {
Lexer(std::string_view string_view) : string_view(string_view) {}
Token NextToken();
private:
uint32_t pos = 0;
std::string_view string_view;
char Peek() const;
};
Notice how thin it is! Indeed, a lexer doesn't provide much more than "the next token" in the raw text it's provided with, but that is all we'll need. Now, to its implementation:
char Lexer::Peek() const {
if (pos >= string_view.size()) return '\0';
return string_view[pos];
}
Token Lexer::NextToken() {
while (pos < string_view.size() &&
std::isspace(static_cast<unsigned char>(Peek())))) {
++pos;
}
if (pos >= string_view.size())
return Token(TokenType::END_OF_FILE, "");
const char c = Peek();
if (std::isdigit(static_cast<unsigned char>(c))) {
std::string val;
while (std::isdigit(static_cast<unsigned char>(Peek())) || Peek() == '.') {
val += Peek();
++pos;
}
return Token(TokenType::NUMBER, val);
}
++pos;
switch (c) {
case '+':
return Token(TokenType::PLUS, "+");
case '-':
return Token(TokenType::MINUS, "-");
case '*':
return Token(TokenType::MULTIPLICATION, "*");
case '/':
return Token(TokenType::DIVISION, "/");
case '(':
return Token(TokenType::LEFT_PARENTHESIS, "(");
case ')':
return Token(TokenType::RIGHT_PARENTHESIS, ")");
default:
throw std::runtime_error("Unexpected character");
}
}The lexer looks at the current character and if it's a whitespace it skips it until it finds a valid character. After finding a valid character, it returns a token representing it. If it finds a digit, it builds a string of the number it found.
Notice how it doesn't try to create numbers or interpret them, like turning "-5" into a double with the value "-5", instead it will return two separate tokens: "-" and "5"; that is because the lexer is supposed to just return tokens, not interpret them - that is the parser's responsibility. The lexer is as dummy as it gets.
Another important point is that the tokens a lexer returns or supports depends on what we're parsing. As I've said before, if we were parsing a programming language we would have to detect and return keywords like "if" or "while". Furthermore, some languages consider white space to be part of their syntax. In the Excel formula "A1:B10 C5:D15" the whitespace character is actually the intersection operator - ignoring it would give out completely incorrect results.
The AST
Let's jump over the parser and understand the AST first. With this, we will understand both the input (tokens from the lexer) and the output (an AST) of the parser before we dive into it.
The AST is the representation of raw text in a meaningful way that we can interpret. It may change form depending on how the raw text is structured. For example, if we had the expression "1 + 2 * 3", the AST would look like this:
(+)
/ \
/ \
1 (*)
/ \
2 3But if we had "(1 + 2) * 3", the AST would look like this:
(*)
/ \
/ \
(+) 3
/ \
1 2 The AST is composed of nodes (like the "+" or the "3"). We'll use structs to represent the nodes we want to interpret, but you could also use std::variant or, if you're in a functional language, sum types. A base struct AstNode will serve as a base for all types of nodes:
struct AstNode {
virtual ~AstNode() = default;
virtual double Evaluate() = 0;
};All children nodes need to know their value or how to get to their value, so we need an Evaluate method to call when we want a value out of a node. Here, we say the return type of Evaluate is double because we'll mostly be dealing with numbers, but in a full-blown interpreter we would have a more complex type to represent all possible values in that language, like strings or even functions. Let's take a look at SumNode:
struct SumNode : AstNode {
SumNode(std::unique_ptr<AstNode> left, std::unique_ptr<AstNode> right)
: left(std::move(left)), right(std::move(right)) {}
double Evaluate() override {
return left->Evaluate() + right->Evaluate();
}
std::unique_ptr<AstNode> left;
std::unique_ptr<AstNode> right;
};SumNode holds pointers to a left and right child nodes. When its Evaluate method is called, it returns the sum of the evaluation of those two nodes. The way the other operations (*, / and -) work are the same, so I'll leave it to you to implement them.
Next, let's look at NumberNode:
struct NumberNode : AstNode {
NumberNode(const std::string &value) : value(std::stod(value)) {}
double Evaluate() override { return value; }
double value;
};NumberNode is for nodes that are themselves numbers. We simply call std::stod (string-to-double) on a std::string and save it to NumberNode::value, then return value when Evaluate is called. There's one last node we need to see before we dive into parsing, UnaryMinus:
struct UnaryMinus : AstNode {
UnaryMinus(std::unique_ptr<AstNode> right) : right(std::move(right)) {}
double Evaluate() override {
return -right->Evaluate();
}
std::unique_ptr<AstNode> right;
};We've said before that the lexer doesn't try to turn the string "-5" into the double value "-5", instead it returns "-" followed by "5". Notice how the UnaryMinus node doesn't hold a double value either, instead it holds another node pointer - this is because we're not guaranteed that the node to it's right is a value (like 5) or another node expression, like in "-(2 * 3)".
NUDs and LEDs
Now that we have everything setup around parsing, let's talk Pratt Parsing.
Pratt Parsing is all about asking yourself when you find a token: does this token expect something to its left? If a token expects something to its left, then it should have a LED associated with it; if it doesn't expect something to its left, then it should have a NUD associated with it.
LED and NUD are both functions that parse a token depending on its context, they stand for Left Denotation and Null Denotation. An easy way to remember this that I've found is to think of what the functions need to parse a token: a LED needs a left, a NUD needs a null or, in other words, nothing. A LED expects a left token, a NUD expects nothing.
Let's practice this a little before diving into code: in the expression "1 * 2 + 3", which of these tokens need to have LEDs and NUDs to be semantically correct?
- 1 -> doesn't need to know what's to its left, so it has a NUD
- * -> it needs a left in order to multiply left and right, so it has a LED
- 2 -> doesn't need to know what's to its left either, so it has a NUD
- + -> it needs a left in order to add left and right, so it has a LED
- 3 -> no left needed either, so it has a NUD
Notice how I used the term "semantically correct": all the base operations are binary, so to be semantically correct they all need something to both their left and to their right. After all, you can't multiply 2 by nothing! There is one special case, though: the Minus ("-") token - it needs both a NUD and a LED. When we encounter Minus in an expression like "1 - 2" we need to call its LED, since to be semantically correct here it needs a left; when we have an expression like "-2 * 3" though, we need to call its NUD, because we are parsing a unary minus instead of a subtraction.
Let's see the code for TokenType::Minus' NUD and LED:
constexpr auto sub_rbp = GetLedBindingPower(TokenType::MINUS).rbp;
constexpr auto unary_minus_rbp = GetNudRightBindingPower(TokenType::MINUS);
std::unique_ptr<AstNode> MinusNudParseFn(Parser &parser, Token & /*token*/) {
auto right = parser.ParseExpression(unary_minus_rbp);
return std::make_unique<UnaryMinus>(std::move(right));
}
std::unique_ptr<AstNode> MinusLedParseFn(Parser & parser, Token & /*token*/,
std::unique_ptr<AstNode> left) {
auto right = parser.ParseExpression(sub_rbp);
return std::make_unique<MinusNode>(std::move(left), std::move(right));
}Both functions receive a reference to the parser so they can ask what's to their right through the ParseExpression function, but only the LED function receives a left Node pointer. sub_rbp and unary_minus_rbp are values for Binding Powers, a topic we will discuss in a moment in the post. For now, just know that it's used to handle associativity in the parser's main loop.
Both functions also receive a Token, which won't be useful for them in this short example, but is useful for the number parse NUD:
std::unique_ptr<AstNode> NumberNudParseFn(Parser & /*parser*/, Token &token) {
return std::make_unique<NumberNode>(token.value);
}The grouping (or parenthesis) parser NUD is special on its own because it doesn't return a node of itself, instead it just returns a node it asked the parser to parse. This enables us to treat anything inside parenthesis as essentially a new expression:
constexpr auto left_parenthesis_rbp =
GetNudRightBindingPower(TokenType::LEFT_PARENTHESIS);
std::unique_ptr<AstNode> GroupingNudParseFn(Parser &parser, Token &token) {
auto right = parser.ParseExpression(left_parenthesis_rbp);
// Eat the closing parenthesis
parser.Advance();
return right;
}It's called when we find an opening parenthesis ("("), it then asks the parser to parse whatever is to its right and returns it, but before leaving it "eats" the closing parenthesis.
The reason we're passing in function arguments that some functions need and others don't is just so we can have a unified interface for our parser. The parser will need to be calling NUDs and LEDs for each token it finds, without worrying if they need the values or not. Speaking of which, let's define the interface for the parser:
struct Parser;
using Led = std::function<std::unique_ptr<interpreter::AstNode>(
Parser &, lexer::Token &, std::unique_ptr<interpreter::AstNode>)>;
using Nud = std::function<std::unique_ptr<interpreter::AstNode>(
Parser &, lexer::Token &)>;
struct Parser {
Parser(lexer::Lexer &lexer) : lexer(lexer) {
current = lexer.NextToken();
InitializeParseFns();
}
std::unique_ptr<interpreter::AstNode> ParseExpression(
int32_t caller_binding_power);
lexer::Token Advance();
private:
lexer::Token current;
lexer::Lexer &lexer;
std::unordered_map<lexer::TokenType, Led> led_parse_fns;
std::unordered_map<lexer::TokenType, Nud> nud_parse_fns;
void InitializeParseFns();
};We define two type aliases Led and Nud, then we say that our parser has a constructor that takes a lexer (which it will call to get tokens) and initializes it internally.
Advance returns the current token and advances the lexer to the next one; since at the constructor we already ask the lexer for NextToken, the first time Advance is called it will return this first token and advance to the next one. Here's its implementation:
Token Parser::Advance() {
auto token = current;
current = lexer.NextToken();
return token;
}InitializeParseFns is just a straightforward initialization of the NUD and LED functions we've already created based on the TokenTypes associated with them:
void Parser::InitializeParseFns() {
nud_parse_fns[TokenType::NUMBER] = NumberNudParseFn;
nud_parse_fns[TokenType::LEFT_PARENTHESIS] = GroupingNudParseFn;
// TokenType::MINUS has both a NUD and a LED function associated with it
nud_parse_fns[TokenType::MINUS] = MinusNudParseFn;
led_parse_fns[TokenType::MINUS] = MinusLedParseFn;
led_parse_fns[TokenType::PLUS] = PlusLedParseFn;
led_parse_fns[TokenType::MULTIPLICATION] = MultiplicationLedParseFn;
led_parse_fns[TokenType::DIVISION] = DivisionLedParseFn;
}Easy. Now, there's one last thing we need to provide to our parser before we get into the main loop: binding powers.
Binding Powers
Binding powers are the way Pratt Parsing handles associativity of operators. Each token should have a left and right binding power, which we often just call lbp and rbp in Pratt parsers. We give higher binding powers to the operators with higher precedence to ensure they grab their operands more tightly. For example, the "*" operator has higher precedence than the "+" operator, so that when we see "1 + 2 * 3" we really want the "2" to bind to "*" and not to "+"; that is, we want our expression to be "1 + (2 * 3)" instead of "(1 + 2) * 3".
You can think of this as a gravitational pull - the higher the number, the more an operator pulls operands to itself. Here are the binding powers for our math tokens:
struct BindingPower {
int32_t lbp;
int32_t rbp;
};
constexpr int32_t GetNudRightBindingPower(lexer::TokenType type) {
switch (type) {
case lexer::TokenType::LEFT_PARENTHESIS:
return 0;
case lexer::TokenType::MINUS:
return 30;
default:
return -1;
}
}
constexpr BindingPower GetLedBindingPower(lexer::TokenType type) {
switch (type) {
case lexer::TokenType::MINUS:
case lexer::TokenType::PLUS:
return {10}, 10};
case lexer::TokenType::MULTIPLICATION:
case lexer::TokenType::DIVISION:
return {20}, 20};
default:
return {-1, -1};
}
}Here, we have defined the binding powers for our tokens when they're in LED and NUD position. Since NUDs don't expect anything to their left, we will only need a right binding power, thus why GetNudRightBindingPower only returns an integer and not a BindingPower instance.
The Pratt main loop
We're finally here, the Pratt main loop! Here it is:
std::unique_ptr<AstNode> Parser::ParseExpression(int32_t caller_binding_power) {
// Get the current token and advance the lexer
auto token = Advance();
// Check if it has a NUD
if (!nud_parse_fns.contains(token.type)) {
throw std::runtime_error("Expected expression");
}
// Parse the first token using the NUD function associated with it
auto nud_fn = nud_parse_fns.at(token.type);
auto expr = nud_fn(*this, token);
// Peek at the upcoming token's binding power before looping
auto [lbp, rbp] = GetLedBindingPower(current.type);
// Continue consuming tokens as long as the upcoming operator's left binding
// power exceeds the binding power of the context that called us
while (caller_binding_power < lbp) {
// Get the current token, advance the lexer and get the token's LED function
token = Advance();
auto led_fn = led_parse_fns.at(token.type);
// Call the LED passing in the current token and the left operand
// The lexer is now pointing at the token to the right of the operator
expr = led_fn(*this, token, std::move(expr));
// We gave a non-const Parser reference to led_fn, we expect it to have kept
// parsing until it reached another token with lower binding power, so we
// need to refresh lbp with the current token's binding power
lbp = GetLedBindingPower(current.type).lbp;
}
return expr;
}...but what... is that? That is the heart of Pratt's algorithm, that is the main loop that does all the magic and ties everything together.
Notice two things: first, it's a recursive function. It will mostly keep going right and getting called back by the parsing functions (NUDs and LEDs) until a condition is met, at which point it will break and unwind back. The condition for breaking is finding a token with a lower lbp than the one that called it. Secondly, it's actually pretty simple if you consider that token consumption is strictly linear; there is no backtracking - it just keeps moving right and parsing everything in one go.
This tiny little function (bloated by my comments) is so powerful that you will see the same logic in every language that implements Pratt Parsing. You don't need to modify it to explore its power: if we wanted to add new syntax to our language we wouldn't even touch it - we would just add new token types, give them a NUD or LED function (or both) and declare its binding powers.
Do we want to support exponents? We create a new EXPONENT token type, declare its binding powers and associate a new LED function to it - since it needs to know what's to its left. Want "pi" to be a constant so we can say "3 * pi"? Same thing - create a new token type, declare its binding power and associate a NUD to it (since pi doesn't care about what's to its left). The main loop remains untouched - you don't ever need to come back here if you want to extend your language.
Now, then, let's try to reason about the function with the expression "1 + 2 * 3 - (4)". I recommend you to have the function somewhere visible on your screen or on a second monitor so you can look at it. This is the final AST the function will give us:
(-)
/ \
(+) (4)
/ \
(1) (*)
/ \
(2) (3)Every time we call Parser::ParseExpression for the first time we will pass in "0" as caller_binding_power. Now, let's follow the lexer:
1 + 2 * 3 - (4)
^
As we enter the function for the first time, we'll grab the first token - "1". We will then look up its NUD function and call it so that this token can be parsed by that function. Every time we call the parser for the first time we expect to encounter a token with a NUD - we don't expect to receive something like "* 2". The token "1" NUD is ParseNumberNudFn, since its type is TokenType::NUMBER and we registered that function for this TokenType; it will return a NumberNode, which we will assign to "expr". After that, we get the binding powers for the next token - that is, "+". Since the lbp (left binding power) for "+" is 10 and caller_binding_power is 0, we enter the while loop.
1 + 2 * 3 - (4) (1)
^
Now, we grab the "+" token through Advance(), moving the lexer forward. We get the LED for "+" and call it, passing in our "expr" - the "1" NumberNode we got. "expr" is now owned by the "+" AstNode, which at the end of the function will assign it to be its "left", but before that it will call Parser::ParseExpression with its own rbp (right binding power) of 10 and assign the result to its "right", but it has to wait for the function call to return a node - we're back at the ParseExpression! Remember, every token has a left and right binding power that we defined at the Binding Powers section. Let's continue:
1 + 2 * 3 - (4) (+) (2)
^ / \
(1) [waiting]
Back at the beginning of Parser::ParseExpression, we grab the first token - but this time it's "2". It has a NUD too, we call it and assign the result to "expr" - this is a different "expr", the first one is still owned by "+", which is waiting for us to finish parsing what's to its right. We get the binding powers for the next token, "*"; the lbp of "*" is 20, which is higher than the caller_binding_power passed in by "+" of 10, so we enter the while loop.
1 + 2 * 3 - (4) (+) (*)
^ / \ / \
(1) [waiting] (2) [waiting]
We grab the token for "*", obtain its LED and pass in the current "expr" ("2"). This demonstrates "2" binding more strongly to "*" than to "+", "2" is now owned by "*" as its "left". The first thing "*"'s LED does is call Parser::ParseExpression again but with its own rbp of 20 and assign the result of that to its "right" in the same fashion of "+". We're back at Parser::ParseExpression.
1 + 2 * 3 - (4) (+) (*) (3)
^ / \ / \
(1) [waiting] (2) [waiting]
We grab the first token, which is now "3", call its NUD and assign the result to "expr". We get the binding powers of the next token but wait: "-"'s lbp is 10, same as "+"'s! This means we will not enter the while loop, since caller_binding_power is "*"'s 20, instead we will just return "expr" right away. "*" gets back "3" and assigns it to its "right". We now have a MultiplicationNode with "2" to its left and "3" to its right.
1 + 2 * 3 - (4) (+) (*)
^ / \ / \
(1) [waiting] (2) (3)
The call that resulted in the MultiplicationNode was started by "+" when it called Parser::ParseExpression (and the lexer was pointing at "2"), so we give this MultiplicationNode back to "+" so it can become its "right". We're finally back at the very first iteration of Parser::ParseExpression and the SumNode we built became our "expr"; now we need to update lbp. When we do that, we look at the next token's type and find out it is "-", with a lbp of 10; since the caller_binding_power of the first iteration was 0, we loop again.
1 + 2 * 3 - (4) (+)
^ / \
(1) (*)
/ \
(2) (3)
We advance the lexer, get the LED for "-" and call it passing in "expr" (which is now the SumNode we just built) to be its "left". The LED calls Parser::ParseExpression again, passing in its own rbp of 10.
1 + 2 * 3 - (4) (-) (grouping NUD)
^ / \ \
(+) [waiting] [waiting]
/ \
(1) (*)
/ \
(2) (3)
Back at the beginning of Parser::ParseExpression, we grab "(", obtain its NUD and call it. "("'s NUD doesn't return a value immediately - instead it calls Parser::ParseExpression again with its own rbp of 0.
"("'s rbp is low because it functions as a new expression - right after "(" we will have an expression from the very beginning.
1 + 2 * 3 - (4) (-) (grouping NUD)
^ / \ \
(+) [waiting] (4)
/ \
(1) (*)
/ \
(2) (3)
We're right back at the beginning of Parser::ParseExpression due to "("'s call, we grab and call "4"'s NUD and assign the result to this iteration's "expr". We get the next token's lbp, which is -1 (")"), so we don't enter the loop and just return the NumberNode with "4" back to "(". "("'s NUD "eats" the closing ")" parenthesis before leaving by calling Parser::Advance() and returns the NumberNode.
1 + 2 * 3 - (4) (-) <-- resulting tree
^ / \
EOF ____| (+) (4)
/ \
(1) (*)
/ \
(2) (3)
We're back again at the first iteration, with an "expr" that is a SubtractionNode with a SumNode as its left and a NumberNode as its right. We update lbp again, which gets updated to -1 since the next token's type is END_OF_FILE. Since lbp is now less than our original caller_binding_power of 0, we exit the while loop and return "expr" - our SubtractionNode.
That's it?
That's it. Notice that we never really care about looking back to tokens that came before, we just keep going forward; when we "go back" it's actually just the call stack unwinding, but the lexer is always moving forward.
And what's best? It's not just for math. You can parse production-grade programming languages with this, complete with function calls, access operators, identifiers and even macros. Take a look at some of the links at the end of this post: some of them are direct links to implementations of Pratt Parsing for programming languages; see if you can spot the similarity of implementation in other languages and environments.
And in case you're wondering, everything is already tied together. This is how the main function would look like:
int main() {
std::string_view expr = "10 + 2 * 3 - 4 / 2";
Lexer lexer{expr};
Parser parser{lexer};
const auto ast_tree = parser.ParseExpression(0);
assert(ast_tree->Evaluate() == 14);
return 0;
}The "interpreter" part was actually just the definitions of our Evaluate methods in each node. Of course, a programming language interpreter would look way more complicated than this.
Citations
[1] Code for this post on GitHub
[2] Vaughan R. Pratt's original paper from 1973 - "Top Down Operator Precedence"
[3] Douglas Crockford - Syntaxation (2013 talk, starts talking about parsing at around 19:00)
[4] Douglas Crockford - Top Down Operator Precedence (JavaScript implementation)
[5] asiobg - "a simple coroutined language to generate state machines for ASIO’s asynchronous agents"