编译原理课程设计_LL(1)文法的判定

1、课程设计报告课程：编译原理课程设计学号：姓名：班级：教师：时间：2015.05.20-2015.07.02计算机学院设计名称：LL（1）文法的判定（假设文法符合的First和Follow集已/未知）设计内容、目的与要求：1、 设计内容(1) LL（1）文法的判定（假设文法符合的First和Follow集已/未知）根据LL(1) 分析法编写一个语法分析程序，可根据自己实际情况，选择以下一项作为分 析算法的输入： a.直接输入根据已知文法构造的分析表M; b.输入文法的FIRST()和FOLLOW(U)集合，由程序自动生成文法的分析表M； c.输入已知文法，由程序自动构造文法的分析表M。(2) 所

2、开发的程序可适用于不同的文法和任意输入串，且能判断该文法是否为 LL(1)文法。(3)如完成前两项，可增加运行实例，对于输入的文法和符号串，所编制的语法分析程序应能正确判断此串是否为文法的句子，并要求输出分析过程。2、 要求： 输入文法，输出判定该文法是否是LL（1）的。计划与进度安排：5月20日5月23日：查阅资料，进一步掌握LL（1）文法的定义，掌握LL（1）分析法及其原理；5月24日5月26日：分析题目，画出系统的流程图；5月27日5月29日：根据流程图，将系统功能划分成各个不同的模块；5月30日5月31日：根据不同的模块，设计与其相对应的函数，并依据分析函数的功能设置函数的参数和返回值

3、；6月1日6月2日：根据上一步的各个函数，编写对应的代码；6月3日6月4日：对各个函数进行编译和检查；6月5日6月6日：编写程序执行的入口函数main（）函数，通过调用各个函数，实现整个程序的基本功能；6月7日6月8日：编写程序执行的入口函数main（）函数，通过调用各个函数，实现整个程序的基本功能；6月9日6月10日：编译整个程序，并根据调试信息进行相应的修改，同时 设计相关的文法进行测试，检查程序是否满足设计要求；6月11日6月12日：使用不同的实例进行测试，同时修改并完善设计；6月13日7月2日：完成设计并答辩。设计过程、步骤（可加页）：1、 数据结构设计 数据结构设计的合理性直接关系着

4、系统功能的实现方便与否。本系统的数据结构包含全局变量的定义和一位数组以及二维数组的定义。int count=0; /*分解的产生式的个数*/int number; /*所有终结符和非终结符的总数*/char start; /*开始符号*/char termin50; /*终结符号*/char non_ter50; /*非终结符号*/char v50; /*所有符号*/char left50; /*左部*/char right5050; /*右部*/char first5050,follow5050; /*各产生式右部的FIRST和左部的FOLLOW集合*/char first15050; /*

5、所有单个符号的FIRST集合*/char select5050; /*各单个产生式的SELECT集合*/char f50,F50; /*记录各符号的FIRST和FOLLOW是否已求过*/char empty20; /*记录可直接推出的符号*/char TEMP50; /*求FOLLOW时存放某一符号串的FIRST集合*/int validity=1; /*表示输入文法是否有效*/int ll=1; /*表示输入文法是否为LL(1)文法*/int M2020; /*分析表*/char choose; /*用户输入时使用*/char empt20; /*求_emp()时使用*/char fo20;

6、 /*求FOLLOW集合时使用*/int dg=0; /*标志输入文法是否是由有递归的文法哈成的LL（）*/2、 函数设计及其说明（1）int in(char c,char *p)功能：判断一个字符是否在指定字符串中说明：若该字符在指定字符串中，函数返回1；否则返回0。（2）void MM()功能：构造预测分析表M。说明：在该函数中，把预测分析表设计成二维数组，构造预测分析表时，文法用其序号代替。（3）void menu() 功能：设置用户界面。 说明：该函数将设计一个人机交互界面，从而选择实现各种功能。（4）void Ch( ) 功能：得到一个不是非终结符的符号。 说明：该函数通过调用in(

7、char c,char *p)函数，返回一个不是非终结符的符号。（5）void merge(char *d,char *s,int type)功能：将单个符号或符号串并入另一符号串 说明：d指向目标符号串，s指向源串，type1，源串中的一并并入目串；type2，源串中的不并入目串。（6）void recur(char *point)功能：分解含有左递归的产生式。说明：完整的产生式在point 中。（7）void non_re(char *point)功能：分解不含有左递归的产生式，即将形如P*Qa|F的产生式分解为P*Qa和PF。说明：完整的产生式在point 中。（8）int judge(

8、) 功能：判断读入的文法是否正确 说明：若读入的文法不正确则返回0，否则返回1。（9）void syntax()功能：检查输入串是否满足，通过分析表判断。 说明：通过分析表判断，检查输入的字符串是否满足。（10）char grammer(char *t,char *n,char *left,char right5050)功能：读入一个文法。 说明：char *t指向终结符号的集合；char *n指向非终结符号的集合；char *left指向文法产生式的左部；char right5050传递的参数是文法产生式的右部。（11）void FOLLOW(int i)功能：求各产生式左部的FOLLOW集

