C++ 递归下降语法分析器实现：自上而下语法分析技术解析

本文以简单四则运算表达式为例，使用 C++ 语言实现递归下降语法分析器，详细介绍自上而下语法分析器（递归子程序法/预测分析法）的设计原理和代码实现，并分析其优缺点。

1. 递归下降语法分析原理

递归下降语法分析是一种自上而下的语法分析方法，它根据语法规则逐层递归地分析输入字符串。每个语法规则对应一个递归函数，函数递归调用自身或其他函数来解析子表达式。

2. 代码实现

假设要分析的语言是一个简单的四则运算表达式语言，语法规则如下：

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

其中，number 表示一个整数。

下面是一个使用递归下降法实现的分析器：

#include <iostream>
#include <cstdlib>
#include <cstring>

using namespace std;

class Analyzer {
public:
    Analyzer(const char* str) : input(str), pos(0) {}
    int parse();
private:
    int expression();
    int term();
    int factor();
    int number();
    const char* input;
    int pos;
};

int Analyzer::parse() {
    return expression();
}

int Analyzer::expression() {
    int result = term();
    while (input[pos] == '+' || input[pos] == '-') {
        char op = input[pos++];
        int value = term();
        if (op == '+') result += value;
        else result -= value;
    }    
    return result;
}

int Analyzer::term() {
    int result = factor();
    while (input[pos] == '*' || input[pos] == '/') {
        char op = input[pos++];
        int value = factor();
        if (op == '*') result *= value;
        else result /= value;
    }    
    return result;
}

int Analyzer::factor() {
    int result;
    if (input[pos] == '(') {
        pos++;
        result = expression();
        if (input[pos] != ')') {
            cerr << "Syntax error: expected ')'";
            exit(1);
        }
        pos++;
    } else {
        result = number();
    }    
    return result;
}

int Analyzer::number() {
    int result = 0;
    while (isdigit(input[pos])) {
        result = result * 10 + input[pos] - '0';
        pos++;
    }    
    return result;
}

int main() {
    const char* input = "2+3*4-(5+6)/2";
    Analyzer analyzer(input);
    int result = analyzer.parse();
    cout << "Result: " << result << endl;
    return 0;
}

在这个例子中，Analyzer 类是递归下降分析器的实现。构造函数接受一个字符串作为输入，parse() 方法开始解析输入并返回结果。expression()、term() 和 factor() 分别对应语法规则中的 expression、term 和 factor。number() 方法用于解析数字。在 expression() 和 term() 方法中，使用 while 循环处理多个加减和乘除操作。factor() 方法中使用了递归来处理括号内的表达式。如果在解析过程中发现语法错误，程序会输出错误信息并退出。在 main() 函数中，构造一个 Analyzer 对象并调用 parse() 方法，输出解析结果。

3. 优缺点

递归下降法的优点是：

• 代码实现简单易懂，易于调试和维护。
• 适用于处理规模较小的语法。

递归下降法的缺点是：

• 对于复杂的语法，递归下降法的代码可能变得非常复杂。
• 对于左递归的语法规则，需要进行转换才能使用递归下降法。

4. 总结

递归下降语法分析是一种常用的自上而下语法分析方法，适用于处理规模较小的语法。对于复杂的语法，需要考虑使用其他的语法分析方法，例如 LR 分析法。