c语言 语法分析器

#include<stdlib.h>

#include<stdio.h>

#include<string.h>

/*******************************************/

int count=0; /*分解的产生式的个数*/

int number; /*所有终结符和非终结符的总数*/

char start; /*开始符号*/

char termin[50]; /*终结符号*/

char non_ter[50]; /*非终结符号*/

char v[50]; /*所有符号*/

char left[50]; /*左部*/

char right[50][50]; /*右部*/

char first[50][50],follow[50][50]; /*各产生式右部的FIRST和左部的FOLLOW集合*/ char first1[50][50]; /*所有单个符号的FIRST集合*/

char select[50][50]; /*各单个产生式的SELECT集合*/

char f[50],F[50]; /*记录各符号的FIRST和FOLLOW是否已求过*/

char empty[20]; /*记录可直接推出@的符号*/

char TEMP[50]; /*求FOLLOW时存放某一符号串的FIRST集合*/

int validity=1; /*表示输入文法是否有效*/

int ll=1; /*表示输入文法是否为LL(1)文法*/

int M[20][20]; /*分析表*/

char choose; /*用户输入时使用*/

char empt[20]; /*求_emp()时使用*/

char fo[20]; /*求FOLLOW集合时使用*/

/*******************************************

判断一个字符是否在指定字符串中

********************************************/

int in(char c,char *p)

{

int i;

if(strlen(p)==0)

return(0);

for(i=0;;i++)

{

if(p[i]==c)

return(1); /*若在，返回1*/

if(i==strlen(p))

return(0); /*若不在，返回0*/

}

}

/*******************************************

得到一个不是非终结符的符号

********************************************/

char c()

{

char c='A';

while(in(c,non_ter)==1)

c++;

return(c);

}

/*******************************************

分解含有左递归的产生式

********************************************/

void recur(char *point)

{ /*完整的产生式在point[]中*/

int j,m=0,n=3,k;

char temp[20],ch;

ch=c(); /*得到一个非终结符*/

k=strlen(non_ter);

non_ter[k]=ch;

non_ter[k+1]='\0';

for(j=0;j<=strlen(point)-1;j++)

{

if(point[n]==point[0])

{ /*如果'|'后的首符号和左部相同*/

for(j=n+1;j<=strlen(point)-1;j++)

{

while(point[j]!='|'&&point[j]!='\0')

temp[m++]=point[j++];

left[count]=ch;

memcpy(right[count],temp,m);

right[count][m]=ch;

right[count][m+1]='\0';

m=0;

count++;

if(point[j]=='|')

{

n=j+1;

break;

}

}

}

else

{ /*如果'|'后的首符号和左部不同*/

left[count]=ch;

right[count][0]='@';

right[count][1]='\0';

count++;

for(j=n;j<=strlen(point)-1;j++)

{

if(point[j]!='|')

temp[m++]=point[j];

else

{

left[count]=point[0];

memcpy(right[count],temp,m);

right[count][m]=ch;

right[count][m+1]='\0';

printf(" count=%d ",count);

m=0;

count++;

}

}

left[count]=point[0];

memcpy(right[count],temp,m);

right[count][m]=ch;

right[count][m+1]='\0';

count++;

m=0;

}

}

}

/*******************************************

分解不含有左递归的产生式

********************************************/

void non_re(char *point)

{

int m=0,j;

char temp[20];

for(j=3;j<=strlen(point)-1;j++)

{

if(point[j]!='|')

temp[m++]=point[j];

else

{

left[count]=point[0];

memcpy(right[count],temp,m);

right[count][m]='\0';

m=0;

count++;

}

}

left[count]=point[0];

memcpy(right[count],temp,m);

right[count][m]='\0';

count++;

m=0;

}

/*******************************************

读入一个文法

********************************************/

char grammer(char *t,char *n,char *left,char right[50][50])

{

char vn[50],vt[50];

char s;

char p[50][50];

int i,j,k;

printf("请输入文法的非终结符号串：");

scanf("%s",vn);

getchar();

i=strlen(vn);

memcpy(n,vn,i);

n[i]='\0';

printf("请输入文法的终结符号串：");

scanf("%s",vt);

getchar();

i=strlen(vt);

memcpy(t,vt,i);

t[i]='\0';

printf("请输入文法的开始符号：");

scanf("%c",&s);

getchar();

printf("请输入文法产生式的条数：");

scanf("%d",&i);

getchar();

for(j=1;j<=i;j++)

{

printf("请输入文法的第%d条（共%d条）产生式：",j,i);

scanf("%s",p[j-1]);

getchar();

}

for(j=0;j<=i-1;j++)

if(p[j][1]!='-'||p[j][2]!='>')

{ printf("\ninput error!");

validity=0;

return('\0');

} /*检测输入错误*/

for(k=0;k<=i-1;k++)

{ /*分解输入的各产生式*/

if(p[k][3]==p[k][0])

recur(p[k]);

else

non_re(p[k]);

}

return(s);

}

