/*----------------------------------------
E->E+T
E->T
T->T*F
T->F
F->(E)
F->i
文件名:wenfaG.txt
-----------------------------------------------
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
#include<malloc.h>
#define FALSE 0
#define TRUE 1
#define MAX 100
#define NULL 0
#define ERROR -1
//1.定义非终结符的结构体
struct no_terminal_sign
{
char no_ter; //非终结符
char firstvt[MAX]; //非终结符的first集合
char lastvt[MAX]; //非终结符的follow集合
};
//2.定义产生式的结构体
typedef struct produce
{
char left; //产生式左部
char right[MAX]; //产生式右部
}pro;
struct father_son
{
char father;
char son;
};
struct no_terminal_sign * search_by_sign(char sign,struct no_terminal_sign *a)//根据一个非终结符找到对应的结构体
{
struct no_terminal_sign *p;
for(p=a;p->no_ter!=NULL;p++)
if(p->no_ter==sign)
return p;
return NULL;
}
//判断字符是否为非终结符，用来识别一个字符是否属于非终结集中
bool is_no_terminal(char sign,struct no_terminal_sign *a)
{
struct no_terminal_sign *p;
for(p=a;p->no_ter!=NULL;p++)
if(p->no_ter==sign)
return true;
return false;
}
bool is_terminal(char sign,char *a)
{
int i;
for(i=0;i<(int)strlen(a);i++)
if(sign==a[i])
return true;
return false;
}
void str(char *p)
{
int length=strlen(p);
int i;
char temp;
for(i=0;i<length/2;i++)
{
temp=p[i];
p[i]=p[length-1-i];
p[length-1-i]=temp;
}
}
//添加firstvt
void firstvt(struct produce *formular,struct no_terminal_sign *no_terminal,char *terminal)
{
struct produce *p;
struct no_terminal_sign *q,*r;
struct father_son fs[MAX];
int n,i,fs_num=0,k,j,flag=1;
bool flags;
for(p=formular;p->left!=NULL;p++)
{
flags=true;
q=search_by_sign(p->left,no_terminal);//根据产生式左部找到对应的非终结符结构体
n=strlen(q->firstvt);
if(is_terminal(p->right[0], terminal))
{
q->firstvt [n]=p->right [0];//第一项为终结浮加入
n++;
}
else
{
if(p->left ==p->right [0])//第一个非终结符和推出符一样即要判断后一个符号如果存在加入
{
if(p->right [1]!='\0')
{
if( is_terminal(p->right[1], terminal))
{
q->firstvt [n]=p->right [1];
n++;
}
else
printf("error");
}
}
else//进入非终结符的递推过程
{
if(fs_num==0)
{
fs[fs_num].father =p->left ;
fs[fs_num].son =p->right[0];
fs_num++;
}
else
{
for(i=0;i<fs_num;i++)//不允许重复加入
if((fs[i].father ==p->left)&&(fs[i].son ==p->right[0]))
{
flags=false;
break;
}
if(flags)
{
fs[fs_num].father =p->left ;
fs[fs_num].son =p->right[0];
fs_num++;
}
}
if(p->right [1]!='\0')
{
if(is_terminal(p->right[1], terminal))
{
q->firstvt [n]=p->right [1];
n++;
}
else
printf("error");
}
}
}
}
//将下层的firstvt拷到上层
for(i=fs_num-1;i>=0;i--)
{
q=search_by_sign(fs[i].father,no_terminal);
r=search_by_sign(fs[i].son,no_terminal);
for(j=0;j<(int)strlen(r->firstvt );j++)
{
flag=1;
for(k=0;k<(int)strlen(q->firstvt );k++)
if(q->firstvt [k]==r->firstvt [j])
{
flag=0;
break;
}
if(flag) q->firstvt [(int)strlen(q->firstvt )]=r->firstvt [j];
}
// strcat(q->firstvt,r->firstvt);
}
}
//添加lastvt集合
void lastvt(struct produce *formular,struct no_terminal_sign *no_terminal,char *terminal)
{
struct produce *p;
struct no_terminal_sign *q,*r;
struct father_son fs[MAX];
int n,i,fs_num=0,k,j,flag=1;
bool flags;
for(p=formular;p->left!=NULL;p++)
{
flags=true;
q=search_by_sign(p->left,no_terminal);//根据产生式左部找到对应的非终结符结构体
n=strlen(q->lastvt);
if(is_terminal(p->right[0], terminal))
{
q->lastvt [n]=p->right [0];//第一项为终结浮加入
n++;
}
else
{
if(p->left ==p->right [0])//第一个非终结符和推出符一样即要判断后一个符号如果存在加入
{
if(p->right [1]!='\0')
{
if(is_terminal(p->right[1], terminal))
{
q->lastvt [n]=p->right [1];
n++;
}
else
printf("error");
}
}
else//进入非终结符的递推过程
{
if(fs_num==0)
{
fs[fs_num].father =p->left ;
fs[fs_num].son =p->right[0];
fs_num++;
}
else
{
for(i=0;i<fs_num;i++)//不允许重复加入
if((fs[i].father ==p->left)&&(fs[i].son ==p->right[0]))
{
flags=false;
break;
}
if(flags)
{
fs[fs_num].father =p->left ;
fs[fs_num].son =p->right[0];
fs_num++;
}
}
if(p->right [1]!='\0')
{
if(is_terminal(p->right[1], terminal))
{
q->lastvt [n]=p->right [1];
n++;
}
else
printf("error");
}
}
}
}
//将下层的lasttvt拷到上层
for(i=fs_num-1;i>=0;i--)
{
q=search_by_sign(fs[i].father,no_terminal);
r=search_by_sign(fs[i].son,no_terminal);
for(j=0;j<(int)strlen(r->lastvt );j++)
{
flag=1;
for(k=0;k<(int)strlen(q->lastvt );k++)
if(q->lastvt [k]==r->lastvt [j])
{
flag=0;
break;
}
if(flag) q->lastvt[(int)strlen(q->lastvt )]=r->lastvt [j];
}
// strcat(q->lastvt,r->lastvt);
}
}
int * Malloc_Array(int x,int y)
{
return (int *)malloc(x*y*sizeof(int));
}
void Free_Array(int *a)
{
free(a);
}
//a 数组首指针，a[x][y]，z二维有几个元素
int Array(int *a,int x,int y,int z)
{
return a[(x*z+y)];//二维数据的元素内容
}
void Array_fuzhi(int *a,int x,int y,int z,int fuzhi)
{
a[(x*z+y)]=fuzhi;//二维数据的元素内容
}
void analysis(struct produce *p,int x,int y,char *terminal,int *a,int guanxi)
{
int tempx,tempy;
unsigned int j;
for(j=0;j<strlen(terminal);j++)
if(p->right[x]==terminal[j]) {tempx=j;break;}
for(j=0;j<strlen(terminal);j++)
if(p->right[y]==terminal[j]) {tempy=j;break;}
Array_fuzhi(a,tempx,tempy,strlen(terminal),guanxi);
}
void analysis_table(struct produce *formular,struct no_terminal_sign *no_terminal,char *terminal,int *a)
{
pro *p;
struct no_terminal_sign *q;
int i,j;
int j1;
int tempx,tempy;
for(p=formular;p->left!=NULL;p++)
{
for(i=0;i<=(int)(strlen(p->right)-2);i++)
{
if((is_terminal(p->right[i],terminal))&&(is_terminal(p->right[i+1], terminal)))
{
analysis(p,i,i+1,terminal,a,0);
}//相等；
if(i<=(int)(strlen(p->right)-3)&&(!is_no_terminal(p->right[i],no_terminal))&&(is_terminal(p->right[i+2], terminal)))
{
analysis(p,i,i+2,terminal,a,0);
}//相等；
if((is_terminal(p->right[i], terminal))&&(is_no_terminal(p->right[i+1],no_terminal)))
{
q=search_by_sign(p->right[i+1],no_terminal);
for(j1=0;j1<(int)strlen(terminal);j1++)
if(p->right[i]==terminal[j1]) {tempx=j1;break;}
for(j=0;j<(int)strlen(q->firstvt);j++)
{
for(j1=0;j1<(int)strlen(terminal);j1++)
if(q->firstvt[j]==terminal[j1]) {tempy=j1;break;}
Array_fuzhi(a,tempx,tempy,strlen(terminal),-1);
//置小于
}
}
if((is_no_terminal(p->right[i],no_terminal))&&(is_terminal(p->right[i+1], terminal)))
{
q=search_by_sign(p->right[i],no_terminal);
for(j1=0;j1<(int)strlen(terminal);j1++)
if(p->right[i+1]==terminal[j1]) {tempy=j1;break;}
for(j=0;j<(int)strlen(q->lastvt);j++)
{
for(j1=0;j1<(int)strlen(terminal);j1++)
if(q->lastvt[j]==terminal[j1]) {tempx=j1;break;}
//analysis(p,tempx,tempy,terminal,a,-1);
Array_fuzhi(a,tempx,tempy,strlen(terminal),1);
//置大于
}
}
}
}
//找$的数组下表
for(j1=0;j1<(int)strlen(terminal);j1++)
if('$'==terminal[j1]) {tempx=j1;break;}
tempy=tempx;
Array_fuzhi(a,tempx,tempy,strlen(terminal),0);//$=$
//对firstvt(s)中的所有集置'$'<b
q=no_terminal;
for(j=0;j<(int)strlen(q->firstvt);j++)
{
for(j1=0;j1<(int)strlen(terminal);j1++)
if(q->firstvt[j]==terminal[j1]) {tempy=j1;break;}
Array_fuzhi(a,tempx,tempy,strlen(terminal),-1);
//置小于
}
//对lastvt(s)中的所有集置b>'$'
tempy=tempx;
for(j=0;j<(int)strlen(q->lastvt);j++)
{
for(j1=0;j1<(int)strlen(terminal);j1++)
if(q->lastvt[j]==terminal[j1]) {tempx=j1;break;}
Array_fuzhi(a,tempx,tempy,strlen(terminal),1);
// 置大于$ //置小于￥
}
}
void print_analysis_table(int *a,int terminal_num,char *terminal)
{
int i,j;
printf(" ");
for(i=0;i<terminal_num;i++)
printf("%4c",terminal[i]);
printf("\n");
for(i=0;i<terminal_num ;i++)//-1小于0等于1大于2初始化
{printf("%c",terminal[i]);
for(j=0;j<terminal_num;j++)
printf("%4d",Array(a,i,j,terminal_num));
printf("\n");
}
}
int is_num(char num)
{
if(num>='0'&&num<'9')
return 1;
else return 0;
}
int xiabiao(char c,char *terminal) /*求字符c在算符优先关系表中的下标*/
{
int i;
for(i=0;i<(int)strlen(terminal);i++)
{
if(c==terminal[i])
return i;
}
return -1;
}
int deal (char *input,char *s,int *a,struct no_terminal_sign *no_terminal,char *terminal,struct produce *formular )
{
int i,j;
int x,y;
int z; /*输入串的长度*/
int m,n,terminal_num=(int)strlen(terminal);
int k=1;
s[k]='$'; /*栈置初值*/
char temp,q;
struct produce *p;
/*计算输入串的长度*/
z=(int)strlen(input);
i=0;
while((temp=input[i])!='\0')
{
if(is_terminal(s[k],terminal))
j=k;
else
j=k-1;
x=xiabiao(s[j],terminal);
if(is_num(temp))
temp='i';
y=xiabiao(temp,terminal);
if(Array(a,x,y,terminal_num)==1)
{
do
{
q=s[j];
if(is_terminal(s[j-1], terminal))
j=j-1;
else j=j-2;
x=xiabiao(s[j],terminal);
y=xiabiao(q,terminal);
}while(Array(a,x,y,terminal_num)!=-1);
for(m=j+1;m<=k;m++)
{
for(p=formular;p->left!=NULL;p++)
{
for(n=0;n<(int)strlen(p->right);n++)
{
if(is_no_terminal(s[m],no_terminal)&&is_no_terminal(p->right[n],no_terminal))
{
if(is_terminal(s[m+1], terminal )&&is_terminal(p->right[n+1], terminal)&&s[m+1]==p->right[n+1])
{
s[j+1]=p->left;
break;
}
}
else
if(is_terminal(s[m],terminal))
if(s[m]==p->right[n])
{
s[j+1]=p->left;
break;
}
}
}
}
k=j+1;
if(k==2&&temp=='$')
{
return 1; /*输入串符合文法的定义*/
}
}
else
if(Array(a,x,y,terminal_num)==-1||Array(a,x,y,terminal_num)==0)
{ /*移进*/
k++;
s[k]=temp;
i++;
}
else
{
return 0;
}
}
return 0;
}
int main()
{
//定义非终结符集
struct no_terminal_sign no_terminal[MAX];
//定义终结符
char terminal[MAX];
//定义开始符号
// char start_sign;
//定义产生式集合
pro formular[MAX],*p;
char input_char[100];//读入的字符
char s[100];//分析栈
int i,j;
//---------------------------------------------------
int pro_num=0;//产生式个数
int noterminal_num=0;//非终结符个数
int terminal_num=0;//终结符个数，构造N*N数组关系表
//读取存放产生式的文件
FILE *in;
char temp[MAX];//读文件临时存储的地方
if((in=fopen("wenfaG.txt","r"))==NULL){
printf("cannot open file!\n");
return 0;
}
//产生式添加并赋初值
while (fscanf(in,"%s",temp)!=-1)
{
formular[pro_num].left=temp[0];//产生式的左部(非终结符号)
strcpy(formular[pro_num].right,temp+3);//产生式子右部去除'->'
pro_num++;//产生式子的个数
}
fclose(in);
formular[pro_num].left=NULL;//最后产生式子NUll
strcpy(formular[pro_num].right,"");//为了可以有效的找到所有的产生式子，故最后做标记
//非终结符和终结符添加并赋初值
for(p=formular;p->left!=NULL;p++)
{
//1.将非终结符加入非终结符集并赋初值
for(i=0;i<noterminal_num;i++)
if(p->left==no_terminal[i].no_ter)//非终结符号已经添加到集合中了
break;
if(i>=noterminal_num)//所有的非终结符号都已经添加完毕，非终结数组做标记
{
no_terminal[noterminal_num].no_ter=p->left;//添加
noterminal_num++;
}
//2.将终结符加入终结符集
for(i=0;p->right[i]!='\0';i++)
if(!((p->right[i]<='Z' && p->right[i]>='A') || (p->right[i]=='~')))
{
for(j=0;j<terminal_num;j++)
if(p->right[i]==terminal[j])//终结符号已经添加到集合中了
break;
if(j>=terminal_num){//所有的终结符号都已经添加完毕，终结数组做标记
terminal[terminal_num]=p->right[i];
terminal_num++;
}
}
}
//各集合终结标志添加
no_terminal[noterminal_num].no_ter='\0';
terminal[terminal_num++]='$';
terminal[terminal_num]='\0';
for(i=0;i<noterminal_num;i++)//初始化firstvt lastvt
for(j=0;j<MAX;j++)
{
no_terminal[i].firstvt[j] ='\0';
no_terminal[i].lastvt[j] ='\0';
}
firstvt(formular,no_terminal, terminal);
for(p=formular;p->left!=NULL;p++)
{
str(p->right);
}
lastvt(formular,no_terminal, terminal);
for(p=formular;p->left!=NULL;p++)
{
str(p->right);
}
//----------------------------------------------------------------------
//二维数组的创建terminal[i]与数组的关系表一一对应
int *a=Malloc_Array(terminal_num,terminal_num);
for(i=0;i<terminal_num ;i++)//-1小于0等于1大于2初始化
for(j=0;j<terminal_num;j++)
Array_fuzhi(a,i,j,terminal_num,2);
printf("二维数组关系表初始化\n");
for(i=0;i<terminal_num ;i++)//-1小于0等于1大于2初始化
{for(j=0;j<terminal_num;j++)
printf("%d",Array(a,i,j,terminal_num));
printf("\n");
}
//---------------------------------------------------------生成表关系函数
analysis_table(formular,no_terminal,terminal,a);
//----------------------------------------------------------打印信息
printf("产生式：\n");
for(i=0,p=formular;p->left!=NULL;p++,i++)
printf("%d%s%c%s%s\n",i,":",p->left,"->",p->right);
printf("非终结符,firstvt lastvt：\n");
for(i=0;no_terminal[i].no_ter!='\0';i++)
printf("%-10c %s %s\n",no_terminal[i].no_ter,no_terminal[i].firstvt,no_terminal[i].lastvt );
printf("\n终结符：\n");
for(i=0;i<terminal_num;i++)
printf("%4c",terminal[i]);
printf("\n优先关系表\n");
print_analysis_table(a,terminal_num,terminal);
printf("\n请输入算符表达式($):\n");
scanf("%s",input_char);
if(deal(input_char,s,a,no_terminal,terminal,formular)) printf("\n语法正确Ok\n");
else printf("\n算数表达式语法错误\n");
// printf("formular:%d,%d",strlen(formular->right),strlen(terminal));
return 1;
}
