C 语言 First 和 Follow 程序

17 Mar 2025 | 6 分钟阅读

First 和 Follow 集合 用于 语法分析 过程。在本文中，我们将结合 C 语言学习 First 和 Follow 集合，并编写一个 C 语言程序来计算 First 和 Follow 集合。

由于 First 和 Follow 集合 用于 编译器设计 和解析技术，建议先了解 语法分析、LL(1) 解析 的基础知识，以及计算给定文法的 First 和 Follow 集合 的规则。

让我们来理解 First 集合 和 Follow 集合：

First 集合

文法中 非终结符 的 First 集合 是指由该 非终结符 生成的字符串的 第一个符号 是的 终结符 集合。换句话说，它是从该 非终结符 推导出的字符串开头可能出现的所有标记的集合。

Follow 集合

文法中 非终结符 的 Follow 集合 是指在文法的任何有效句子中，可能紧跟在由该 非终结符 推导出的 字符串 后面的终结符集合。换句话说，它是任何有效句子中可能出现在 非终结符 之后的标记的集合。

示例

让我们考虑以下作为输入的 上下文无关文法

输入

E=AB
A=ilove
B=jtptutorials

计算给定文法的 First 和 Follow 集合的 C 程序

代码

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

// Functions used to find Follow
void grammarfollow(char, int, int);
void follow(char c);

// Function used to find First
void find_first(char, int, int);

int count, n = 0;

// Stores the final resultof the First Sets
char final_first[10][100];

// Stores the final resultof the Follow Sets
char final_follow[10][100];
int m = 0;

// Stores the production rules
char production[10][10];
char f[10], first[10];
int k;
char ck;
int e;

int main(int argc, char** argv)
{
    int jm = 0;
    int km = 0;
    int i, choice;
    char c, ch;
    count = 3;

    // Initialize the production rules for the context-free grammar
    strcpy(production[0], "E=AB");
    strcpy(production[1], "A=ilove");
    strcpy(production[2], "B=jtptutorials");
    int ff;
    char done[count];
    int ptr = -1;

    // Initializing the final_first array
    for (k = 0; k < count; k++) {
        for (ff= 0; ff< 100; ff++) {
final_first[k][ff] = '!';
        }
    }
    int point1 = 0, point2, xxx;

    for (k = 0; k < count; k++) {
        c = production[k][0];
        point2 = 0;
        xxx = 0;

        // Checking if the first of c has already been calculated
        for (ff= 0; ff<= ptr; ff++)
            if (c == done[ff])
                xxx = 1;

        if (xxx == 1)
            continue;

        // Calling function
find_first(c, 0, 0);
        ptr += 1;

        // Adding c to the calculated list
        done[ptr] = c;
        printf("\n First(%c) = { ", c);
final_first[point1][point2++] = c;

        // Printing the First Sets of the given grammar
        for (i = 0 + jm; i < n; i++) {
            int fs = 0, chk = 0;

            for (fs = 0; fs< point2; fs++) {

                if (first[i] == final_first[point1][fs]) {
                    chk = 1;
                    break;
                }
            }
            if (chk == 0) {
                printf("%c, ", first[i]);
final_first[point1][point2++] = first[i];
            }
        }
        printf("}\n");
        jm = n;
        point1++;
    }
    printf("\n");
    printf("=================================""\n\n");
    char donee[count];
    ptr = -1;

    // Initializing the final_follow array
    for (k = 0; k < count; k++) {
        for (ff= 0; ff< 100; ff++) {
final_follow[k][ff] = '!';
        }
    }
    point1 = 0;
    int land = 0;
    for (e = 0; e < count; e++) {
        ck = production[e][0];
        point2 = 0;
        xxx = 0;

        // Checking if Follow of ckhas already been calculated
        for (ff= 0; ff<= ptr; ff++)
            if (ck == donee[ff])
                xxx = 1;

        if (xxx == 1)
            continue;
        land += 1;

        // Function call
        follow(ck);
        ptr += 1;

        // Adding ck to the calculated list
        donee[ptr] = ck;
        printf(" Follow(%c) = { ", ck);
final_follow[point1][point2++] = ck;

        // Printing the Follow Sets of the given grammar
        for (i = 0 + km; i < m; i++) {
            int fs= 0, chk = 0;
            for (fs= 0; fs< point2; fs++) {
                if (f[i] == final_follow[point1][fs]) {
                    chk = 1;
                    break;
                }
            }
            if (chk == 0) {
                printf("%c, ", f[i]);
final_follow[point1][point2++] = f[i];
            }
        }
        printf(" }\n\n");
        km = m;
        point1++;
    }
}

