• 日期: 2025-10-17 16:40:02
  • 标签: 常规

LL(1) 文法识别：First、Follow 和 Select 集合的 C 语言实现

本文将介绍使用 C 语言实现 LL(1) 文法识别中 First、Follow 和 Select 集合的计算过程。

示例代码

以下是使用 C 语言实现 LL(1) 文法的 First、Follow 和 Select 集合的示例代码：

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

#define MAX_NON_TERMINALS 10
#define MAX_TERMINALS 10
#define MAX_RULES 10

typedef struct {
    char nonTerminal;
    char terminals[MAX_TERMINALS];
    int numTerminals;
} Rule;

typedef struct {
    char nonTerminal;
    char firstSet[MAX_TERMINALS];
    int numFirstSet;
    char followSet[MAX_TERMINALS];
    int numFollowSet;
} NonTerminal;

void addTerminal(char set[], int *numSet, char terminal) {
    int i;
    for (i = 0; i < *numSet; i++) {
        if (set[i] == terminal) {
            return;
        }
    }
    set[*numSet] = terminal;
    (*numSet)++;
}

void calculateFirstSet(Rule rules[], int numRules, NonTerminal nonTerminals[], int numNonTerminals) {
    int i, j, k, changed;
    for (i = 0; i < numNonTerminals; i++) {
        nonTerminals[i].numFirstSet = 0;
    }
    do {
        changed = 0;
        for (i = 0; i < numRules; i++) {
            Rule rule = rules[i];
            NonTerminal nonTerminal;
            for (j = 0; j < numNonTerminals; j++) {
                if (nonTerminals[j].nonTerminal == rule.nonTerminal) {
                    nonTerminal = nonTerminals[j];
                    break;
                }
            }
            for (j = 0; j < rule.numTerminals; j++) {
                if (rule.terminals[j] >= 'A' && rule.terminals[j] <= 'Z') {
                    NonTerminal subNonTerminal;
                    for (k = 0; k < numNonTerminals; k++) {
                        if (nonTerminals[k].nonTerminal == rule.terminals[j]) {
                            subNonTerminal = nonTerminals[k];
                            break;
                        }
                    }
                    for (k = 0; k < subNonTerminal.numFirstSet; k++) {
                        if (subNonTerminal.firstSet[k] != '@') {
                            addTerminal(nonTerminal.firstSet, &nonTerminal.numFirstSet, subNonTerminal.firstSet[k]);
                        }
                    }
                    if (subNonTerminal.numFirstSet == 0 || (subNonTerminal.numFirstSet == 1 && subNonTerminal.firstSet[0] == '@')) {
                        addTerminal(nonTerminal.firstSet, &nonTerminal.numFirstSet, '@');
                    }
                } else {
                    addTerminal(nonTerminal.firstSet, &nonTerminal.numFirstSet, rule.terminals[j]);
                    break;
                }
            }
            nonTerminals[j] = nonTerminal;
        }
        for (i = 0; i < numNonTerminals; i++) {
            if (nonTerminals[i].numFirstSet != numFirstSet) {
                changed = 1;
                break;
            }
        }
    } while (changed);
}

void calculateFollowSet(Rule rules[], int numRules, NonTerminal nonTerminals[], int numNonTerminals) {
    int i, j, k, changed;
    for (i = 0; i < numNonTerminals; i++) {
        nonTerminals[i].numFollowSet = 0;
    }
    addTerminal(nonTerminals[0].followSet, &(nonTerminals[0].numFollowSet), '$');
    do {
        changed = 0;
        for (i = 0; i < numRules; i++) {
            Rule rule = rules[i];
            for (j = 0; j < rule.numTerminals - 1; j++) {
                if (rule.terminals[j] >= 'A' && rule.terminals[j] <= 'Z') {
                    NonTerminal nonTerminal;
                    for (k = 0; k < numNonTerminals; k++) {
                        if (nonTerminals[k].nonTerminal == rule.terminals[j]) {
                            nonTerminal = nonTerminals[k];
                            break;
                        }
                    }
                    if (rule.terminals[j + 1] >= 'A' && rule.terminals[j + 1] <= 'Z') {
                        NonTerminal subNonTerminal;
                        for (k = 0; k < numNonTerminals; k++) {
                            if (nonTerminals[k].nonTerminal == rule.terminals[j + 1]) {
                                subNonTerminal = nonTerminals[k];
                                break;
                            }
                        }
                        for (k = 0; k < subNonTerminal.numFirstSet; k++) {
                            if (subNonTerminal.firstSet[k] != '@') {
                                addTerminal(nonTerminal.followSet, &(nonTerminal.numFollowSet), subNonTerminal.firstSet[k]);
                            }
                        }
                        if (subNonTerminal.numFirstSet == 0 || (subNonTerminal.numFirstSet == 1 && subNonTerminal.firstSet[0] == '@')) {
                            NonTerminal prevNonTerminal;
                            for (k = 0; k < numNonTerminals; k++) {
                                if (nonTerminals[k].nonTerminal == rule.nonTerminal) {
                                    prevNonTerminal = nonTerminals[k];
                                    break;
                                }
                            }
                            for (k = 0; k < prevNonTerminal.numFollowSet; k++) {
                                addTerminal(nonTerminal.followSet, &(nonTerminal.numFollowSet), prevNonTerminal.followSet[k]);
                            }
                        }
                    } else {
                        addTerminal(nonTerminal.followSet, &(nonTerminal.numFollowSet), rule.terminals[j + 1]);
                    }
                    nonTerminals[k] = nonTerminal;
                }
            }
        }
        for (i = 0; i < numNonTerminals; i++) {
            if (nonTerminals[i].numFollowSet != numFollowSet) {
                changed = 1;
                break;
            }
        }
    } while (changed);
}

