/*
* 该程序用于计算某个产生式的闭包
* RexfieldVon
* 2013年8月9日16:01:38
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h> #ifndef bool
# define bool char
#endif #ifndef true
# define true
#endif #ifndef false
# define false
#endif struct Collection
{
char LeftUnterminal; // 左非终结符
char *Expression; // 产生式
char PreviewSymbol; // 前瞻符号
bool Processed; // 是否被处理
struct Collection *next;
};
/* 三级指针
* 第一级指向整个产生式组
* 第二级指向单个产生式
* 第三级指向产生式符号单元
* 约定：①所有的大写字母为非终结符②所有小写字母为终结符③'\377'为eof④'\0'为ε⑤'\376'为占位符·
*/
char*** GrammerRule;
/*
* 文法书写约定：
* 每个字符串表示一个单独的产生式
* 第一个字符为产生式左边的非终结符，由初始化引擎进行产生式归并
* 整个文法以 null 结束
*/
char *Grammer[] =
{
"GL",
"LLP", "LP",
"P(P)", "P()",
"\0"
};
/*
* 初始化文法序列
*/
void InitizationGrammerRule()
{
// 分配表头空间
GrammerRule = (char***)malloc(sizeof(int) * );
memset(GrammerRule, '\0', sizeof(int) * );
// 扫描整个文法记录每个非终结符产生式的个数
int UnterminalOp[], index;
char Unterminal;
memset(UnterminalOp, '\0', * );
for (index = ; (Unterminal = Grammer[index][]) != '\0'; index++)
{
UnterminalOp[Unterminal]++;
}
// 写入产生式
for (index = ; (Unterminal = Grammer[index][]) != '\0'; index++)
{
if(GrammerRule[Unterminal] == NULL)
{
GrammerRule[Unterminal] = (char**)malloc(sizeof(int) * (UnterminalOp[Unterminal] + ));
memset(GrammerRule[Unterminal], '\0', sizeof(int) * (UnterminalOp[Unterminal] + ));
}
// 找到空位
int blank = ;
while (GrammerRule[Unterminal][blank] != '\0') {blank++;}
GrammerRule[Unterminal][blank] = &Grammer[index][];
}
} /*
* 取得终结符数量
* return 终结符的数量
*/
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 + ;
}
} /*
* 打印 LR(1) 项
* Item : struct Collection* 需要打印的项
*/
void PrintItem(struct Collection *Item)
{
printf("[%c ->", Item->LeftUnterminal);
int i = ;
for(; Item->Expression[i] != '\0'; i++)
{
printf(" ");
switch (Item->Expression[i])
{
case '\377':
printf("<eof>");
break;
case '\376':
printf("<@>");
break;
default:
printf("%c", Item->Expression[i]);
break;
}
}
if (Item->PreviewSymbol == '\377')
{
printf(", <eof>]\n");
}
else
{
printf(", %c]\n", Item->PreviewSymbol);
}
} /*
* 添加项到集合
* S : struct Collection* 项集
* LeftUnterminal : char 左非终结符
* Expression : char* 产生式
* PreviewSymbol : char 前瞻符号
*/
void AddItem(struct Collection *S, char LeftUnterminal, char *Expression, char PreviewSymbol)
{
static struct Collection *Tail = NULL;
if (Tail == NULL) {Tail = S;}
while (Tail->next != NULL) {Tail = Tail->next;}
// 检查是否重复
struct Collection *SPtr = S;
for (; SPtr != NULL; SPtr = SPtr->next)
{
if (SPtr->LeftUnterminal == LeftUnterminal &&
SPtr->PreviewSymbol == PreviewSymbol &&
strcmp(SPtr->Expression, Expression) == )
{
return;
}
}
struct Collection *NewItem = (struct Collection*)malloc(sizeof(struct Collection));
NewItem->LeftUnterminal = LeftUnterminal;
NewItem->Expression = strdup(Expression);
NewItem->PreviewSymbol = PreviewSymbol;
NewItem->next = NULL;
NewItem->Processed = false;
Tail->next = NewItem;
Tail = Tail->next;
} /*
* 闭包运算
* S : struct Collection* 项集
* TerminalCount : int 终结符个数
*/
void Closure(struct Collection *S, int TerminalCount)
{
bool CollectChanged;
struct Collection *Ptr = S;
do // while (S is still changing)
{
CollectChanged = false;
while (Ptr != NULL) // for each item [A->β·Cζ，α]∈S
{
PrintItem(Ptr);
char *Placeholder = strchr(Ptr->Expression, '\376');
if (Placeholder != NULL && *(Placeholder + ) != '\0') // 占位符不能在产生式尾
{
char Unterminal = *(Placeholder + );
if (Unterminal >= 'A' && Unterminal <= 'Z')
{
int ProductionIndex;
for (ProductionIndex = ; GrammerRule[Unterminal][ProductionIndex] != NULL; ProductionIndex++) // for each production C->γ∈P
{
char *FIRST = (char*)malloc(TerminalCount + ), FirstSymbol = *(Placeholder + );
FirstSymbol = (FirstSymbol != '\0')? FirstSymbol : Ptr->PreviewSymbol;
memset(FIRST, '\0', TerminalCount + );
int FIRSTCount = , i;
GetFIRST(FirstSymbol, FIRST, &FIRSTCount);
for (i = ; i < FIRSTCount; i++) // for each b∈FIRST(ζα)
{
if (FIRST[i] != '\0') // S <- S∪{[C->·γ,b]}
{
char *Expr = (char*)malloc();
Expr[] = '\376';
Expr[] = '\0';
Expr = strcat(Expr, GrammerRule[Unterminal][ProductionIndex]);
AddItem(S, Unterminal, Expr, FIRST[i]);
CollectChanged = true;
}
}
}
}
}
Ptr = Ptr->next;
}
}
while (CollectChanged == true);
} int main(int argc, char **argv)
{
InitizationGrammerRule(); // 初始化文法
int TerminalCount = GetTerminalCount();
struct Collection *S = (struct Collection*)malloc(sizeof(struct Collection));
S->LeftUnterminal = 'G';
S->Expression = "\376L";
S->PreviewSymbol = '\377';
S->next = NULL;
S->Processed = false;
Closure(S, TerminalCount);
return ;
}