LL(1)文法的判别

《LL(1)文法的判别》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验四：LL（1）文法的判别一、实验名称LL（1）文法的判别二、实验目的（1）能导出空串的非终结符算法（2）实现首符集，后跟符集和可选集算法（3）输出要指出是否为LL（1）文法，三、实验原理①将数组X[]中对应每一非终结符的标记置初值为"未定"。②扫描文法中的产生式。(a)删除所有右部含有终结符的产生式，若这使得以某一非终结符为左部的所有产生式都被删除，则将数组中对应该非终结符的标记值改为"否"，说明该非终结符不能推出ε。(b)若某一非终结符的某一产生式右部为ε，则将数组中对应该非终结符的标志置为"是"，并从文法中删除该非终结符的所有产生式。例中对应非终结符A、B的标志改为"是"。

2、③扫描产生式右部的每一符号。(a)若所扫描到的非终结符号在数组中对应的标志是"是"，则删去该非终结符，若这使产生式右部为空，则对产生式左部的非终结符在数组中对应的标志改"是"，并删除该非终结符为左部的所有产生式。(b)若所扫描到的非终结符号在数组中对应的标志是"否"，则删去该产生式，若这使产生式左部非终结符的有关产生式都被删去，则把在数组中该非终结符对应的标志改成"否"。④重复③，直到扫描完一遍文法的产生式，数组中非终结符对应的特征再没有改变为止。由②中(a)、(b)得知例中对应非终结符D的标志改为"否"，对应非终结符A、B的标志改为"是"。经过上述②中(a)、(b)两步后文法中的

3、产生式只剩下：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集等。如何

4、理解转化的过程是相当重要，以及如何去创建程序去实现这一转化过程。这样的编程对于我来说是相当困难的，这次的程序并非自己编写的。但是我会一步步去理解该程序的每步含义，争取就算自己不会编写代码，但至少做到实现过程、步骤。通过实验进一步理解编译原理这门课程，知道这么可是多么难学，知道和理解了该理论在计算机中是怎样执行的，对该理论在实践中的应用有深刻的理解。在这次课程设计中，我们组就是按照实验指导的思想来完成，加强培养实践动手能力和程序开发能力。一、附录#include#includeintcount=0;/*分解的产生式的个数*/intnumber;/

5、*所有终结符和非终结符的总数*/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]

6、;/*记录各符号的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)retu

7、rn(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[]中*/intj