资源描述：
《lr(1)实验报告(附代码)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、实验三LR(1)分析法实验学时：4实验类型：验证实验要求：必修一、实验目的构造LR(1)分析程序，利用它进行语法分析，判断给岀的符号串是否为该文法识别的句子，了解LR(K)分析方法是严格的从左向右扫描，和自底向上的语法分析方法。实验内容对下列文法，用LR(1)分析法对任意输入的符号串进行分析:(产生式有误,进行修改)(1)E-E+T(2)E・E—T(E->T)(3)T-T*F(4)T-T/F(T->F)(5)F-(E)(6)F-i三.实验目的1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。2、
2、如果遇到错误的表达式，应输出错误提示信息。3、程序输入/输出实例:输入一以#结束的符号串(包括+—*/()i#)：在此位置输入符号串输出过程如下：步骤状态栈符号栈剩余输入串动作10#i+i*i#移进j+門的LR分析过程步骤状态栈符号栈输入串动作说明10#ACTION[Ozi]=S5状态5入栈205#i+i*i#r&FT归约,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入栈501#E+i*i#ACTI
3、ON",+]二S®状态6入栈6016#E+i*i#ACTION[6J]=S5/状态5入栈70165#E+i引#佐FT归约,GOTO(6,F)=3入栈80163#E+F*i#r4：T->F归约ZGOTO(6ZT)=9入栈90169#E+T*i#ACTION[9/]=S7z状态7入栈1001697#E+T*i#ACTION[7J]=S5狀态5入栈11016975#E+T*i#r&FT归约,GOTO(7,F)=10入栈120169710#E+T*F#rs：T->T*F归约,GOTO(6,T)=9入栈130169#
4、E+T#ri：E->E+T,GOTO(0,E)“入栈1401#E#Acc:分析成功实验报告正文的内容:♦描述LR⑴语法分析程序的设计思想：♦定义项目的一般形式是［A->oc・
5、3,aia2...ak］,这样的一个项目称为一个LR(k)项目。项目中的aia2...ak称为它的向前搜索符串(或展望串)，令K二1,即为LR⑴语法分析程序。在此，重新定义CLOSURE⑴的算法：项目集I的闭包CLOSURE⑴构造方法：1.1的但可项目都属于CLOSURE(I)。2.若项目［ArrBh间属于CLOSURE(I),B-g
6、是一个产生式，那么，对于FIRST(阴中的每个终结符b，如果［B—&切原来不在CLOSURE⑴中，则把它加进去。3.重复执行步骤2,直至CLOSURE(I)不再增大为止。G0()的算法保持与LR语法分析程序一样,通过以下方法构造文法分析动作ACTION和状态转换GOTO构造如下：1.若项目［A->oc・a［3,切属于Ik且GO(Ik/a)二Ij,a为终结符，则置ACTION［k,a］为〃sj"。2•若项目［A-oc•间属于Ik,则置ACTION［kza］为〃rj〃；其中假定A-oc为文法G的第j个产生式。3
7、.若项目[SJS・,#]属于Ik,则置ACTION[kz#]为〃acc"。4.若GO(k,A)=Ij,则置GOTO[kfA]=jo3.分析表中凡不能用规则1至4填入信息的空白栏均填上〃出错标志〃。当具体面对输入串时,通过查表进行分析该进行何种动作。♦程序结构描述:函数调用格式、参数含义、返回值描述、函数功能均在程序源代码出注释出来,在此不再赘述,详细含义请参照源代码cpp文件。♦详细的算法描述(程序执行流程图)：(1)总控程序,也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。(2)分析表或分析函数
8、,不同的文法分析表将不同”同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表(ACTION)和状态转换(GOTO)表两个部分，它们都可用二维数组表示。G)分析栈，包括文法符号栈和相应的状态栈,它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。.LR分析器由三个部分组成:LR分析器结构^♦其中:SP为栈指针zS[i]为状态栈，X[i]为文法符号栈。状态转换表用GOTO[i,X]=j表示，规定当栈顶状态为i,遇到当前文法符号为X时应转向状态j”X为终结符或非终结符。♦ACT
9、IONSa]规定了栈顶状态为i时遇到输入符号a应执行。动作有四种可能：⑴移进：action[i,a]二Sj:状态j移入到状态栈，把a移入到文法符号栈，其中ij表示状态号。⑵归约：action[i,a]=rk:当在栈顶形成句柄时，则归约为相应的非终结符A,即文法中有A-B的产生式,若B的长度为R(即
10、B
11、二R),则从状态栈和文法符号栈中自顶向下去掉R个符号,即栈指针SP减去R,并把A移入文法符号栈内,j=GOTO[
