这是一个能识别加法和乘法的语法分析器，例如在提示输入后输入一个算式：3+5*2*（2+1）这类的，那么就会给出匹配过程，并判断是不是成功，请赏析！由于构造了first集，follow集，select集之类，所以比较占篇幅，惭愧！
#include<string.h>
int isterminal(char a)
{if((a=='i')||(a=='+')||(a=='*')||(a=='(')||(a==')')||(a=='$'))
return(1);
else return(0);
}
int notin(char a,char *b)
{char *c;
for(c=b;(*c)!='\0';c++)
{if((*c)==a) break;
}
if((*c)=='\0') return(1);
else return(0);
}
void add(char *g,char *q,char *a)
{char *tem;
tem=a;
for(;(*tem)!='\0';tem++)
{if(notin((*tem),g))
{(*q)=(*tem);
q++;
(*q)='\0';
}
}
}
int maybenull(char E)
{char product[8][5]={"SBA","A+BA","A","BDC","C*DC","C","D(S)","Di"};
int i;
for(i=0;i<8;i++)
{if((product[i][0]==E)&&(product[i][1]=='\0'))
break;
}
if(i<8) return(1);
else if(i>=8) return(0);
}
char *first(char E)
{char product[8][5]={"SBA","A+BA","A","BDC","C*DC","C","D(S)","Di"};
char group[200],*q;
int i,j;
q=group;
if(isterminal(E))
{(*q)=E;
q++;
(*q)='\0';
}
else
{for(i=0;i<8;i++)
{if(product[i][0]==E)
{if(isterminal(product[i][1])&¬in(product[i][1],group))
{(*q)=product[i][1];
q++;
(*q)='\0';
}
else if((!isterminal(product[i][1]))&&((product[i][1])!='\0'))
{add(group,q,first(product[i][1]));
for(j=1;j<(strlen(product[i]));j++)
{if(maybenull(product[i][j])&&(product[i][j+1]!='\0'))
add(group,q,first(product[i][j+1]));
}
}
}
}
}
return(group);
}
char *follow(char E)
{char product[8][5]={"SBA","A+BA","A","BDC","C*DC","C","D(S)","Di"};
char group[200],*q,*tem;
int i,j,k;
q=group;
if(E=='S')
{(*q)='$';
q++;
(*q)='\0';
}
for(i=0;i<8;i++)
{for(j=1;j<strlen(product[i]);j++) /*startfor1*/
{if(product[i][j]==E) /*startif*/
{if(isterminal(product[i][j+1])) /*startif1*/
{(*q)=product[i][j+1];
q++;
(*q)='\0';
} /*endif1*/
else if(!isterminal(product[i][j+1])) /*startif2*/
{if(product[i][j+1]=='\0') /*startif3*/
{if(product[i][0]!=E)
add(group,q,follow(product[i][0]));
} /*startif3*/
else if(product[i][j+1]!='\0') /*startif4*/
{tem=first(product[i][j+1]);
for(;(*tem)!='\0';tem++)
{if(notin((*tem),group))
{(*q)=(*tem);
q++;
(*q)='\0';
}
}
for(k=j+1;k<(strlen(product[i])-1);k++) /*startfor2*/
{if(maybenull(product[i][k]))
{add(group,q,first(product[i][k+1]));
}
else break;
} /*endfor2*/
if(k==(strlen(product[i])-1))add(group,q,follow(product[i][k]));
} /*endif4*/
} /*endif2*/
} /*endif*/
} /*endfor1*/
}
return(group);
}
char *select(int n)
{char product[8][5]={"SBA","A+BA","A","BDC","C*DC","C","D(S)","Di"};
char group[200],*q;
int i=1,j=0;
q=group;
if(product[n][i]!='\0')
{add(group,q,first(product[n][1]));
for(j=i;j<(strlen(product[n]));j++)
{if(maybenull(product[n][j]))
{if(product[n][j+1]!='\0')
add(group,q,first(product[n][j+1]));
else if(product[n][j+1]=='\0') add(group,q,follow(product[n][0]));
}
else break;
}
}
else if(product[n][1]=='\0') add(group,q,follow(product[n][0]));
return(group);
}
void print(char *a)
{char *b=a;
if(strlen(a)==1)printf("%c->null",*b);
else
{printf("%c->",*b);
for(b++;(*b)!='\0';b++)printf("%c",*b);
}
}
main()
{char product[8][5]={"SBA","A+BA","A","BDC","C*DC","C","D(S)","Di"};
char s[200],*p,sentence[40][7],type[40],stack[15]="$S";
int count=0,i,j,k=0;
printf("Please write in the string you want to analysis:\n");
gets(s);
p=s;
while((*p)!='\0') /*while1*/
{if(((*p)=='+')||((*p)=='*')||((*p)=='(')||((*p)==')'))
{sentence[count][0]=(*p);
type[count]=(*p);
type[count+1]='$';
type[count+2]='\0';
sentence[count][1]='\0';
p++;
count++;
}
else if((*p)>='0'&&(*p)<='9')
{for(i=0;(*p)>='0'&&(*p)<='9';i++)
{sentence[count][i]=(*p);
p++;
}
sentence[count][i]='\0';
type[count]='i';
type[count+1]='$';
type[count+2]='\0';
count++;
}
else
{printf("Fail to analyse!");
break;
}
} /*endwhile1*/
sentence[count][0]='$';
sentence[count][1]='\0';
count++;
printf("The process of analysis is below:\n\n");
printf("Stack\t\t\tInput String\t\tOutput\n\n");
printf("%s\t\t\t%s$\n",stack,s);
p=type;
while((*p)!='\0')
{if(stack[strlen(stack)-1]=='$')break;
if(!isterminal(stack[strlen(stack)-1]))
{for(i=0;i<8;i++)
{if((product[i][0]==stack[strlen(stack)-1])&&(!(notin((*p),select(i)))))
{stack[strlen(stack)-1]='\0';
if(strlen(product[i])>1)
{for(j=strlen(product[i])-1;j>=1;j--)
stack[strlen(stack)]=product[i][j];
}
printf("%s\t\t\t",stack);
for(j=k;j<count;j++)printf("%s",sentence[j]);
printf("\t\t\t");
print(product[i]);
printf("\n");
break;
}
else continue;
}
if(i>=8)
{printf("\nError analysis!");
break;
}
}
else if(isterminal(stack[strlen(stack)-1]))
{if(stack[strlen(stack)-1]==(*p))
{stack[strlen(stack)-1]='\0';
p++;
printf("%s\t\t\t",stack);
for(j=k;j<count;j++)printf("%s",sentence[j]);
printf("\n");
k++;
}
else printf("Error analysis!");
}
}
if(((*p)=='$')&&stack[strlen(stack)-1]=='$')
printf("Analyse Successfully!");
getch();
}
评论