9、。 说明：i为分解后的产生式的序号。（12）void first2(int i)功能：求单个符号的FIRST集。 说明：i为符号在所有输入符号中的序号。（13）void FIRST(int i,char *p)功能：求各产生式右部的FIRST集。 说明：i为分解后的产生式的序号；char *p指向产生式的右部。（14）int ll1()功能：判断读入文法是否为一个LL(1)文法。 说明：若输入的文法是LL(1)文法，返回1，否则报错，返回0。（15）void emp(char c)功能：求所有能直接推出的符号,这里利用代替。 说明：char c 是需要判断的符号。（16）int _emp(ch

10、ar c)功能：求某一符号能否推出 说明：char c 是需要判断的符号，若能推出，则返回1，否则返回0。3、 总控算法及流程（1） 推导出非终结符首先进行第一次扫描，把能够直接推出$的非终结符号记录到空串表，把不能直接推出$的符号依次记录下来，然后单个扫描每一个不能直接推出$的符号。扫描这个符号能够直接推出的第一个非终结符记录到一个队列，接下来依次检查队列中每一个元素，把二次能够推出$的符号记录到空串表，把二次也推不出空串的继续送入到队列，然后再从队列取元素扫描，直到队列为空没能找到能够星推导出$的终结符，那么可以确定这个非终结符推导不出$，接下去扫描下一个非终结符。 （2）确定FIRST集

11、FIRST集使用以下四个步骤判定：1)、若XVTT,则FIRST(X)=X 2)、若XVN,且有产生式Xa，aVT则把a加入到FIRST(X)中，即aFIRST(X) 3)、若XVN,且有产生式X$，则把$也加到FIRST(X)中，即$FIRST(X) 4)、若XVN, Y1，Y2，Yi 都VN，且有产生式XY1Y2Yn。 当Y1，.Yi-1=$ (1in)，则FIRST(Y1)-$，FIRST(Yi-1)- $，FIRST(Yi)都包含在FIRST(X)中，即： FIRST(Yi-1)-$ FIRST(X) 所有Y1,Yn *= $ ,则把$加到FIRST(X)中,即: FIRST(Yi)

12、FIRST(X) 其中第1-3个方法都很好处理，关键是第四个方法判断时首先判断第一个字符为非终结符，设定一个布尔型扫描标志FLAG，赋初值TRUE，接下去依次扫描产生式右部每一个字符Yi，假如第i个字符可以推出空，那么就把这个字符的FIRST集去除$加入到产生式左部字符的FIRST集中，即FIRST(Yi)-$FIRST(X),假如Yi是终结符或者不可以推出$，那么就把这个字符的FIRST集直接加入到FIRST(X)中，即FIRST(Yi)FIRST(X)同时置FLAG为FALSE不再向下扫描，假如Yi恰好是最后一个字符，那么不管它能不能星推导出空都直接把它的FIRST集加入到FIRST(X)

13、中。同时要设置一个队列和一组布尔型变量记录FIRST集是否完成，队列用来记录FIRST(X)用到了哪些其它非终结符的FIRST集。 第一遍扫描完成后就扫描队列，把FIRST集完成的非终结符的FIRST集加入到那些没有完成的非终结符的FIRST集中去，没有完成的非终结符再送回到队列，这时候可能出现死循环，比如FIRST(S)用到了FIRST(A),而FIRST(A)用到了FIRST(B)，FIRST(B)又用到了FIRST(S),这时候S,A,B的FIRST标志均为FALSE，无限循环下去。这时候可以记录一下，比如循环了100次，强行设置FIRST(S)的标志为TRUE，那么FIRST(A),F