void follow(char c)
{
    int i, j;

    // Adding "$" to the Follow Setof the start symbol
    if (production[0][0] == c) {
        f[m++] = '$';
    }
    for (i = 0; i < 10; i++) {
        for (j = 2; j < 10; j++) {
            if (production[i][j] == c) {
                if (production[i][j + 1] != '\0') {
                    // Calculate the first of the next non-terminal in the production
grammarfollow(production[i][j + 1], i,
                                (j + 2));
                }

                if (production[i][j + 1] == '\0'
&& c != production[i][0]) {
 // Calculate the Follow of thenon-terminal in the L.H.S. of theproduction
                    follow(production[i][0]);
                }
            }
        }
    }
}

void find_first(char c, int q1, int q2)
{
    int j;

    // The case where we will encounter a terminal
    if (!(isupper(c))) {
        first[n++] = c;
    }
    for (j = 0; j < count; j++) {
        if (production[j][0] == c) {
            if (production[j][2] == '#') {
                if (production[q1][q2] == '\0')
                    first[n++] = '#';
                else if (production[q1][q2] != '\0'
&& (q1 != 0 || q2 != 0)) {
      // Recursion to calculate the First new non-terminal we encounter after
                    // epsilon
                    find_first(production[q1][q2], q1,
                              (q2 + 1));
                }
                else
                    first[n++] = '#';
            }
            else if (!isupper(production[j][2])) {
                first[n++] = production[j][2];
            }
            else {
// Recursion to calculate First ofthe new non-terminal we encounterat the beginning
                find_first(production[j][2], j, 3);
            }
        }
    }
}

void grammarfollow(char c, int c1, int c2)
{
    int k;

    // The case where we will encountera terminal
    if (!(isupper(c)))
        f[m++] = c;
    else {
        int i = 0, j = 1;
        for (i = 0; i < count; i++) {
            if (final_first[i][0] == c)
                break;
        }

// Including the First set of the non-terminal in the Follow ofthe original query
        while (final_first[i][j] != '!') {
            if (final_first[i][j] != '#') {
                f[m++] = final_first[i][j];
            }
            else {
                if (production[c1][c2] == '\0') {
            // The case where we will reach theend of the production
                    follow(production[c1][0]);
                }
                else {
                    // Recursion to the next symbolin case we encounter a "#"
grammarfollow(production[c1][c2], c1,
                                c2 + 1);
                }
            }
            j++;
        }
    }
}

输出

说明

上述 C 程序 将打印出给定文法的计算得到的 First 和 Follow 集合。让我们来理解 First 和 Follow 集合 是如何计算的。

步骤 1：计算 First 集合

First(E): 它包含产生式 E -> AB 的 第一个终结符，即 A 的 First 集合 中的 'i'。

First(A): 它包含产生式 A ->"ilove" 的 第一个终结符，即 'i'。

First(B): 它包含产生式 B ->"jtptutorials" 的 第一个终结符，即 'j'。

步骤 2：计算 Follow 集合

Follow(E): 由于 'E' 是 开始符号，Follow(E) 将包含 '$' 符号，它代表输入的结束，因为开始符号后面可以跟着输入的结束。

Follow(A): 它包含在任何产生式中可能跟在 'A' 后面的 终结符。在此文法中，'A' 后面跟着 'B'，所以我们将 First(B) 包含在 Follow(A) 中。

Follow(B): 它包含在任何产生式中可能跟在 'B' 后面的 终结符。由于没有其他产生式 跟随 'B'，我们将查看 Follow(E)，因为 'E' 可以产生 'B'。

结论

我们已经理解了如何编写 C 程序来计算给定上下文无关文法的 First 和 Follow 集合。

下一主题C 语言的插值查找

C 语言 First 和 Follow 程序

First 集合

Follow 集合

示例

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C 语言教程

C 语言控制语句

C 语言函数

C 语言数组

C 语言指针

C 语言动态内存

C 语言字符串

C 语言数学

C 语言结构体和联合体

C 语言文件处理

C 语言预处理器

C 语言命令行

C 语言程序

C 语言面试

选择题

C 语言编程测试

C 语言基础测试

C 语言控制语句测试

C 语言函数测试

C 语言数组测试

C 语言指针测试

C 语言字符串测试

C 语言结构体测试

C 语言预处理器测试

数学

C 语言杂项

C 语言 First 和 Follow 程序

First 集合

Follow 集合

示例

结论

相关帖子

C 语言用户定义函数 vs. 库函数

C 语言打印数组中最小元素的程序

C 语言控制语句

C 语言图案程序

C 语言 getchar() 函数

C 语言动态数组

C 语言队列

C 语言关系运算符

C 语言 Strtol() 函数

辛普森方法

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器