Как разобрать базовую арифметику (, например, «5+5» ), используя простой анализатор рекурсивного спуска в C++?

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

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

using namespace std;

vector 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 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 symbolize(string input){
    int position = 0;
    char c;
    //stringstream s;
    vector 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().