语法分析器实验报告.doc

该【语法分析器实验报告 】是由【花双韵芝】上传分享，文档一共【8】页，该文档可以免费在线阅读，需要了解更多关于【语法分析器实验报告 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。语法分析器的设计实验报告一、实验内容语法分析程序用LL(1)语法分析方法。首先输入定义好的文法书写文件(所用的文法可以用LL(1)分析),先求出所输入的文法的每个非终结符是否能推出空,再分别计算非终结符号的FIRST集合,每个非终结符号的FOLLOW集合,以及每个规则的SELECT集合,并判断任意一个非终结符号的任意两个规则的SELECT集的交集是不是都为空,如果是,则输入文法符合LL(1)文法,可以进行分析。对于文法:G[E]:E->E+T|TT->T*F|FF->i|(E)分析句子i+i*i是否符合文法。二、基本思想1、语法分析器实现语法分析是编译过程的核心部分,它的主要任务是按照程序的语法规则,从由词法分析输出的源程序符号串中识别出各类语法成分,同时进行词法检查,为语义分析和代码生成作准备。这里采用自顶向下的LL(1)分析方法。语法分析程序的流程图如图5-4所示。开始读入文法有效 是LL(1) 文法 判断句型 结束报错语法分析程序流程图该程序可分为如下几步:(1)读入文法(2)判断正误(3)若无误,判断是否为 LL(1)文法(4)若是,构造分析表;(5)由句型判别算法判断输入符号串是为该文法的句型。三、核心思想该分析程序有15部分组成:(1)首先定义各种需要用到的常量和变量;(2)判断一个字符是否在指定字符串中;(3)读入一个文法;(4)将单个符号或符号串并入另一符号串;(5)求所有能直接推出&的符号;(6)求某一符号能否推出‘ &’;(7)判断读入的文法是否正确;(8)求单个符号的FIRST;(9)求各产生式右部的 FIRST;(10)求各产生式左部的 FOLLOW;(11)判断读入文法是否为一个 LL(1)文法;(12)构造分析表M;(13)句型判别算法;(14)一个用户调用函数;(15)主函数;下面是其中几部分程序段的算法思想:1、求能推出空的非终结符集Ⅰ、实例中求直接推出空的 empty集的算法描述如下:voidemp(charc){ 参数c为空符号chartemp[10]; 定义临时数组inti;for(i=0;i<=count-1;i++) 从文法的第一个产生式开始查找{if产生式右部第一个符号是空符号并且右部长度为 1,then将该条产生式左部符号保存在临时数组 temp中将临时数组中的元素合并到记录可推出 &符号的数组empty中。}Ⅱ、求某一符号能否推出 '&'int_emp(charc){thenif返回1(A->B,B可推出空)右部长度为 1但第一个字符为终结符,then返回0(A->a,a为终结符)else{for(k=0;k<=j-1;k++){查找临时数组 empt[]. 并标记mark-=1(A->AB)if 找到的字符与当前字符相同 (A->AB)结束本次循环else(mark 等于0)查找右部符号是否可推出空字 ,把返回值赋给 result把当前符号加入到临时数组 empt[]里.}if 当前字符不能推出空字且还没搜索完全部的产生式then 跳出本次循环继续搜索下一条产生式else if if 当前产生式右部符号可推出空字且当前字符不是右部的最后一个字符 then获取右部符号下一个字符在所有字符集中的位置if 此字符的 FIRST集还未查找 then找其FIRST集,并标其查找状态为 1把求得的 FIRST集并入到 当前右部符号串可推出空且是右部符号串的最后一个字符Y1Y2 Yk,若对一切 1<=i<=k,均有&∈FIRST(Yi),则将&∈符号加进把空字加入到当前字符 c的FIRST集.(即产生式为c→FIRST(c))thenelse不能推出空字则结束循环标识当前字符 c已查找其 FIRST集.}3. 计算FOLLOW集FOLLOW集的构造可用如下方法来求:对于文法中的符号 X?VN,其FOLLOW(A)集合可反复应用下列规则计算,集合不再增大为止。(1)对于文法开始符号 S,因为S S,故#?FOLLOW(S);直到FOLLOW(A)若A→??B?,其中B?VN,??(VT?VN)*、??(VT?VN)+,则FIRST(?)-{?}?FOLLOW(B);若A→??B或A→??B?(????),则FOLLOW(A)?FOLLOW(B)。FOLLOW集的算法描述如下:voidFOLLOW(inti)为待求的非终结符把当前字符放到一临时数组ifX 为开始符号 then#foll[] 中,标识求已求其∈FOLLOW(X) X的产生式注:比如求 FOLLOW(B)则找A→αX或A→?X?(? ε)的产生式ifX 在产生式右部的最后 (形如产生式 A→?X)then查找非终结符 A是否已经求过其 非终结符A已求过其 FOLLOW集thenFOLLOW(A)∈FOLLOW(X)继续查下一条产生式是否含有XelseelseifXif求A之FOLLOW集,并标识为 A已求其FOLLOW集不在产生式右部的最后 (形如A→?B?)then右部X后面的符号串 ?能推出空字?then查找?是否已经求过其 已求过?的FOLLOW集thenFOLLOW(A)∈FOLLOW(B)结束本次循环elseif? 不能推出空字 then求FIRST(?)把FIRST(?)中所有非空元素加入到 FOLLOW(B)中标识当前要求的非终结符 :对所有的规则产生式 A→x:(1)若x不能推出空字?,则SELECT(A→x)=FIRST(x) ;若x可推出空字?,则SELECT(A→x)=FIRST(x)–{?}?FOLLOW(A)。算法描述如下:for(i=0;i<= 产生式总数-1;i++)先把当前产生式右部的 FIRST集(一切非空元素 ,不包括 ε)放入到当前产生式的SELECT(i);if 产生式右部符号串可推出空字 ?then把i指向的当前产生式左部的非终结符号的 FOLLOW集并入到 SELECT(i)中判断是否LL(1)文法要判断是否为LL(1)文法,需要输入的文法G有如下要求:具有相同左部的规则的SELECT集两两不相交,即:SELECT(A→?)∩SELECT(A→?)=?如果输入的文法都符合以上的要求,则该文法可以用算法描述如下:把第一条产生式的 SELECT(0)集放到一个临时数组for(i=1;i<= 产生式总数-1;i++)求temp的长度lengthLL(1)temp[]中方法分析。ifi 指向的当前产生式的左部等于上一条产生式的左部 then把SELECT(i)并入到temp数组中Iftemp 的长度小于 length 加上SELECT(i)的长度返回0else把temp清空把SELECT(i)存放到temp中结果返回1;四、算法#include<>#include<>#include<>/*******************************************/intcount=0; 回1(A->B,B可推出空)return(1);elseif(j==1&&in(right[i][0],termin)==1)A->AB)mark=1;}if(mark==1) -- 产生式X→a(a∈VT)或X→&,则把a或&加进FIRST(X)temp[0]=right[j][0];temp[1]='\0';merge(first1[i],temp,1);}for(k=0;k<(int)strlen(right[j]);k++){empt[0]='\0';}else}break;免循环递归if(c==start){免循环递归{免循环递归merge(follow[i],follow[m],1);表示已求,0表示未求followflag[j]='0';表示已求,0表示未求}for(j=0;j<=(int)strlen(v)-1;j++){first2(j); ;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==(int)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:%sstr:",S);for(p=j;p<=(int)strlen(str)-1;p++)printf("%c",str[p]);printf("\n");}}/*******************************************一个用户调用函数********************************************/voidmenu(){syntax();printf("\n 是否继续(yorn):");scanf("%c",&choose);getchar();while(choose=='y'){menu();}}/*******************************************主函数********************************************/voidmain(){inti,j;start=grammer(termin,non_ter,left,right); // 读入一个文法printf("count=%d",count);printf("\n 开始符号为:%c",start);strcpy(v,non_ter);strcat(v,termin);printf("\nprintf("\n所有符号集为非终结符集合:%s",v);:{%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();}}}由于算法仍有很多错误,最终结果没能实现,这点很失望!五、实验心得通过本次实验,我收获了很多东西。首先对编译原理这门课有了进一步的深刻理解,同时对LL(1)文法分析的原理和过程有了进一步的巩固,也锻炼了我编程的能力,巩固了平时所学的知识,真正做到了学以致用。在做实验的过程中,发现自己在编写程序过程中,总是会忽略各种细节,从而导致经常修改一些很小的低级错误才能使程序正常运行,不仅浪费时间,还影响对其他地方的修改,并且在很多步骤处理上,方法不正确。使结果不能符合要求,深刻体会到了自己在编程方面与别人的差距,在今后的学****中,我会注意改正自己在这方面的缺点,促使自己的编程水平不断进步。编译原理是一门专业学科,对于现阶段的我来说,只能掌握它的一些基本原理和概念,对于一些更深层的知识还是有很多难以理解的地方。但在这次实验过程中,锻炼了自己的思考能力,也锻炼了自己的动手编程能力,对于将知识的转化有了很大的帮助。