syntax-analysis.rar_syntax

一．[目的要求] ① 对输入文法，由程序自动构造FIRST FOLLOW集 ② 对输入文法，由程序自动生成它的LL(1)分析表； ③ 对于给定的输入串，应能判断识别该串是否为给定文法的句型。 二．[题目分析] 该程序可分为如下几步： （1）读入文法 （2）判断正误 （3）若无误，判断是否为LL(1)文法 （4）若是，构造分析表； （5）由总控算法判断输入符号串是否为该文法的句型。 [源程序清单] #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("\n请输入文法的非终结符号串："); 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