用c++语言写语法分析

语法分析是编译原理中非常重要的一部分，它可以将源程序转换成语法树或中间代码，是编译器的核心部分之一。在C++语言中，可以通过手动编写语法分析器来实现。

1. 定义语法规则

首先需要定义源程序的语法规则，通常使用上下文无关文法（Context-Free Grammar，CFG）来描述。例如，可以定义一个简单的算术表达式的语法规则：

<expression> ::= <term> | <expression> '+' <term> | <expression> '-' <term>
<term> ::= <factor> | <term> '*' <factor> | <term> '/' <factor>
<factor> ::= '(' <expression> ')' | <number>
<number> ::= <digit> | <number> <digit>
<digit> ::= '0' | '1' | ... | '9'

这里 `<expression>` 表示一个表达式，可以是一个 `<term>`，或者由一个 `<expression>` 和一个加号或减号和一个 `<term>` 组成；`<term>` 表示一个项，可以是一个 `<factor>`，或者由一个 `<term>` 和一个乘号或除号和一个 `<factor>` 组成；`<factor>` 表示一个因子，可以是一个括号内的 `<expression>`，或者一个数字 `<number>`；`<number>` 表示一个数字，由一个或多个 `<digit>` 组成；`<digit>` 表示一个数字字符。

2. 生成语法树

在定义好语法规则后，就可以使用递归下降分析（Recursive Descent Parsing）算法来生成语法树。递归下降分析是一种自顶向下的语法分析方法，它从语法树的根节点开始，逐步向下扩展，直到叶子节点为止。

在实现递归下降分析时，需要为每个非终结符编写一个对应的函数，用于识别该非终结符的语法规则。例如，在上述算术表达式的语法规则中，可以为每个非终结符编写如下的函数：

TreeNode* parseExpression()
{
    TreeNode* term = parseTerm();
    if (match('+') || match('-')) {
        TreeNode* node = new TreeNode(currentToken());
        node->left = term;
        node->right = parseExpression();
        return node;
    }
    return term;
}

TreeNode* parseTerm()
{
    TreeNode* factor = parseFactor();
    if (match('*') || match('/')) {
        TreeNode* node = new TreeNode(currentToken());
        node->left = factor;
        node->right = parseTerm();
        return node;
    }
    return factor;
}

TreeNode* parseFactor()
{
    if (match('(')) {
        TreeNode* expression = parseExpression();
        match(')');
        return expression;
    }
    else {
        TreeNode* number = new TreeNode(currentToken());
        match(DIGIT);
        return number;
    }
}

其中，`parseExpression()` 函数用于解析一个表达式，首先调用 `parseTerm()` 函数获取一个项，然后判断当前符号是否为加号或减号，如果是，则创建一个加减运算的节点，并将该节点的左子树设置为前面获取的项，右子树设置为下一个表达式的解析结果；如果不是，则直接返回前面获取的项。`parseTerm()` 和 `parseFactor()` 函数的实现方式类似，用于解析一个项和一个因子。

在每个函数中，需要使用 `match()` 函数来判断当前符号是否符合预期。如果当前符号与预期不符，则抛出一个异常，提示语法错误。

3. 示例代码

下面是一个完整的语法分析器示例代码，用于解析上述算术表达式语法：

#include <iostream>
#include <string>
#include <stdexcept>

using namespace std;

// 词法分析器
enum TokenType {
    ADD, SUB, MUL, DIV, LPAREN, RPAREN, DIGIT, END
};

class Token {
public:
    Token(TokenType type, int value = 0)
        : type(type), value(value) {}

    TokenType getType() const { return type; }
    int getValue() const { return value; }

private:
    TokenType type;
    int value;
};

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

    Token getNextToken() {
        while (pos < input.length()) {
            char ch = input[pos];
            switch (ch) {
            case '+': ++pos; return Token(ADD);
            case '-': ++pos; return Token(SUB);
            case '*': ++pos; return Token(MUL);
            case '/': ++pos; return Token(DIV);
            case '(': ++pos; return Token(LPAREN);
            case ')': ++pos; return Token(RPAREN);
            default:
                if (isdigit(ch)) {
                    int value = 0;
                    while (pos < input.length() && isdigit(input[pos])) {
                        value = value * 10 + input[pos] - '0';
                        ++pos;
                    }
                    return Token(DIGIT, value);
                }
                else {
                    throw runtime_error("invalid character");
                }
            }
        }
        return Token(END);
    }

private:
    string input;
    size_t pos;
};

// 语法分析器
class TreeNode {
public:
    TreeNode(Token token)
        : token(token), left(nullptr), right(nullptr) {}

    Token getToken() const { return token; }
    TreeNode* getLeft() const { return left; }
    TreeNode* getRight() const { return right; }
    void setLeft(TreeNode* node) { left = node; }
    void setRight(TreeNode* node) { right = node; }

private:
    Token token;
    TreeNode* left;
    TreeNode* right;
};

class Parser {
public:
    Parser(const string& input)
        : lexer(input), current(lexer.getNextToken()) {}

    TreeNode* parse() {
        return parseExpression();
    }

private:
    Token current;
    Lexer lexer;

    void advance() {
        current = lexer.getNextToken();
    }

    bool match(TokenType type) {
        return current.getType() == type;
    }

    TreeNode* parseExpression() {
        TreeNode* term = parseTerm();
        if (match(ADD) || match(SUB)) {
            Token op = current;
            advance();
            TreeNode* node = new TreeNode(op);
            node->setLeft(term);
            node->setRight(parseExpression());
            return node;
        }
        return term;
    }

    TreeNode* parseTerm() {
        TreeNode* factor = parseFactor();
        if (match(MUL) || match(DIV)) {
            Token op = current;
            advance();
            TreeNode* node = new TreeNode(op);
            node->setLeft(factor);
            node->setRight(parseTerm());
            return node;
        }
        return factor;
    }

    TreeNode* parseFactor() {
        if (match(LPAREN)) {
            advance();
            TreeNode* expression = parseExpression();
            if (!match(RPAREN)) {
                throw runtime_error("unmatched parenthesis");
            }
            advance();
            return expression;
        }
        else if (match(DIGIT)) {
            Token token = current;
            advance();
            return new TreeNode(token);
        }
        else {
            throw runtime_error("invalid factor");
        }
    }
};

// 测试程序
void printTree(TreeNode* node, int depth = 0) {
    if (node == nullptr) return;
    for (int i = 0; i < depth; ++i) cout << "  ";
    cout << node->getToken().getType() << " " << node->getToken().getValue() << endl;
    printTree(node->getLeft(), depth + 1);
    printTree(node->getRight(), depth + 1);
}

int main() {
    string input;
    cout << "Enter an arithmetic expression: ";
    getline(cin, input);

    try {
        Parser parser(input);
        TreeNode* root = parser.parse();
        printTree(root);
    }
    catch (exception& ex) {
        cerr << "Error: " << ex.what() << endl;
    }

    return 0;
}

在上述代码中，`Lexer` 类用于识别源程序中的单词，并将其转换成一系列 `Token` 对象；`Parser` 类用于解析 `Token` 对象，并生成语法树；`TreeNode` 类用于表示语法树的节点。

在程序运行时，可以输入一个算术表达式，例如 `1+2*3-4/2`，程序将会输出该表达式对应的语法树：

ADD 0
  DIGIT 1
  SUB 0
    MUL 0
      DIGIT 2
      DIGIT 3
    DIV 0
      DIGIT 4
      DIGIT 2