I wrote several recursive climbing parsers, and one of the things I struggled with was recursion. It seems obvious to me that the correct recursion can be expressed recursively, for example
addExpr
: primaryExpr '+' addExpr
| primaryExpr;
something along the lines
parseAddExpr() {
auto x = parsePrimaryExpr();
if (next_token == '+') {
auto result = make_unique<PlusExpr>();
result->lhs = x;
result->rhs = parseAddExpr();
return std::move(result);
}
return std::move(x);
}
But for left recursion, all I could think of was a while loop.
mulExpr
: mulExpr '*' addExpr
| addExpr;
parseMulExpr() {
auto expr = parseAddExpr();
while(next_token == '*') {
auto mul_expr = make_unique<MulExpr>();
mul_expr->lhs = std::move(expr);
mul_expr->rhs = parseAddExpr();
expr = std::move(mul_expr);
}
return std::move(expr);
}
I mean, this is normal, but I always felt that it should have a recursive version. Is it possible to implement a left-associative operator in a recursive rather than iterative order?
Puppy source
share