/*******************************************

将单个符号或符号串并入另一符号串

********************************************/

void merge(char *d,char *s,int type)

{ /*d是目标符号串，s是源串，type＝1，源串中的' @ '一并并入目串； type＝2，源串中的' @ '不并入目串*/

int i,j;

for(i=0;i<=strlen(s)-1;i++)

{

if(type==2&&s[i]=='@')

;

else

{

for(j=0;;j++)

{

if(j<strlen(d)&&s[i]==d[j])

break;

if(j==strlen(d))

{

d[j]=s[i];

d[j+1]='\0';

break;

}

}

}

}

}

/*******************************************

求所有能直接推出@的符号

********************************************/

void emp(char c)

{ /*即求所有由' @ '推出的符号*/

char temp[10];

int i;

for(i=0;i<=count-1;i++)

{

if(right[i][0]==c&&strlen(right[i])==1)

{

temp[0]=left[i];

temp[1]='\0';

merge(empty,temp,1);

emp(left[i]);

}

}

}

/*******************************************

求某一符号能否推出' @ '

********************************************/

int _emp(char c)

{ /*若能推出，返回1；否则，返回0*/

int i,j,k,result=1,mark=0;

char temp[20];

temp[0]=c;

temp[1]='\0';

merge(empt,temp,1);

if(in(c,empty)==1)

return(1);

for(i=0;;i++)

{

if(i==count)

return(0);

if(left[i]==c) /*找一个左部为c的产生式*/

{

j=strlen(right[i]); /*j为右部的长度*/

if(j==1&&in(right[i][0],empty)==1)

return(1);

else if(j==1&&in(right[i][0],termin)==1)

return(0);

else

{

for(k=0;k<=j-1;k++)

if(in(right[i][k],empt)==1)

mark=1;

if(mark==1)

continue;

else

{

for(k=0;k<=j-1;k++)

{

result*=_emp(right[i][k]);

temp[0]=right[i][k];

temp[1]='\0';

merge(empt,temp,1);

}

}

}

if(result==0&&i<count)

continue;

else if(result==1&&i<count)

return(1);

}

}

}

/*******************************************

判断读入的文法是否正确

********************************************/

int judge()

{

int i,j;

for(i=0;i<=count-1;i++)

{

if(in(left[i],non_ter)==0)

{ /*若左部不在非终结符中，报错*/

printf("\nerror1!");

validity=0;

return(0);

}

for(j=0;j<=strlen(right[i])-1;j++)

{

if(in(right[i][j],non_ter)==0&&in(right[i][j],termin)==0&&right[i][j]!='@')

{ /*若右部某一符号不在非终结符、终结符中且不为' @ '，报错*/ printf("\nerror2!");

validity=0;

return(0);

}

}

}

return(1);

}

/*******************************************

求单个符号的FIRST

********************************************/

void first2(int i)

{ /*i为符号在所有输入符号中的序号*/ char c,temp[20];

int j,k,m;

c=v[i];

char ch='@';

emp(ch);

if(in(c,termin)==1) /*若为终结符*/

{

first1[i][0]=c;

first1[i][1]='\0';

}

else if(in(c,non_ter)==1) /*若为非终结符*/

{

for(j=0;j<=count-1;j++)

{

if(left[j]==c)

{

if(in(right[j][0],termin)==1||right[j][0]=='@')

{

temp[0]=right[j][0];

temp[1]='\0';

merge(first1[i],temp,1);

}

else if(in(right[j][0],non_ter)==1)

{

if(right[j][0]==c)

continue;

for(k=0;;k++)

if(v[k]==right[j][0])

break;

if(f[k]=='0')

{

first2(k);

f[k]='1';

}

merge(first1[i],first1[k],2);

for(k=0;k<=strlen(right[j])-1;k++)

{

empt[0]='\0';

if(_emp(right[j][k])==1&&k<strlen(right[j])-1)

{

for(m=0;;m++)

if(v[m]==right[j][k+1])

break;

if(f[m]=='0')

{

first2(m);

f[m]='1';

}

merge(first1[i],first1[m],2);

}

else if(_emp(right[j][k])==1&&k==strlen(right[j])-1)

{

temp[0]='@';

temp[1]='\0';

merge(first1[i],temp,1);

}

else

break;

}

}

}

}

}

f[i]='1';

}

/*******************************************

求各产生式右部的FIRST

********************************************/

void FIRST(int i,char *p)

