实验四-LR(1)分析法

江苏科技大学计算机学院编译原理实验报告0941901228章进兴实验四LR(1)分析法一、实验目的构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。二、实验内容对下列文法，用LR（1）分析法对任意输入的符号串进行分析：（1）E-E+T（2）E-T（3）T-T*F（4）T-F（5）F-(E)（6）F-i三、LR（1）分析法实验设计思想及算法(1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。(2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。LR分析器由三个部分组成：江苏科技大学计算机学院编译原理实验报告0941901228章进兴其中:SP为栈指针，S[i]为状态栈，X[i]为文法符号栈。状态转换表用GOTO[i，X]=j表示，规定当栈顶状态为i，遇到当前文法符号为X时应转向状态j，X为终结符或非终结符。ACTION[i，a]规定了栈顶状态为i时遇到输入符号a应执行。动作有四种可能：(1)移进：action[i，a]=Sj：状态j移入到状态栈，把a移入到文法符号栈，其中i,j表示状态号。(2)归约：action[i，a]=rk：当在栈顶形成句柄时，则归约为相应的非终结符A，即文法中有A-B的产生式，若B的长度为R(即|B|=R)，则从状态栈和文法符号栈中自顶向下去掉R个符号，即栈指针SP减去R，并把A移入文法符号栈内，j=GOTO[i,A]移进状态栈，其中i为修改指针后的栈顶状态。(3)接受acc:当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是'#'，则为分析成功。(4)报错:当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入端不是该文法能接受的符号串。江苏科技大学计算机学院编译原理实验报告0941901228章进兴四、实验要求1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。2、如果遇到错误的表达式，应输出错误提示信息。3、程序输入/输出实例：输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串输出过程如下：步骤状态栈符号栈剩余输入串动作10#i+i*i#移进i+i*i的LR分析过程步骤状态栈符号栈输入串动作说明10#i+i*i#ACTION[0,i]=S5,状态5入栈205#i+i*i#r6:F→i归约,GOTO(0,F)=3入栈303#F+i*i#r4:T→F归约,GOTO(0,T)=3入栈402#T+i*i#r2:E→T归约,GOTO(0,E)=1入栈江苏科技大学计算机学院编译原理实验报告0941901228章进兴501#E+i*i#ACTION[1,+]=S6,状态6入栈6016#E+i*i#ACTION[6,i]=S5,状态5入栈70165#E+i*i#r6:F→i归约,GOTO(6,F)=3入栈80163#E+F*i#r4:T→F归约,GOTO(6,T)=9入栈90169#E+T*i#ACTION[9,*]=S7,状态7入栈1001697#E+T*i#ACTION[7,i]=S5,状态5入栈11016975#E+T*i#r6:F→i归约,GOTO(7,F)=10入栈120169710#E+T*F#r3:T→T*F归约,GOTO(6,T)=9入栈130169#E+T#r1:E→E+T,GOTO(0,E)=1入栈1401#E#Acc：分析成功4、输入符号串为非法符号串(或者为合法符号串)算术表达式文法的LR分析表状态ACTIONGOTOi+*()#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r5五、实验步骤1、根据流程图编写出各个模块的源程序代码上机调试。江苏科技大学计算机学院编译原理实验报告0941901228章进兴2、编制好源程序后，设计若干用例对系统进行全面的上机测试，并通过所设计的LR(1)语法分析程序；直至能够得到完全满意的结果。3、书写实验报告；实验报告正文的内容：描述LR(1)语法分析程序的设计思想。程序结构描述：函数调用格式、参数含义、返回值描述、函数功能；函数之间的调用关系图。详细的算法描述（程序执行流程图）。给出软件的测试方法和测试结果。实验总结（设计的特点、不足、收获与体会）。六、源程序1、操作类packageLR1Analysis;classnode{intlen;charch;}publicclassLR1_Operation{privateintstateStack[]=newint[100];//状态栈privateintstatePointer=0;//状态栈指针privatechar[]symbolStack=newchar[100];//符号栈privateintsymbolPointer=0;//符号栈指针privatechar[]inputChar=newchar[1000];//输入串privateintinputPointer=0;//输入串指针privateString[][]dataStrings=newString[1000][5];//数据传递串组privateintrow=0;//数据串组行数privateStringtempString=newString();privateintnow;privateintd,t;privatebooleanresult=true;privatefinalchar[]constChar={'i','(','+','-','*','/',')','#'};//常字符privateStringresultString=newString();privateString[][]TableString=newString[12][10];publicLR1_Operation(){江苏科技大学计算机学院编译原理实验报告0941901228章进兴}//状态查找返回值-1:acc-2:归约-3:失败其它:状态转移publicintaction(intstate,charch){if(state==0){switch(ch){case'E':return1;case'T':return2;case'F':return3;case'(':return4;case'i':return5;}}if(state==1){switch(ch){case'+':return6;case'#':return-1;}}if(state==2){switch(ch){case'*':return7;case'+':case')':case'#':return-2;}}if(state==3){switch(ch){case'*':case'+':case')':case'#':return-2;}}if(state==4){switch(ch){case'E':return8;case'T':return2;case'F':return3;case'(':return4;case'i':return5;}}if(state==5){switch(ch){case'*':case'+':case')':case'#':return-2;}江苏科技大学计算机学院编译原理实验报告0941901228章进兴}if(state==6){switch(ch){case'T':return9;case'F':return3;case'(':return4;case'i':return5;}}if(state==7){switch(ch){case'F':return10;case'(':return4;case'i':return5;}}if(state==8){switch(ch){case'+':return6;case')':return11;}}if(state==9){switch(ch){case'*':return7;case'+':case')':case'#':return-2;}}if(state==10){switch(ch){case'*':case'+':case')':case'#':return-2;}}if(state==11){switch(ch){case'*':case'+':case')':case'#':return-2;}}return-3;}//打印状态栈publicvoidprintState(){tempString=;for(inti=0;i=now;i++){江苏科技大学计算机学院编译原理实验报告0941901228章进兴System.out.print(stateStack[i]+);tempString+=stateStack[i]+;}resultString+=tempString+\t\t;System.out.print(\t\t);}//打印符号栈publicvoidprintSymbol(){tempString=;for(inti=0;i=now;i++){System.out.print(symbolStack[i]);tempString+=symbolStack[i];}resultString+=tempString+\t\t;System.out.print(\t\t);}//打印输入串publicvoidprintInput(){tempString=;for(inti=0;iinputPointer;i++){System.out.print();}for(inti=inputPointer;iinputChar.length;i++){System.out.print(inputChar[i]);tempString+=inputChar[i];}resultString+=tempString+\t\t;System.out.print(\t\t);}//检查字符是否在字符表中publicbooleancheckChar(charneedCheck){for(inti=0;iconstChar.length;i++){if(needCheck==constChar[i]){returntrue;}}returnfalse;}publicnodego(inta){nodeb=newnode();if(a==3){System.out.print(r4:T-F归约,GOTO(+stateStack[now-1]+,T)=江苏科技大学计算机学院编译原理实验报告0941901228章进兴+action(stateStack[now-1],'T')+入栈\n);dataStrings[row-1][4]=r4:T-F归约,GOTO(+stateStack[now-1]+,T)=+action(stateStack[now-1],'T')+入栈;resultString+=r4:T-F归约,GOTO(+stateStack[now-1]+,T)=+action(stateStack[now-1],'T')+入栈\r\n;b.ch='T';b.len=1;returnb;}if(a==5){System.out.print(r6:F-i归约,GOTO(+stateStack[now-1]+,F)=+action(stateStack[now-1],'F')+入栈\n);dataStrings[row-1][4]=r6:F-i归约,GOTO