Recursive descent parsing, revisited in Java 21
First published on Habr (in Russian) on 24 February 2020; this is a rewritten and updated version.
I was still at school when a book on C and C++ ended with a listing called "recursive calculator". It took me many evenings to understand how a few short functions could evaluate 2 + 3 * (4 - 5). In 2020 I wrote that explanation up for Habr. This is the same idea six years later, with what I would now tell a student first, and with modern Java.
The full program is one file: Calc.java. Run it with java Calc.java; Java 21 needs no separate compilation step.
Start with a grammar
Before code, describe what an expression looks like. Three rules are enough for the four operations and brackets:
expression -> term (('+' | '-') term)*
term -> factor (('*' | '/') factor)*
factor -> NUMBER | '(' expression ')'Read * as "repeat zero or more times". An expression is a sum of terms, a term is a product of factors, a factor is a number or a whole expression in brackets. The last rule is where the recursion lives: a bracket sends us back to the first rule.
Precedence falls out of the layering. * binds tighter than + because multiplication is handled one level deeper: by the time expression sees a +, term has already consumed 3 * (4 - 5) as one piece.
The trap in the 2020 version
My original article wrote the rules recursively:
E -> T + E | T - E | TIt looks equivalent, but it is not. Implemented literally, 10 - 4 - 3 becomes 10 - (4 - 3) = 9, because the recursion groups from the right. Subtraction and division are left-associative and must group from the left: (10 - 4) - 3 = 3.
The 2020 code got the right answer anyway, because it turned the recursion into a loop and accumulated the result from left to right. The grammar and the code disagreed, and nothing in the text said so. The rules above use repetition (*) instead of right recursion, so the grammar now says what the loop does.
Tokens first
The old article skipped tokenization and started from an array of strings. A tokenizer is short, and it is where errors such as 1 # 2 are best reported, so here it is. Tokens are records behind a sealed interface:
sealed interface Token permits Num, Name, Sym {}
record Num(double value) implements Token {}
record Name(String text) implements Token {}
record Sym(char c) implements Token {}The tokenizer walks the string once: digits and dots become a Num, letters and digits a Name, any of +-*/^(), a Sym, spaces are skipped, anything else is an error with its position.
Build a tree, then evaluate it
In 2020 the parser computed the result while parsing. That is fine for a calculator, but a tree is more useful: you can print it, simplify it, evaluate it for many values of x, or compile it. Records make the tree almost free:
sealed interface Expr permits Number, Var, Unary, Binary, Call {}
record Number(double value) implements Expr {}
record Var(String name) implements Expr {}
record Unary(char op, Expr operand) implements Expr {}
record Binary(char op, Expr left, Expr right) implements Expr {}
record Call(String function, List<Expr> args) implements Expr {}The grammar, extended
Now add what a real calculator needs: unary minus, powers, variables and functions such as max(1, x * 2, sqrt(16)).
expression -> term (('+' | '-') term)*
term -> unary (('*' | '/') unary)*
unary -> '-' unary | power
power -> primary ('^' unary)?
primary -> NUMBER | NAME | NAME '(' args ')' | '(' expression ')'Two decisions are hidden here.
-2 ^ 2is-4, as in mathematics: the power is computed first, then negated. That is whyunarysits abovepower.2 ^ 3 ^ 2is2 ^ 9 = 512: powers group from the right. Here right recursion is exactly what we want, sopowercallsunaryfor its right side instead of looping.
Each rule becomes one method. The two loops are the left-associative rules:
private Expr expression() {
Expr left = term();
while (peek('+') || peek('-')) {
char op = next();
left = new Binary(op, left, term());
}
return left;
}
private Expr term() {
Expr left = unary();
while (peek('*') || peek('/')) {
char op = next();
left = new Binary(op, left, unary());
}
return left;
}
private Expr unary() {
if (peek('-')) {
next();
return new Unary('-', unary());
}
return power();
}
private Expr power() {
Expr base = primary();
if (peek('^')) {
next();
return new Binary('^', base, unary()); // right-associative: 2^3^2 = 2^9
}
return base;
}primary is where Java 21 pattern matching pays off. One switch over the sealed token type decides between a number, a function call, a variable and a bracket, and the compiler checks that no case is missing:
private Expr primary() {
if (pos >= tokens.size()) throw error("unexpected end of expression");
Token t = tokens.get(pos++);
return switch (t) {
case Num n -> new Number(n.value());
case Name n when peek('(') -> call(n.text());
case Name n -> new Var(n.text());
case Sym s when s.c() == '(' -> {
Expr inner = expression();
expect(')');
yield inner;
}
case Sym s -> throw error("unexpected '" + s.c() + "'");
};
}Evaluation is another switch, this time over the tree:
static double eval(Expr e, Map<String, Double> vars) {
return switch (e) {
case Number n -> n.value();
case Var v -> { /* look the name up in vars */ }
case Unary u -> -eval(u.operand(), vars);
case Binary b -> { /* +, -, *, /, ^ on the two sides */ }
case Call c -> { /* sqrt, sin, max */ }
};
}Check it
The main method of the file prints this:
2 + 3 * (4 - 5) + 6 - 7 = -2.0 ok
2 + 2 * (3 + 4 * (5 - 6)) = 0.0 ok
10 - 4 - 3 = 3.0 ok
-2 ^ 2 = -4.0 ok
2 ^ 3 ^ 2 = 512.0 ok
2 * -x = -6.0 ok
max(1, x * 2, sqrt(16)) = 6.0 ok
-(1 + 2) * 3 = -9.0 ok
2 + -> unexpected end of expression at token 2
(1 + 2 -> ')' expected at token 4
2 3 -> unexpected Num[value=3.0] at token 1
1 # 2 -> Unexpected character '#' at 2The tree for 2 + 3 * x, printed by the records themselves:
Binary[op=+, left=Number[value=2.0], right=Binary[op=*, left=Number[value=3.0], right=Var[name=x]]]What to take away
- Write the grammar first. Each rule becomes a method, and precedence is the order of the layers.
- Use repetition for left-associative operators and right recursion only where you want right grouping, as with powers.
- Separate tokenizing, parsing and evaluation. Each step is small and can be tested on its own.
- In Java 21, records and sealed interfaces make the tree a few lines, and
switchwith patterns makes the compiler check every case.
A good exercise: add comparisons with a new top rule, comparison -> expression (('<' | '==') expression)?, and start parsing from it; then add a ternary a ? b : c on top of that. If the grammar is right, the code follows almost mechanically.