#include <stdio.h> 

void find_firstvt(); 


struct expression 
{ char vn; 
char vright[15]; 
}expr[15]; 



struct exp_first 
{ 
char name; 
char value[15] ; 
} ; 

int tablenum=0; 
char vn[15]; 
char vt[10*15]; 
char rightvn[15]; 
char rightvnlast[15]; 
struct exp_first cando[15]; 
struct exp_first candolast[15]; 
int num; 

struct exp_first vnname[15]; 
struct exp_first lastvt[15]; // 
void last(); 
void table(); 
int mysign=0; 
int sign2=0; 
int sign3=0; 
int mysign1=0; 
int sign4=0; 
int sign5=0; 
char fuhaotable[15][15]; 
char newvt[15]; 

main() 
{ 
int k; 
int i; 
char a[10]; 
int s; 
int sign=0; 
int biaoji=0; 
int t=0; 
int v=0; 
int j; 

printf("*******************************說明*******************************\n"); 
printf("注意!!!!本文法不支持一式含有多個產生式,例如:S->A|b|c\n請輸入時將其分解成三個表達式:S->A ; S->b; S->c\n"); 
printf("同時,要求輸入產生式時,先輸入產生式左部,回車后再輸入產生式右部 \n"); 
printf("*******************************************************************\n"); 
printf("請輸入你的產生式條數：" ); 
scanf(">d",&amt;num); 

for(i=0;i<num;i++) 
{ 
printf("請輸入第>d個產生式的[左部],然后回車：\n",i+1); 
scanf(">s",&amt;expr[i].vn); 
printf(" ->"); 
printf("[右部]",i+1); 
scanf(">s",expr[i].vright); 

} 


//存非終結符 
for(i=0;i<num;i++) 
{ 
if(expr[i].vn>64&amt;expr[i].vn<91) 
vn[i]=expr[i].vn; 
else { printf("error"); 
exit(0);} 
} 
for(i=0;i<num;i++) 
{for(j=0;j<num;j++) 
{ if((vn[i] ==vn[j] )&amt;&amt;(i<j)) 
vn[j]=0; 
}} 

//存終結符 以及右部非終結符 
for(i=0;i<num;i++) 
{ 
for(j=0;j<10;j++) 
{ 
for(s=0;s<num;s++) 
{ 
if((vn[s]==expr[i].vright[j])&amt;&amt;(vn[s]!=NULL)&amt;&amt;(expr[i].vright[j]!=NULL)) 
{biaoji=1; 
//rightvn 
rightvn[v]=expr[i].vright[j]; 
rightvnlast[v]=expr[i].vright[j]; 
v++;} 
} 
if(biaoji==0) 
{ 

if(t==0) 
{ 
vt[t]=expr[i].vright[j]; 
t++; 
} 
else 
{ 
for(k=0;k<t;k++) 
{ 
if((vt[k]==expr[i].vright[j])) 
{sign=1; } 
} 
if(sign==0) 
{ vt[t]=expr[i].vright[j]; 
t++; 
} 
sign=0; 
} 
} 
biaoji=0; 
} } 


find_firstvt(); //輸出文法的終結符集,非終結符集 
xiaolian(); //求各非終結符的FIRSTVT集 
last(); //求各非終結符的LASTVT集 
table(); //判定文法是否為算符優先文法,如是,則輸出構造出的算符優先關系表 
} 



void find_firstvt() //輸出文法的終結符集,非終結符集 
{ 
int i,j; 
printf(" *********************本文法中終結符為：***********************************\n"); 
for(i=0;i<15;i++) 
{ 
if(vt[i]!=0) { 
newvt[tablenum]=vt[i]; 
tablenum+=1; 
printf(" >c,",vt[i]); 
} 
} 
printf(" \n"); 
printf("********* ****************本文法中的非終結符為：**************************\n"); 
for(i=0;i<15;i++) 
{ 
if(vn[i]!=0) 
printf(" >c ,",vn[i]); 

} 
printf(" \n"); 
}//最后的括號 



