Как выполнить синтаксический анализ основной арифметики (например, "5 + 5" ) с помощью простого рекурсивного парсера спуска в С++?

Это было на мой взгляд некоторое время. Я заинтригован рекурсивными парсерами спуска и хотел бы знать, как их реализовать. Я хочу простой анализатор, который будет понимать простую арифметику, такую ​​как "5 + 5" или "(5 + 5) * 3".

Я считаю, что первым шагом является запись "токенизатора", который принимает всю входную строку и разбивает ее на множество подстрок. Эта часть, которую я сделал (мне даже пришлось спросить об этом здесь. Вам не нужно следовать ссылке, если вы этого не хотите, так как я Здесь я также размещаю ссылочный код.) С этим токенизатором я заканчиваю с vector of string s или жетонами. Теперь, трудная часть: я бы хотел разобрать эти жетоны.

Я прочитал статью статью Википедии о парсерах рекурсивного спуска. Я понимаю общую концепцию, но, как всегда, реализация немного запутанна. В этой статье существует реализация 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().