c++ - 手写递归上升解析器中的递归左递归

Question

我一直在编写一些递归上升解析器，而我一直在努力解决的问题之一是左递归。在我看来，右递归可以递归地表达，就像

addExpr
    : primaryExpr '+' addExpr
    | primaryExpr;

按照

的思路

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);
}

但是对于左递归，我能想出的只是一个 while 循环。

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);
}

我的意思是，这个功能很好，但我总觉得它应该有一个递归版本。是否有可能以递归而非迭代的方式实现左结合运算符？

Answer 1

您的函数是递归下降，而不是递归上升。您遇到的递归下降解析器与左递归有关的问题是众所周知和研究过的。任何涉及解析的编译器类(class)或教科书都会讨论问题及其解决方法。

使用迭代是一种非常正常、有效的处理方式。 See these course notes例如。在这些注释中，规则 T -> T '*' S | T'/'S | S(这是添加了除法的 mulExpr 规则)转换为规则 T -> S { ('*' | '/') S } ，其中大括号 {...} 表示“零次或多次重复”。

更新

根据您的评论，我认为您对“递归下降”和“递归上升”的含义有些混淆。

递归下降

递归下降的基本思想是为文法中的每个非终结符创建一个函数。与某些非终结符 A 相对应的函数的工作是在可能的情况下完全解析 A 的一个实例，必要时调用出现在右侧的非终结符的函数A 的语法产生式。

因此，例如，您的语法有一个非终结符 addExpr 和这两个产生式:

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

因此，递归下降解析器将有一个用于 addExpr 的函数，它试图匹配 addExpr 产生式之一的右侧，调用 的函数>primaryExpr 和 addExpr(它本身!)是必要的，因为这些非终结符出现在 addExpr 的产品中。

事实上，这正是您在 parseAddExpr 函数中所拥有的。它寻找一种方法来匹配其中一个 addExpr 产生式，必要时调用 parsePrimaryExpr 和 parseAddExpr。

递归上升

递归上升是一种(非常不常见的)实现 LR 解析的方法。 LR 解析器有一个状态表，一行代表每个状态，一列代表每个终端。在递归上升解析器中，我们不将表表示为数据。相反，我们为每个状态创建一个函数，并且该状态的行在函数中体现为一个 switch 语句。

在 LR 解析器中，状态和非终结符之间，或者状态和产生式之间通常不存在一对一的对应关系。一般来说，状态多于产品。每个状态代表作品中的一组位置。

你的解析器

查看您帖子中的函数，我没有看到任何证据表明您已经构建或体现了状态表。我看到的是一组直接对应于语法非终结符的函数。这种对应关系是递归下降的标志。

此外，您遇到左递归产生式问题这一事实表明您正在使用递归下降。 LR 解析器没有左递归问题，而递归下降解析器有。