编译原理语法分析实验报告

班级：计科0702 姓名：宝旭程 学号：0708030225 指导老师：张晓艳

1.设计要求

（1）对输入文法，它能判断是否为LL(1)文法，若是，则转（2）；否则报错并

终止；

（2）输入已知文法，由程序自动生成它的LL(1)分析表；

（3）对于给定的输入串，应能判断识别该串是否为给定文法的句型。

2.分析

该程序可分为如下几步： （1）读入文法 （2）判断正误

（3）若无误，判断是否为LL(1)文法 （4）若是，构造分析表；

（5）由总控算法判断输入符号串是否为该文法的句型。

3.流程图

是LL(1)文法？ 有效？ 读入文法 开始 是 是 判断句型 报错 结束 4.源程序

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

语法分析程序 #include #include #include

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) { } char c() { }

char c='A';

c++;

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

return(c); int i;

if(strlen(p)==0) { }

return(0);

if(p[i]==c)

return(1); /*若在，返回1*/ if(i==strlen(p))

return(0); /*若不在，返回0*/ for(i=0;;i++)

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])

{ /*如果‘|’后的首符号和左部相同*/ } 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; 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;

}

}

}

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

printf(\" count=%d \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++; }

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; m=0;

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

scanf(\"%s\ i=strlen(vn); memcpy(n,vn,i);

n[i]='\\0';

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

scanf(\"%s\ i=strlen(vt); memcpy(t,vt,i);

t[i]='\\0'; scanf(\"%c\getchar();

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

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

printf(\"\\ninput error!\"); return('\\0'); validity=0;

printf(\"请输入文法的第%d条（共%d条）产生式：\scanf(\"%s\

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

scanf(\"%d\ for(j=1;j<=i;j++)

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

} /*检测输入错误*/ for(k=0;k<=i-1;k++)

{ /*分解输入的各产生式*/ if(p[k][3]==p[k][0]) recur(p[k]); }

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

{ /*d是目标符号串，s是源串，type＝1，源串中的‘ ^ ’一并并入目串；

type＝2，源串中的‘ ^ ’不并入目串*/ for(i=0;i<=strlen(s)-1;i++) int i,j;

} return(s);

else

non_re(p[k]);

}

{ }

else { }

for(j=0;;j++) {

if(jbreak; {

d[j]=s[i]; d[j+1]='\\0'; break; } ;

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

if(j==strlen(d))

void emp(char c)

{ /*即求所有由‘ ^ ’推出的符号*/ }

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++) 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]);

{

if(i==count)

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

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

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

return(0);

return(0);

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

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

if(in(right[i][k],empt)==1) } int judge() { int i,j;

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

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

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

printf(\"\\nerror1!\"); validity=0;

}

}

}

continue; return(1);

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);

mark=1;

if(mark==1)

continue;

{

if(result==0&&i}

}

}

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);

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++) {

{

{

temp[1]='\\0'; }

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

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

continue;

if(v[k]==right[j][0]) for(k=0;;k++) merge(first1[i],temp,1);

if(left[j]==c)

if(in(right[j][0],termin)==1||right[j][0]=='^') temp[0]=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++)

}

}

}

}

f[i]='1';

}

void FIRST(int i,char *p) { int length; int j,k,m; char temp[20]; length=strlen(p);

if(length==1) { empt[0]='\\0';

if(_emp(right[j][k])==1&&kif(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; }

/*如果右部为单个符号*/

{ }

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

for(j=0;;j++)

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

break;

if(p[0]=='^') } else {

for(j=0;;j++) {

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'; if(v[j]==p[0])

break;

if(i>=0)

first[i][0]='^'; first[i][1]='\\0'; } else { }

TEMP[0]='^'; TEMP[1]='\\0';

{ {

if(i>=0)

}

if(i>=0) else {

empt[0]='\\0';

if(_emp(p[k])==1&&kmerge(first[i],first1[j],2);

}

}

}

{ } { }

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

break; temp[0]='^'; temp[1]='\\0'; if(i>=0)

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

merge(TEMP,temp,1);

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

break;

for(m=0;;m++)

if(i>=0)

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

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

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

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)

{ /*若为开始符号*/ } {

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

for(k=0;;k++)

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

temp[0]='#'; temp[1]='\\0';

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

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

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

for(m=0;;m++)

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

break; /*m为产生式左部非终结符在所有符号中的序号*/

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

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

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

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

if(result==1)

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

for(n=k+1;n<=strlen(right[j])-1;n++) temp[strlen(right[j])-k-1]='\\0'; FIRST(-1,temp); merge(follow[i],TEMP,2);

{ /*避免循环递归*/ }

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

FOLLOW(m); F[m]='1'; }

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

empt[0]='\\0';

result*=_emp(right[j][n]); if(in(v[m],fo)==1) {

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

}

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

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

FOLLOW(m); F[m]='1';

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

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

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

}

}

}

}

