写一个消去文法左递归的C语言程序,中间添加一个循环使程序可以反复输入,输入#时结束循环
时间: 2024-05-15 13:19:58 浏览: 172
消除左递归的C语言程序大概步骤如下:
1. 定义一个函数,接受一个字符串作为输入,输出消除左递归后的字符串。
2. 在函数中,将输入字符串按照“|”分割成若干个子串。
3. 对于每个子串,判断是否以非终结符开头,如果是则表示存在左递归,需要进行消除。
4. 对于存在左递归的子串,先将其右部分提取出来,然后生成新的非终结符。
5. 将原来的子串中以该非终结符开头的部分替换为新的非终结符。
6. 最后将新的非终结符与原来的非终结符一起输出。
以下是一个简单的示例程序,可以进行反复输入:
```
#include <stdio.h>
#include <string.h>
#define MAX_LEN 100
void remove_left_recursion(char *input, char *output) {
char *tok;
char *subtok;
char *ptr;
char alpha;
char new_nt[MAX_LEN];
char new_rule[MAX_LEN];
char rest_rule[MAX_LEN];
int count = 0;
// 按照“|”分割成子串
tok = strtok(input, "|");
while (tok != NULL) {
alpha = tok[0];
// 判断是否存在左递归
if (alpha == output[0]) {
ptr = strchr(tok, '>');
ptr++;
subtok = strtok(ptr, "|");
while (subtok != NULL) {
// 生成新的非终结符
sprintf(new_nt, "%c'", alpha);
// 生成新的规则
sprintf(new_rule, "%s %c' | ", subtok, alpha);
// 记录右部剩下的部分
strcpy(rest_rule, subtok + 1);
// 将左递归的部分替换为新的非终结符
sprintf(subtok, "%s %s", new_nt, rest_rule);
// 输出新的规则
printf("%s", new_rule);
subtok = strtok(NULL, "|");
count++;
}
} else {
// 直接输出原来的规则
printf("%s | ", tok);
count++;
}
tok = strtok(NULL, "|");
}
// 如果存在左递归,输出新的非终结符和规则
if (count > 1) {
sprintf(new_nt, "%c'", output[0]);
printf("%s -> ", new_nt);
// 输出不含左递归的部分
tok = strtok(input, "|");
while (tok != NULL) {
alpha = tok[0];
if (alpha != output[0]) {
printf("%s | ", tok);
}
tok = strtok(NULL, "|");
}
printf("%c' | ε", new_nt);
} else {
// 没有左递归,直接输出原来的非终结符和规则
printf("%s", input);
}
}
int main() {
char input[MAX_LEN];
char output[MAX_LEN];
int repeat = 1;
while (repeat) {
printf("请输入要消除左递归的规则(用“|”分割多个规则,以“#”结束):\n");
fgets(input, MAX_LEN, stdin);
input[strcspn(input, "\n")] = '\0';
if (strcmp(input, "#") == 0) {
repeat = 0;
break;
}
remove_left_recursion(input, output);
printf("\n消除左递归后的规则为:%s\n\n", output);
}
return 0;
}
```
阅读全文