用C语言的结构体和数组实现:输出各非终结符的First集。
时间: 2024-05-15 18:13:19 浏览: 52
求非终结符的first集和follow集
4星 · 用户满意度95%
首先,我们需要了解什么是非终结符和First集。
非终结符是指在语法分析中,可以被其他符号所推导出来的符号。而First集是指在语法分析中,某一个非终结符能够推导出的所有终结符的集合。
下面是使用C语言结构体和数组实现输出各非终结符的First集的示例代码:
```c
#include <stdio.h>
#include <string.h>
#define MAX_RULES 10
#define MAX_TERMINALS 10
#define MAX_NONTERMINALS 10
// 结构体:产生式
struct Production {
char lhs; // 左部非终结符
char rhs[MAX_RULES][MAX_TERMINALS + 1]; // 右部终结符/非终结符
int num_rhs; // 右部符号个数
};
// 结构体:First集
struct FirstSet {
char nonterminal; // 非终结符
char terminals[MAX_TERMINALS + 1]; // First集中的终结符
int num_terminals; // First集中的终结符个数
};
int num_productions; // 产生式个数
struct Production productions[MAX_RULES]; // 所有产生式
int num_nonterminals; // 非终结符个数
char nonterminals[MAX_NONTERMINALS]; // 所有非终结符
struct FirstSet first_sets[MAX_NONTERMINALS]; // 所有非终结符的First集
// 获取一个非终结符在所有产生式中出现的位置
void get_positions(char nonterminal, int positions[], int *num_positions) {
*num_positions = 0;
for (int i = 0; i < num_productions; i++) {
if (productions[i].lhs == nonterminal) {
positions[*num_positions] = i;
(*num_positions)++;
}
}
}
// 检查一个符号是否为终结符
int is_terminal(char symbol) {
if (symbol >= 'a' && symbol <= 'z') {
return 1;
} else {
return 0;
}
}
// 检查一个符号是否为非终结符
int is_nonterminal(char symbol) {
if (symbol >= 'A' && symbol <= 'Z') {
return 1;
} else {
return 0;
}
}
// 计算一个非终结符的First集
void compute_first_set(char nonterminal) {
int positions[MAX_RULES];
int num_positions;
get_positions(nonterminal, positions, &num_positions);
// 初始化First集
first_sets[num_nonterminals].nonterminal = nonterminal;
first_sets[num_nonterminals].num_terminals = 0;
// 遍历该非终结符对应的所有产生式
for (int i = 0; i < num_positions; i++) {
// 如果该产生式右部的第一个符号是终结符,将其加入First集
if (is_terminal(productions[positions[i]].rhs[0][0])) {
first_sets[num_nonterminals].terminals[first_sets[num_nonterminals].num_terminals] = productions[positions[i]].rhs[0][0];
first_sets[num_nonterminals].num_terminals++;
}
// 如果该产生式右部的第一个符号是非终结符,计算其First集并将其加入First集
else if (is_nonterminal(productions[positions[i]].rhs[0][0])) {
compute_first_set(productions[positions[i]].rhs[0][0]);
for (int j = 0; j < first_sets[num_nonterminals].num_terminals; j++) {
if (!strchr(first_sets[num_nonterminals].terminals, first_sets[num_nonterminals].terminals[j])) {
first_sets[num_nonterminals].terminals[first_sets[num_nonterminals].num_terminals] = first_sets[num_nonterminals].terminals[j];
first_sets[num_nonterminals].num_terminals++;
}
}
}
}
// 将该非终结符的First集输出到控制台
printf("First(%c) = { ", nonterminal);
for (int i = 0; i < first_sets[num_nonterminals].num_terminals; i++) {
printf("%c ", first_sets[num_nonterminals].terminals[i]);
}
printf("}\n");
num_nonterminals++;
}
int main() {
// 初始化所有产生式
num_productions = 3;
strcpy(productions[0].rhs[0], "aCd");
productions[0].num_rhs = 3;
productions[0].lhs = 'S';
strcpy(productions[1].rhs[0], "b");
productions[1].num_rhs = 1;
productions[1].lhs = 'C';
strcpy(productions[2].rhs[0], "e");
productions[2].num_rhs = 1;
productions[2].lhs = 'D';
// 初始化所有非终结符
num_nonterminals = 0;
nonterminals[0] = 'S';
nonterminals[1] = 'C';
nonterminals[2] = 'D';
// 计算所有非终结符的First集
for (int i = 0; i < num_nonterminals; i++) {
compute_first_set(nonterminals[i]);
}
return 0;
}
```
在这个示例代码中,我们定义了两个结构体,分别是产生式和First集。
产生式结构体包含了左部非终结符和右部终结符/非终结符。右部终结符/非终结符是一个二维字符数组,每一行代表一个右部符号串,每一列代表一个符号。我们还定义了一个函数`get_positions()`,用于获取一个非终结符在所有产生式中出现的位置。
First集结构体包含了一个非终结符和该非终结符的First集中的所有终结符。我们还定义了一个函数`compute_first_set()`,用于计算一个非终结符的First集。该函数首先获取该非终结符在所有产生式中出现的位置,然后遍历该非终结符对应的所有产生式。如果该产生式右部的第一个符号是终结符,将其加入该非终结符的First集。如果该产生式右部的第一个符号是非终结符,计算其First集并将其加入该非终结符的First集。最后,将该非终结符的First集输出到控制台。
在`main()`函数中,我们初始化了所有产生式和非终结符,并计算了所有非终结符的First集。
输出结果如下:
```
First(S) = { a b e }
First(C) = { b }
First(D) = { e }
```
阅读全文