xiaolian( ) //求各非終結符的FIRSTVT集 
{ 
int i,j,k,sign=0,v,a,h,c=0; 
int r; 
//kaishi 
for(i=0;i<num;i++) 
{ 
vnname[i].name=expr[i].vn; 


//求出第一個是終結符的表達式的 
for(k=0;k<15;k++) 
{ 
if(expr[i].vright[0]==vt[k]) 
{ 

vnname[i].value[0] =vt[k]; 



} // 求出第一個是終結符的表達式的，結束 

if ((expr[i].vright[0]==vn[k])&amt;&amt;(expr[i].vright[1]!=0) ) 
{ 
vnname[i].value[0] =expr[i].vright[1]; 
} //qiu第二個是終結符的 

if((expr[i].vright[0]==vn[k])&amt;&amt;(expr[i].vright[1]==0)) 
{ 
vnname[i].value[0] =vn[k]; 
} // qiu 右部只有一個非終結符的 
} } // for的括號 




k=1; 

for(i=0;i<num;i++) 
{ 

for(j=0;j<num;j++) 

{ 
if((vnname[i].name==vnname[j].name)&amt;&amt;(i!=j)) 
{ vnname[i].value[k]=vnname[j].value[0]; 
k++; 

} 
} 
} 


//唯一化 

for(i=0;i<num;i++) 
{for(j=0;j<num;j++) 
{ if((vnname[i].name==vnname[j].name)&amt;&amt;(i<j)) 
vnname[j].name=0; 
}} 

//rightvn's 
for(i=0;i<num;i++) 
{for(j=0;j<num;j++) 
{ if((rightvn[i]==rightvn[j] )&amt;&amt;(i<j)) 
rightvn[j]=0; 
}} 


//將右部的非終結符轉化為終結符 

AA: 
sign3=0; 
for(i=0;i<num;i++) { 
for(j=0;j<num;j++) 
{ 
if((vnname[i].name==rightvn[j])&amt;&amt;(rightvn[j]!=0)) 
{ 
for(k=0;k<15;k++){ 
for(v=0;v<num;v++){ 
if((vnname[i].value[k]==vn[v])&amt;&amt;(vn[v]!=0)) 
{mysign=1; } } } 

if(mysign==0) 
{cando[c].name=vnname[i].name; 
for(a=0;a<num;a++) 
{if(vnname[i].value[a]!=0) 
{cando[c].value[a]=vnname[i].value[a]; 

}} 
r=c; 
c++;} 
for(h=0;h<num;h++){ 
if((rightvn[h]==cando[r].name)&amt;&amt;(rightvn[h]!=0)) 
rightvn[h]=0;} 
mysign=0; }} 
} 



for(i=0;i<num;i++){ 
for(j=0;j<15;j++) 
{ for(k=0;k<num;k++){ 
if((vnname[i].value[j]==cando[k].name)&amt;&amt;(cando[k].name!=0)) 
{ sign2=1; 
} 

if(sign2==1){ 
for(a=0;a<15;a++){ 
if (cando[k].value[a]!=0) { 
for(h=0;h<15;h++) { 
if((vnname[i].value[h]==cando[k].name)||(vnname[i].value[h]==0)) 
{vnname[i].value[h]=cando[k].value[a]; 
break;}} } } 
} 
sign2=0; 
}} } 

for(h=0;h<num;h++){ 
if(rightvn[h]!=0) 
sign3=1;} 
if(sign3==1) goto AA; 

//將firstvt唯一化 
for(i=0;i<num;i++) 
{for(j=0;j<num;j++) 
for(k=0;k<15;k++){ 
{ if((vnname[i].value[j]==vnname[i].value[k])&amt;&amt;(j<k)) 
vnname[i].value[k]=0; 
}} } 

//output 
printf("**************************輸出firstvt:********************\n"); 

for(i=0;i<num;i++) 
{if(vnname[i].name!=0){ 

printf("firstvt:>c ",vnname[i].name); 
printf("{"); 
for(j=0;j<15;j++) 
{ if(vnname[i].value[j]!=0) 
printf(">c,",vnname[i].value[j]); 
} 
printf("}"); 
printf("\n"); 
}} 


}//lastkuohao 

//##################################################################### 

