Parsing Math with Pratt Parsing

WASHINGTON RAMOS' WEBSITE

LINKEDIN<br>GITHUB

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<br>learned about a technique for parsing called Pratt Parsing, one that is not very mainstream and thus not very well<br>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<br>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<br>C# could also read it. If you are from C++: some correctness and ceremonies were sacrificed for the sake of<br>education.

This post is also a little beginner-friendly, so if you already understand what a lexer and ASTs are, you might feel<br>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<br>representational state that can either be interpreted or compiled. In our case, we'll transform (parse) raw text<br>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<br>code that transforms raw text into chunks of data, often referred to as Tokens. In our case, the tokens would be:

- (unary minus)<br>5 (number 5)<br>* (multiplication)<br>10 (number 10)<br>+ (plus)<br>( (opening parenthesis)<br>25 (number 25)<br>/ (division)<br>5 (number 5)<br>) (closing parenthesis)

Then, we'll feed all those tokens into a parser that will transform them into an Abstract Syntax Tree, which we'll<br>refer to as "AST" from now on for brevity. Our AST would look like this:

(+)<br>/ \<br>/ \<br>(*) (/)<br>/ \ / \<br>(-) 10 25 5

From here, we'll (hopefully) have already learned Pratt's technique, but we'll keep going and have it interpreted<br>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<br>enjoy writing lexers by hand, but we'll write one anyway for the sake of education. Before we get into the lexer,<br>let's first define Token, as it is the output of a lexer:

enum class TokenType {<br>NUMBER,<br>PLUS,<br>MINUS,<br>DIVISION,<br>MULTIPLICATION,<br>LEFT_PARENTHESIS,<br>RIGHT_PARENTHESIS,<br>END_OF_FILE<br>};

struct Token {<br>TokenType type;<br>std::string value;<br>};

The more complex your project becomes the more complex these two become. For example, the Token could also have<br>fields to save where it was seen - like which line and column; there could be more token types too, were we parsing<br>a programming language we would probably have token types like "IF" and "WHILE" to represent those tokens.

Next, the lexer's interface:

struct Lexer {<br>Lexer(std::string_view &string_view) : string_view(string_view) {}<br>Token NextToken();

private:<br>uint32_t pos = 0;<br>std::string_view &string_view;<br>char Peek() const;<br>};

Notice how thin it is! Indeed, a lexer doesn't provide much more than "the next token" in the raw text it's<br>provided with, but that is all we'll need. Now, to its implementation:

char Lexer::Peek() const {<br>if (pos >= string_view.size()) return '\0';

return string_view[pos];

Token Lexer::NextToken() {<br>while (pos string_view.size() &&<br>std::isspace(static_castunsigned char>(Peek())))) {<br>++pos;

if (pos >= string_view.size())<br>return Token(TokenType::END_OF_FILE, "");

const char c = Peek();

if (std::isdigit(static_castunsigned char>(c))) {<br>std::string val;<br>while (std::isdigit(static_castunsigned char>(Peek())) || Peek() == '.') {<br>val += Peek();<br>++pos;<br>return Token(TokenType::NUMBER, val);

++pos;<br>switch (c) {<br>case '+':<br>return Token(TokenType::PLUS, "+");<br>case '-':<br>return Token(TokenType::MINUS, "-");<br>case '*':<br>return Token(TokenType::MULTIPLICATION, "*");<br>case '/':<br>return Token(TokenType::DIVISION, "/");<br>case '(':<br>return Token(TokenType::LEFT_PARENTHESIS, "(");<br>case ')':<br>return Token(TokenType::RIGHT_PARENTHESIS, ")");<br>default:<br>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.<br>After finding a valid character, it returns a token representing it. If it finds a digit, it builds a string of the<br>number it found.

Notice how it doesn't try to create numbers or<br>interpret them, like turning "-5" into a double with the value "-5", instead it will return two separate tokens: "-"<br>and "5"; that is because the lexer is supposed to just return tokens, not interpret them - that is the parser's<br>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<br>before, if we were...