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

Question

这已经在我脑海中浮现了一段时间.我对递归下降解析器很感兴趣,并且想知道如何实现它.我想要的是一个简单的解析器,它将理解简单的算术,如"5 + 5"或"(5 + 5)*3".

我认为第一步是编写一个'tokenizer',它获取整个输入字符串并将其分解为许多子字符串.这部分我已经完成了(我甚至不得不在这里询问.如果你不想,你不必关注链接,因为我也在这里发布了相关代码.)使用这个标记器我的,我结束了一个vector的stringS,或令牌.现在,困难的部分:我想解析那些令牌.

我已经阅读了关于递归下降解析器的维基百科文章.我确实理解整体概念,但一如既往,实施有点令人困惑.在那篇文章中,有一个非常简单的编程语言的递归下降解析器的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中,则没有例外,因此您最好使用选项1并使用返回值来表示成功.然后会有很多

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

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

当您想要编译整个语言并使用优化或JIT时,事情变得更有趣,并尝试从语法错误中优雅地恢复并继续解析.

关于这个主题的书是龙书.