自上而下语法分析实验报告

1实验二：自上而下语法分析一、实验目的和要求根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对自上而下分析法的理解，从而实现一个LL(1)文法分析器。二、实验内容（1）功能描述：LL（1）分析法的功能是利用LL（1）控制程序根据显示栈栈顶内容、向前看符号以LL（1）预测分析表，对输入符号串自上而下的分析过程。本程序是基于已构建好的某一个语法的预测分析表来对用户的输入字符串进行分析，判断输入的字符串是否属于该文法的句子。（2）程序基本实现思想：接收用户输入的字符串（字符串以“#”表示结束）后，对用做分析栈的一维数组和存放分析表的二维数组进行初始化。然后取出分析栈的栈顶字符，判断是否为终结符，若为终结符则判断是否为“#”且与当前输入符号一样，若是则语法分析结束，输入的字符串为文法的一个句子，否则出错若不为“#”且与当前输入符号一样则将栈顶符号出栈，当前输入符号从输入字符串中除去，进入下一个字符的分析。若不为“#”且不与当前输入符号一样，则出错。若栈顶符号为非终结符时，查看预测分析表，看栈顶符号和当前输入符号是否构成产生式，若产生式的右部为ε，则将栈顶符号出栈，取出栈顶符号进入下一个字符的分析。若不为ε，将产生式的右部逆序的入栈，取出栈顶符号进入下一步分析。（3）程序要求：程序输入/输出示例：对下列文法，用LL(1)分析法对任意输入的符号串进行分析：E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→i|(E)2该文法的预测分析表为：输出的格式如下：LL（1）分析：输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i#输出结果：显示步骤、分析栈、剩余输入串和所用产生式的分析推导过程，若出错，则显示出在哪一步出错，并显示i+i*i#为不合法符号串。（4）程序流程图：3（5）程序结构描述：publicbooleanjudge(){StringinputChar=inputString.substring(0,1);//当前输入字符booleanflage=false;if(count1=0){for(inti=0;i6;i++){if(fenxi[count1].equals(Vt[i])){//判断分析栈栈顶的字符是否为终结符flage=true;break;}}}if(flage){//为终结符时if(fenxi[count1].equals(inputChar)){if(fenxi[count1].equals(#)&&inputString.length()==1){//栈顶符号为结束标志时Stringfenxizhan=;for(inti=0;ifenxi.length;i++){//拿到分析栈里的全部内容if(fenxi[i]==null){break;}else{fenxizhan=fenxizhan+fenxi[i];}}//输出当前分析栈情况，输入字符串，所用产生式或匹配System.out.print(+count);StringcountToString=Integer.toString(count);intfarWay=12-countToString.length();for(intk=0;kfarWay;k++){System.out.print();}System.out.print(newStringBuffer(fenxizhan).reverse());//输出分析栈farWay=17-fenxizhan.length();for(intk=0;kfarWay;k++){System.out.print();}System.out.print(inputString);farWay=20-inputString.length();for(intk=0;kfarWay;k++){System.out.print();}System.out.println(接受);flag=true;returntrue;}else{//分析栈栈顶符号不为结束标志符号时。。。。。。4//将栈顶符号出栈，栈顶指针减一fenxi[count1]=null;count1-=1;if(inputString.length()1){//当当前输入字符串的长度大于1时，将当前输入字符从输入字符串中除去inputString=inputString.substring(1,inputString.length());}else{//当前输入串长度为1时inputChar=inputString;}count++;judge();}}else{//判断与输入符号是否一样System.out.println(分析到第+count+步时出错！);flag=false;returnfalse;}}else{//非终结符时booleanfla=false;for(inti=0;i6;i++){//查询当前输入符号位于终结符集的位置if(inputChar.equals(Vt[i])){fla=true;count2=i;//终结符位置break;}}if(!fla){System.out.println(分析到第+count+步时出错！);flag=false;returnfalse;}for(inti=0;i5;i++){//查询栈顶的符号位于非终结符集的位置if(fenxi[count1].equals(Vn[i])){count3=i;//非终结符位置break;}}if(P[count3][count2]!=error){//栈顶的非终结符与输入的终结符存在产生式时Stringp=P[count3][count2];Strings1=p.substring(2,p.length());//获取对应的产生式if(s1.equals(ε)){//产生式推出“ε”时。。。。。。//将栈顶符号出栈，栈顶指针指向下一个元素fenxi[count1]=null;count1-=1;5count++;judge();}else{//产生式不推出“ε”时intk=s1.length();。。。。。。for(inti=1;i=k;i++){//将产生式右部的各个符号入栈Strings2=s1.substring(s1.length()-1,s1.length());//分析栈最后一个字符s1=s1.substring(0,s1.length()-1);if(s2.equals(')){s2=s2+s1.substring(s1.length()-1,s1.length());//,+倒数第二个字符i++;s1=s1.substring(0,s1.length()-1);}fenxi[count1]=s2;if(ik)count1++;}count++;judge();}}else{System.out.println(分析到第+count+步时出错！);flag=false;returnfalse;}}returnflag;}三、实验结果1、显示预测分析表，提示用户输入字符串2、输入的字符串为正确的句子6测试数据：输入字符串i*i+i#3、输入的字符串中包含了不属于终结符集的字符四、实验总结这次实验让我更加熟悉了LL（1）的工作流程以及LL(1)预测分析表的构造方法，我加深了对预测分析LL（1）分析法的理解，同时体验到了编译原理中一些7算法的巧妙。以前课堂上搞不懂的算法流程通过实验都能得到进一步的了解。通过本次上机实验，由于LL（1）分析法程序是一个相当复杂的程序，它需要利用到大量的编译原理，编程技巧和数据结构。由于先前掌握的知识不够牢固深刻使之在实验过程中出现了大量的问题。由于课前的充分准备，不断地调试最后顺利完成了实验。五、源码/****/packagecom.fgy.practice;importjava.io.BufferedReader;importjava.io.InputStreamReader;/***@authorguiyang*/publicclassLL{StringVn[]={E,'E,T,'T,F};//非终结符集StringVt[]={i,+,*,(,),#};//终结符集StringP[][]=newString[5][6];//预测分析表Stringfenxi[];//分析栈intcount=1;//步骤intcount1=1;//’分析栈指针intcount2=0,count3=0;//预测分析表指针StringinputString=;//输入的字符串booleanflag;publicvoidsetCount(intcount,intcount1,intcount2,intcount3){this.count=count;//1this.count1=count1;//1this.count2=count2;//0this.count3=count3;//08flag=false;}publicvoidsetFenxi(){//初始化分析栈fenxi=newString[20];fenxi[0]=#;fenxi[1]=E;}publicvoidsetP(){//初始化预测分析表for(inti=0;i5;i++){for(intj=0;j6;j++){P[i][j]=error;}}P[0][0]=-TE';P[0][3]=-TE';P[1][1]=-+TE';P[1][4]=-ε;P[1][5]=-ε;P[2][0]=-FT';P[2][3]=-FT';P[3][1]=-ε;P[3][2]=-*FT';P[3][4]=-ε;P[3][5]=-ε;P[4][0]=-i;P[4][3]=-(E);//打印出预测分析表System.out.println(已构建好的预测分析表);System.out.println(----------------------------------------------------------------------);for(inti=0;i6;i++){System.out.print(+Vt[i]);//11}9System.out.println();System.out.println(----------------------------------------------------------------------);for(inti=0;i5;i++){System.out.print(+newStringBuffer(Vn[i]).reverse()+);//9for(intj=0;j6;j++){System.out.print(+P[i][j]+);}System.out.println();}System.out.println(----------------------------------------------------------------------);}publicvoidsetInputString(Stringinput){inputString=input;}publicbooleanjudge(){StringinputChar=inputString.substring(0,1);//当前输入字符booleanflage=false;if(count1=0){for(inti=0;i6;i++){if(fenxi[count1].equals(Vt[i])){//判断分析栈栈顶的字符是否为终结符flage=true;break;}}}if(flage){//为终结符时if(fenxi[count1].equals(inputChar)){if(fenxi[count1].equals(#)&&