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

1、编译原理实验报告一.LL（1）文法分析1. 设计要求（1） 对输入文法，它能判断是否为 LL（1）文法，若是，则转（2）;否则报错并 终止；（2）输入已知文法，由程序自动生成它的 LL（1）分析表；（3）对于给定的输入串，应能判断识别该串是否为给定文法的句型。2. 分析该程序可分为如下几步：（1）读入文法（2）判断正误（3）若无误，判断是否为LL（1）文法（4）若是，构造分析表；（5）由总控算法判断输入符号串是否为该文法的句型。3. 流程图4.源程序/* 语法分析程序作者： xxx学号： xxx*#include#include#include/*int count=0; int number

2、; char start;char termin50;/* 分解的产生式的个数 */* 所有终结符和非终结符的总数 */* 开始符号 */* 终结符号 */char non_ter50;char v50;char left50;/* 非终结符号 */* 所有符号 */* 左部 */char right5050;/*右部 */char first5050,follow5050;/* 各产生式右部的 FIRST 和左部的 FOLLOW 集合 */char first15050; char select5050;char f50,F50;char empty20;char TEMP50;/*所有单个

3、符号的 FIRST 集合 */*各单个产生式的 SELECT 集合*/* 记录各符号的 FIRST 和 FOLLOW 是否已求过 */ /*记录可直接推出A的符号*/*求 FOLLOW 时存放某一符号串的 FIRST 集合*/int validity=1;int ll=1;int M2020;/*表示输入文法是否有效 */* 表示输入文法是否为 LL(1) 文法 */*分析表 */char choose;char empt20;char fo20;/*用户输入时使用 */*求_emp()时使用*/* 求 FOLLOW 集合时使用 */*判断一个字符是否在指定字符串中* int in(char

4、c,char *p)int i;if(strlen(p)=0)return(0);for(i=0;i+)if(pi=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 temp20,ch;ch=c(); /* 得到一个非终结

5、符 */k=strlen(non_ter);non_terk=ch;non_terk+1=0;for(j=0;j=strlen(point)-1;j+)if(pointn=point0)/* 如果 |后的首符号和左部相同 */for(j=n+1;j=strlen(point)-1;j+)while(pointj!=|&pointj!=0)tempm+=pointj+;leftcount=ch;memcpy(rightcount,temp,m);rightcountm=ch;rightcountm+1=0;m=0;count+;if(pointj=|)n=j+1;break;else/* 如果

6、|后的首符号和左部不同*/leftcount=ch;rightcount0=A;rightcount1=0;count+;for(j=n;j=strlen(point)-1;j+)if(pointj!=|)tempm+=pointj;elseleftcount=point0; memcpy(rightcount,temp,m);rightcountm=ch;rightcountm+1=0;printf( count=%d ,count);m=0;count+;leftcount=point0; memcpy(rightcount,temp,m); rightcountm=ch; rightco

7、untm+1=0; count+;m=0;/*分解不含有左递归的产生式*/void non_re(char *point)int m=0,j;char temp20;for(j=3;j=strlen(point)-1;j+)if(pointj!=|)tempm+=pointj;elseleftcount=point0; memcpy(rightcount,temp,m); rightcountm=0;m=0;count+;leftcount=point0;memcpy(rightcount,temp,m);rightcountm=0;count+;m=0;/*读入一个文法 */ char gr

8、ammer(char *t,char *n,char *left,char right5050) char vn50,vt50;char s;char p5050;int i,j,k;printf(n 请输入文法的非终结符号串： ); scanf(%s,vn);getchar();i=strlen(vn);memcpy(n,vn,i);ni=0;printf( 请输入文法的终结符号串： );scanf(%s,vt);getchar();i=strlen(vt);memcpy(t,vt,i);ti=0;printf( 请输入文法的开始符号： );scanf(%c,&s);getchar();pr

9、intf( 请输入文法产生式的条数： );scanf(%d,&i);getchar();for(j=1;j=i;j+)printf(”请输入文法的第 %d条(共%d条)产生式： scanf(%s,pj-1);getchar();for(j=0;j) printf(ninput error!);validity=0;return(0);/* 检测输入错误 */for(k=0;k=i-1;k+)/* 分解输入的各产生式 */if(pk3=pk0)recur(pk);else non_re(pk); return(s);/* 将单个符号或符号串并入另一符号串*/void merge(char *d,

10、char *s,int type)A 一并并入目串；/*d是目标符号串，s是源串，type= 1,源串中的type= 2，源串中的人不并入目串*/int i,j;for(i=0;i=strlen(s)-1;i+)if(type=2&si=A)Jelsefor(j=0;j+)if(jstrlen(d)&si=dj) break;if(j=strlen(d)dj=si;dj+1=0;break;/*求所有能直接推出A的符号* void emp(char c)/*即求所有由A 推出的符号*/char temp10;int i;for(i=0;i=count-1;i+)if(righti0=c&str

11、len(righti)=1)temp0=lefti;temp1=0;merge(empty,temp,1);emp(lefti);求某一符号能否推出 A*int _emp(char c)/*若能推出，返回1；否则，返回 0*/int i,j,k,result=1,mark=0;char temp20;temp0=c;temp1=0;merge(empt,temp,1);if(in(c,empty)=1)return(1);for(i=0;i+)if(i=count)return(0);if(lefti=c)/*找一个左部为c的产生式*/j=strlen(righti); /*j 为右部的长度

12、*/if(j=1&in(righti0,empty)=1)return(1);else if(j=1&in(righti0,termin)=1)return(0);elsefor(k=0;k=j-1;k+)if(in(rightik,empt)=1)mark=1;if(mark=1)continue;elsefor(k=0;k=j-1;k+) result*=_emp(rightik); temp0=rightik; temp1=0; merge(empt,temp,1);if(result=0&icount)continue;else if(result=1&icount)return(1)

13、; /*判断读入的文法是否正确 */ int judge()int i,j;for(i=0;i=count-1;i+)if(in(lefti,non_ter)=0) /* 若左部不在非终结符中，报错 */ printf(nerror1!);validity=0;return(0);for(j=0;j=strlen(righti)-1;j+)if(in(rightij,non_ter)=0&in(righ tij,termin)=O&rightij!=A)A ，报错 */ /* 若右部某一符号不在非终结符、终结符中且不为printf(nerror2!);validity=0;return(0);

14、return(1);/*求单个符号的 FIRST*/void first2(int i)/*i 为符号在所有输入符号中的序号 */char c,temp20;int j,k,m;c=vi;char ch=A;emp(ch);if(in(c,termin)=1)/*若为终结符 */first1i0=c;first1i1=0;else if(in(c,non_ter)=1)/*若为非终结符 */for(j=0;j=count-1;j+)if(leftj=c)if(in(rightj0,termin)=1|rightj0=A)temp0=rightj0;temp1=0;merge(first1i,t

15、emp,1);else if(in(rightj0,non_ter)=1)if(rightj0=c)continue;for(k=0;k+)if(vk=rightj0)break;if(fk=0)first2(k);fk=1;merge(first1i,first1k,2);for(k=0;k=strlen(rightj)-1;k+)empt0=0;if(_emp(rightjk)=1&k=O)firstiO=A： firsti1=O;elseTEMPO=a：TEMP1=O;elsefor(j=O;j+)if(vj=pO)break;if(i=O)memcpy(firsti,first1j,s

16、trlen(first1j); firstistrlen(first1j)=O;elsememcpy(TEMP,first1j,strlen(first1j); TEMPstrlen(first1j)=O;else/* 如果右部为符号串 */for(j=O;j+)if(vj=pO) break;if(i=O) merge(firsti,first1j,2);elsemerge(TEMP,first1j,2); for(k=O;k=length-1;k+)empt0=0;if(_emp(pk)=1&k=0) merge(firsti,first1m,2);elsemerge(TEMP,first

17、1m,2);else if(_emp(pk)=1&k=length-1)tempO=A：temp1=0;if(i=O)merge(firsti,temp,1);elsemerge(TEMP,temp,1);else if(_emp(pk)=O)break;/*求各产生式左部的 FOLLOW*/void FOLLOW(int i)int j,k,m,n,result=1;char c,temp2O;c=non_teri;/*c 为待求的非终结符 */tempO=c;temp1=O;merge(fo,temp,1);if(c=start) /* 若为开始符号 */tempO=#;temp1=O;m

18、erge(followi,temp,1);for(j=O;j=count-1;j+)if(in(c,rightj)=1)/*找一个右部含有c的产生式*/ for(k=0;k+)if(rightjk=c)break;/*k 为 c 在该产生式右部的序号 */for(m=0;m+)if(vm=leftj)break;/*m 为产生式左部非终结符在所有符号中的序号 */if(k=strlen(rightj)-1)/*如果c在产生式右部的最后*/if(in(vm,fo)=1)merge(followi,followm,1);continue;if(Fm=0)FOLLOW(m); Fm=1; merge

19、(followi,followm,1);else/*如果c不在产生式右部的最后*/for(n=k+1;n=strlen(rightj)-1;n+)empt0=0; result*=_emp(rightjn);if(result=1)/*如果右部c后面的符号串能推出A*/if(in(vm,fo)=1) /*避免循环递归 */merge(followi,followm,1);continue;if(Fm=0)FOLLOW(m);Fm=1;merge(followi,followm,1);for(n=k+1;n=strlen(rightj)-1;n+)tempn-k-1=rightjn;tempst

20、rlen(rightj)-k-1=0;FIRST(-1,temp);merge(followi,TEMP,2);Fi=1;/*判断读入文法是否为一个 LL(1) 文法*/int ll1()int i,j,length,result=1;char temp50;for(j=0;j=49;j+)/* 初始化 */firstj0=0;followj0=0;first1j0=0;selectj0=0;TEMPj=0;tempj=0;fj=0;Fj=0;for(j=0;j=strlen(v)-1;j+)first2(j);/*求单个符号的 FIRST 集合 */printf(nfirst1:);for(

21、j=0;j=strlen(v)-1;j+)printf(%c:%s ,vj,first1j);printf(nempty:%s,empty);printf(n:n_emp:);for(j=0;j=strlen(v)-1;j+)printf(%d ,_emp(vj);for(i=0;i=count-1;i+)FIRST(i,righti); /* 求 FIRST*/printf(n);for(j=0;j=strlen(non_ter)-1;j+)/* 求 FOLLOW*/if(foj=0)fo0=0; FOLLOW(j); printf(nfirst:);for(i=0;i=count-1;i+

22、)printf(%s ,firsti); printf(nfollow:); for(i=0;i=strlen(non_ter)-1;i+)printf(%s ,followi); for(i=0;i=count-1;i+) /* 求每一产生式的 SELECT 集合 */ memcpy(selecti,firsti,strlen(firsti);selectistrlen(firsti)=0; for(j=0;j=strlen(righti)-1;j+) result*=_emp(rightij);if(strlen(righ ti)=1 &rightiO=A) result=1;if(res

23、ult=1) for(j=O;j+)if(vj=lefti) break;merge(selecti,followj,1); printf(nselect:); for(i=O;i=count-1;i+)printf(%s ,selecti); memcpy(temp,selectO,strlen(selectO); tempstrlen(selectO)=O; for(i=1;i=count-1;i+) /* 判断输入文法是否为 LL(1) 文法 */ length=strlen(temp);if(lefti=lefti-1) merge(temp,selecti,1); if(strlen

24、(temp)length+strlen(selecti) return(O);elsetempO=O;memcpy(temp,selecti,strlen(selecti);tempstrlen(selecti)=0; return(1);/*构造分析表 M*/void MM()int i,j,k,m;for(i=0;i=19;i+)for(j=0;j=19;j+) Mij=-1;i=strlen(termin);termini=#;/* 将 #加入终结符数组 */termini+1=0;for(i=0;i=count-1;i+)for(m=0;m+)if(non_term=lefti)bre

25、ak; /*m 为产生式左部非终结符的序号 */ for(j=0;j=O;n-)Sp+=rightmn;Sq+strlen(rightm)=O;printf(nS:%s str:,S);for(p=j;p=strlen(str)-1;p+)printf(%c,strp);printf( );/*一个用户调用函数*/void menu()syntax();printf(n 是否继续？ (y or n):);scanf(%c,&choose);getchar();while(choose=y)menu();/*主函数*/void main()int i,j;start=grammer(termin

26、,non_ter,left,right); /* 读入一个文法 */ printf(count=%d,count);printf(nstart:%c,start);strcpy(v,non_ter);strcat(v,termin);printf(nv:%s,v);printf(nnon_ter:%s,non_ter);printf(ntermin:%s,termin);printf(nright:);for(i=0;i=count-1;i+)printf(%s ,righti);printf(nleft:);for(i=0;i=count-1;i+)printf(%c ,lefti);if(

27、validity=1)validity=judge();printf(nvalidity=%d,validity);if(validity=1)printf(n 文法有效 );ll=ll1();printf(nll=%d,ll);if(ll=0)printf(n 该文法不是一个 LL1 文法！ );elseMM();printf(n);for(i=0;i=19;i+)for(j=0;j=0)printf(M%d%d=%d ,i,j,Mij);printf(n);menu();5.执行结果(1)输入一个文法畫女-123 的的产的的的 .iil 文文文文文文nn_te ： ETFfiB BifTi

28、in : -i:ETFAB+-*/*()itart ：E匸+: +-see八MiirbocSXPehugXsynai. eie*i 式式式 匕 -I匕 F c 二 El-z产户产 s - EITS:数知如知E-E+r SE-T ：TA*FBF9EDBBF-Tfthl0H4J-J M 9 3(6 1-3 M：1I41=7J-7 MC21 E*1 J-S Iir2 JCC J9 MOJISJ-B MCami-lH13JI51-2 nt3JI7J-2 HL43101-6 ML4311J-6 HE4J21-4 14113J-5 H14JI5J-& nL4J71-6 涯培 X沧刚一alldllty=l

29、irstl：E：P： + B 11 0 0Ci * / * (itt+- +t-*z tt +#- m x / nit- ci(2 )输入一个符号串(3)再次输入一个符号串，然后退出程序二词法分析一、问题描述识别简单语言的单词符号识别简单语言的基本字、标识符、无符号整数、运算符和界符。1题目选择计算机高级程序语言之一 一一C语言，运用恰当的词法分析技术线路，设计和实现其对应的词法分析器。单词符号begi nifthe n while do end l ( l I d )2.要求1).给出一简单语言单词符号的种别编码种别编码12345610112) .词法分析程序的功能输入是源程序字符串，以 #

30、结束。输出是单词符号的二元组。分析器输出结果存入到磁盘文件中，具有出错处理功能3) .建议和提示：技术线路选择如下两种之一：正则式T NF2DFAtmin DFL程序设计或 正则文法NFAtDFAtmin DFAt程序设计系统分析词法分析器对应的正则文法表达如下：S 一标示符或关键字|数字字符|运算符标示符或关键字一 character AA character |number| （标示符或关键字要以字母开 头）数字字符number| :（数字字符只能由数字组成）character a|b|c |y|z|A|B|C |Y|Znu mber -0|1|2|3|4|5|6|7|8|9运算符 Y|v

31、|v=|=|：|：=|+|-|*|/|=|；|（|）|n该词法分析程序要识别的字符类别包括关键字，标示符， 数字字符，运算符，结束符这里把关键字和标示符归为同 一类，识别完之后根据查标示符表得到是标示符还是关键字。 因此对于自动机DFA来说，有几个相应的状态，对应识别不同 单词串。当然词法分析程序还要有过滤空格字符，注释符号， 回车换行符等一些特殊字符。当词法分析器遇到符号的时候 就表示词法分析已经完成，程序结束。三、系统设计基于以上的讨论，我设计了本实验词法分析器的有限自动机的每当读入完一个字符串后，自动机回到开始状态 S,读入下一个字符串的第一个字母。这里所说的字符串是指标示符或 者关键字

32、或者数字或者特殊符号。当读入的第一个字符是字母的时候说明这个状态机要识别 的是标示符或者字符串，后面的字符可以是字母或者数字。所 以在标示符或关键字状态的时候读入的下一个字符是字母或者 是数字的时候其状态还是会转向自己；当读入的下个字符是回 车或空格的时候表示识别完成；当读入的下个字符是特殊符号的时候（非字母或数字）按正常思维状态应转向出错处理，不过由于本实验是词法分析，标示符不合法应该是语义分析阶段做的事，所以本程序没有给出出错处理。识别字符串后还应区分这个单词是标示符还是关键字。实现过程是查关键字表，将识别的字符串同关键字表中的每一个元素比较，若有相同则说 明识别的是关键字，否则是标示符。

33、当读入的第一个字符是数字的时候说明这个状态机要识别 的是数字。后面的字符可以是数字，表示多位数。所以在数字 状态的时候读入的下一个字符是数字的时候其状态还是会转向 自己；当读入的下个字符是回车或空格的时候表示识别完成； 当读入的下个字符非数字时候，会发生语义错误，本程序是词 法分析所以没有给出。当读入的第一个字符是特殊字符的时候说明这个状态机要 识别的是特殊字符。双目特殊字符 （ 如:=,=等 ）后面的字符还可 以是特殊字符。所以在特殊字符状态的时候读入的下一个字符 是特殊字符的时候其状态还是会转向自己；当读入的下个字符 是回车或空格的时候表示识别完成；当读入的下个字符非数字 时候，状态机理应

34、转向出错处理，不过本程序同样没有给出。最后程序读入符号 #时，说明源程序读入完毕，程序结束。四.系统实现程序流程图如下所示:打开要识别的源程序文件, 初始化关键字表。调用扫描子程序，对每个字 符串扫描，识别所属类型。输出每个单词二元组。其中syn=O,表示读到的字符是 #。关键字表设置代码如下：“whilechar *rwtab6=“ begin ”， “ if ” ,“thendo” ,“ end” ;这里只给出了六个常用的关键字，真正的编译器的话应该给出所有的关键字。扫描子程序算法:关键字 标示符置 Syn=1-6置syn=10程序源代码如下：#in clude#in cludechar

35、prog80, toke n8;/prog存储源程序字符串，token存储单个字符char ch;FILE * fp;int syn, p, m, n ,sum ;char *rwtab6= begin,if,then,while,do,end ;void scaner();void main(int argc,char* argv)p=0;fp=fopen(./input.txt,r);if(!fp) printf(File open error!n);do ch=getc(fp);progp+=ch ; while ( ch!=#);p=0;fp=fopen(./output.txt,w)

36、;if(!fp) printf(File open error!n);doscaner();switch(syn)case 11:fprintf (fp,%2d,syn);fprintf (fp,%8dn,sum);break; /输出数字case -1:fprintf(fp,inpu t errorn); break;/ 出错case 29: break;/过滤回车default:fprintf (fp,%2d,syn); /输出保留字或者标识 符fprintf (fp,%8sn,token);while (syn!=0);fclose(fp);void scaner() / 词法扫描子程序

37、m=0,sum=0;for ( n=0; n=A&ch=a&ch=A&ch=a&ch=0&ch=9)/ 为字母字符或数字字符tokenm+=ch; ch=progp+;tokenm+=0; / 插入空格p-;syn=10;/种别编码for (n=0 ; n=0&ch=0&ch=9)sum=sum*10+ch-0;ch=progp+;p- ;syn=11;/数字的 syn 为 11 elseswitch(ch) case ) /字符为 syn=21; tokenm+=ch; else if (ch=) /字符为 = syn=22; tokenm+=ch;else syn=20; /字符就是 :m=0; tokenm+=ch; ch=progp+;if (ch=) /字符为 = syn=24; tokenm+=ch; syn=23;p-;break;case :m=0; tokenm+=ch; ch=progp+;if (ch=) /字符为 := syn=18; tokenm+=ch; else/ 字符为： syn=18; p-; break;case +: syn=13; token0=ch; break; case -: syn=14; token0=ch;