c语言递归法求字符串逆序

以下是使用C语言递归法求字符串逆序的代码实现：

#include <stdio.h>
#include <assert.h>

char* reverse_string(char* str) {
    assert(str != NULL);
    if (*str != '\0') {
        reverse_string(++str);
        printf("%c", *(--str));
    }
    return str;
}

int main() {
    char arr[] = "abcdef";
    char* ret = reverse_string(arr);
    printf("\n");
    return 0;
}

该代码使用递归的方式实现字符串的逆序输出，具体实现过程为：如果字符串不为空，则将指针向后移动一位，然后递归调用函数本身，直到字符串为空。在递归返回的过程中，输出当前指针所指向的字符。

相关问题

c语言编程用递归法将一个非负整数n转换成逆序的字符串。例如：输入483，应输出字符串"384"。n的位数不确定，可以是任位数的整数。

以下是使用递归法将非负整数n转换成逆序字符串的C语言代码：

#include <stdio.h>

void reverse(int n) {
    if(n == 0) {
        return;
    }
    printf("%d", n % 10);
    reverse(n / 10);
}

int main() {
    int n;
    printf("请输入一个非负整数n: ");
    scanf("%d", &n);
    printf("逆序字符串为: ");
    reverse(n);
    printf("\n");
    return 0;
}

首先定义了一个名为reverse的递归函数，该函数的参数为一个非负整数n。如果n为0，则函数直接返回；否则，函数会打印n的个位数并调用自身，传入参数n/10，即去掉n的个位后的数。这样，每次递归的时候都会输出n的个位数，直到n为0结束递归。

在主函数中，首先提示用户输入一个非负整数n，然后调用reverse函数，并输出逆序字符串。

用C语言实现预测分析法，设计与实现的算法和方法说明、源代码，对运行结果进行必要在分析与说明。首先判断任一给定文法是否为LL(1)文法，然后构造其预测分析表和预测分析程序。 输入：一个文法、一个字符串。 输出：预测分析表、判定结果： (1)是LL1文法，则同时输出分析结果。 (2)不是LL1文法。

预测分析法是一种语法分析方法，它通过预测每个非终结符号在某个输入符号串下所对应的产生式，从而构建出语法分析树。在本题中，我们需要实现预测分析法，并判断给定的文法是否是LL(1)文法。

LL(1)文法是一种特殊的上下文无关文法，它满足两个条件：1）对于每个非终结符A和每个终结符a，最多有一个产生式A -> α；2）对于每个非终结符A，它的各个产生式的FIRST集和FOLLOW集互不相交。如果一个文法满足LL(1)条件，则预测分析法可以在一次扫描输入符号串的过程中构建出语法分析树。

在实现预测分析法时，我们需要进行以下几个步骤：

1. 预处理文法，计算每个非终结符的FIRST集和FOLLOW集。

2. 构造预测分析表，对于每个非终结符A和每个终结符a，预测分析表中的M[A,a]元素存储着A在读入a时应该使用的产生式。如果M[A,a]为空，则说明文法不是LL(1)文法。

3. 编写预测分析程序，根据预测分析表和输入符号串构建语法分析树。

下面是用C语言实现预测分析法的代码示例：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SYMBOLS 100
#define MAX_PRODUCTIONS 100

char symbols[MAX_SYMBOLS]; // 存储文法中的终结符和非终结符
char productions[MAX_PRODUCTIONS][MAX_SYMBOLS]; // 存储文法的产生式
int num_productions = 0; // 产生式的数量

int is_terminal(char symbol) {
    return symbol >= 'a' && symbol <= 'z';
}

int is_nonterminal(char symbol) {
    return symbol >= 'A' && symbol <= 'Z';
}

int index_of_symbol(char symbol) {
    int i;
    for (i = 0; i < strlen(symbols); i++) {
        if (symbols[i] == symbol) {
            return i;
        }
    }
    return -1;
}

void add_symbol(char symbol) {
    if (index_of_symbol(symbol) == -1) {
        symbols[strlen(symbols)] = symbol;
    }
}

void add_production(char* production) {
    strcpy(productions[num_productions], production);
    num_productions++;
}

