递归子程序法实现语法分析器

递归子程序法是一种常见的语法分析方法。它的基本思想是将文法规则转换为一组递归子程序，每个递归子程序对应一个非终结符号。在语法分析过程中，程序递归调用这些子程序，从而实现对输入串的逐个扫描和分析。

下面我们以一个简单的四则运算表达式文法为例，演示如何使用递归子程序法实现语法分析器。该文法包含加、减、乘、除、括号和整数常量等符号。具体文法规则如下：

E -> E + T | E - T | T
T -> T * F | T / F | F
F -> ( E ) | num

其中，E、T 和 F 分别表示表达式、项和因子，num 表示整数常量。

下面是一个基于递归子程序法实现的语法分析器的伪代码：

// 全局变量：指向输入串的指针
char* input_ptr;

// 递归子程序：E -> E + T | E - T | T
int E() {
    int result = T();
    while (*input_ptr == '+' || *input_ptr == '-') {
        char op = *input_ptr;
        input_ptr++;
        int operand = T();
        if (op == '+') {
            result += operand;
        } else {
            result -= operand;
        }
    }
    return result;
}

// 递归子程序：T -> T * F | T / F | F
int T() {
    int result = F();
    while (*input_ptr == '*' || *input_ptr == '/') {
        char op = *input_ptr;
        input_ptr++;
        int operand = F();
        if (op == '*') {
            result *= operand;
        } else {
            result /= operand;
        }
    }
    return result;
}

// 递归子程序：F -> ( E ) | num
int F() {
    int result;
    if (*input_ptr == '(') {
        input_ptr++;
        result = E();
        input_ptr++; // 消耗右括号
    } else {
        result = parse_num();
    }
    return result;
}

// 辅助函数：解析一个整数常量并返回其值
int parse_num() {
    int result = 0;
    while (*input_ptr >= '0' && *input_ptr <= '9') {
        result = result * 10 + (*input_ptr - '0');
        input_ptr++;
    }
    return result;
}

// 主函数：解析输入串，并返回表达式的值
int parse(char* input) {
    input_ptr = input;
    return E();
}

在以上代码中，E()、T() 和 F() 分别对应文法规则中的 E、T 和 F。它们通过递归调用自身和其它子程序来实现对输入串的逐个扫描和分析。parse_num() 函数用于解析整数常量。parse() 函数是语法分析器的入口函数，它初始化输入指针并调用 E()，最终返回表达式的值。

需要注意的是，递归子程序法只适用于某些特定的文法，例如 LL(1) 文法。对于一些复杂的文法，需要使用其它的语法分析方法，例如 LR 分析法。