c++ - 如何在 C++ 中使用简单的递归下降解析器解析基本算术(例如 "5+5")？

Question

这件事在我的脑海里已经有一段时间了。我对递归下降解析器很感兴趣，并且想知道如何实现它。我想要的是一个简单的解析器，它可以理解简单的算术，例如“5+5”或“(5+5)*3”。

我认为第一步是编写一个“tokenizer”，它将整个输入字符串分解为许多子字符串。这部分我已经完成(我什至不得不询问它 here 。如果你不想的话，你不必点击链接，因为我也在此处发布相关代码。)我的这个标记器，我最终得到一个 string 或标记的 vector。现在，困难的部分:我想解析这些标记。

我已阅读 Wikipedia article on recursive descent parsers .我确实了解整体概念，但与往常一样，实现有点令人困惑。在那篇文章中，有一个用于非常简单的编程语言的递归下降解析器的 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;
}

编辑:我应该提到我的代码总是打印:ERROR: syntax error，来自factor()函数。

Answer 1

维基百科文章包含一个看起来非常完整的解析器(但没有词法分析器!)，它什么都不做。

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

想到了两种方法:

1. 让每个函数接受一个 something* result 参数。对于简单的方程解析器，这可能是所有元素的 float* result。

2. 只需将所有函数从 void rule_x()... 更改为 float rule_x()... 即可返回结果。

在任何一种情况下，您都需要一些方法来处理错误。如果您在 C 中，则没有异常(exception)，因此您最好使用选项 1 并使用返回值来指示成功。然后会有很多

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

但在 C++ 中，您可以将解析包装在异常处理程序中，并在错误中抛出异常，从而中止解析的其余部分。

如果您愿意，事情会变得更加有趣，比如使用优化或 JIT 编译整个语言，并尝试从语法错误中优雅地恢复并继续解析。

了解这个主题的书是 dragon book .