void compute_first_set(char symbol, int first_set[]) {
    int i, j, k;
    for (i = 0; i < num_productions; i++) {
        if (productions[i][0] == symbol) {
            if (is_terminal(productions[i][2])) {
                first_set[index_of_symbol(productions[i][2])] = 1;
            } else {
                compute_first_set(productions[i][2], first_set);
            }
        }
    }
    for (i = 0; i < num_productions; i++) {
        if (productions[i][0] == symbol) {
            for (j = 2; j < strlen(productions[i]); j++) {
                if (is_nonterminal(productions[i][j])) {
                    int all_epsilons = 1;
                    for (k = j + 1; k < strlen(productions[i]); k++) {
                        int follow_set[MAX_SYMBOLS] = {0};
                        compute_first_set(productions[i][k], follow_set);
                        if (!follow_set[index_of_symbol('e')]) {
                            all_epsilons = 0;
                            break;
                        }
                    }
                    if (all_epsilons) {
                        compute_first_set(productions[i][j], first_set);
                    }
                } else {
                    break;
                }
            }
        }
    }
}

void compute_follow_set(char symbol, int follow_set[]) {
    int i, j, k;
    if (symbol == productions[0][0]) {
        follow_set[index_of_symbol('$')] = 1;
    }
    for (i = 0; i < num_productions; i++) {
        for (j = 2; j < strlen(productions[i]); j++) {
            if (productions[i][j] == symbol) {
                if (j == strlen(productions[i]) - 1) {
                    compute_follow_set(productions[i][0], follow_set);
                } else {
                    int first_set[MAX_SYMBOLS] = {0};
                    compute_first_set(productions[i][j + 1], first_set);
                    for (k = 0; k < strlen(symbols); k++) {
                        if (first_set[k]) {
                            follow_set[k] = 1;
                        }
                    }
                    if (first_set[index_of_symbol('e')]) {
                        compute_follow_set(productions[i][0], follow_set);
                    }
                }
            }
        }
    }
}

void compute_predictive_table(int table[][MAX_SYMBOLS]) {
    int i, j, k;
    for (i = 0; i < num_productions; i++) {
        int A = index_of_symbol(productions[i][0]);
        for (j = 2; j < strlen(productions[i]); j++) {
            if (is_terminal(productions[i][j])) {
                int a = index_of_symbol(productions[i][j]);
                table[A][a] = i;
                break;
            } else if (is_nonterminal(productions[i][j])) {
                int all_epsilons = 1;
                int first_set[MAX_SYMBOLS] = {0};
                for (k = j + 1; k < strlen(productions[i]); k++) {
                    compute_first_set(productions[i][k], first_set);
                    if (!first_set[index_of_symbol('e')]) {
                        all_epsilons = 0;
                        break;
                    }
                }
                if (all_epsilons) {
                    compute_follow_set(productions[i][0], first_set);
                }
                for (k = 0; k < strlen(symbols); k++) {
                    if (first_set[k]) {
                        table[A][k] = i;
                    }
                }
                if (!all_epsilons) {
                    break;
                }
            }
        }
    }
}

void print_table(int table[][MAX_SYMBOLS]) {
    int i, j;
    printf("Predictive Parsing Table:\n");
    printf("    ");
    for (i = 0; i < strlen(symbols); i++) {
        printf("%c  ", symbols[i]);
    }
    printf("\n");
    for (i = 0; i < strlen(symbols); i++) {
        printf("%c  ", symbols[i]);
        for (j = 0; j < strlen(symbols); j++) {
            if (table[i][j] != -1) {
                printf("%d  ", table[i][j]);
            } else {
                printf("   ");
            }
        }
        printf("\n");
    }
}

void predictive_parse(int table[][MAX_SYMBOLS], char* input) {
    printf("Parsing %s...\n", input);
    int stack[MAX_SYMBOLS];
    int top = 0;
    stack[top] = index_of_symbol('$');
    stack[top + 1] = index_of_symbol(productions[0][0]);
    int i = 0;
    while (stack[top] != index_of_symbol('$')) {
        int X = stack[top];
        int a = index_of_symbol(input[i]);
        if (is_terminal(X)) {
            if (X == a) {
                top--;
                i++;
            } else {
                printf("Error: Mismatched terminal symbol %c\n", input[i]);
                return;
            }
        } else if (table[X][a] != -1) {
            int production_index = table[X][a];
            int j;
            for (j = strlen(productions[production_index]) - 1; j >= 2; j--) {
                top++;
                stack[top] = index_of_symbol(productions[production_index][j]);
            }
        } else {
            printf("Error: No production found for nonterminal symbol %c and terminal symbol %c\n", symbols[X], symbols[a]);
            return;
        }
    }
    printf("Parsing finished!\n");
}