{

int length;

int j,k,m;

char temp[20];

length=strlen(p);

if(length==1) /*如果右部为单个符号*/

{

if(p[0]=='@')

{

if(i>=0)

{

first[i][0]='@';

first[i][1]='\0';

}

else

{

TEMP[0]='@';

TEMP[1]='\0';

}

}

else

{

for(j=0;;j++)

if(v[j]==p[0])

break;

if(i>=0)

{

memcpy(first[i],first1[j],strlen(first1[j]));

first[i][strlen(first1[j])]='\0';

}

else

{

memcpy(TEMP,first1[j],strlen(first1[j]));

TEMP[strlen(first1[j])]='\0';

}

}

}

else /*如果右部为符号串*/

{

for(j=0;;j++)

if(v[j]==p[0])

break;

if(i>=0)

merge(first[i],first1[j],2);

else

merge(TEMP,first1[j],2);

for(k=0;k<=length-1;k++)

{

empt[0]='\0';

if(_emp(p[k])==1&&k<length-1)

{

for(m=0;;m++)

if(v[m]==right[i][k+1])

break;

if(i>=0)

merge(first[i],first1[m],2);

else

merge(TEMP,first1[m],2);

}

else if(_emp(p[k])==1&&k==length-1)

{

temp[0]='@';

temp[1]='\0';

if(i>=0)

merge(first[i],temp,1);

else

merge(TEMP,temp,1);

}

else if(_emp(p[k])==0)

break;

}

}

}

/*******************************************

求各产生式左部的FOLLOW

********************************************/

void FOLLOW(int i)

{

int j,k,m,n,result=1;

char c,temp[20];

c=non_ter[i]; /*c为待求的非终结符*/

temp[0]=c;

temp[1]='\0';

merge(fo,temp,1);

if(c==start)

{ /*若为开始符号*/

temp[0]='#';

temp[1]='\0';

merge(follow[i],temp,1);

}

for(j=0;j<=count-1;j++)

{

if(in(c,right[j])==1) /*找一个右部含有c的产生式*/

{

for(k=0;;k++)

if(right[j][k]==c)

break; /*k为c在该产生式右部的序号*/

for(m=0;;m++)

if(v[m]==left[j])

break; /*m为产生式左部非终结符在所有符号中的序号*/ if(k==strlen(right[j])-1)

{ /*如果c在产生式右部的最后*/

if(in(v[m],fo)==1)

{

merge(follow[i],follow[m],1);

continue;

}

if(F[m]=='0')

{

FOLLOW(m);

F[m]='1';

}

merge(follow[i],follow[m],1);

}

else

{ /*如果c不在产生式右部的最后*/

for(n=k+1;n<=strlen(right[j])-1;n++)

{

empt[0]='\0';

result*=_emp(right[j][n]);

}

if(result==1)

{ /*如果右部c后面的符号串能推出^*/

if(in(v[m],fo)==1)

{ /*避免循环递归*/

merge(follow[i],follow[m],1);

continue;

}

if(F[m]=='0')

{

FOLLOW(m);

F[m]='1';

}

merge(follow[i],follow[m],1);

}

for(n=k+1;n<=strlen(right[j])-1;n++)

temp[n-k-1]=right[j][n];

temp[strlen(right[j])-k-1]='\0';

FIRST(-1,temp);

merge(follow[i],TEMP,2);

}

}

}

F[i]='1';

}

/*******************************************

判断读入文法是否为一个LL(1)文法

********************************************/

int ll1()

{

int i,j,length,result=1;

char temp[50];

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

{ /*初始化*/

first[j][0]='\0';

follow[j][0]='\0';

first1[j][0]='\0';

select[j][0]='\0';

TEMP[j]='\0';

temp[j]='\0';

f[j]='0';

F[j]='0';

}

for(j=0;j<=strlen(v)-1;j++)

first2(j); /*求单个符号的FIRST集合*/ printf("\n各非终结符导出的first集:");

for(j=0;j<=strlen(v)-1;j++)

printf("%c:%s ",v[j],first1[j]);

printf("\n能导空的非终结符集合:%s",empty);

// printf("\n_emp:");

//for(j=0;j<=strlen(v)-1;j++)

// printf("%d ",_emp(v[j]));

for(i=0;i<=count-1;i++)

FIRST(i,right[i]); /*求FIRST*/

for(j=0;j<=strlen(non_ter)-1;j++)

{ /*求FOLLOW*/ if(fo[j]==0)

{

fo[0]='\0';

FOLLOW(j);

}

}

//printf("\nfirst:");

//for(i=0;i<=count-1;i++)

// printf("%s ",first[i]);

printf("\nfollow集合:");

for(i=0;i<=strlen(non_ter)-1;i++)

printf("%s ",follow[i]);

for(i=0;i<=count-1;i++)

{ /*求每一产生式的SELECT集合*/ memcpy(select[i],first[i],strlen(first[i]));

select[i][strlen(first[i])]='\0';

for(j=0;j<=strlen(right[i])-1;j++)

result*=_emp(right[i][j]);

if(strlen(right[i])==1&&right[i][0]=='@')

result=1;

if(result==1)

{

for(j=0;;j++)

if(v[j]==left[i])

break;

merge(select[i],follow[j],1);

}

}

printf("\nselect集合顺序是:");

for(i=0;i<=count-1;i++)

printf("%s ",select[i]);

memcpy(temp,select[0],strlen(select[0]));

temp[strlen(select[0])]='\0';

for(i=1;i<=count-1;i++)

{ /*判断输入文法是否为LL(1)文法*/ length=strlen(temp);

if(left[i]==left[i-1])

{

merge(temp,select[i],1);

if(strlen(temp)<length+strlen(select[i]))

return(0);

}

else

{

temp[0]='\0';

memcpy(temp,select[i],strlen(select[i]));

temp[strlen(select[i])]='\0';

}

}

return(1);

}