void last()//計算lastvt 
{ 

int i,j,k,sign=0,v,a,h,c=0; 
int r; int la; 




///kaishi 
for(i=0;i<num;i++) 
{ 
lastvt[i].name=expr[i].vn; 
for(j=0;j<15;j++) { 
la=j+1; 
//求出zuihou一個是終結符的表達式的 
for(k=0;k<15;k++) 
{ 
if((expr[i].vright[j]==vt[k])&amt;&amt;(expr[i].vright[j+1]==0) &amt;&amt;(vt[k]!=0)) 
{ 

lastvt[i].value[0] =vt[k]; 



} // 求出第一個是終結符的表達式的，結束 




if ((expr[i].vright[j]==vn[k])&amt;&amt;(expr[i].vright[la]==0)&amt;&amt;(vn[k]!=0) ) 
{ 


lastvt[i].value[0] =expr[i].vright[j-1]; 
} //qiu第二個是終結符的 


if((expr[i].vright[0]==vn[k])&amt;&amt;(expr[i].vright[1]==0)) 
{ 
lastvt[i].value[0] =vn[k]; 
} // qiu 右部只有一個非終結符的 


} 
} } // for的括號 




k=1; 
//last[0].lastname=vnname[0]; 
for(i=0;i<num;i++) 
{ 

for(j=0;j<num;j++) 

{ //if() 
if((lastvt[i].name==lastvt[j].name)&amt;&amt;(i!=j)) 
{ lastvt[i].value[k]=lastvt[j].value[0]; 
k++; 

} 
} 
} 




//唯一化 

for(i=0;i<num;i++) 
{for(j=0;j<num;j++) 
{ if((lastvt[i].name==lastvt[j].name)&amt;&amt;(i<j)) 
lastvt[j].name=0; 
}} 

//rightvn's 
for(i=0;i<num;i++) 
{for(j=0;j<num;j++) 
{ if((rightvnlast[i]==rightvnlast[j] )&amt;&amt;(i<j)) 
rightvnlast[j]=0; 
}} 

BB: 
sign5=0; 
for(i=0;i<num;i++) { 
for(j=0;j<num;j++) 
{ 
if((lastvt[i].name==rightvnlast[j])&amt;&amt;(rightvnlast[j]!=0)) 
{ 
for(k=0;k<15;k++){ 
for(v=0;v<num;v++){ 
if((lastvt[i].value[k]==vn[v])&amt;&amt;(vn[v]!=0)) 
{mysign1=1; } } } 

if(mysign1==0) 
{candolast[c].name=lastvt[i].name; 
for(a=0;a<num;a++) 
{if(lastvt[i].value[a]!=0) 
{candolast[c].value[a]=lastvt[i].value[a]; 

}} 
r=c; 
c++;} 
for(h=0;h<num;h++){ 
if((rightvnlast[h]==candolast[r].name)&amt;&amt;(rightvnlast[h]!=0)) 
rightvnlast[h]=0;} 
mysign1=0; }} 
} 


for(i=0;i<num;i++){ 
for(j=0;j<15;j++) 
{ for(k=0;k<num;k++){ 
if((lastvt[i].value[j]==candolast[k].name)&amt;&amt;(candolast[k].name!=0)) 
{ sign4=1; 
} 

if(sign4==1){ 
for(a=0;a<15;a++){ 
if (candolast[k].value[a]!=0) { 
for(h=0;h<15;h++) { 
if((lastvt[i].value[h]==candolast[k].name)||(lastvt[i].value[h]==0)) 
{lastvt[i].value[h]=candolast[k].value[a]; 
break;}} } } 
} 
sign4=0; 
}} } 

for(h=0;h<num;h++){ 
if(rightvnlast[h]!=0) 
sign5=1;} 
if(sign5==1) goto BB; 

//將lastvt唯一化 
for(i=0;i<num;i++) 
{for(j=0;j<num;j++) 
for(k=0;k<15;k++){ 
{ if((lastvt[i].value[j]==lastvt[i].value[k])&amt;&amt;(j<k)) 
lastvt[i].value[k]=0; 
}} } 


printf("***************************輸出lastvt：******************************\n"); 

for(i=0;i<num;i++) 
{if(lastvt[i].name!=0){ 

printf(" lastvt：>c ",lastvt[i].name); 
printf("{"); 
for(j=0;j<15;j++) 
{ if(lastvt[i].value[j]!=0) 
printf(">c ， ",lastvt[i].value[j]); 
} 
printf("}"); 
printf("\n"); 
}} 

} 







