合肥工业大学编译原理实验 LL(1)分析法

实验题目：LL(1)分析法免费下载，不客气班级：学号：姓名：EditedbyMagicYang完成日期：2013-5-28一、实验目的通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。使学生了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练学生掌握开发应用程序的基本方法。有利于提高学生的专业素质，为培养适应社会多方面需要的能力。二、实验内容根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分析程序。分析法的功能是利用LL（1）控制程序根据显示栈栈顶内容、向前看符号以及LL（1）分析表，对输入符号串自上而下的分析过程。文法为（1）E-TG（2）G-+TG|-TG（3）G-ε（4）T-FS（5）S-*FS|/FS（6）S-ε（7）F-(E)（8）F-i三、数据结构及生成的算法描述事先已经构造好的表：Vn数组------非终结符表Vt数组------终结符Gr数组------文法事先定义的表及变量：非终结符按照在非终结符中的位置与first集follow集对应fi二维数组------first集,为真表示该终结符在该行对应的非终结符的first集中fo二维数组------follow集,为真表示该终结符在该行对应的非终结符的follow集中M二维数组------预测分析表用到的方法：intor(inti,Strings)---返回最近的在其右边一个“|”位置intvn(charc)---返回c在非终结符表中的位置intvt(charc)---返回c在终结符表中的位置voidaddfi(Strings,intj)---求关于某一个产生式的first集voidfirst(charv)---求非终结符c关于该文法的first集，first调用addfivoidfir()---求所以非终结符的first集，fir调用firstvoidaddfo(Strings,intj)---求关于某一个产生式的follow集voidfollow(charv)---求非终结符v关于该文法的follow集，follow调用addfovoidfol()---求所以非终结符的follow集,fol调用followvoidMM(intj,inti,Strings,intm)---将某一个产生式填入预测分析表中voidbuild_M()---构造预测分析表，build_M调用MMvoidisright(Strings)---分析一个符号串是否符合该文法四、算法流程图五、源程序代码和测试的结果packagepackage_two;importjava.util.*;importjava.io.*;publicclassLL{charVn[]={'E','T','G','F','S'};//非终结符charVt[]={'+','-','*','/','(',')','i','#','ε'};//终结符//非终结符按照在非终结符中的位置与first集follow集对应booleanfi[][]=newboolean[Vn.length][Vt.length+1];//first集,为真表示该终结符在该行对应的非终结符的first集中booleanfo[][]=newboolean[Vn.length][Vt.length+1];//follow集,为真表示该终结符在该行对应的非终结符的follow集中StringM[][]=newString[Vn.length][Vt.length-1];//预测分析表StringGr[]={E-TG,G-+TG|-TG,G-ε,T-FS,S-*FS|/FS,S-ε,F-(E),F-i};//文法LL(){fir();//求first集fol();//求follow集build_M();//求预测分析表}intor(inti,Strings){//返回最近的在其右边一个“|”位置for(i=i+1;is.length();i++){if(s.charAt(i)=='|')returni;//存在，就返回位置}return-1;//返回-1表示没有“|”在其右边}intvn(charc){//返回c在非终结符表中的位置inti;for(i=0;iVn.length;i++){if(c==Vn[i])returni;//在表中，就返回位置}return-1;//返回-1表示不在表中}intvt(charc){//返回c在终结符表中的位置inti;for(i=0;iVt.length;i++){if(c==Vt[i])returni;//在表中，就返回位置}return-1;//返回-1表示不在表中}voidaddfi(Strings,intj){//求关于某一个产生式的first集intv=vn(s.charAt(0));//v为产生式左边的非终结符inti;if(vt(s.charAt(j))!=-1){//产生式右边第一个为终结符fi[v][vt(s.charAt(j))]=true;//就把s.charAt(j)加入s.charAt(0)的first集}else{//产生式右边第一个为非终结符if(!fi[vn(s.charAt(j))][Vt.length]){//如果s.charAt(j)的first集没有求，先求s.charAt(j)的first集first(s.charAt(j));}for(i=0;iVt.length;i++){//把s.charAt(j)的first集中不为ε的加入s.charAt(0)的first集if(fi[vn(s.charAt(j))][i]&&Vt[i]!='ε'){fi[v][i]=true;}}if(vt('ε')!=-1)//终结符中有εif(fi[vn(s.charAt(j))][vt('ε')]){//如果ε属于当前s.charAt(j)的first集if(j==s.length()-1){//j=s.length()-1就将ε加入s.charAt(0)的first集fi[v][vt('ε')]=true;return;}if(s.charAt(j+1)!='|'){//s.charAt(j+1)不是“|”就将s.charAt(j+1)的first集加入s.charAt(0)的first集j++;addfi(s,j);}else{//s.charAt(j+1)是“|”就将ε加入s.charAt(0)的first集fi[v][vt('ε')]=true;}}}}voidfirst(charv){//求非终结符v关于该文法的first集inti,j;Strings;for(i=0;iGr.length;i++){s=Gr[i];if(s.charAt(0)==v){//产生式的左边是要求的非终结符j=3;if(s.charAt(0)!=s.charAt(j))//要求的非终结符与右边第一个不同时，求first集addfi(s,j);//求关于此产生式的first集while(or(j,s)!=-1&&js.length())//判断有无‘|’，有就继续求first集{j=or(j,s);//得到‘|’位置if(s.charAt(0)!=s.charAt(j+1))//要求的非终结符与右边第一个不同时，求first集addfi(s,j+1);//求关于此产生式的first集}}}fi[vn(v)][Vt.length]=true;//将fi[vn(v)][Vt.length]设为true，表示已求v的first集}voidfir(){//求所以非终结符的first集inti,j;for(i=0;iVn.length;i++){//非终结符的first集未求时，求该非终结符的first集if(!fi[i][Vt.length]){first(Vn[i]);}}System.out.println(first集);for(i=0;iVn.length;i++){//输出非终结符的first集System.out.println(Vn[i]);for(j=0;jVt.length;j++){if(fi[i][j]){System.out.print(+Vt[j]);}}System.out.println();}}voidaddfo(Strings,intj){//求关于某一个产生式的follow集inti;//考察字符位于产生式末尾时将产生式左边的那个字符的follow集加到考察字符的follow集中if(j==s.length()-1||(js.length()-1&&s.charAt(j+1)=='|')){if(s.charAt(0)!=s.charAt(j)){//考察字符与产生式左边的非终结符不同时if(!fo[vn(s.charAt(0))][Vt.length]){//产生式左边的非终结符的follow集未求时，先求产生式左边的非终结符的follow集follow(s.charAt(0));}for(i=0;iVt.length;i++){//产生式左边的非终结符的follow集加到考察字符的follow集中if(fo[vn(s.charAt(0))][i]){fo[vn(s.charAt(j))][i]=true;}}}}//将考察字符右边第一个字符的first集加到考察字符的follow集中if(js.length()-1&&s.charAt(j+1)!='|'){if(vt(s.charAt(j+1))!=-1){//该字符为终结符if(Vt[vt(s.charAt(j+1))]!='ε')//该字符不为ε，将该字符加入考察字符的follow集中fo[vn(s.charAt(j))][vt(s.charAt(j+1))]=true;}else{//该字符不为终结符for(i=0;iVt.length;i++){//该字符的first集中除ε的非终结符加入考察字符的follow集中if(fi[vn(s.charAt(j+1))][i]&&Vt[i]!='ε'){fo[vn(s.charAt(j))][i]=true;}}if(vt('ε')!=-1){//非终结符中有ε//当考察字符右边的字符串的first集中有'ε'将产生式左边的那个字符的follow集加到考察字符的follow集中if(s.charAt(0)==s.charAt(j))return;////考察字符与产生式左边的非终结符时同时，返回booleanm=true;//当考察字符右边的字符串的first集中有'ε'，m为真，没有时，m为假for(i=j+1;is.length();i++){if(vt(s.charAt(i))!=-1){//当考察字符右边的字符串中有终结符，m为假m=false;break;}if(s.charAt(i)=='|'){//遇到'|'跳出break;}if(!fi[vn(s.charAt(i))][vt('ε')]){//当考察字符右边的字符串中的有一非终结符的first集中不含ε，m为假m=false;}}if(m){//m为真，将产生式左边的那个字符的follow集加到考察字符的follow集中if(!fo[vn(s.charAt(0))][Vt.length]){//产生式左边的非终结符的follow集未求时，先求产生式左边的非终结符的follow集follow(s.charAt(0));}for(i=0;iVt.length;i++){//产生式左边的非终结符的follow集加到考察字符的follow集中if(fo[vn(s.charAt(0))][i]){fo[vn(s.charAt(j))][i]=true;}}}}}}}voidfollow(charv){//求非