14、IRST(B)也就依次可以求出了。我们在实际计算时也是这样处理的，只是没有把标志写出来而是记录在心里的。（3）确定FOLLOW集FOLLOW集使用以下三个步骤判定： 1)、如果 X 是开始符 那么把 # 加入到 FOLLOW(X) 2)、若=B是一个产生式,则把FIRST()$加至FOLLOW(B)中 3)、若=B是一个产生式，或=B是一个产生式而*=$(即$FIRST()），则把 FOLLOW(A)加至FOLLOW(B)中。 FOLLOW集的求法与FIRST集类似，但有不同的地方。FOLLOW集需要扫描每一个产生式。而FIRST集扫描的是产生式左部不同的产生式，然后扫描左部相同的产生式的每一

15、个右部。FOLLOW集第一次扫描可以确定哪些FIRST集或FOLLOW集属于所求的FOLLOW集，由于FIRST集已经求出，所以第一次扫描就可以把相应的FIRST集加入到FOLLOW集中，设置FOLLOW集完成标记位，设置队列，把未完成的非终结符送入队列，依次取出队列元素，把求出FOLLOW集的非终结符的FOLLOW集加入到相应的FOLLOW集中，把未求出的送回队列。如果碰到死循环使用FIRST集一样的方法处理就可以。（4）确定SELLECT集FIRST集FOLLOW集都已经求出来后SELLECT集就很好求了，扫描每一个产生式，使用以下三个步骤确定： A AVN，V*， 1)、若是终结符，那么

16、SELLECT(A)=； 2)、若是$，则SELECT(A)=FOLLOW(A)； 3)、若是非终结符，那么 若*=$，则SELECT(A)=(FIRST()-$)FOLLOW(A)； 若*=$ 则SELECT(A)=FIRST()。（5）LL(1)文法的判定当SELLECT集求出来后就可以判断是不是一个文法是不是LL(1)文法了，扫描产生式左部相同的SELLCET集是否含有相同元素，一旦发现相同元素立刻返回0，扫描结束没有发现相同元素则返回1。（6）句子的判定当一个文法确定是LL(1)文法时就可以对输入的语句进行判定了。首先要安装SELLECT集生成LL(1)预测分析表，最简单的方法是使用哈

17、希表来表示，把每一个产生式左部依次和这个产生式SELLECT集中的每一个终结符组成关键字，其值即为这个产生式，送入哈希表。这样在进行句子的分析时就可以很容易判断是否使用某一个产生式来进行规约。在实际分析时设置两个栈，把#压入分析栈和剩余栈，把开始符压入分析栈，把输入串从右向左送入剩余栈，然后只要两个栈元素个数同时大于1，那么依次从两个栈中取出两个元素进行比较，假如一样就匹配，假如可以规约就规约，否则就不是该文法的句子。图1 整个系统控制流程图结果与分析（可以加页）： 1、 输入一个LL(1)进行测试，测试文法，测试结果如下图所示G(Z)：Z-dAZ | bAc A-aA|图4 输入LL(1)文

18、法并测试2、 输入上述文法的一个句型进行测试，测试结果如下图所示待测试的句型1： bac 图5 测试满足指定文法的句型待测试句型2：abc图6 测试不满足指定文法的句型3、测试一个非LL(1)文法图7 测试非LL(1)文法设计体会与建议： xx：近一个月的设计过程，虽然题目早已经布下，但当时正在学习中，看到题目仅是一头雾水，没有一点头绪。刚拿到题目的时候，乍看很简单，但当真正入手做的时候，觉得设计一个合理的数据结构不是一件很容易的事。因为一个好的软件设计，应该考虑到它的健壮性和可扩充性，而且能够做的比较完善，对于系统运行中可能遇到的问题能够给出人性化的提示。这需要在问题分析和题目设计的过程中逐

19、渐改进。就本次设计而言，要构造预测分析表，就要考虑输入的文法是否是LL（1）文法，这个文法应该满足：无二义性，无左递归，无左公因子，同时对检测的结果应该给予适当的处理。经过查找资料和他人的耐心答疑，我终于设计处理较为合理的程序，达到了预期的课程设计目的。随着课程的深入，逐渐了解到一点解题的方法，但对于上机实践还是没有什么想法，后来到图书馆和网上找了很多资料，才了解到大致的实现方法，有根据以前的一点编程经验，于是开始一个模块一个模块的去实现，然后在进行整合，合并成一个完整的程序。xx：通过本次课程设计，使学到的理论知识得到了实践，清晰地看到了LL（1）分析的全过程，掌握了first，follow

