ll1文法的识别 实现first follow select 用c实现
以下是用C语言实现LL(1)文法的识别，包括求First集、Follow集和Select集的算法。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_RULES 100
#define MAX_SYMBOLS 100
typedef struct {
char lhs;
char rhs[MAX_SYMBOLS];
int numSymbols;
} Production;
typedef struct {
char symbol;
char* firstSet;
char* followSet;
} Symbol;
Production rules[MAX_RULES];
Symbol symbols[MAX_SYMBOLS];
int numRules = 0;
int numSymbols = 0;
void addSymbol(char symbol) {
for (int i = 0; i < numSymbols; i++) {
if (symbols[i].symbol == symbol) {
return;
}
}
symbols[numSymbols].symbol = symbol;
symbols[numSymbols].firstSet = NULL;
symbols[numSymbols].followSet = NULL;
numSymbols++;
}
void addProduction(char lhs, char* rhs) {
rules[numRules].lhs = lhs;
strcpy(rules[numRules].rhs, rhs);
rules[numRules].numSymbols = strlen(rhs);
numRules++;
}
void calculateFirstSet(Symbol* symbol) {
if (symbol->firstSet != NULL) {
return;
}
symbol->firstSet = (char*) malloc(sizeof(char) * numSymbols);
memset(symbol->firstSet, 0, sizeof(char) * numSymbols);
for (int i = 0; i < numRules; i++) {
if (rules[i].lhs == symbol->symbol) {
if (rules[i].rhs[0] >= 'A' && rules[i].rhs[0] <= 'Z') { // Non-terminal symbol
calculateFirstSet(&symbols[rules[i].rhs[0] - 'A']);
for (int j = 0; j < numSymbols; j++) {
symbol->firstSet[j] |= symbols[rules[i].rhs[0] - 'A'].firstSet[j];
}
} else { // Terminal symbol
symbol->firstSet[rules[i].rhs[0] - 'a'] = 1;
}
}
}
}
void calculateFollowSet(Symbol* symbol) {
if (symbol->followSet != NULL) {
return;
}
symbol->followSet = (char*) malloc(sizeof(char) * numSymbols);
memset(symbol->followSet, 0, sizeof(char) * numSymbols);
if (symbol->symbol == rules[0].lhs) { // Start symbol
symbol->followSet['$' - 'a'] = 1;
}
for (int i = 0; i < numRules; i++) {
for (int j = 0; j < rules[i].numSymbols; j++) {
if (rules[i].rhs[j] == symbol->symbol) {
if (j == rules[i].numSymbols - 1) { // Last symbol in the rule
if (rules[i].lhs != symbol->symbol) { // Avoid infinite recursion
calculateFollowSet(&symbols[rules[i].lhs - 'A']);
for (int k = 0; k < numSymbols; k++) {
symbol->followSet[k] |= symbols[rules[i].lhs - 'A'].followSet[k];
}
}
} else {
if (rules[i].rhs[j + 1] >= 'A' && rules[i].rhs[j + 1] <= 'Z') { // Next symbol is non-terminal
calculateFirstSet(&symbols[rules[i].rhs[j + 1] - 'A']);
for (int k = 0; k < numSymbols; k++) {
symbol->followSet[k] |= symbols[rules[i].rhs[j + 1] - 'A'].firstSet[k];
}
if (symbols[rules[i].rhs[j + 1] - 'A'].firstSet['$' - 'a']) { // Next symbol can be empty
if (rules[i].lhs != symbol->symbol) { // Avoid infinite recursion
calculateFollowSet(&symbols[rules[i].lhs - 'A']);
for (int k = 0; k < numSymbols; k++) {
symbol->followSet[k] |= symbols[rules[i].lhs - 'A'].followSet[k];
}
}
}
} else { // Next symbol is terminal
symbol->followSet[rules[i].rhs[j + 1] - 'a'] = 1;
}
}
}
}
}
}
void calculateSelectSet(int ruleIndex, char* selectSet) {
memset(selectSet, 0, sizeof(char) * numSymbols);
if (rules[ruleIndex].rhs[0] >= 'A' && rules[ruleIndex].rhs[0] <= 'Z') { // First symbol is non-terminal
for (int i = 0; i < numSymbols; i++) {
selectSet[i] |= symbols[rules[ruleIndex].rhs[0] - 'A'].firstSet[i];
}
if (symbols[rules[ruleIndex].rhs[0] - 'A'].firstSet['$' - 'a']) { // First symbol can be empty
for (int i = 0; i < numSymbols; i++) {
selectSet[i] |= symbols[rules[ruleIndex].lhs - 'A'].followSet[i];
}
}
} else { // First symbol is terminal
selectSet[rules[ruleIndex].rhs[0] - 'a'] = 1;
}
}
void printSet(char* set) {
for (int i = 0; i < numSymbols; i++) {
if (set[i]) {
printf("%c ", symbols[i].symbol);
}
}
printf("\n");
}
int main() {
addSymbol('E');
addSymbol('T');
addSymbol('F');
addSymbol('+');
addSymbol('*');
addSymbol('(');
addSymbol(')');
addSymbol('i');
addProduction('E', "E+T");
addProduction('E', "T");
addProduction('T', "T*F");
addProduction('T', "F");
addProduction('F', "(E)");
addProduction('F', "i");
for (int i = 0; i < numSymbols; i++) {
calculateFirstSet(&symbols[i]);
calculateFollowSet(&symbols[i]);
}
printf("First(E): ");
printSet(symbols['E' - 'A'].firstSet);
printf("First(T): ");
printSet(symbols['T' - 'A'].firstSet);
printf("First(F): ");
printSet(symbols['F' - 'A'].firstSet);
printf("Follow(E): ");
printSet(symbols['E' - 'A'].followSet);
printf("Follow(T): ");
printSet(symbols['T' - 'A'].followSet);
printf("Follow(F): ");
printSet(symbols['F' - 'A'].followSet);
char selectSet[MAX_SYMBOLS];
for (int i = 0; i < numRules; i++) {
calculateSelectSet(i, selectSet);
printf("Select(%c -> %s): ", rules[i].lhs, rules[i].rhs);
printSet(selectSet);
}
return 0;
}
在上述代码中，我们首先定义了Production和Symbol结构体来表示产生式和文法符号。rules和symbols数组分别存储所有的产生式和文法符号。
addSymbol函数用于将文法符号添加到symbols数组中。addProduction函数用于将产生式添加到rules数组中。
calculateFirstSet函数用于计算文法符号的First集。对于每个非终结符，我们遍历所有的产生式，如果产生式的左部等于该非终结符，则将产生式右部的第一个符号的First集合并到该非终结符的First集中。如果产生式的右部的第一个符号是终结符，则将该终结符加入到该非终结符的First集中。
calculateFollowSet函数用于计算文法符号的Follow集。对于每个文法符号，我们遍历所有的产生式，查找该文法符号在产生式右部出现的位置，然后根据产生式右部的下一个符号的类型（非终结符或终结符）来决定如何计算Follow集。如果产生式右部的下一个符号是非终结符，则将该非终结符的First集合并到该文法符号的Follow集中。如果产生式右部的下一个符号是终结符，则将该终结符加入到该文法符号的Follow集中。
calculateSelectSet函数用于计算产生式的Select集。对于给定的产生式，我们根据产生式右部的第一个符号的类型（非终结符或终结符）来决定如何计算Select集。如果产生式右部的第一个符号是非终结符，则将该非终结符的First集合并到Select集中。如果产生式右部的第一个符号是终结符，则将该终结符加入到Select集中。
最后，我们使用printSet函数来打印First集、Follow集和Select集。
在main函数中，我们首先添加了所有的文法符号和产生式。然后，我们通过调用calculateFirstSet和calculateFollowSet函数来计算所有文法符号的First集和Follow集。最后，我们使用calculateSelectSet函数来计算所有产生式的Select集，并使用printSet函数打印结果。
请注意，上述代码只是一个简单的示例，只支持少量的文法符号和产生式。您可以根据实际需求进行扩展和修改
原文地址: https://www.cveoy.top/t/topic/hBFx 著作权归作者所有。请勿转载和采集!