/*
* 该程序用于计算某个非终结符的 FIRST+ 集合
* RexfieldVon
* 2013年6月30日16:02:47
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h> /* 三级指针
* 第一级指向整个产生式组
* 第二级指向单个产生式
* 第三级指向产生式符号单元
* 约定：所有的大写字母为非终结符
* 假设：无左递归、FIRST集中不会出现重复符号
*/
char*** GrammerRule; /*
* 初始化文法序列
*/
void InitizationGrammerRule()
{
// 分配表头空间
GrammerRule = (char***)malloc(sizeof(int) * );
memset(GrammerRule, '\0', sizeof(int) * );
// 分配文法空间并写入产生式
// G -> E
GrammerRule['G'] = (char**)malloc(sizeof(int) * );
GrammerRule['G'][] = (char*)malloc();
memcpy(GrammerRule['G'][], "E\0", ); // E
GrammerRule['G'][] = NULL;
// E -> T F
GrammerRule['E'] = (char**)malloc(sizeof(int) * );
GrammerRule['E'][] = (char*)malloc();
memcpy(GrammerRule['E'][], "TF\0", ); // T F
GrammerRule['E'][] = NULL;
// F -> '+' T F | '-' T F | e
GrammerRule['F'] = (char**)malloc(sizeof(int) * );
GrammerRule['F'][] = (char*)malloc();
memcpy(GrammerRule['F'][], "+TF\0", ); // '+' T F
GrammerRule['F'][] = (char*)malloc();
memcpy(GrammerRule['F'][], "-TF\0", ); // '-' T F
GrammerRule['F'][] = (char*)malloc();
memcpy(GrammerRule['F'][], "\0", ); // e （该产生式存在但是为空）
GrammerRule['F'][] = NULL;
// T -> A U
GrammerRule['T'] = (char**)malloc(sizeof(int) * );
GrammerRule['T'][] = (char*)malloc();
memcpy(GrammerRule['T'][], "AU\0", ); // A U
GrammerRule['T'][] = NULL;
// U -> '*' A U | '/' A U | e
GrammerRule['U'] = (char**)malloc(sizeof(int) * );
GrammerRule['U'][] = (char*)malloc();
memcpy(GrammerRule['U'][], "*AU\0", ); // '*' A U
GrammerRule['U'][] = (char*)malloc();
memcpy(GrammerRule['U'][], "/AU\0", ); // '/' A U
GrammerRule['U'][] = (char*)malloc();
memcpy(GrammerRule['U'][], "\0", ); // e （该产生式存在但是为空）
GrammerRule['U'][] = NULL;
// A -> '(' E ')' | d | n
GrammerRule['A'] = (char**)malloc(sizeof(int) * );
GrammerRule['A'][] = (char*)malloc();
memcpy(GrammerRule['A'][], "(E)\0", ); // '(' E ')'
GrammerRule['A'][] = (char*)malloc();
memcpy(GrammerRule['A'][], "d\0", ); // d
GrammerRule['A'][] = (char*)malloc();
memcpy(GrammerRule['A'][], "n\0", ); // n
GrammerRule['A'][] = NULL;
} /*
* 取得终结符数量
*/
int GetTerminalCount()
{
int i, TerminalCount = ;
for (i = ; i < ; i++)
{
if (GrammerRule[i] != NULL)
{
int k = ;
while (GrammerRule[i][k] != NULL)
{
int n = ;
while (GrammerRule[i][k][n] != '\0')
{
char c = GrammerRule[i][k][n];
if (c < 'A' || c > 'Z')
{
TerminalCount++;
}
n++;
}
k++;
}
}
}
return TerminalCount;
} /*
* 递归取得 FIRST 集
* Token : char 需要打印的符号
* FIRST : char* FIRST集
* Ptr : int* FIRST集的位置指针
*/
void GetFIRST(char Token, char *FIRST, int *Ptr)
{
if (Token >= 'A' && Token <= 'Z' && GrammerRule[Token] != NULL)
{
int i = ;
while (GrammerRule[Token][i] != NULL)
{
GetFIRST(GrammerRule[Token][i++][], FIRST, Ptr);
}
}
else if (Token < 'A' || Token > 'Z')
{
FIRST[*Ptr] = Token;
*Ptr = *Ptr + ;
}
} /*
* 添加符号到 FOLLOW 集
* FOLLOW : char* FOLLOW集
* Ptr : int* FOLLOW集的位置指针
* NewItem : char 将加入的符号
*/
void AddFOLLOWItem(char *FOLLOW, int *Ptr, char NewItem)
{
int i = ;
for (; i < *Ptr; i++)
{
if (FOLLOW[i] == NewItem)
{
return ;
}
}
FOLLOW[*Ptr] = NewItem;
*Ptr = *Ptr + ;
} /*
* 取得 FOLLOW 集
* Unterminal : char 需要打印的非终结符
* FOLLOW : char* FOLLOW集
* Ptr : int* FOLLOW集的位置指针
* TerminalCount : int 终结符数量
*/
void GetFOLLOW(char Unterminal, char *FOLLOW, int *Ptr, int TerminalCount)
{
int RuleIndex, ExprIndex, TokenIndex;
// 开始遍历整个文法
for (RuleIndex = ; RuleIndex < ; RuleIndex++)
{
if (GrammerRule[RuleIndex] == NULL)
{
continue;
}
// 搜索整个文法找到指定的非终结符
for (ExprIndex = ; GrammerRule[RuleIndex][ExprIndex] != ; ExprIndex++)
{
for (TokenIndex = ; GrammerRule[RuleIndex][ExprIndex][TokenIndex] != '\0'; TokenIndex++)
{
if (GrammerRule[RuleIndex][ExprIndex][TokenIndex] == Unterminal)
{
char nc = GrammerRule[RuleIndex][ExprIndex][TokenIndex + ];
if (nc == '\0' && RuleIndex != Unterminal) // 情形三：反复计算：将FOLLOW(P)加入FOLLOW(U)
{
GetFOLLOW((char)RuleIndex, FOLLOW, Ptr, TerminalCount);
}
else if (nc >= 'A' && nc <= 'Z') // 情形二：间接计算：将FIRST(P)加入FOLLOW(U)
{
char *FIRST = (char*)malloc(TerminalCount + );
memset(FIRST, '\0', TerminalCount + );
int FIRSTPtr = , InsertPtr;
GetFIRST(nc, FIRST, &FIRSTPtr);
for (InsertPtr = ; InsertPtr < FIRSTPtr; InsertPtr++)
{
if (FIRST[InsertPtr] != '\0')
{
AddFOLLOWItem(FOLLOW, Ptr, FIRST[InsertPtr]);
}
else // 对于 P->... U B，FOLLOW ← FIRST(B) - <e> + FOLLOW(P)
{
GetFOLLOW((char)RuleIndex, FOLLOW, Ptr, TerminalCount);
}
}
}
else if (nc != '\0') // 情形一：直接计算：将终结符加入FOLLOW(U)
{
AddFOLLOWItem(FOLLOW, Ptr, nc);
}
}
}
}
}
} void GetFIRSTPlus(char Unterminal, int Index, char *FIRSTPlus, int *Ptr, int TerminalCount)
{
if (GrammerRule[Unterminal][Index] != NULL)
{
GetFIRST(GrammerRule[Unterminal][Index][], FIRSTPlus, Ptr);
int i = ;
while (i < *Ptr)
{
if (FIRSTPlus[i++] == '\0')
{
FIRSTPlus[*Ptr] = '\377';
*Ptr = *Ptr + ;
GetFOLLOW(Unterminal, FIRSTPlus, Ptr, TerminalCount);
break;
}
}
}
} /*
* 打印指定非终结符的 FIRST+ 集
* Unterminal : char 需要打印的非终结符
* TerminalCount : int 终结符数量
*/
void PrintUnterminalFIRSTPlus(char Unterminal, int TerminalCount)
{
char *FIRSTPlus = (char*)malloc(TerminalCount + );
memset(FIRSTPlus, '\0', TerminalCount + );
int Ptr, Index = , i;
for (; GrammerRule[Unterminal][Index] != NULL; Index++)
{
Ptr = ;
GetFIRSTPlus(Unterminal, Index, FIRSTPlus, &Ptr, TerminalCount);
printf("FIRST+(%c, %c): ", Unterminal, GrammerRule[Unterminal][Index][]);
for (i = ; i < Ptr; i++)
{
if (FIRSTPlus[i] == '\377')
{
printf("<eof> ");
}
else if (FIRSTPlus[i] == '\0')
{
printf("<e> ");
}
else
{
printf("%c ", FIRSTPlus[i]);
}
}
printf("\n");
}
} int main(int argc, char **argv)
{
InitizationGrammerRule(); // 初始化文法
int TerminalCount = GetTerminalCount();
PrintUnterminalFIRSTPlus('E', TerminalCount);
PrintUnterminalFIRSTPlus('F', TerminalCount);
PrintUnterminalFIRSTPlus('T', TerminalCount);
PrintUnterminalFIRSTPlus('U', TerminalCount);
PrintUnterminalFIRSTPlus('A', TerminalCount);
return ;
}