C++实现9+5*2/3-6递归下降语法分析器，按照使用生产使过程输出，要求有完整输出程序

实现一个递归下降语法分析器，可以分为三个步骤：词法分析、语法分析和计算表达式。

1. 词法分析

词法分析的目的是将输入的字符串分解成若干个符号，这些符号可以是数字、操作符、括号等。在本题中，我们仅需要考虑四种符号：加号、减号、乘号、除号和数字。因此，我们可以用一个枚举类型来表示这些符号：

enum Token {
    TOKEN_PLUS,
    TOKEN_MINUS,
    TOKEN_TIMES,
    TOKEN_DIVIDE,
    TOKEN_NUMBER,
    TOKEN_END
};

其中，TOKEN_END 表示输入的字符串已经全部读取完毕。

读取符号的过程可以用一个 getNextToken() 函数来实现。该函数读取输入字符串中的下一个符号，并返回它所代表的 Token 类型和数值（如果是数字）。如果输入的字符串不符合要求，函数应该返回 TOKEN_END。

#include <cctype>
#include <iostream>
#include <string>

using namespace std;

class Lexer {
public:
    Lexer(const string& input) : input(input), pos(0) {}

    // 读取下一个 Token
    Token getNextToken() {
        // 跳过空格
        while (pos < input.length() && isspace(input[pos]))
            pos++;

        if (pos == input.length())
            return TOKEN_END;

        // 读取数字
        if (isdigit(input[pos])) {
            int value = 0;
            while (pos < input.length() && isdigit(input[pos])) {
                value = value * 10 + input[pos] - '0';
                pos++;
            }
            return TOKEN_NUMBER;
        }

        // 读取操作符
        switch (input[pos]) {
            case '+':
                pos++;
                return TOKEN_PLUS;
            case '-':
                pos++;
                return TOKEN_MINUS;
            case '*':
                pos++;
                return TOKEN_TIMES;
            case '/':
                pos++;
                return TOKEN_DIVIDE;
            default:
                return TOKEN_END;
        }
    }

private:
    const string& input; // 输入的字符串
    size_t pos; // 当前读取的位置
};

2. 语法分析

语法分析的任务是将输入的符号序列转换成抽象语法树（AST），其中每个节点表示一个表达式或者操作符。在本题中，我们只需要考虑加、减、乘、除四种操作符，因此可以用一个 enum 类型来表示它们：

enum Operator {
    OP_PLUS,
    OP_MINUS,
    OP_TIMES,
    OP_DIVIDE
};

对于每个符号序列，我们可以定义一个对应的产生式来描述它的语法结构。例如，对于表达式 9+5*2/3-6，它的语法结构如下所示：

expression -> term { ( '+' | '-' ) term }
term -> factor { ( '*' | '/' ) factor }
factor -> NUMBER | '(' expression ')'

其中，expression、term、factor 都是非终结符号，NUMBER 是终结符号。

为了实现语法分析，我们需要用一个 Parser 类来表示语法分析器。该类的主要方法是 parseExpression()，它根据上述的产生式递归地解析输入的符号序列，并返回对应的抽象语法树。

class Parser {
public:
    Parser(const string& input) : lexer(input) {}

    // 解析表达式
    int parseExpression() {
        int value = parseTerm();

        while (true) {
            Token token = lexer.getNextToken();
            if (token == TOKEN_PLUS) {
                value += parseTerm();
            } else if (token == TOKEN_MINUS) {
                value -= parseTerm();
            } else {
                break;
            }
        }

        return value;
    }

private:
    // 解析项
    int parseTerm() {
        int value = parseFactor();

        while (true) {
            Token token = lexer.getNextToken();
            if (token == TOKEN_TIMES) {
                value *= parseFactor();
            } else if (token == TOKEN_DIVIDE) {
                value /= parseFactor();
            } else {
                lexer.pos--; // 回退一个符号
                break;
            }
        }

        return value;
    }

    // 解析因子
    int parseFactor() {
        Token token = lexer.getNextToken();
        if (token == TOKEN_NUMBER) {
            return lexer.number;
        } else if (token == TOKEN_PLUS) {
            return parseFactor();
        } else if (token == TOKEN_MINUS) {
            return -parseFactor();
        } else if (token == TOKEN_END) {
            return 0;
        } else {
            // 读取括号内的表达式
            int value = parseExpression();
            token = lexer.getNextToken();
            if (token != TOKEN_END && token != TOKEN_PLUS && token != TOKEN_MINUS && token != TOKEN_TIMES && token != TOKEN_DIVIDE) {
                throw runtime_error("Invalid input");
            }
            return value;
        }
    }

private:
    Lexer lexer; // 词法分析器
};

3. 计算表达式

最后，我们用一个 main() 函数来调用上述的 Lexer 和 Parser 类，并计算输入的表达式的值：

int main() {
    string input = "9+5*2/3-6";
    Parser parser(input);
    int result = parser.parseExpression();
    cout << input << " = " << result << endl;
    return 0;
}

完整代码如下：