20、，select的机上实现方法，掌握了分析表的构造过程和方法，但遗憾的是，对于一些实现方法，例如句型分析的跟踪过程，仍是参考的网上的源程序，感到了自己的不足，还需更加努力！语法分析是编译过程的核心部分，它的任务是在词法分析识别单词符号串的基础上，分析并判断程序的的语法结构是否符合语法规则。语言的语法结构是用上下文无关文法描述的。因此语法分析器的工作的本质上就是按文法的产生式，识别输入符号串是否为一个句子。对于一个文法，当给你一串符号是，如何知道它是不是该文法的一个句子，这是这个课程设计所要解决的一个问题。其实要知道一串符号是不是该文法的一个句子，只要判断是否能从文法的开始符号出发推导出这个输入串

21、。语法分析可以分为两类，一类是自上而下的分析法，一类是自下而上的分析法。自上而下的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号出发，自上而下的为输入串建立一棵语法树。或者说，为输入串寻找一个最左推倒，这种分析过程的本质是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程我主要是自上而下的过程。xxx： 这次最大的收获就是清楚了编译的整个过程，在学习编译原理这门课程之时，在做实验的过程中和第二章联系起来，非常清晰的理解了程序的编译实现过程。读完了一个完整的源程序，知道了它里面的功能模快以及结构组织，也明白了编译的基本原理。其中先输入一个文法，然后判断将各非终结符的FIRST和F

22、OLLOW集求出，再求出SELECT集，就可以来判断此文法是不是LL（1）文法，如果是LL（1）文法，就将此文法的预测分析表求出，还要可以判断输入的字符串是不是这个文法的一个句型。在实验中加深了在课堂上说学到编译原理知识的理解，实验中实践了书本上的知识和原理。设计前应做好准备，即根据设计目的、要求来分析，选择相应的数据结构，使用语言参照算法中的流程编写词法分析的程序。将编好的程序上机进行调试，注意调试的例子应有词法正确的，也应有词法错误的或是超出所选数据结构范围的。xxx：通过这次程序设计，我更加清楚透彻的明白了LL(1)分析法的过程，LL(1)分析法的解决步骤是首先接收到用户输入的一个文法，

23、对文法进行检测和处理，消除左递归得到LL(1)文法，当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈，从这个分析法我就比较熟练地掌握了自上而下语法分析的基本思想，此外，巩固了所学的数据结构的知识，自己所学的知识能够联系起来，使得知识自成系统。在实现和调试时次采取模块化的思想，使得本次课程设计比较顺利，增强了自己的信心，提高了自己的编程能力和动手能力以及独立分析问题、解决问

24、题的能力和综合运用所学知识的能力。附录：程序代码#include#include#include/*/int count=0;/*分解的产生式的个数*/int number;/*所有终结符和非终结符的总数*/char start;/*开始符号*/char termin50;/*终结符号*/char non_ter50;/*非终结符号*/char v50;/*所有符号*/char left50;/*左部*/char right5050;/*右部*/char first5050,follow5050;/*各产生式右部的FIRST和左部的FOLLOW集合*/char first15050;/*所有单

25、个符号的FIRST集合*/char select5050;/*各单个产生式的SELECT集合*/char f50,F50;/*记录各符号的FIRST和FOLLOW是否已求过*/char empty20;/*记录可直接推出的符号*/char TEMP50;/*求FOLLOW时存放某一符号串的FIRST集合*/int validity=1;/*表示输入文法是否有效*/int ll=1;/*表示输入文法是否为LL(1)文法*/int M2020;/*分析表*/char choose;/*用户输入时使用*/char empt20;/*求_emp()时使用*/char fo20;/*求FOLLOW集合时

26、使用*/* 判断一个字符是否在指定字符串中*/int in(char 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,k,m=0,n=3;cha

27、r ch,temp20;ch=c();/*得到一个不是非终结符的符号*/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);/*从temp所指向的内存单元顺序取m个字节复制到右部*/rightcountm=ch;r

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

29、tcount=point0; memcpy(rightcount,temp,m); rightcountm=ch; rightcountm+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;else leftcount=point0; memcpy(rightcount,temp,m); rightcountm=0;m=0;count+; leftcount=point0

