优先表.doc
《优先表.doc》由会员分享，可在线阅读，更多相关《优先表.doc（7页珍藏版）》请在冰点文库上搜索。
本程序是使用C语言在TC2.0的环境下编写的编译原理中算符优先表的构造，供大家参考之用，切勿直接抄袭。
程序正确无误，若环境不同，则有可能发生错误，请确保编译环境为TC2.0。
要正确的运行本程序还需要将本文档最后的产生式存入chanshen.txt中。
程序亦有很多可以改进的地方，若有更好的方法，可以发信息给我，交流之用。
/*******************************************
题目：
构造优先表
作者：
Jolor（2008118228）
创建时间：
2011年4月19日
*******************************************/
#include
#include
#include
#defineMAX20
#defineNULL0
#defineTRUE1
#defineFALSE0
/******************************************
程序中所用到的结构体和变量
******************************************/
structno_sign/*非终结符的结构体*/
{
charbig_char;/*非终结符*/
charfirstvt[MAX];/*非终结符的FIRSTVT集合*/
charlastvt[MAX];/*非终结符的LASTVT集合*/
};
structsign/*终结符的结构体*/
{
charsmall_char;/*终结符*/
};
typedefstructchanshengshi/*产生式的结构体*/
{
charleft;/*产生式的左部*/
charright[MAX];/*产生式的右部*/
}chanshengshi;
structcandidate/*候选式结构体*/
{
charcandidate[MAX];/*候选式串*/
};
/******************************************
程序中所用到的变量
******************************************/
intno_sign_num=0;/*非终结符的数目*/
intsign_num=0;/*终结符的数目*/
intchanshengshi_num=0;/*产生式的数目*/
intcandidate_num=0;/*候选式的数目*/
intF[MAX][MAX];/*布尔数组F，行列为终结符号的数目*/
intL[MAX][MAX];/*布尔数组L，行列为终结符号的数目*/
charstart_sign;/*开始符号*/
structchanshengshiformular[MAX];/*产生式的集合*/
structno_signno_terminal[MAX];/*非终结符的集合*/
structsignterminal[MAX];/*终结符的集合*/
structcandidatecandi[MAX];/*候选式的结合*/
/******************************************
初始化函数
******************************************/
voidinit（）
{
}
/******************************************
分析文件中的产生式函数
******************************************/
voidanalysis（FILE*fp）
{
inti,j;/*循环变量*/
charsign;/*暂存一个字符*/
chartemp[MAX];/*存放字符串的临时数组*/
chanshengshi*p;/*产生式指针*/
sign=fgetc（fp）;
start_sign=sign;/*读取的第一个字符为开始符号*/
rewind（fp）;/*文件指针重新回到文件开始位置*/
while（fscanf（fp,"%s",temp）!
=-1）/*扫描文件，为产生式集合赋值*/
{
formular[chanshengshi_num].left=temp[0];
strcpy（formular[chanshengshi_num].right,temp+3）;
chanshengshi_num++;
}
/*printf（"Thenumberofchanshengshi:
%d.\n",chanshengshi_num）;*/
formular[chanshengshi_num].left=NULL;/*将产生式集合中的第一个空元素赋值，作为扫描结束标志*/
strcpy（formular[chanshengshi_num].right,""）;
for（p=formular;p->left!
=NULL;p++）
{
for（i=0;i if（p->left==no_terminal[i].big_char）
break;
if（i>=no_sign_num）/*将还没有在非终结符集合中非终结符加入集合*/
{
no_terminal[no_sign_num].big_char=p->left;
strcpy（no_terminal[no_sign_num].firstvt,""）;
strcpy（no_terminal[no_sign_num].lastvt,""）;
no_sign_num++;
}
for（i=0;p->right[i]!
=NULL;i++）/*扫描产生式的右部，将终结符加入终结符的集合*/
{
if（!
（p->right[i]<='Z'&&p->right[i]>='A'））/*去除非终结符号*/
{
for（j=0;j if（p->right[i]==terminal[j].small_char）
break;
if（j>=sign_num）/*将不在终结符集合中的终结符加入结合*/
{
terminal[sign_num].small_char=p->right[i];
sign_num++;
}
}
}
for（i=0;i if（strcmp（p->right,candi[i].candidate）==0）
break;
if（i>=candidate_num）/*将不在候选式集合中的候选式加入候选式集合*/
{
strcpy（candi[candidate_num].candidate,p->right）;
candidate_num++;
}
}
no_terminal[no_sign_num].big_char=NULL;/*为非终结符集合添加结束标志*/
strcpy（no_terminal[no_sign_num].firstvt,""）;
strcpy（no_terminal[no_sign_num].lastvt,""）;
sign_num++;
terminal[sign_num].small_char='#';/*为终结符集合添加‘#’标志*/
sign_num++;
terminal[sign_num].small_char=NULL;/*为终结符集合添加结束标志，最终的数目会为所有的终结符号数目+2*/
formular[chanshengshi_num].left=NULL;/*为产生式集合添加结束标志*/
strcpy（formular[chanshengshi_num].right,""）;
strcpy（candi[candidate_num].candidate,""）;/*为候选式集合添加结束标志*/
fclose（fp）;/*关闭文件*/
}
/******************************************
显示关于产生式、非终结符、终结符的详细信息
******************************************/
voidshow_chanshengshi（）
{
inti,j;
printf（"Thestart_sign:
%c\n",start_sign）;
printf（"Thenumberofno_terminal:
%d.\n",no_sign_num）;
printf（"Thenumberofterminal:
%d.\n",sign_num-2）;
printf（"Thenumberofchanshengshi:
%d.\n",chanshengshi_num）;
printf（"Theno_terminalare:
\n"）;
for（i=0;i printf（"%c",no_terminal[i].big_char）;
printf（"\n"）;
printf（"Theterminalare:
\n"）;
for（i=0;i printf（"%c",terminal[i].small_char）;
printf（"\n"）;
printf（"Thechanshengshi'srightare:
\n"）;
for（i=0;i printf（"%s\n",formular[i].right）;
printf（"Thenumberofcandidate:
%d.\n",candidate_num）;
for（i=0;i printf（"%s\n",candi[i].candidate）;
printf（"TheF[][]is:
\n"）;
for（i=0;i {
for（j=0;j printf（"%d",F[i][j]）;
printf（"\n"）;
}
}
/******************************************
形成布尔数组F（P，a）（正确）
******************************************/
voidproduce_F（）
{
inti,j,s;
chartemp[MAX];/*暂存右部字符串*/
chanshengshi*p;
for（i=0;i for（j=0;j F[i][j]=0;
for（i=0;i for（j=0;j {
for（s=0;formular[s].left!
=NULL;s++）
if（formular[s].left==no_terminal[i].big_char）
{
strcpy（temp,formular[s].right）;/*将产生式的右部存入临时数组*/
if（temp[0]==terminal[j].small_char）/*筛选有形如P->a的产生式，并将F【P】【a】置为真*/
F[i][j]=TRUE;
if（temp[0]<='Z'&&temp[0]>='A'）/*筛选有形如P->Qa的产生式，并将F【P】【a】置为真*/
{
if（temp[1]==terminal[j].small_char）
F[i][j]=TRUE;
}
}
}
}
/******************************************
形成布尔数组L（P，a）（正确）
******************************************/
voidproduce_L（）
{
inti,j,s,d;
chartemp[MAX];/*暂存右部字符串*/
chanshengshi*p;
for（i=0;i for（j=0;j L[i][j]=0;
for（i=0;i for（j=0;j {
for（s=0;formular[s].left!
=NULL;s++）
if（formular[s].left==no_terminal[i].big_char）
{
strcpy（temp,formular[s].right）;/*将产生式的右部存入临时数组*/
for（d=0;d if（temp[d]==NULL）break;/*找到产生式的右部的结束位置*/
if（temp[d-1]==terminal[j].small_char）/*筛选有形如P->...a的产生式，并将F【P】【a】置为真*/
F[i][j]=TRUE;
if（temp[d-1]<='Z'&&temp[d-1]>='A'）/*筛选有形如P->...aQ的产生式，并将F【P】【a】置为真*/
{
if（temp[d-2]==terminal[j].small_char）
F[i][j]=TRUE;
}
}
}
printf（"TheL[][]is:
\n"）;
for（i=0;i {
for（j=0;j printf（"%d",L[i][j]）;
printf（"\n"）;
}
}
/******************************************
主函数
******************************************/
voidmain（）
{
inti,j;/*循环变量*/
charsign;/*暂存一个字符*/
chartemp[MAX];/*存放字符串的临时数组*/
chanshengshi*p;/*产生式指针*/
FILE*fp;
if（（fp=fopen（"chansheng.txt","r"））==NULL）
{
printf（"Sorry,can'topenthefile.\n"）;/*读取文件不成功退出*/
return;
}
analysis（fp）;
produce_F（）;
produce_L（）;
getch（）;
}
/*使用的产生式，需存入chanshen.txt，需注意保存的路径*/
/*E->TA*/
/*A->+TA*/
/*T->FB*/
/*B->*FB*/
/*F->（E）*/
/*F->i*/
升级会员 