语法分析器源代码.docx
《语法分析器源代码.docx》由会员分享，可在线阅读，更多相关《语法分析器源代码.docx（26页珍藏版）》请在冰点文库上搜索。
语法分析器源代码
#include
#include
#include
#defineHIGHER1
#defineLOWER-1
#defineEQUAL0
#defineTRUE1
#defineFALSE0
#defineOPER_NUM50//默认算符数目
#defineVN_NUM50//默认非终结符数目
#defineMAX_BUFFER128//每行输入行最大长度
#defineMAX_GRA_NUM20//最大文法数目
#defineEMPTY-2//算符优先表初始值，表示这对算符没有优先关系
#defineSTACK_SIZE64
typedefstruct
{
charc;//非终极符符号
intfirstvt[OPER_NUM];//firstvt集，保存算符在oper_list中的下标
intfir_n,last_n;
intlastvt[OPER_NUM];
}vn_t;
intprior_table[OPER_NUM][OPER_NUM];
charoper_list[OPER_NUM];
intoper_num=0;
vn_tvn_list[VN_NUM];
intvn_num=0;
char*grammar[MAX_GRA_NUM][2];
intgra_num=0;
charstart_vn;
charstack[STACK_SIZE];
inttop=0;
voidget_input（char*buf）;
intbuf_deal（char*buf）;
voidget_FIRVT_LASTVT（intvn_n）;
intcreate_table（）;
voidinit_table（）;
intanalyze（char*sentence）;
voiddisplay_table（）;
voiddisplay_fir_lastvt（）;
intget_oper（charc）;//得到算符c的数组下标没有返回-1
intget_vn（charc）;//得到非终结符c的数组下标，没有返回-1
intis_vn（chara）
{
return（（'A'<=a&&a<='Z'）?
1:
0）;
}
intget_oper（charc）
{
inti;
for（i=0;iif（oper_list[i]==c）
returni;
return-1;
}
intget_vn（charc）
{
inti;
for（i=0;iif（vn_list[i].c==c）
returni;
return-1;
}
charreduce（intstart,intend,intsize）//规约
{
char*tar,*g,t1,t2,left;
inti,j=0,gi,ti,cn=0;
intsame;
tar=（char*）malloc（sizeof（char）*MAX_BUFFER）;
if（!
tar）
{
printf（"Allocationfails.\n"）;
exit（-1）;
}
for（i=start;i<=end;++i）//将此最左素短语的终结符存入tar字符串
{
if（!
is_vn（stack[i]））
tar[j++]=stack[i];
}
tar[j++]='\0';
for（i=0;i{
g=grammar[i][1];
gi=0;
ti=0;
same=FALSE;
t1=g[gi];
t2=tar[ti];
while（t1!
='\0'）
{
if（t2=='\0'&&!
is_vn（t1））
{
same=FALSE;
break;
}
if（!
is_vn（t1））
{
if（t1!
=t2）{
same=FALSE;
break;
}
t2=tar[++ti];
same=TRUE;
}
t1=g[++gi];
}
if（same&&t2=='\0'）
break;
}
if（i==gra_num）
{
printf（"无法找到相应文法！
\n"）;
returnFALSE;
}
left=grammar[i][0][0];
returnvn_list[get_vn（left）].c;
}
intanalyze（char*sentence）
{
charr,c,new_vn;
inti=0,k=0,j,pi,printi=1,cou=1;//i是sentence[]和stack[]的索引
intr_index,s_index,pre_index;
printf（"\n\n规约过程如下表所示：
\n"）;
printf（"--------------------------------------\n"）;
stack[top++]='#';
printf（"序号\t符号栈\t最左素短语\t规约\t\n"）;
do
{
r=sentence[i++];
if（（r_index=get_oper（r））==-1）
{
printf（"Error:
您输入的字符不在文法定义中！
\n"）;
flushall（）;c=getchar（）;flushall（）;
returnFALSE;
}
if（!
is_vn（stack[k]））
{
j=k;
s_index=get_oper（stack[j]）;
}
else
{
j=k-1;
s_index=get_oper（stack[j]）;
}
while（prior_table[s_index][r_index]==HIGHER）
{
do
{
pre_index=s_index;
if（!
is_vn（stack[j-1]））
{
j--;
s_index=get_oper（stack[j]）;
}
else
{
j-=2;
s_index=get_oper（stack[j]）;
}
}while（prior_table[s_index][pre_index]!
=LOWER）;
printf（"%d\t",cou++）;
for（pi=0;pi{
printf（"%c",stack[pi]）;
}
printf（"\t"）;
for（pi=j+1;pi<=k;++pi）
{
if（pi==j+1）
printf（"%c",stack[pi]）;
else
printf（"%c",stack[pi]）;
}
if（（new_vn=reduce（j+1,k,k-j））==0）
{
returnFALSE;
}
printf（"\t\t%c\n",new_vn）;
k=j+1;//规约最左素短语
stack[k]=new_vn;
top=k+1;
}
if（prior_table[s_index][r_index]==LOWER||prior_table[s_index][r_index]==EQUAL）
{
stack[++k]=r;
top++;
}
else
{
printf（"Error:
您输入的句型有错误！
\n"）;
returnFALSE;
}
}while（r!
='#'）;
printf（"--------------------------------------\n"）;
returnTRUE;
}
intbuf_deal（char*buf）
{
inti=2,count=0;
charpre=buf[0],now;
char*left_g,*right_g,*new_buf;
left_g=（char*）malloc（sizeof（char）*2）;
right_g=（char*）malloc（sizeof（char）*（MAX_BUFFER-2））;
if（!
left_g||!
right_g）
{
printf（"Allocationfails.\n"）;
exit（-2）;
}
if（is_vn（pre））
{
if（get_vn（pre）==-1）
{
vn_list[vn_num].c=pre;
vn_list[vn_num].fir_n=0;
vn_list[vn_num].last_n=0;
vn_num++;
}
left_g[count]=pre;
count++;
left_g[count]='\0';
}
else
returnFALSE;
if（buf[1]!
='-'||buf[2]!
='>'）
returnFALSE;
pre=buf[2];
count=0;
while（（now=buf[++i]）!
='\0'）
{
if（now!
='|'）
{
right_g[count]=now;
count++;
if（is_vn（now）&&is_vn（pre））
returnFALSE;
if（is_vn（now））
{
if（get_vn（now）==-1）
{
vn_list[vn_num].c=now;
vn_list[vn_num].fir_n=0;
vn_list[vn_num].last_n=0;
vn_num++;
}
else
continue;
}
else
{
if（get_oper（now）==-1）
{
oper_list[oper_num]=now;
oper_num++;
}
else
continue;
}
pre=now;
}
else
{
right_g[count]='\0';
grammar[gra_num][0]=left_g;
grammar[gra_num][1]=right_g;
gra_num++;
break;
}
}
if（buf[i]=='\0'）
{
right_g[count]='\0';
grammar[gra_num][0]=left_g;
grammar[gra_num][1]=right_g;
gra_num++;
}
else
{
new_buf=（char*）malloc（sizeof（char）*MAX_BUFFER）;
new_buf[0]=left_g[0];
new_buf[1]='-';
new_buf[2]='>';
strcpy（&new_buf[3],&buf[++i]）;
returnbuf_deal（new_buf）;
}
returnTRUE;
}
intcreate_table（）
{
intgi=0,ti,ni,fi,li,i;
char*ng,t,next,next1;
intt_index,n_index,n_index1,n_vn,t_vn;
vn_ttemp;
for（gi=0;gi{
ng=grammar[gi][1];
t=ng[0];
ti=0;
t_index=get_oper（t）;
next=ng[1];
ni=1;
n_index=get_oper（next）;
while（next!
='\0'）
{
if（t_index!
=-1&&n_index!
=-1）
{
if（prior_table[t_index][n_index]==EMPTY）
prior_table[t_index][n_index]=EQUAL;
else
{
printf（"%c与%c有多种优先关系！
\n",oper_list[t_index],oper_list[n_index]）;
returnFALSE;
}
}
elseif（t_index!
=-1&&n_index==-1&&ng[ni+1]!
='\0'）
{
next1=ng[ni+1];
n_index1=get_oper（next1）;
if（prior_table[t_index][n_index1]==EMPTY）
prior_table[t_index][n_index1]=EQUAL;
else
{
printf（"%c与%c有多种优先关系！
\n",oper_list[t_index],oper_list[n_index1]）;
returnFALSE;
}
prior_table[t_index][oper_num-1]=-3;
prior_table[oper_num-1][n_index1]=-3;
}
if（t_index!
=-1&&n_index==-1）
{
n_vn=get_vn（next）;
temp=vn_list[n_vn];
for（fi=0;fi{
if（prior_table[t_index][temp.firstvt[fi]]==EMPTY）
prior_table[t_index][temp.firstvt[fi]]=LOWER;
else
{
printf（"%c与%c有多种优先关系！
\n",oper_list[t_index],oper_list[temp.firstvt[fi]]）;
returnFALSE;
}
}
}
elseif（t_index==-1&&n_index!
=-1）
{
n_vn=get_vn（t）;
temp=vn_list[n_vn];
for（fi=0;fi{
if（prior_table[temp.lastvt[fi]][n_index]==EMPTY）
prior_table[temp.lastvt[fi]][n_index]=HIGHER;
else
{
printf（"%c与%c有多种优先关系！
\n",oper_list[fi],oper_list[n_index]）;
returnFALSE;
}
}
}
t=ng[++ti];
next=ng[++ni];
t_index=get_oper（t）;
n_index=get_oper（next）;
}
}
for（i=0;i{
if（prior_table[oper_num-1][i]!
=-3）
prior_table[oper_num-1][i]=LOWER;
}
for（i=0;i{
if（prior_table[i][oper_num-1]!
=-3）
prior_table[i][oper_num-1]=HIGHER;
}
prior_table[oper_num-1][oper_num-1]=EQUAL;
returnTRUE;
}
voiddisplay_fir_lastvt（）
{
inti,j;
for（i=0;i{
printf（"FIRSTVT\（%c\）={",vn_list[i].c）;
for（j=0;j{
if（j==vn_list[i].fir_n-1）
printf（"%c",oper_list[vn_list[i].firstvt[j]]）;
else
printf（"%c,",oper_list[vn_list[i].firstvt[j]]）;
}
printf（"}\n"）;
printf（"LASTVT\（%c\）={",vn_list[i].c）;
for（j=0;j{
if（j==vn_list[i].last_n-1）
printf（"%c",oper_list[vn_list[i].lastvt[j]]）;
else
printf（"%c,",oper_list[vn_list[i].lastvt[j]]）;
}
printf（"}\n\n"）;
}
}
voiddisplay_table（）
{
inti,j;
printf（"\n\t算符"）;
for（i=0;iprintf（"\t%c",oper_list[i]）;
printf（"\n"）;
for（i=0;i{
printf（"\t%c",oper_list[i]）;
for（j=0;j{
if（prior_table[i][j]==1）
printf（"\t>"）;
elseif（prior_table[i][j]==-1）
printf（"\t<"）;
elseif（prior_table[i][j]==0）
printf（"\t="）;
else
printf（"\tNO"）;
}
printf（"\n"）;
}
}
voidfirstvt（intvn）
{
inti,j,t,c_index,v_i,orin,pre=-1;
char*ng,c;
for（i=0;i{
if（grammar[i][0][0]==vn_list[vn].c）
{
ng=grammar[i][1];
c=ng[0];
if（（c_index=get_oper（c））!
=-1）{
vn_list[vn].firstvt[vn_list[vn].fir_n++]=c_index;
continue;
}
else
{
v_i=get_vn（c）;
if（v_i!
=vn&&v_i!
=pre）
{
if（vn_list[v_i].fir_n==0）
firstvt（v_i）;
orin=vn_list[vn].fir_n;
vn_list[vn].fir_n+=vn_list[v_i].fir_n;
t=0;
for（j=orin;j{
vn_list[vn].firstvt[j]=vn_list[v_i].firstvt[t++];
}
}
pre=v_i;
if（ng[1]!
='\0'）
{
vn_list[vn].firstvt[vn_list[vn].fir_n++]=get_oper（ng[1]）;
}
}
}
}
}
voidlastvt（intvn）
{
inti,j,t,c_index,v_i,orin,ni=0,pre=-1;
c
升级会员 