/******************************************* 构造分析表M

********************************************/ void MM()

{

int i,j,k,m;

for(i=0;i<=19;i++)

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

M[i][j]=-1;

i=strlen(termin);

termin[i]='#'; /*将#加入终结符数组*/ termin[i+1]='\0';

for(i=0;i<=count-1;i++)

{

for(m=0;;m++)

if(non_ter[m]==left[i])

break; /*m为产生式左部非终结符的序号*/ for(j=0;j<=strlen(select[i])-1;j++)

{

if(in(select[i][j],termin)==1)

{

for(k=0;;k++)

if(termin[k]==select[i][j])

break; /*k为产生式右部终结符的序号*/ M[m][k]=i;

}

}

}

}

/******************************************* 判断符号串是否是该文法的句型

********************************************/ void syntax()

{

int i,j,k,m,n,p,q;

char ch;

char S[50],str[50];

printf("请输入该文法的句型：");

scanf("%s",str);

getchar();

i=strlen(str);

str[i]='#';

str[i+1]='\0';

S[0]='#';

S[1]=start;

S[2]='\0';

j=0;

ch=str[j];

while(1)

{

if(in(S[strlen(S)-1],termin)==1)

{

if(S[strlen(S)-1]!=ch)

{

printf("该符号串不是文法的句型！");

return;

}

else if(S[strlen(S)-1]=='#')

{

printf("该符号串是文法的句型."); return;

}

else

{

S[strlen(S)-1]='\0';

j++;

ch=str[j];

}

}

else

{

for(i=0;;i++)

if(non_ter[i]==S[strlen(S)-1])

break;

for(k=0;;k++)

{

if(termin[k]==ch)

break;

if(k==strlen(termin))

{

printf("词法错误！");

return;

}

}

if(M[i][k]==-1)

{

printf("语法错误！");

return;

}

else

{

m=M[i][k];

if(right[m][0]=='@')

S[strlen(S)-1]='\0';

else

{

p=strlen(S)-1;

q=p;

for(n=strlen(right[m])-1;n>=0;n--)

S[p++]=right[m][n]; S[q+strlen(right[m])]='\0';

}

}

}

printf("S:%s str:",S);

for(p=j;p<=strlen(str)-1;p++)

printf("%c",str[p]);

printf(" \n");

}

}

/******************************************* 一个用户调用函数

********************************************/ void menu()

{

syntax();

printf("\n是否继续？(y or n):");

scanf("%c",&choose);

getchar();

while(choose=='y')

{

menu();

}

}

/******************************************* 主函数

********************************************/ void main()

{

int i,j;

start=grammer(termin,non_ter,left,right); printf("count=%d",count);

/*读入一个文法*/

printf("\n开始符号为:%c",start);

strcpy(v,non_ter);

strcat(v,termin);

printf("\n所有符号集为:%s",v);

printf("\n非终结符集合:{%s",non_ter);

printf("}");

printf("\n终结符集合:{%s",termin);

printf("}");

printf("\n文法所有右边表达式依次是:");

for(i=0;i<=count-1;i++)

printf("%s ",right[i]);

printf("\n文法所有左边开始符依次是:"); for(i=0;i<=count-1;i++)

printf("%c ",left[i]);

if(validity==1)

validity=judge();

//printf("\nvalidity=%d",validity);

if(validity==1)

{

ll=ll1();

// printf("\nll=%d",ll);

if(ll==0)

printf("\n该文法不是一个LL1文法！"); else

{

printf("\n该文法是一个LL(1)文法！"); MM();

// printf("\n");

//for(i=0;i<=19;i++)

// for(j=0;j<=19;j++)

// if(M[i][j]>=0)

//printf("M[%d][%d]=%d ",i,j,M[i][j]); menu();

}

}

}

本文来源：https://www.bwwdw.com/article/xzfi.html