资源描述：
《LR(1)分析法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、实验三LR(1)分析法一、实验目的构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR(K)分析方法是严格的从左向右扫描，和自底向上的语法分析方法。二、实验内容对下列文法，用LR(1)分析法对任意输入的符号串进行分析：(1)E・E+T(2)E-E—T(3)T・T*F(4)T-T/F(5)F-(E)(6)F-i三、LR(1)分析法实验设计思想及算法(1)总控程序，也可以称为驱动程序。对所冇的LR分析器总控程序都是相同的。(2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，
2、分析表将不同，分析表又可以分为动作表(ACTION)和状态转换(GOTO)表两个部分，它们都可用二维数组表示。(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。♦LR分析器由三个部分组成:LR分析器结构:♦其中:SP为栈指针，S[i]为状态栈，X[i]为文法符号栈。状态转换表用GOTO[i,X]二j表示，规定当栈顶状态为i,遇到当前文法符号为X时应转向状态j,X为终结符或非终结符。♦ACTION[i,a]规定了栈顶状态为i时遇到输入符号a应执行。动作冇四种可能：(1)移进：ac
3、tion[i,a]=Sj：状态j移入到状态栈，把a移入到文法符号栈,其中i,j表示状态号。(2)归约:action[i,a]=rk：当在栈顶形成句柄时，则归约为相应的非终结符A,即文法中有A-B的产生式，若B的长度为R(即IBI=R),则从状态栈和文法符号栈屮口顶向卜•去掉R个符号，即栈指针SP减去R,并把A移入文法符号栈内，j=GOTO[i,A]移进状态栈，其中i为修改指针后的栈顶状态。(3)接受acc:当归约到文法符号栈中只剩文法的开始符号S时，并口输入符号串己结束即当前输入符是#,则为分析成功。⑷报错：当遇到状态栈顶为某一状态下出现
4、不该遇到的文法符号时，则报错，说明输入端不是该文法能接受的符号串。四、实验要求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:
5、T->F归约,GOTO(0,T)=3入栈402#T+i*i#r2:E-T归约,GOTO(0,E)=1入栈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归约,
6、GOTO(7,F)=10入栈120169710#E+T*F#r3:T-T*F归约,GOTO(6,T)=9入栈130169#E+T#n：E-E+T,GOTO(0,E)=l入栈1401#E#Acc：分析成功4、输入符号串为非法符号吊（或者为合法符号串）算术表达式文法的LR分析表状态ACTIONGOTO■1+*()#ETF0s5s41231s6acc2『2s7辽f23f41*4F44S5s48235f6f6T66s5s4937S5s4108S6Sii9ns7「1F
7、10D11巧f5巧f5五、实验步骤1、根据流程图编写出各个模块的源程序代码上机调
8、试。2、编制好源程序后，设计若干用例对系统进行全而的上机测试，并通过所设计的LR(1)语法分析程序；直至能够得到完全满意的结杲。3、书写实验报告；实验报告正文的内容：♦描述LR(1)语法分析程序的设计思想。♦程序结构描述：函数调用格式、参数含义、返冋值描述、函数功能；函数Z间的调用关系图。♦详细的算法描述(程序执行流程图)。♦给出软件的测试方法和测试结果。♦实验总结(设计的特点、不足、收获与体会)。源程序：#include#includc#include#include9、>#includeusingnamespacestd;intk=0;structNodel{intstate;charvt;ints;}map[100];//当状态栈中的状态遇到