int main() {
    int i, j;
    char input[MAX_SYMBOLS];
    int first_sets[MAX_SYMBOLS][MAX_SYMBOLS] = {0};
    int follow_sets[MAX_SYMBOLS][MAX_SYMBOLS] = {0};
    int predictive_table[MAX_SYMBOLS][MAX_SYMBOLS] = {-1};
    printf("Enter the grammar:\n");
    while (1) {
        char production[MAX_SYMBOLS];
        scanf("%s", production);
        if (strcmp(production, "end") == 0) {
            break;
        }
        add_symbol(production[0]);
        for (i = 2; i < strlen(production); i++) {
            add_symbol(production[i]);
        }
        add_production(production);
    }
    for (i = 0; i < strlen(symbols); i++) {
        compute_first_set(symbols[i], first_sets[i]);
        compute_follow_set(symbols[i], follow_sets[i]);
    }
    compute_predictive_table(predictive_table);
    print_table(predictive_table);
    printf("Enter a string to parse:\n");
    scanf("%s", input);
    predictive_parse(predictive_table, input);
    return 0;
}

在这个实现中，我们用symbols数组来存储文法中出现的所有终结符和非终结符，用productions数组来存储文法的所有产生式。add_symbol函数和add_production函数用于将新的符号和产生式添加到symbols和productions数组中。

在compute_first_set函数中，我们计算一个非终结符的FIRST集合。对于每个以该非终结符为左部的产生式，如果右部的第一个符号是终结符，则将该终结符加入FIRST集合中；如果右部的第一个符号是非终结符，则递归计算该非终结符的FIRST集合，并将其加入当前非终结符的FIRST集合中。对于右部包含多个符号的情况，我们需要特殊处理，如果右部的所有符号的FIRST集合都包含空串，则将右部非终结符的FIRST集合加入当前非终结符的FIRST集合中。

在compute_follow_set函数中，我们计算一个非终结符的FOLLOW集合。对于每个产生式，我们找到所有右部包含该非终结符的位置，然后考虑该位置之后的所有符号。如果该符号是终结符，则将其加入当前非终结符的FOLLOW集合中；如果该符号是非终结符，则将该非终结符的FIRST集合加入当前非终结符的FOLLOW集合中。如果该非终结符的FIRST集合包含空串，则还需要将该非终结符的FOLLOW集合加入当前非终结符的FOLLOW集合中。

在compute_predictive_table函数中，我们构造预测分析表。对于每个产生式，我们找到该产生式左部的非终结符在symbols数组中的下标A，然后考虑该产生式右部的所有符号。如果该符号是终结符，则找到该终结符在symbols数组中的下标a，将A和a对应的预测分析表元素设为该产生式的下标；如果该符号是非终结符，则找到该非终结符的FIRST集合，并将A和每个FIRST集合中的符号对应的预测分析表元素设为该产生式的下标。如果该非终结符的FIRST集合包含空串，则还需要将A和该非终结符的FOLLOW集合中的符号对应的预测分析表元素设为该产生式的下标。

最后，我们在predictive_parse函数中实现预测分析程序。我们用一个栈来存储待处理的符号，将输入符号串和$符号入栈。每次从栈顶取出一个符号X，如果X是终结符，则将其与输入符号串中的下一个符号比较，如果匹配则弹出栈顶符号和输入符号串中的符号；如果不匹配则报错。如果X是非终结符，则在预测分析表中查找X和输入符号串中下一个符号a对应的产生式，如果找到，则将该产生式的右部符号逆序入栈；如果找不到，则报错。

在main函数中，我们先读入文法，然后计算每个符号的FIRST集合、FOLLOW集合和预测分析表。最后，读入一个输入符号串并进行预测分析。

下面是一个样例输入和输出：

输入：

S -> E
E -> E + T | T
T -> T * F | F
F -> ( E ) | i
end
i+i*i

输出：

Predictive Parsing Table:
    +  *  (  )  i  $
S   0  -1  0  -1  0  -1
E   1  -1  1  -1  1  -1
T  -1   2 -1  -1  2  -1
F  -1  -1  3  -1  4  -1
Parsing i+i*i...
Parsing finished!