Pratt-parsing expression evaluator
A C++23 calculator REPL that parses expressions with Pratt parsing and remembers variables.
Each line goes through three stages. The lexer turns it into tokens: numbers and names are atoms, and + - * / = are operators. The parser builds an expression tree. The evaluator walks the tree depth first to get the answer.
The parser is a Pratt parser. Every operator has a left and a right binding power, and parse_expression(min) keeps absorbing operators whose left power is at least min, parsing each right-hand side with that operator's right power. Higher powers bind tighter, so * grabs its operands before +, and because each right power is one more than its left, equal operators group left to right.
Assignments store values in a hash map, so later lines can use them.
Input line
1 + 2 * a + b
Lexer
Atoms and operators
Pratt parser
Tree by binding power
Evaluator
Walks the tree, stores variables
- Input line to Lexer
- Lexer to Pratt parser
- Pratt parser to Evaluator
See it work
Binding powers, from the code
| Operator | Left | Right |
|---|---|---|
| = | 0 | 1 |
| + - | 1 | 2 |
| * / | 3 | 4 |
The tree for 1 + 2 * a + b
+
+
b
134
1
*
2
a
2
- + to +
- + to b
- + to 1
- + to *
- * to 2
- * to a
A real session
| Typed | Answer |
|---|---|
| a = 2 | 2 |
| b = a * 67 | 134 |
| 1 + 2 * a + b | 139 |
| 10 - 4 - 3 | 3 |
Each line typed into the REPL, in order, and the answer it gave.