void calculateSelectSet(Rule rules[], int numRules, NonTerminal nonTerminals[], int numNonTerminals) {
    int i, j, k;
    for (i = 0; i < numRules; i++) {
        Rule rule = rules[i];
        NonTerminal nonTerminal;
        for (j = 0; j < numNonTerminals; j++) {
            if (nonTerminals[j].nonTerminal == rule.nonTerminal) {
                nonTerminal = nonTerminals[j];
                break;
            }
        }
        if (rule.terminals[0] >= 'A' && rule.terminals[0] <= 'Z') {
            NonTerminal subNonTerminal;
            for (k = 0; k < numNonTerminals; k++) {
                if (nonTerminals[k].nonTerminal == rule.terminals[0]) {
                    subNonTerminal = nonTerminals[k];
                    break;
                }
            }
            for (k = 0; k < subNonTerminal.numFirstSet; k++) {
                if (subNonTerminal.firstSet[k] != '@') {
                    addTerminal(rule.terminals, &(rule.numTerminals), subNonTerminal.firstSet[k]);
                }
            }
            if (subNonTerminal.numFirstSet == 0 || (subNonTerminal.numFirstSet == 1 && subNonTerminal.firstSet[0] == '@')) {
                for (k = 0; k < nonTerminal.numFollowSet; k++) {
                    addTerminal(rule.terminals, &(rule.numTerminals), nonTerminal.followSet[k]);
                }
            }
        }
        rules[i] = rule;
    }
}

int main() {
    Rule rules[MAX_RULES];
    int numRules;
    NonTerminal nonTerminals[MAX_NON_TERMINALS];
    int numNonTerminals;

    printf("Enter the number of rules: ");
    scanf("%d", &numRules);

    printf("Enter the rules:\n");
    for (int i = 0; i < numRules; i++) {
        scanf("%s", rules[i].terminals);
        rules[i].nonTerminal = rules[i].terminals[0];
        rules[i].numTerminals = strlen(rules[i].terminals) - 1;
    }

    numNonTerminals = 0;
    for (int i = 0; i < numRules; i++) {
        if (rules[i].nonTerminal >= 'A' && rules[i].nonTerminal <= 'Z') {
            NonTerminal nonTerminal;
            nonTerminal.nonTerminal = rules[i].nonTerminal;
            addTerminal(nonTerminal.terminals, &(nonTerminal.numTerminals), rules[i].terminals[1]);
            nonTerminals[numNonTerminals] = nonTerminal;
            numNonTerminals++;
        }
    }

    calculateFirstSet(rules, numRules, nonTerminals, numNonTerminals);
    calculateFollowSet(rules, numRules, nonTerminals, numNonTerminals);
    calculateSelectSet(rules, numRules, nonTerminals, numNonTerminals);

    printf("\nFirst Sets:\n");
    for (int i = 0; i < numNonTerminals; i++) {
        printf("%c: ", nonTerminals[i].nonTerminal);
        for (int j = 0; j < nonTerminals[i].numFirstSet; j++) {
            printf("%c ", nonTerminals[i].firstSet[j]);
        }
        printf("\n");
    }

    printf("\nFollow Sets:\n");
    for (int i = 0; i < numNonTerminals; i++) {
        printf("%c: ", nonTerminals[i].nonTerminal);
        for (int j = 0; j < nonTerminals[i].numFollowSet; j++) {
            printf("%c ", nonTerminals[i].followSet[j]);
        }
        printf("\n");
    }

    printf("\nSelect Sets:\n");
    for (int i = 0; i < numRules; i++) {
        printf("%s: ", rules[i].terminals);
        for (int j = 0; j < rules[i].numTerminals; j++) {
            printf("%c ", rules[i].terminals[j]);
        }
        printf("\n");
    }

    return 0;
}

代码说明

该代码可以接受用户输入文法规则，并计算出每个非终结符的 First、Follow 和 Select 集合。请注意，代码中的文法规则应符合以下要求：

  • 每个非终结符都以大写字母表示。
  • 每个终结符都以小写字母或其他符号表示。
  • 每个规则都以非终结符开头，后跟终结符或非终结符的序列。

例如，以下是一个符合要求的文法规则的示例输入：

Enter the number of rules: 4
Enter the rules:
S=AB
A=aA
A=@
B=b

代码将输出每个非终结符的 First、Follow 和 Select 集合。

代码功能

  • calculateFirstSet 函数计算每个非终结符的 First 集合。
  • calculateFollowSet 函数计算每个非终结符的 Follow 集合。
  • calculateSelectSet 函数计算每个规则的 Select 集合。

总结

本文介绍了使用 C 语言实现 LL(1) 文法识别中 First、Follow 和 Select 集合的计算过程，并提供了示例代码。希望本文能帮助你理解 LL(1) 文法的识别过程。

附加信息

  • LL(1) 文法是一种上下文无关文法，其识别过程可以利用 First 和 Follow 集合来构建预测分析表。
  • First 集合包含一个非终结符推导出的所有可能句型的第一个符号。
  • Follow 集合包含一个非终结符后面可能出现的符号。
  • Select 集合包含一个规则的左部非终结符能够推导出的所有句型的第一个符号，用于构建预测分析表。

希望本文能对你有所帮助！


原文地址: https://www.cveoy.top/t/topic/o4qV 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录