//判定文法是否為算符優先文法 
//,如是,生成算符優先關系表 

void table() 
{ int i,j,k,v,h,w,a; 
int b,c; 
//table 初始花 
for(h=0;h<tablenum;h++){ 

{ 

fuhaotable[0][h+1]=newvt[h]; 
fuhaotable[h+1][0]=newvt[h];} 
} 


for(i=0;i<num+1;i++) 
{ 
for(j=0;j<15;j++) 
{for(k=0;k<num+1;k++) 
{ for(v=0;v<tablenum+1;v++) 
{//如果右部只有一個非終結符 
if((expr[i].vright[j]==vn[k])&amt;&amt;(expr[i].vright[j+1]==0)&amt;&amt;(vn[k]!=0)&amt;&amt;(j==0)); 
//如果右部只有一個終結符 
if((expr[i].vright[j]==vn[k])&amt;&amt;(expr[i].vright[j+1]==0)&amt;&amt;(vn[k]!=0)&amt;&amt;(j==0)); 
// 求出“〉”關系的 

if((expr[i].vright[j]==lastvt[k].name)&amt;&amt;(expr[i].vright[j+1]==newvt[v])&amt;&amt;(lastvt[k].name!=0)&amt;&amt;(newvt[v]!=0)) 
{for(h=0;h<tablenum+1;h++){ 

for(a=0;a<15;a++){ 

if((fuhaotable[h][0]==lastvt[k].value[a])&amt;&amt;(lastvt[k].value[a]!=0)) 
{ for(w=0;w<tablenum+1;w++) 
{if((fuhaotable[0][w]==newvt[v])&amt;&amt;(newvt[v]!=0)) 
{ 
if(fuhaotable[h][w]==0) 


fuhaotable[h][w]='>'; 
else {printf("本文法不是算符優先文法!!"); 
goto END;} 
} 
} 
} // } 
}} 
} 
// 
//求出“<”關系的 
// 

// 
if((expr[i].vright[j]==vnname[k].name)&amt;&amt;(expr[i].vright[j-1]==newvt[v])&amt;&amt;(vnname[k].name!=0)&amt;&amt;(newvt[v]!=0)&amt;&amt;(j!=0)) 
{for(h=0;h<tablenum+1;h++){ 


if((fuhaotable[h][0]==newvt[v])&amt;&amt;(newvt[v]!=0)) 
{ 
for(w=0;w<tablenum+1;w++) 
{ for(a=0;a<15;a++) 
{ 
if((fuhaotable[0][w]==vnname[k].value[a])&amt;&amt;(vnname[k].value[a]!=0)) 
{ 
if(fuhaotable[h][w]==0) 
fuhaotable[h][w]='<'; 
else {printf("本文法不是算符優先文法!!"); 
goto END;} 
} 
} 
} 
}} 
} 
//求出"="關系的 
if((expr[i].vright[j]==newvt[v])&amt;&amt;(expr[i].vright[j+2]==newvt[k])&amt;&amt;(newvt[k]!=0)&amt;&amt;(newvt[v]!=0)) 
{for(h=0;h<tablenum+1;h++){ 

// for(a=0;a<15;a++) 
{ if((fuhaotable[h][0]==newvt[v])&amt;&amt;(newvt[v]!=0)) 
{ 
for(w=0;w<tablenum+1;w++) 
{ 
if((fuhaotable[0][w]==newvt[k])&amt;&amt;(newvt[k]!=0)) 
{ 
if(fuhaotable[h][w]==0) 
fuhaotable[h][w]='='; 
else {printf("本文法不是算符優先文法!!"); 
goto END;} 

} 
} 
} 
}} 
} 


}}} } //for de 

//output 
printf("############################得到算符優先關系表如下:#########################\n "); 
for(h=0;h<tablenum+1;h++){ 
for(w=0;w<tablenum+1;w++) { 


printf(" >c ",fuhaotable[h][w] ) ;} 
printf("\n-------------------------------------------------\n"); 
} 
END:; 
} //table 的括號