如何使用简单的递归下降解析器在C++中解析基本算术表达式（例如“5 + 5”）？

Question

这个问题困扰了我一段时间。我对递归下降解析器很感兴趣，想知道如何实现它。我想要的是一个简单的解析器，可以理解像“5+5”或“(5+5)*3”这样的简单算术表达式。

我认为第一步是编写一个“分词器”，将整个输入字符串拆成多个子字符串。这部分我已经完成了（我甚至不得不在此处询问过）。如果您不想跟随链接，因为我也在这里发布有关代码。使用我的此分词器，我最终会得到一个vector的string或令牌。现在，难点来了：我想解析这些令牌。

我已经阅读了递归下降分析器的维基百科文章。我确实理解了总体概念，但是像往常一样，实现有点令人困惑。在那篇文章中，有一个非常简单的编程语言的递归下降分析器的C实现，也在文章中讨论过。我尽力研究了那段代码，并试图基本上为我的程序编写相同的内容。以下是该代码。

我真正困惑的是这个解析器的作用。它似乎会遍历程序并“期望”语法的某些部分。但是一旦到达那里，它会做什么呢？例如，这是维基百科代码中应该解析“项”的一个函数：

void term(void) {
    factor();
    while (sym == times || sym == slash) {
        getsym();
        factor();
    }
}

这是为了解析以下语法而设计的：

term = factor {("*"|"/") factor} .

这是有意义的。但它对实际术语做了什么呢？比如说，该术语只是“6”，或者是“3×2”，结果为6。它将如何将其合并到其余输入中？term()不应返回double而不是void（以返回6）吗？还是用其他方法完成？

此外，使解析器像输出代码一样与立即处理输入（即编译器与解释器）之间有什么区别？在这个例子中，这两种方式是否理论上实现方式相同，还是根本不同？

欢迎任何意见。以下是我目前的代码：

#include <iostream>
#include <string>
#include <vector>
#include <ctype.h>
#include <sstream>

using namespace std;

vector<string> symbolize(string);
bool accept(string);
void getSymbol();
void error(string s);
bool expect(string);
void expression();
void term();
void factor();

int currentPosition = -1;
string symbol;
vector<string> symbols;

int main(int argc, const char * argv[])
{

    string input;
    getline(cin,input);

    symbols = symbolize(input);
    getSymbol();
    expression();


    return 0;
}

void factor(){
    if(isdigit(symbol.c_str()[0])){}
    else if(accept("(")){
        expression();
        expect(")");
    }
    else {
        error("Syntax error");
    }

}

void term(){
    factor();
    while(symbol=="*"||symbol=="/"){
        getSymbol();
        factor();
    }
}

void expression(){
    if(symbol == "+" || symbol == "-") getSymbol();
    term();
    while(symbol == "+" || symbol == "-"){
        getSymbol();
        term();
    }
}

void error(string s){
    cout << endl << "ERROR: " << s << endl;
}

void getSymbol(){
    currentPosition++;
    if(currentPosition>=symbols.size())error("Unexpectedly reached end of input");

}

bool expect(string s){
    if(accept(s))return true;
    else error("Expected '" + s + "'");
    return false;
}

bool accept(string s){
    if(s==symbol){getSymbol();return true;}
    return false;
}

// Takes a string and breaks it into substrings
vector<string> symbolize(string input){
    int position = 0;
    char c;
    //stringstream s;
    vector<string> symbols;
    enum symbolType {TEXT,OPERATOR}symbolType,charType;

    while(position < input.size()){
        stringstream s;
        c = input.at(position);
        if(isalnum(c))symbolType = TEXT;
        else symbolType = OPERATOR;
        charType = symbolType;

        while(symbolType == charType){
            s << c;
            position++;
            if(position>=input.length())break;
            c = input.at(position);
            if(isspace(c)||c=='\n'){position++; break;}
            if(isalnum(c)) charType = TEXT;
            else charType = OPERATOR;
        }

        symbols.push_back(s.str());
    }

    return symbols;
}

编辑：我应该提到，我的代码总是打印：错误：语法错误，来自factor()函数。

- user377628

---

演示代码并没有对读取的输入进行任何操作。你需要自己添加这部分内容。 - Mooing Duck

通常情况下，解释器在读取第二个数字后会立即执行乘法并返回结果。编译器将创建一个“乘法”对象，并将左侧和右侧返回的对象传递给它，然后返回（或存储）该对象。 - Mooing Duck

@MooingDuck 但是当同一个函数递归运行时，它如何知道它在第二个结果上？ - user377628

@Hassen 项调用了两次因子（正如你的代码所示），并存储了这两个结果。一个是第一个，一个是第二个。term 可能会被递归地再次调用这一事实是无关紧要的。 - Mooing Duck

@MooingDuck 所以实际上在 while 循环内完成数字的乘法或除法？ - user377628

Answer 1

这篇维基百科文章包含一个非常完整的解析器（但没有词法分析器！），仅用于解析。

实际上，为了解释结果，一般的想法是，每个解析函数将部分解释的结果传递回其父/调用者。树中每个规则的结果可能是不同类型的。如果您正在为完整的语言编写解析器，则部分解释的结果可以是简单的常量（可以是任何类型）或整个函数（稍后可能需要编译）。在方程式解析器的情况下，每个规则将仅对从调用其他函数获得的元素执行所需的操作，并将结果传递回调用它的函数。

有两种方法：

1. 每个函数接受一个“something* result”参数。在简单的方程式解析器的情况下，这可能是所有元素的“float* result”。

2. 通过将所有函数从“void rule_x()...”更改为“float rule_x()...”来简单地返回结果。

无论哪种情况，您都需要处理错误。如果您在使用C语言，则没有异常可用，因此最好使用选项1，并使用返回值来指示成功。然后会有很多错误处理的代码。

if(!expression(&result)) return 0;

但是在C++中，您可以将解析包装在异常处理程序中，在出现错误时抛出异常以终止其余解析。

当您想要编译整个语言并进行优化或JIT，并尝试从语法错误中恢复并继续解析时，情况会变得更加有趣。

关于此主题的书籍是龙书。

- Michael Slade