手工编写的递归上升语法分析器中的递归左递归

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

您的函数是递归下降，而不是递归上升。递归下降语法分析器在左递归中遇到的问题是众所周知的，并且已经进行了研究。任何涉及解析的编译器课程或教科书都会讨论这个问题和解决方法

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

更新

根据你的评论，我认为你对"递归下降"one_answers"递归上升"的含义有些困惑。

递归下降

递归下降的基本思想是为语法中的每个非终结符创建一个函数。与某些非终结符A相对应的函数的工作是，如果可能的话，完全解析A的一个实例，根据需要调用语法中A+结果右侧出现的非终结符的函数。

例如，您的语法有一个非终结符addExpr，它包含以下两个生成：

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

因此，递归下降语法分析器将为addExpr提供一个函数，该函数试图匹配其中一个addExpr结果的右侧，根据需要调用primaryExpr和addExpr（本身！）的函数，因为这些非终结符出现在addExpr的结果中。

事实上，这正是你在parseAddExpr函数中所拥有的。它寻找一种匹配addExpr产品之一的方法，根据需要调用parsePrimaryExpr和parseAddExpr。

递归上升

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

在LR解析器中，状态和非终结符之间，或者状态和结果之间通常存在一对一的对应关系，而不是。一般来说，会有更多的州而不是生产。每个状态表示产品中的位置集。

您的解析器

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

此外，您在使用左递归生成时遇到麻烦的事实是，您正在使用递归下降。LR解析器在左递归方面没有问题，递归下降解析器有问题。