LL语法分析c实现first集follow集分析表分析栈.docx
《LL语法分析c实现first集follow集分析表分析栈.docx》由会员分享，可在线阅读，更多相关《LL语法分析c实现first集follow集分析表分析栈.docx（33页珍藏版）》请在冰点文库上搜索。
LL语法分析c实现first集follow集分析表分析栈
//LL
（1）文法（源代码）
#include"stdio.h"
#include"stdlib.h"
#defineMaxRuleNum8
#defineMaxVnNum5
#defineMaxVtNum5
#defineMaxStackDepth20
#defineMaxPLength20
#defineMaxStLength50
structpRNode/*产生式右部结构*/
{
intrCursor;
structpRNode*next;
};
structpNode
{
intlCursor;
intrLength;/*右部长度*/
structpRNode*rHead;/*右部结点头指针*/
};
charVn[MaxVnNum+1];/*非终结符集*/
intvnNum;
charVt[MaxVtNum+1];/*终结符集*/
intvtNum;
structpNodeP[MaxRuleNum];
intPNum;
charbuffer[MaxPLength+1];
charch;
charst[MaxStLength];/*要分析的符号串*/
structcollectNode
{
intnVt;
structcollectNode*next;
};
structcollectNode*first[MaxVnNum+1];/*first集*/
structcollectNode*follow[MaxVnNum+1];/*follow集*/
intanalyseTable[MaxVnNum+1][MaxVtNum+1+1];
intanalyseStack[MaxStackDepth+1];/*分析栈*/
inttopAnalyse;/*分析栈顶*/
voidInit（）;/*初始化*/
intIndexCh（charch）;
voidInputVt（）;/*输入终结符*/
voidInputVn（）;/*输入非终结符*/
voidShowChArray（char*collect,intnum）;/*输出Vn或Vt的内容*/
voidInputP（）;/*产生式输入*/
boolCheckP（char*st）;/*判断产生式正确性*/
voidFirst（intU）;
voidAddFirst（intU,intnCh）;/*加入first集*/
boolHaveEmpty（intnVn）;
voidFollow（intV）;/*计算follow集*/
voidAddFollow（intV,intnCh,intkind）;
voidShowCollect（structcollectNode**collect）;/*输出first或follow集*/
voidFirstFollow（）;/*计算first和follow*/
voidCreateAT（）;/*构造预测分析表*/
voidShowAT（）;/*输出分析表*/
voidIdentify（char*st）;
voidInitStack（）;
voidShowStack（）;
voidPop（）;
voidPush（intr）;
intmain（）
{
chartodo,ch;
Init（）;
InputVn（）;
InputVt（）;
InputP（）;
getchar（）;
FirstFollow（）;
printf（"所得first集为：
"）;
ShowCollect（first）;
printf（"所得follow集为：
"）;
ShowCollect（follow）;
CreateAT（）;
ShowAT（）;
todo='y';
while（'y'==todo）
{
printf（"\n是否继续进行句型分析？
（y/n）:
"）;
todo=getchar（）;
while（'y'!
=todo&&'n'!
=todo）
{
printf（"\n（y/n）?
"）;
todo=getchar（）;
}
if（'y'==todo）
{
inti;
InitStack（）;
printf（"请输入符号串（以#结束）:
"）;
ch=getchar（）;
i=0;
while（'#'!
=ch&&i{
if（''!
=ch&&'\n'!
=ch）
{
st[i++]=ch;
}
ch=getchar（）;
}
if（'#'==ch&&i{
st[i]=ch;
Identify（st）;
}
else
printf（"输入出错！
\n"）;
}
}
getchar（）;
}
voidInit（）
{
inti,j;
vnNum=0;
vtNum=0;
PNum=0;
for（i=0;i<=MaxVnNum;i++）
Vn[i]='\0';
for（i=0;i<=MaxVtNum;i++）
Vt[i]='\0';
for（i=0;i{
P[i].lCursor=NULL;
P[i].rHead=NULL;
P[i].rLength=0;
}
PNum=0;
for（i=0;i<=MaxPLength;i++）
buffer[i]='\0';
for（i=0;i{
first[i]=NULL;
follow[i]=NULL;
}
for（i=0;i<=MaxVnNum;i++）
{
for（j=0;j<=MaxVnNum+1;j++）
analyseTable[i][j]=-1;
}
}
intIndexCh（charch）
{
intn;
n=0;/*isVn?
*/
while（ch!
=Vn[n]&&'\0'!
=Vn[n]）
n++;
if（'\0'!
=Vn[n]）
return100+n;
n=0;/*isVt?
*/
while（ch!
=Vt[n]&&'\0'!
=Vt[n]）
n++;
if（'\0'!
=Vt[n]）
returnn;
return-1;
}
/*输出Vn或Vt的内容*/
voidShowChArray（char*collect）
{
intk=0;
while（'\0'!
=collect[k]）
{
printf（"%c",collect[k++]）;
}
printf（"\n"）;
}
/*输入非终结符*/
voidInputVn（）
{
intinErr=1;
intn,k;
charch;
while（inErr）
{
printf（"\n请输入所有的非终结符，注意：
"）;
printf（"请将开始符放在第一位，并以#号结束:
\n"）;
ch='';
n=0;
/*初始化数组*/
while（n{
Vn[n++]='\0';
}
n=0;
while（（'#'!
=ch）&&（n{
if（''!
=ch&&'\n'!
=ch&&-1==IndexCh（ch））
{
Vn[n++]=ch;
vnNum++;
}
ch=getchar（）;
}
Vn[n]='#';/*以“#”标志结束用于判断长度是否合法*/
k=n;
if（'#'!
=ch）
{
if（'#'!
=（ch=getchar（）））
{
while（'#'!
=（ch=getchar（）））
;
printf（"\n符号数目超过限制！
\n"）;
inErr=1;
continue;
}
}
/*正确性确认，正确则，执行下下面，否则重新输入*/
Vn[k]='\0';
ShowChArray（Vn）;
ch='';
while（'y'!
=ch&&'n'!
=ch）
{
if（'\n'!
=ch）
{
printf（"输入正确确认?
（y/n）:
"）;
}
scanf（"%c",&ch）;
}
if（'n'==ch）
{
printf（"录入错误重新输入！
\n"）;
inErr=1;
}
else
{
inErr=0;
}
}
}
/*输入终结符*/
voidInputVt（）
{
intinErr=1;
intn,k;
charch;
while（inErr）
{
printf（"\n请输入所有的终结符，注意：
"）;
printf（"以#号结束:
\n"）;
ch='';
n=0;
/*初始化数组*/
while（n{
Vt[n++]='\0';
}
n=0;
while（（'#'!
=ch）&&（n{
if（''!
=ch&&'\n'!
=ch&&-1==IndexCh（ch））
{
Vt[n++]=ch;
vtNum++;
}
ch=getchar（）;
}
Vt[n]='#';
k=n;
if（'#'!
=ch）
{
if（'#'!
=（ch=getchar（）））
{
while（'#'!
=（ch=getchar（）））
;
printf（"\n符号数目超过限制！
\n"）;
inErr=1;
continue;
}
}
Vt[k]='\0';
ShowChArray（Vt）;
ch='';
while（'y'!
=ch&&'n'!
=ch）
{
if（'\n'!
=ch）
{
printf（"输入正确确认?
（y/n）:
"）;
}
scanf（"%c",&ch）;
}
if（'n'==ch）
{
printf（"录入错误重新输入！
\n"）;
inErr=1;
}
else
{
inErr=0;
}
}
}
/*产生式输入*/
voidInputP（）
{
charch;
inti=0,n,num;
printf（"请输入文法产生式的个数：
"）;
scanf（"%d",&num）;
PNum=num;
getchar（）;/*消除回车符*/
printf（"\n请输入文法的%d个产生式,并以回车分隔每个产生式：
",num）;
printf（"\n"）;
while（i{
printf（"第%d个：
",i）;
/*初始化*/
for（n=0;nbuffer[n]='\0';
/*输入产生式串*/
ch='';
n=0;
while（'\n'!
=（ch=getchar（））&&n{
if（''!
=ch）
buffer[n++]=ch;
}
buffer[n]='\0';
if（CheckP（buffer））
{
pRNode*pt,*qt;
P[i].lCursor=IndexCh（buffer[0]）;
pt=（pRNode*）malloc（sizeof（pRNode））;
pt->rCursor=IndexCh（buffer[3]）;
pt->next=NULL;
P[i].rHead=pt;
n=4;
while（'\0'!
=buffer[n]）
{
qt=（pRNode*）malloc（sizeof（pRNode））;
qt->rCursor=IndexCh（buffer[n]）;
qt->next=NULL;
pt->next=qt;
pt=qt;
n++;
}
P[i].rLength=n-3;
i++;
}
else
printf（"输入符号含非法在成分，请重新输入！
\n"）;
}
}
/*判断产生式正确性*/
boolCheckP（char*st）
{
intn;
if（100>IndexCh（st[0]））
returnfalse;
if（'-'!
=st[1]）
returnfalse;
if（'>'!
=st[2]）
returnfalse;
for（n=3;'\0'!
=st[n];n++）
{
if（-1==IndexCh（st[n]））
returnfalse;
}
returntrue;
}
voidFirst（intU）
{
inti,j;
for（i=0;i{
if（P[i].lCursor==U）
{
structpRNode*pt;
pt=P[i].rHead;
j=0;
while（j{
if（100>pt->rCursor）
{
AddFirst（U,pt->rCursor）;
break;
}
else
{
if（NULL==first[pt->rCursor-100]）
{
First（pt->rCursor）;
}
AddFirst（U,pt->rCursor）;
if（!
HaveEmpty（pt->rCursor））
{
break;
}
else
{
pt=pt->next;
}
}
j++;
}
if（j>=P[i].rLength）/*当产生式右部都能推出空时*/
AddFirst（U,-1）;
}
}
}
/*加入first集*/
voidAddFirst（intU,intnCh）
{
structcollectNode*pt,*qt;
intch;/*用于处理Vn*/
pt=NULL;
qt=NULL;
if（nCh<100）
{
pt=first[U-100];
while（NULL!
=pt）
{
if（pt->nVt==nCh）
break;
else
{
qt=pt;
pt=pt->next;
}
}
if（NULL==pt）
{
pt=（structcollectNode*）malloc（sizeof（structcollectNode））;
pt->nVt=nCh;
pt->next=NULL;
if（NULL==first[U-100]）
{
first[U-100]=pt;
}
else
{
qt->next=pt;/*qt指向first集的最后一个元素*/
}
pt=pt->next;
}
}
else
{
pt=first[nCh-100];
while（NULL!
=pt）
{
ch=pt->nVt;
if（-1!
=ch）
{
AddFirst（U,ch）;
}
pt=pt->next;
}
}
}
boolHaveEmpty（intnVn）
{
if（nVn<100）
returnfalse;
structcollectNode*pt;
pt=first[nVn-100];
while（NULL!
=pt）
{
if（-1==pt->nVt）
returntrue;
pt=pt->next;
}
returnfalse;
}
voidFollow（intV）
{
inti;
structpRNode*pt;
if（100==V）/*当为初始符时*/
AddFollow（V,-1,0）;
for（i=0;i{
pt=P[i].rHead;
while（NULL!
=pt&&pt->rCursor!
=V）
pt=pt->next;
if（NULL!
=pt）
{
pt=pt->next;
if（NULL==pt）
{
if（NULL==follow[P[i].lCursor-100]&&P[i].lCursor!
=V）
{
Follow（P[i].lCursor）;
}
AddFollow（V,P[i].lCursor,0）;
}
else
{
while（NULL!
=pt&&HaveEmpty（pt->rCursor））
{
AddFollow（V,pt->rCursor,1）;
pt=pt->next;
}
if（NULL==pt）
{
if（NULL==follow[P[i].lCursor-100]&&P[i].lCursor!
=V）
{
Follow（P[i].lCursor）;
}
AddFollow（V,P[i].lCursor,0）;
}
else
{
AddFollow（V,pt->rCursor,1）;
}
}
}
}
}
voidAddFollow（intV,intnCh,intkind）
{
structcollectNode*pt,*qt;
intch;
pt=NULL;
qt=NULL;
if（nCh<100）/*为终结符时*/
{
pt=follow[V-100];
while（NULL!
=pt）
{
if（pt->nVt==nCh）
break;
else
{
qt=pt;
pt=pt->next;
}
}
if（NULL==pt）
{
pt=（structcollectNode*）malloc（sizeof（structcollectNode））;
pt->nVt=nCh;
pt->next=NULL;
if（NULL==follow[V-100]）
{
follow[V-100]=pt;
}
else
{
qt->next=pt;/*qt指向follow集的最后一个元素*/
}
pt=pt->next;
}
}
else
{
if（0==kind）
{
pt=follow[nCh-100];
while（NULL!
=pt）
{
ch=pt->nVt;
AddFollow（V,ch,0）;
pt=pt->next;
}
}
else
{
pt=first[nCh-100];
while（NULL!
=pt）
{
ch=pt->nVt;
if（-1!
=ch）
{
AddFollow（V,ch,1）;
}
pt=pt->next;
}
}
}
}
/*输出first或follow集*/
voidShowCollect（structcollectNode**collect）
{
inti;
structcollectNode*pt;
i=0;
while（NULL!
=collect[i]）
{
pt=collect[i];
printf（"\n%c:
\t",Vn[i]）;
while（NULL!
=pt）
{
if（-1!
=pt->nVt）
{
printf（"%c",Vt[pt->nVt]）;
}
else
printf（"#"）;
pt=pt->next;
}
i++;
}
printf（"\n"）;
}
/*计算first和follow*/
voidFirstFollow（）
{
inti;
i=0;
while（'\0'!
=Vn[i]）
{
if（NULL==first[i]）
First（100+i）;
i++;
}
i=0;
while（'\0'!
=Vn[i]）
{
if（NULL==follow[i]）
Follow（100+i）;
i++;
}
}
/*构造预测分析表*/
voidCreateAT（）
{
inti;
structpRNode*pt;
structcollectNode*ct;
for（i=0;i{
pt=P[i].rHead;
while（NULL!
=pt&&HaveEmpty（pt->rCursor））
{
ct=first[pt->rCursor-100];
while（NULL!
=ct）
{
if（-1!
=ct->nVt）
analyseTable[P[i].lCursor-100][ct->nVt]=i;
ct
升级会员 