30、; memcpy(rightcount,temp,m); rightcountm=0; count+;m=0;/* 读入一个文法*/char grammer(char *t,char *n,char *left,char right5050)char vn50,vt50;char s;char p5050;int i,j,k;printf(请输入文法的非终结符号串：); scanf(%s,vn);/getchar();/*取出缓冲区剩余的回车键，不要也可*/ i=strlen(vn); memcpy(n,vn,i);ni=0;printf(n请输入文法的终结符号串：); scanf(%s,vt

31、);getchar(); i=strlen(vt); memcpy(t,vt,i);ti=0; printf(n请输入文法的开始符号：);scanf(%c,&s);/getchar();printf(n请输入文法产生式的条数：); scanf(%d,&i);/getchar(); for(j=1;j=i;j+)printf(n请输入文法的第%d条（共%d条）产生式：,j,i);scanf(%s,pj-1); getchar(); for(j=0;j)printf(nInput error!n); validity=0;return(0); /*检测输入错误*/for(k=0;k=i-1;k+)

32、/*分解输入的各产生式*/if(pk3=pk0) recur(pk);else non_re(pk);return(s);/* 将单个符号或符号串并入另一符号串*/void merge(char *d,char *s,int type)/*d是目标串s是源串，type1，源串中的并入目串；type2，源串中的不并入目串*/ int i,j;for(i=0;i=strlen(s)-1;i+) if(type=2&si=);elsefor(j=0;j+) if(jstrlen(d)&si=dj) break; if(j=strlen(d) dj=si; dj+1=0; break;/* 求所有能直

33、接推出的符号*/void emp(char c)/*即求所有由推出的符号*/char temp10;int i;for(i=0;i=count-1;i+)if(righti0=c&strlen(righti)=1)temp0=lefti;temp1=0;merge(empty,temp,1);emp(lefti);/* 求某一符号能否推出*/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) re

34、turn(1);for(i=0;i+)if(i=count) return(0);if(lefti=c)/*找一个左部为c的产生式*/ j=strlen(righti);/*j为右部的长度*/if(j=1&in(righti0,empty)=1) return(1);else if(j=1&in(righti0,termin)=1) return(0);else for(k=0;k=j-1;k+) if(in(rightik,empt)=1) mark=1;if(mark=1) continue;else for(k=0;k=j-1;k+)result*=_emp(rightik);temp0

35、=rightik;temp1=0;merge(empt,temp,1); if(result=0&icount) continue; else if(result=1&icount) return(1);/* 判断读入的文法是否正确*/int judge() int i,j;for(i=0;i=count-1;i+)if(in(lefti,non_ter)=0)/*若左部不在非终结符中，报错*/printf(nLeft error!);validity=0;return(0);for(j=0;j=strlen(righti)-1;j+)if(in(rightij,non_ter)=0&in(r

36、ightij,termin)=0&rightij!=)/*若右部某一符号不在非终结符、终结符中且不为，报错*/printf(nRight error!);validity=0;return(0);return(1);/* 求单个符号的FIRST集*/void first2(int i)/*i为符号在所有输入符号中的序号*/ char c,ch=,temp20;int j,k,m;c=vi;emp(ch);if(in(c,termin)=1)/*若为终结符*/ first1i0=c; first1i1=0; else if(in(c,non_ter)=1)/*若为非终结符*/for(j=0;j=

37、count-1;j+) if(leftj=c) if(in(rightj0,termin)=1|rightj0=) temp0=rightj0; temp1=0;merge(first1i,temp,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=0)

38、 firsti0=; firsti1=0;elseTEMP0=;TEMP1=0;elsefor(j=0;j+)if(vj=p0) break;if(i=0) memcpy(firsti,first1j,strlen(first1j); firstistrlen(first1j)=0;elsememcpy(TEMP,first1j,strlen(first1j);TEMPstrlen(first1j)=0; else/*如果右部为符号串*/for(j=0;j+)if(vj=p0) break;if(i=0) merge(firsti,first1j,2);else merge(TEMP,firs

39、t1j,2);for(k=0;k=length-1;k+)empt0=0;if(_emp(pk)=1&k=0) merge(firsti,first1m,2);else merge(TEMP,first1m,2); else if(_emp(pk)=1&k=length-1) temp0=;temp1=0;if(i=0) merge(firsti,temp,1); else merge(TEMP,temp,1);else if(_emp(pk)=0) break;/* 求各产生式左部的FOLLOW集*/void FOLLOW(int i)int j,k,m,n,result=1;char c,temp20;c=non_teri;/*c为待求的非终结符*/temp0=c;temp1=0;merge(fo,temp,1);if(c=start)/*若为开始符号*/temp0=#;temp1=0;merge(followi,temp,1); for(j=0;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=strl