#include <stdio.h>
#include <stdlib.h>
char data[20][20]; //算符優先關系
char s[100]; //模擬符號堆疊s
char lable[20]; //文法終極符集
char input[100]; //文法輸入符號串
char string[20][10]; //用于輸入串的分析
int k;
char a;
int j;
char q;
int r; //文法規則個數
int r1;
int m,n,N; //轉化后文法規則個數
char st[10][30]; //用來存盤文法規則
char first[10][10]; //文法非終結符FIRSTVT集
char last[10][10]; //文法非終結符LASTVT集
int fflag[10]={0}; //標志第i個非終結符的FIRSTVT集是否已求出
int lflag[10]={0}; //標志第i個非終結符的LASTVT集是否已求出
int zhongjie(char c); //判斷字符c是否是終極符
int xiabiao(char c); //求字符c在算符優先關系表中的下標
void out(int j,int k,char *s); //列印s堆疊
void firstvt(char c); //求非終結符c的FIRSTVT集
void lastvt(char c); //求非終結符c的LASTVT集
void table(); //創建文法優先關系表
int main()
{
int i,j,k=0;
printf("請輸入文法規則數：");
scanf("%d",&r);
printf("請輸入文法規則：\n");
for(i=0;i<r;i++)
{
scanf("%s",st[i]); //存盤文法規則，初始化FIRSTVT集和LASTVT集*/
first[i][0]=0; //first[i][0]和last[i][0]分別表示st[i][0]非終極符的FIRSTVT集和LASTVT集中元素的個數
last[i][0]=0;
}
for(i=0;i<r;i++) //判斷文法是否合法
{
for(j=0;st[i][j]!='\0';j++)
{
if(st[i][0]<'A'||st[i][0]>'Z')
{
printf("不是算符文法!\n");
exit(-1);
}
if(st[i][j]>='A'&&st[i][j]<='Z')
{
if(st[i][j+1]>='A'&&st[i][j+1]<='Z')
{
printf("不是算符文法!\n");
exit(-1);
}
}
}
}
for(i=0;i<r;i++)
{
for(j=0;st[i][j]!='\0';j++)
{
if((st[i][j]<'A'||st[i][j]>'Z')&&st[i][j]!='-'&&st[i][j]!='>'&&st[i][j]!='|')
lable[k++]=st[i][j];
}
}
lable[k]='#';
lable[k+1]='\0';
table();
printf("每個非終結符的FIRSTVT集為：\n"); //輸出每個非終結符的FIRSTVT集
for(i=0;i<r;i++)
{
printf("%c: ",st[i][0]);
for(j=0;j<first[i][0];j++)
{
printf("%c ",first[i][j+1]);
}
printf("\n");
}
printf("每個非終結符的LASTVT集為：\n"); //輸出每個非終結符的LASTVT集
for(i=0;i<r;i++)
{
printf("%c: ",st[i][0]);
for(j=0;j<last[i][0];j++)
{
printf("%c ",last[i][j+1]);
}
printf("\n");
}
printf("算符優先分析表如下:\n");
for(i=0;lable[i]!='\0';i++)
printf("\t%c",lable[i]);
printf("\n");
for(i=0;i<k+1;i++)
{
printf("%c\t",lable[i]);
for(j=0;j<k+1;j++)
{
printf("%c\t",data[i][j]);
}
printf("\n");
}
for(i=0;i<k+1;i++){
for(j=0;j<k+1;j++){
if(data[i][j]=='>'&&data[j][i]!='<'&&data[j][i]!='\0') break;
else if(data[i][j]=='<'&&data[j][i]!='>'&&data[j][i]!='\0') break;
else if(data[i][j]=='='&&data[j][i]!='='&&data[j][i]!='\0') break;
}}
if(i==(k+1)&&j==(k+1)) printf("該文法是算符優先文法。\n");
else printf("該文法不是算符優先文法。\n");
return 0;
}
void table()
{
char text[20][10];
int i,j,k,t,l,x=0,y=0;
int m,n;
x=0;
for(i=0;i<r;i++)
{
firstvt(st[i][0]);
lastvt(st[i][0]);
}
for(i=0;i<r;i++)
{
text[x][y]=st[i][0];
y++;
for(j=1;st[i][j]!='\0';j++)
{
if(st[i][j]=='|')
{
text[x][y]='\0';
x++;
y=0;
text[x][y]=st[i][0];
y++;
text[x][y++]='-';
text[x][y++]='>';
}
else
{
text[x][y]=st[i][j];
y++;
}
}
text[x][y]='\0';
x++;
y=0;
}
r1=x;
printf("轉化后的文法為:\n");
for(i=0;i<x;i++)
{
printf("%s\n",text[i]);
}
for(i=0;i<x;i++)
{
string[i][0]=text[i][0];
for(j=3,l=1;text[i][j]!='\0';j++,l++)
string[i][l]=text[i][j];
string[i][l]='\0';
}
for(i=0;i<x;i++)
{
for(j=1;text[i][j+1]!='\0';j++)
{
if(zhongjie(text[i][j])&&zhongjie(text[i][j+1]))
{
m=xiabiao(text[i][j]);
n=xiabiao(text[i][j+1]);
data[m][n]='=';
}
if(text[i][j+2]!='\0'&&zhongjie(text[i][j])&&zhongjie(text[i][j+2])&&!zhongjie(text[i][j+1]))
{
m=xiabiao(text[i][j]);
n=xiabiao(text[i][j+2]);
data[m][n]='=';
}
if(zhongjie(text[i][j])&&!zhongjie(text[i][j+1]))
{
for(k=0;k<r;k++)
{
if(st[k][0]==text[i][j+1])
break;
}
m=xiabiao(text[i][j]);
for(t=0;t<first[k][0];t++)
{
n=xiabiao(first[k][t+1]);
data[m][n]='<';
}
}
if(!zhongjie(text[i][j])&&zhongjie(text[i][j+1]))
{
for(k=0;k<r;k++)
{
if(st[k][0]==text[i][j])
break;
}
n=xiabiao(text[i][j+1]);
for(t=0;t<last[k][0];t++)
{
m=xiabiao(last[k][t+1]);
data[m][n]='>';
}
}
}
}
m=xiabiao('#');
for(t=0;t<first[0][0];t++)
{
n=xiabiao(first[0][t+1]);
data[m][n]='<';
}
n=xiabiao('#');
for(t=0;t<last[0][0];t++)
{
m=xiabiao(last[0][t+1]);
data[m][n]='>';
}
data[n][n]='=';
}
void firstvt(char c)
{
int i,j,k,m,n;
for(i=0;i<r;i++)
{
if(st[i][0]==c)
break;
}
if(fflag[i]==0)
{
n=first[i][0]+1;
m=0;
do
{
if(m==2||st[i][m]=='|')
{
if(zhongjie(st[i][m+1]))
{
first[i][n]=st[i][m+1];
n++;
}
else
{
if(zhongjie(st[i][m+2]))
{
first[i][n]=st[i][m+2];
n++;
}
if(st[i][m+1]!=c)
{
firstvt(st[i][m+1]);
for(j=0;j<r;j++)
{
if(st[j][0]==st[i][m+1])
break;
}
for(k=0;k<first[j][0];k++)
{
int t;
for(t=0;t<n;t++)
{
if(first[i][t]==first[j][k+1])
break;
}
if(t==n)
{
first[i][n]=first[j][k+1];
n++;
}
}
}
}
}
m++;
}while(st[i][m]!='\0');
first[i][n]='\0';
first[i][0]=--n;
fflag[i]=1;
}
}
void lastvt(char c)
{
int i,j,k,m,n;
for(i=0;i<r;i++)
{
if(st[i][0]==c)
break;
}
if(lflag[i]==0)
{
n=last[i][0]+1;
m=0;
do
{
if(st[i][m+1]=='\0'||st[i][m+1]=='|')
{
if(zhongjie(st[i][m]))
{
last[i][n]=st[i][m];
n++;
}
else
{
if(zhongjie(st[i][m-1]))
{
last[i][n]=st[i][m-1];
n++;
}
if(st[i][m]!=c)
{
lastvt(st[i][m]);
for(j=0;j<r;j++)
{
if(st[j][0]==st[i][m])
break;
}
for(k=0;k<last[j][0];k++)
{
int t;
for(t=0;t<n;t++)
{
if(last[i][t]==last[j][k+1])
break;
}
if(t==n)
{
last[i][n]=last[j][k+1];
n++;
}
}
}
}
}
m++;
}while(st[i][m]!='\0');
last[i][n]='\0';
last[i][0]=--n;
lflag[i]=1;
}
}
void out(int j,int k,char *s)
{
int n=0;
int i;
for(i=j;i<=k;i++)
{
printf("%c",s[i]);
n++;
}
for(;n<15;n++)
{
printf(" ");
}
}
int xiabiao(char c) //求字符c在算符優先關系表中的下標
{
int i;
for(i=0;lable[i]!='\0';i++)
{
if(c==lable[i])
return i;
}
return -1;
}
int zhongjie(char c)//判斷字符c是否是終極符
{
int i;
for(i=0;lable[i]!='\0';i++)
{
if(c==lable[i])
return 1;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/52062.html
標籤：C語言
上一篇：如何解碼opus成pcm檔案？
下一篇：腦袋都想破了，這也太難了....