用C++实现递归下降语法分析

好的，下面是一个简单的示例代码，实现了对以下文法的递归下降语法分析：

E -> T + E
E -> T - E
E -> T
T -> int

其中，E表示表达式，T表示项，int表示整数，"+"表示加法运算，"-"表示减法运算。

#include <iostream>
#include <string>
#include <cstdlib>

using namespace std;

// 前向声明
class Parser;

// 抽象语法树节点类
class ASTNode {
public:
    virtual ~ASTNode() {}
    virtual int evaluate() = 0;
};

// 整数节点类
class IntNode : public ASTNode {
public:
    IntNode(int value) : m_value(value) {}
    virtual int evaluate() { return m_value; }
private:
    int m_value;
};

// 二元运算节点类
class BinOpNode : public ASTNode {
public:
    BinOpNode(ASTNode* left, ASTNode* right) : m_left(left), m_right(right) {}
    virtual ~BinOpNode() {
        delete m_left;
        delete m_right;
    }
protected:
    ASTNode* m_left;
    ASTNode* m_right;
};

// 加法节点类
class AddNode : public BinOpNode {
public:
    AddNode(ASTNode* left, ASTNode* right) : BinOpNode(left, right) {}
    virtual int evaluate() { return m_left->evaluate() + m_right->evaluate(); }
};

// 减法节点类
class SubNode : public BinOpNode {
public:
    SubNode(ASTNode* left, ASTNode* right) : BinOpNode(left, right) {}
    virtual int evaluate() { return m_left->evaluate() - m_right->evaluate(); }
};

// 词法分析器
class Lexer {
public:
    Lexer(const string& input) : m_input(input), m_pos(0) {}
    char get_char() {
        if (m_pos >= m_input.length()) {
            return '\0';
        }
        return m_input[m_pos++];
    }
private:
    string m_input;
    int m_pos;
};

// 语法分析器
class Parser {
public:
    Parser(const string& input) : m_lexer(input), m_current_token('\0') {}
    ASTNode* parse() {
        next_token();
        return parse_expr();
    }
private:
    Lexer m_lexer;
    char m_current_token;
    void next_token() {
        m_current_token = m_lexer.get_char();
    }
    ASTNode* parse_expr() {
        ASTNode* node = parse_term();
        while (m_current_token == '+' || m_current_token == '-') {
            char op = m_current_token;
            next_token();
            ASTNode* right = parse_term();
            if (op == '+') {
                node = new AddNode(node, right);
            } else {
                node = new SubNode(node, right);
            }
        }
        return node;
    }
    ASTNode* parse_term() {
        if (m_current_token == 'i') {
            next_token();
            return new IntNode(atoi(m_current_token));
        } else {
            throw "语法错误";
        }
    }
};

int main() {
    string input = "i+2-3";
    Parser parser(input);
    ASTNode* root = parser.parse();
    cout << root->evaluate() << endl;
    delete root;
    return 0;
}

这个示例代码实现了一个简单的四则运算语法分析器，可以通过输入一个字符串，解析出其中的表达式，并计算出其结果。代码主要分为三个部分：

1. ASTNode及其派生类：这些类表示语法树中的各种节点，其中IntNode表示整数节点，BinOpNode表示二元运算节点，AddNode和SubNode分别表示加法和减法节点。

2. Lexer：这个类负责将输入字符串解析为一个个字符，供语法分析器使用。

3. Parser：这个类负责将字符流解析为语法树。它的核心是parse_expr和parse_term两个函数，分别用于解析表达式和项。在parse_expr函数中，首先解析一个项，然后进入一个循环，不断解析加法或减法运算符和后面的项，直到没有运算符为止。在parse_term函数中，如果当前字符是'i'，则表示它是一个整数节点，解析其值并返回；否则，抛出语法错误异常。

在main函数中，我们创建一个Parser对象，并将输入字符串传给它进行解析。然后，我们获得解析出的语法树根节点，并调用其evaluate函数计算出表达式的值。最后，我们删除语法树根节点，释放内存。

注意：这个示例代码只是一个简单的示例，实际的语法分析器需要处理更复杂的语法规则和错误情况。