Recursive left recursion in manual recursive floating-point parsing

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?

+5
source share
1 answer

- , . , , , , . , , .

- , . ., , . T -> T '*' S | T '/' S | S ( mulExpr ) T -> S { ('*' | '/') S }, {...} " ".

UPDATE

, , , " " " ".

- . , A, , A, , , A .

, , addExpr :

addExpr -> primaryExpr '+' addExpr
addExpr -> primaryExpr

addExpr, addExpr, primaryExpr addExpr (!) , addExpr .

, , parseAddExpr. addExpr , parsePrimaryExpr parseAddExpr .

( ) LR-. LR . . , switch .

LR- , , . , , . .

, , . , , , . .

, , , - , . LR .

+8

All Articles