实现Firstvt 算法
时间: 2023-09-24 11:02:49 浏览: 42
Firstvt 算法是编译原理中的一个算法,用于求文法中每个非终结符的 Firstvt 集合。下面给出 Firstvt 算法的实现步骤:
1. 对于文法中的每个终结符 a,将 a 加入到 Firstvt(a) 中。
2. 对于文法中的每个非终结符 A,对于文法中每个形如 A → α 的产生式,将 Firstvt(α) 中的所有符号加入到 Firstvt(A) 中。
3. 重复执行步骤 2 直到 Firstvt 集合不再发生变化为止。
下面是一个示例文法及其 Firstvt 集合的求解过程:
文法 G:
S → ABc
A → a
A → ε
B → b
对于终结符 a、b、c,将它们加入到 Firstvt(a)、Firstvt(b)、Firstvt(c) 中。
对于非终结符 A、B,根据产生式 A → a 和 A → ε 可得 Firstvt(A) = {a},根据产生式 B → b 可得 Firstvt(B) = {b}。
对于产生式 S → ABc,根据 Firstvt(ABc) = {a, b},将 a、b 加入到 Firstvt(S) 中。
重复执行步骤 2,得到 Firstvt(S) = {a, b},Firstvt(A) = {a},Firstvt(B) = {b},Firstvt(c) = {c}。最终得到文法 G 的每个非终结符的 Firstvt 集合。
相关问题
FIRSTVT集生成算法C语言实现
以下是一个简单的FIRSTVT集生成算法的C语言实现,假设输入文法已经存储在一个数组中,文法符号用字符表示:
```c
#include <stdio.h>
#include <string.h>
#define MAX_PROD 50
#define MAX_LEN 10
char grammar[MAX_PROD][MAX_LEN];
int n;
int is_terminal(char c) {
return !(c >= 'A' && c <= 'Z');
}
void firstvt(char c, int *first) {
int i, j, k, nt;
for (i = 0; i < n; i++) {
if (grammar[i][0] == c) {
j = 2;
while (grammar[i][j] != '\0') {
if (is_terminal(grammar[i][j])) {
first[grammar[i][j] - 'a'] = 1;
break;
}
firstvt(grammar[i][j], first);
nt = 0;
for (k = j + 1; grammar[i][k] != '\0'; k++) {
if (is_terminal(grammar[i][k])) {
first[grammar[i][k] - 'a'] = 1;
break;
}
if (first[grammar[i][k] - 'A'] == 0) {
break;
}
nt++;
}
if (nt == k - j - 1) {
first[grammar[i][k] - 'A'] = 1;
}
j = k;
}
}
}
}
int main() {
int i, j;
int first[26] = {0};
printf("输入文法产生式个数:");
scanf("%d", &n);
printf("输入文法产生式:\n");
for (i = 0; i < n; i++) {
scanf("%s", grammar[i]);
}
printf("FIRSTVT集:\n");
for (i = 0; i < n; i++) {
firstvt(grammar[i][0], first);
printf("FIRSTVT(%c) = {", grammar[i][0]);
for (j = 0; j < 26; j++) {
if (first[j]) {
printf("%c, ", j + 'a');
}
}
printf("}\n");
memset(first, 0, sizeof(first));
}
return 0;
}
```
在该实现中,首先输入文法产生式的个数和具体内容,并在循环中逐个计算每个非终结符号的FIRSTVT集。在计算FIRSTVT集的过程中,使用了递归调用,对每个产生式符号进行处理,直到遇到终结符号或者无法推导出终结符号为止。
注意,该实现只适用于文法符号为单个字符的情况,如果文法符号包含多个字符,需要相应地修改代码。
求firstvt和lastvt集合的算法思路
求一个文法的 FirstVT 和 LastVT 集合,可以采用如下算法思路:
1. 对每个非终结符号,初始化其 FirstVT 集合为空集,初始化其 LastVT 集合为空集。
2. 对于每个产生式 A → α,将 First(α) 中所有非空终结符号加入 A 的 FirstVT 集合。若 α 可以推导出 ε,则将 A 的 FollowVT 集合加入 A 的 FirstVT 集合。
3. 对于每个产生式 A → α,将 Last(α) 中所有非空终结符号加入 A 的 LastVT 集合。若 α 可以推导出 ε,则将 A 的 FollowVT 集合加入 A 的 LastVT 集合。
4. 重复执行步骤 2 和 3,直到没有新的终结符号可以加入 FirstVT 或 LastVT 集合为止。
5. 对于每个产生式 A → α,若存在一个非终结符号 B,使得 α 可以写作 γB,则将 B 的 FirstVT 集合加入 A 的 FollowVT 集合。
6. 对于每个产生式 A → α,若存在一个非终结符号 B,使得 α 可以写作 Bγ,则将 B 的 LastVT 集合加入 A 的 FollowVT 集合。
7. 重复执行步骤 5 和 6,直到没有新的非终结符号可以加入 FollowVT 集合为止。
8. 对于每个非终结符号 A,其 FirstVT 和 LastVT 集合即为步骤 2 和 3 最终计算得到的结果。
以上就是求 FirstVT 和 LastVT 集合的算法思路。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)