5

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

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

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

4

1 回答 1

8

您的功能是递归下降，而不是递归上升。您遇到的递归下降解析器与左递归的问题是众所周知和研究的。任何涵盖解析的编译器课程或教科书都将讨论问题和解决方法。

使用迭代是一种完全正常、有效的处理方式。 例如，请参阅这些课程笔记。在这些注释中，规则T -> T '*' S | T '/' S | S（即mulExpr添加了除法的规则）被转换为规则T -> S { ('*' | '/') S }，其中大括号{...}表示“零次或多次重复”。

更新

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

递归下降

递归下降的基本思想是为语法中的每个非终结符创建一个函数。对应于某个非终结符A的函数的工作是尽可能完整地解析A的一个实例，并根据需要调用出现在文法中A产生式右侧的非终结符的函数。

因此，例如，您的语法具有addExpr以下两个产生式的非终结符：

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

因此，递归下降解析器将有一个函数 foraddExpr尝试匹配其中一个产生式的右侧addExpr，并根据需要调用函数 forprimaryExpr和addExpr（本身！），因为这些非终结符出现在addExpr的产生式中。

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

递归上升

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

在 LR 解析器中，状态和非终结符之间或状态和产生式之间通常没有一一对应的关系。通常会有比生产更多的状态。每个状态代表产品中的一组位置。

你的解析器

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

此外，您在使用左递归产生式时遇到麻烦的事实是您使用递归下降的一个死胡同。LR 解析器不存在左递归问题，而递归下降解析器则存在问题。

于 2012-09-08T19:04:54.590 回答