F[i]='1';

int ll1() {

int i,j,length,result=1;

char temp[50]; for(j=0;j<=49;j++) { }

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

first2(j); /*求单个符号的FIRST集合*/ printf(\"\\nfirst1:\"); for(j=0;j<=strlen(v)-1;j++)

printf(\"%c:%s \

/*初始化*/ first[j][0]='\\0'; first1[j][0]='\\0'; select[j][0]='\\0'; TEMP[j]='\\0'; temp[j]='\\0'; f[j]='0'; F[j]='0';

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

printf(\"\\nempty:%s\

printf(\"\\n:::\\n_emp:\"); for(j=0;j<=strlen(v)-1;j++) for(i=0;i<=count-1;i++)

FIRST(i,right[i]); /*求FIRST*/ printf(\"\\n\");

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

if(fo[j]==0) { }

fo[0]='\\0'; FOLLOW(j);

printf(\"%d \

{ /*求FOLLOW*/

}

printf(\"\\nfirst:\"); for(i=0;i<=count-1;i++) printf(\"%s \printf(\"\\nfollow:\");

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

printf(\"%s \for(i=0;i<=count-1;i++)

{ /*求每一产生式的SELECT集合*/

memcpy(select[i],first[i],strlen(first[i])); select[i][strlen(first[i])]='\\0'; } void MM() {

int i,j,k,m;

}

printf(\"\\nselect:\"); for(i=0;i<=count-1;i++) printf(\"%s \

memcpy(temp,select[0],strlen(select[0])); temp[strlen(select[0])]='\\0'; for(i=1;i<=count-1;i++)

{ /*判断输入文法是否为LL(1)文法*/ } return(1);

if(left[i]==left[i-1]) { } else { }

temp[0]='\\0';

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

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

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

if(strlen(temp)return(0);

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

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

for(j=0;;j++)

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

break;

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

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

length=strlen(temp);

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'; }

void syntax() {

int i,j,k,m,n,p,q; char S[50],str[50]; scanf(\"%s\getchar(); i=strlen(str); str[i]='#'; str[i+1]='\\0'; S[0]='#'; S[1]=start; S[2]='\\0'; j=0; ch=str[j]; {

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

char ch;

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

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

{ }

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

for(k=0;;k++)

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

break; /*k为产生式右部终结符的序号*/

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

break; /*m为产生式左部非终结符的序号*/

for(m=0;;m++)

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

M[m][k]=i;

while(1)

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

{ }

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

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

return;

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

} else {

{ }

if(M[i][k]==-1) { } else {

printf(\"\\n语法错误！\"); return;

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

if(termin[k]==ch) { }

printf(\"\\n词法错误！\"); return; break; if(k==strlen(termin))

break;

} else { }

j++; ch=str[j];

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

for(i=0;;i++)

for(k=0;;k++)

m=M[i][k]; if(right[m][0]=='^')

else {

p=strlen(S)-1;

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

q=p;

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

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

}

}

printf(\"\\nS:%s str:\

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

printf(\"%c\ printf(\" \");

}

}

void menu() { syntax();

printf(\"\\n是否继续？(y or n):\"); scanf(\"%c\ getchar(); while(choose=='y') { menu();

}

}

void main() { int i,j;

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

printf(\"\\nstart:%c\ strcpy(v,non_ter); strcat(v,termin); printf(\"\\nv:%s\

printf(\"\\nnon_ter:%s\ printf(\"\\ntermin:%s\

printf(\"\\nright:\"); for(i=0;i<=count-1;i++) printf(\"%s \ printf(\"\\nleft:\");

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

printf(\"%c \ if(validity==1)

validity=judge();

printf(\"\\nvalidity=%d\

/*读入一个文法*/ }

if(validity==1) { }

ll=ll1();

printf(\"\\nll=%d\if(ll==0) else {

MM();

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

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

printf(\"M[%d][%d]=%d \printf(\"\\n该文法不是一个LL1文法！\");

printf(\"\\n文法有效\");

printf(\"\\n\");

printf(\"\\n\"); menu(); }

5.执行结果

（1）输入一个文法（非LL(1)文法）

（2）输入一个文法（是LL（1）文法）

（3）输入一个符号串

（4）再次输入一个符号串，然后退出程序