writing about pratt parsing so I remember it

I decided to create a parser for C expressions, which might eventually evolve into a compiler. After working on a calculator using the shunting yard algorithm, I wanted to explore a more advanced method called pratt parsing. While the dragon book and most programming language courses mainly cover LR or recursive descent parsing, pratt parsing is more commonly found in compiler development and PLT circles. It's mentioned in Crafting Interpreters and a few other online resources.

To understand pratt parsing, I studied Pratt's original paper extensively. At first, the concept seemed challenging due to the recursion involved in operator precedence. However, once I connected it back to the shunting yard algorithm, the lightbulb went off. The shunting yard algorithm is simpler than pratt parsing, as it uses an output stream and an operator stack. Operators are defined with binding powers, with higher powers binding more tightly (e.g., * has a higher binding power than + in arithmetic).

The main drawback of shunting yard is its lack of extensibility. For example, it doesn't support subexpressions or unary operators in a straightforward manner. This is where pratt parsing comes in. The key to adapting shunting yard to pratt parsing is to leverage the call stack to implicitly handle subexpressions as they become necessary. Unlike recursive descent, pratt parsing only nests calls for subexpressions when needed, keeping the core implementation simple.

Here's a basic pratt-style parser in C, equivalent to the shunting yard version:

```c

while (has_more_input()) {

token = get_next_token();

if (token.type == NUMBER) {

push_operand(token.value);

} else if (token.type == OPERATOR) {

while (!is_at_end() && next_token_precedence() >= token.precedence) {

operator = get_operator();

pop_two_operands();

apply_operator(operator);

}

push_operator(token);

}

}

```

This simple parser demonstrates the power of implicit stack management, which simplifies extensibility. To add parentheses, you can adjust the precedence checking logic:

```c

if (token.type == LEFT_PAREN) {

push_operator(token);

} else if (token.type == RIGHT_PAREN) {

while (top_of_stack() != LEFT_PAREN) {

operator = get_operator();

pop_two_operands();

apply_operator(operator);

}

pop_operator(); // Discard the left parenthesis

}

```

By defining operator behavior in separate functions, pratt parsing remains straightforward while allowing for easy addition of new operators. This elegant approach makes the core parsing mechanism simple, while each operator handles its own logic. I hope this explanation helps others who are on the journey of understanding pratt parsing. Happy parsing!