15

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

我认为第一步是编写一个“标记器”，它将整个输入字符串分解为许多子字符串。这部分我已经完成了（我什至不得不在这里询问它。如果你不想的话，你不必点击链接，因为我在这里也发布了相关代码。）使用这个标记器我的，我最终得到一个vectorof strings 或令牌。现在，困难的部分：我想解析这些标记。

我已阅读有关递归下降解析器的 Wikipedia 文章。我确实了解整体概念，但与往常一样，实现有点令人困惑。在那篇文章中，有一个用于非常简单的编程语言的递归下降解析器的 C 实现，文章中也进行了讨论。我尽我所能研究了该代码，并尝试基本上编写相同的东西，但对于我的程序。下面是那个代码。

我真正困惑的是这个解析器做了什么。它似乎通过程序并“预期”语法的某些部分。但是一旦它到达那里，它会做什么？例如，这里有一个来自维基百科代码的函数，它应该解析一个“术语”：

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

这是为了解析这个语法：

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

这是有道理的。但它与实际术语有什么关系？假设该术语只是“6”，或者是“3 * 2”并且结果为6。它将如何将其合并到输入的其余部分中？不应该term()返回 adouble而不是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()函数中打印：

4

1 回答 1

6

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

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

想到了两种方法：

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

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

无论哪种情况，您都需要某种方法来处理错误。如果您在 C 中，则没有例外，因此您最好使用选项 1 并使用返回值来指示成功。那么会有很多

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

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

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

入题的书是龙书。

于 2012-04-30T05:47:41.853 回答