LL1文法的判别.doc

实验四:LL(1)文法的判别实验名称LL(1)文法的判别实验目的(1)能导出空串的非终结符算法(2)实现首符集,后跟符集和可选集算法(3)输出要指出是否为LL(1)文法,实验原理①将数组X[]中对应每一非终结符的标记置初值为"未定"。②扫描文法中的产生式。(a)删除所有右部含有终结符的产生式,若这使得以某一非终结符为左部的所有产生式都被删除,则将数组中对应该非终结符的标记值改为"否",说明该非终结符不能推出ε。(b)若某一非终结符的某一产生式右部为ε,则将数组中对应该非终结符的标志置为"是",并从文法中删除该非终结符的所有产生式。例中对应非终结符A、B的标志改为"是"。③扫描产生式右部的每一符号。(a)若所扫描到的非终结符号在数组中对应的标志是"是",则删去该非终结符,若这使产生式右部为空,则对产生式左部的非终结符在数组中对应的标志改"是",并删除该非终结符为左部的所有产生式。(b)若所扫描到的非终结符号在数组中对应的标志是"否",则删去该产生式,若这使产生式左部非终结符的有关产生式都被删去,则把在数组中该非终结符对应的标志改成"否"。④重复③,直到扫描完一遍文法的产生式,数组中非终结符对应的特征再没有改变为止。由②中(a)、(b)得知例中对应非终结符D的标志改为"否",对应非终结符A、B的标志改为"是"。经过上述②中(a)、(b)两步后文法中的产生式只剩下:S→AB和C→AD,也就是只剩下右部全是非终结符串的产生式。再由③中的(a)步扫描到产生式S→AB时,在数组中A、B对应的标志都为"是",删去后S的右部变为空,所以S对应标志置为"是"。最后由③中的(b)扫描到产生式C→AD时,其中,A对应的标志为"是",D对应的标志是"否",删去该产生式后,再无左部为C的产生式,所以C的对应标志改为"否"实验小结通过本次实验,熟悉了LL(1)文法,掌握了LL(1)文法的判定方法,具体实践了FIRST集、FOLLOW集、SELECT集的计算,加深了对LL(1)文法的理解。此外,将理论用于实践,亲身体会到了怎样求FIRST集等。如何理解转化的过程是相当重要,以及如何去创建程序去实现这一转化过程。这样的编程对于我来说是相当困难的,这次的程序并非自己编写的。但是我会一步步去理解该程序的每步含义,争取就算自己不会编写代码,但至少做到实现过程、步骤。通过实验进一步理解编译原理这门课程,知道这么可是多么难学,知道和理解了该理论在计算机中是怎样执行的,对该理论在实践中的应用有深刻的理解。在这次课程设计中,我们组就是按照实验指导的思想来完成,加强培养实践动手能力和程序开发能力。附录#include<>#include<>intcount=0;/*分解的产生式的个数*/intnumber;/*所有终结符和非终结符的总数*/charstart;/*开始符号*/chartermin[50];/*终结符号*/charnon_ter[50];/*非终结符号*/charv[50];/*所有符号*/charleft[50];/*左部*/charright[50][50];/*右部*/charfirst[50][50],follow[50][50];/*各产生式右部的FIRST和左部的FOLLOW集合*/charfirst1[50][50];/*所有单个符号的FIRST集合*/charselect[50][50];/*各单个产生式的SELECT集合*/charf[50],F[50];/*记录各符号的FIRST和FOLLOW是否已求过*/charempty[20];/*记录可直接推出^的符号*/charTEMP[50];/*求FOLLOW时存放某一符号串的FIRST集合*/intvalidity=1;/*表示输入文法是否有效*/intll=1;/*表示输入文法是否为LL(1)文法*/intM[20][20];/*分析表*/charchoose;/*用户输入时使用*/charempt[20];/*求_emp()时使用*/charfo[20];/*求FOLLOW集合时使用*/intin(charc,char*p){ inti; if(strlen(p)==0) return(0); for(i=0;;i++) { if(p[i]==c) return(1);/*若在,返回1*/ if(i==strlen(p)) return(0);/*若不在,返回0*/}}//判断一个字符是否在指定字符串中charc(){ charc='A';while(in(c,non_ter)==1) c++; return(c);}//得到一个不是非终结符的符号voidrecur(char*point)//分解含有左递归的产生式{/*完整的产生式在point[]中*/in