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、如果遇到错误的表达式，应输出错误提示信息。3、程序输入/输出实例：输入一以#结束的符号串（包括+—*/（）i#）：在此位置输入符号串输出过程如下：步骤状态栈符号栈剩余输入串 动作1 0 # i+i*i# 移进i+i*i的LR分析过程步骤状态栈符号栈输入串动作说明10#i+i*i#ACTION[0,i]=S5,状态5入栈205#i+i*i#r6：Ffi归约,6。10（0乃）=3入栈303#F+i*i#r：：TfF归约,6010(0,1)=3入栈402#T+i*i#f：EfT归约,6010（0刘）=1入栈501#E+i*i#ACTION[1,+]=S6,状态6入栈6016#E+i*i#ACTION[6,i]=S6,状态5入栈70165#E+i*i#r6：Ffi归约,3。10（6乃）=3入栈80163#E+F*i#r6：TfF归约,6010(6,1)=9入栈90169#E+T*i#ACTION[9,*]=S7,状态7入栈1001697#E+T*i#ACTION[7,i]=S7,状态5入栈11016975#E+T*i#r6：Ffi归约,601。（7廿）=10入栈120169710#E+T*F#r6：TfT*F归约,GOTO(6,T)=9入栈130169#E+T#r1：EfE+T,GOTO(0,E)=1入栈1401#E#Acc：分析成功实验报告正文的内容：描述LR(1)语法分析程序的设计思想：定义项目的一般形式是［A- - ,aa-a］,这样的一个项目称为一个LR(k)项目。项目中的aa-a称为V晶向箭搜索符串(或展望串)，令K=l,即为LR⑴语法分析程昌；在上匕，重新定义CLOSURE⑴的算法：项目集I的闭包CLOSURE(I)构造方法：.I的任何项目都属于CLOSURE(I)。.若项目［Af-B,a］属于CLOSURE(I),是一个产生式，那么，对于FIRST(a)中的每个终结符b,如果［B--，b］原来不在CLOSURE(I)中，则把它加进去。.重复执行步骤2,直至CLOSURE(I)不再增大为止。GO()的算法保持与LR语法分析程序一样，通过以下方法构造文法分析表:动作ACTION和状态转换GOTO构造如下：.若项目［A--a,b］属于<且G0(%a)=L，a为终结符，则置ACTION［k,a］为“sj”。及卜」.若项目［A--，a］属于I,则置ACTIONS,a］为；其中假定Af为文法G的第j个产生式。3,若项目［SfS・，即属于(，则置ACTION［k,即为“acc”。.若G0(I,A)=I,则置GOT(5［k,A］=jo.分析表4凡不能花规则1至4填入信息的空白栏均填上“出错标志”。当具体面对输入串时，通过查表进行分析该进行何种动作。程序结构描述：函数调用格式、参数含义、返回值描述、函数功能均在程序源代码出注释出来，在此不再赘述，详细含义请参照源代码cpp文件。详细的算法描述(程序执行流程图)：(1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。⑵分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表(ACTION)和状态转换(GOTO)表两个部分，它们都可用二维数组表示。⑶分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。LR分析器由三个部分组成：LR分析器结构:其中：SP为栈指针，S[i]为状态栈，X[i]为文法符号栈。状态转换表用GOTO",X]=j表示，规定当栈顶状态为i,遇到当前文法符号为X时应转向状态j,X为终结符或非终结符。ACTION[i,a]规定了栈顶状态为i时遇到输入符号a应执行。动作有四种可能：⑴移进：action[i，a]=Sj：状态j移入到状态栈，把a移入到文法符号栈，其中i,j表示状态号。⑵归约：action[i，a]=rk：当在栈顶形成句柄时，则归约为相应的非终结符A，即文法中有A-B的产生式，若B的长度为R(即|B|二R)，则从状态栈和文法符号栈中自顶向下去掉R个符号，即栈指针SP减去R，并把人移入文法符号栈内，j=GOTO[i,A]移进状态栈，其中i为修改指针后的栈顶状态。⑶接受acc:当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是‘#'，则为分析成功。(4)报错:当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入端不是该文法能接受的符号串。本程序原本的设计思想与实验二相仿，但由于此种设计思想会导致程序灵活性大大降低，故对设计思想进行优化，在此，不在对原程序设计思想进行阐述，仅对改良后的程序设计思想进行阐述。该文法的LR(1)分析表：算术表达式文法的LR分析表状态ACTIONGOTOi+*()#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311rrrr本程序根据给出的LR(1)文法分析表，构造string类的action[12][6]={"S5","0","0","S4","0","0",&"E:\5tudF.PPT'.潴详康专口ebug\^t®2.exe""E:\Etjdy\.PPT\辕谭康武Debug^56S2,exe[分、，斤KM**MMKMMK*MMM：/MM寅 MMM：X*区分析文法产生式为 “：->E+Trb：F->iB分析成功acc是否继续分析T或y继续动作说明ficnoNra,<]^：4,1ACIIDN[4,il^5,iMIIONth〉17士i,状态:L:[大楼

K：F-XE)归约：GoTo<0,F>=3

r4：T->F归纵Goin⑶T>=2我

t理：E-3T归的，GoTo<0,E)=1A分,机M-r ■♦■♦>1，]<**]<]<演•看风如用言风风惬同风风犬LRCl)分J斤 MMKMOC/MMMJ(MM：X*― ‘ 、Ir?Goro<4,F)=3/\rar4：T-〉F归纵

m：E-yr归约,GdT(j44,T)=2应域

配1口《44)印就栈找,GoTo<6,F>=3AS由CIIONE,*]=2?/悔

ACII0hl：7,i]-35,l^rt：F->i[

r4：T->F!、-亓T|i**t*r*相*t*hh州****片依=*抬妹安»t

日露息鬻状态出栈rb：F7i归约f4：T->F归约,GnT(K6,T>=9/栈r6：F->i归约,Gor(]《？,F>=l(J入栈

r3：T-3T*F归约.Gur(j《6.T〉A入带

pLEQE'T归约：GaTe>《0,E〉¥i入栈密用祗功fiCTI0N[l,+l=S6,^ACIION：G,il^JE,i^-,CoTa<0,F>=aX^

一Gold阳,T)=2忒唠r2：E->T月约,Gora<0,E>=lAfeF->i♦MMMXKXX就 MXMMXXMMX]jR1cl1分、；1斤KMX就MXXMX ■宜就XMHXMJCX7葡史字符串+i«i#<i*i#+i*itU1659163B1G9ttE+ittE+FitE+T016?? #£*T*«16975#E+I*i016971S#E+T*F91G9#E+T符号栈-->1日：MM：)C MMK*连输次字符串|Ci>Eajtyji/-w噂-具一尺jfjf*状态栈符号栈剩余attCi>it04#<i>#H45>»043tt<F)#342ittT348#<E>#04811tt<E>tt93#F#92ttTft91*Ett042U<T'E:'studyVPPI儡谭l^\Debug^iSZ.exe9480481133r2：E->TlJ3^J,GoTuS.EAF人栈

第nIONm1=Sil,状态li入戕

r5：F-)<E>归约.GuT(j<@.F)4人栈

v4：T-3F归约,CoTo总入榜

h£；E-，T归约，GoTuF.EAl•我栈

acc 流所成功骤r6：F-'i归匏,

r4：T-)F归”,

r2：E-3T归约,3T(j44,F>=3入榜GoTo<4,T>=2A.''

CjT<j<4㈤印入第11511：山〉1畤11,状态1：1人栈K：F-XE）归约：GuT（K@,F）=3人栈

r4：T-〉F归阂.Gold。」）=2人栈

MII0N[2,*]=G7,状态?其橇

ACII0N：7,<]T4,状态4人相动作说明MIION⑶（]鹏4,状态4久啮

fiCII0h[4,ll^S5,状态5人栈俞人字符串tt<E#<E>ttF状态栈符号栈剩余输，3#04!>*<?«045tt<i>*<>#343tt<F>*<>#342#<T>*<>#348tt<E>*<>#04811tt<E>阻#F32itT*C>tt027#T"<>#Error迎ength()-3;for(intj=0;j<N;j++){t(0)<<")=";(Production[i-1].at(0));t(0)=='S'){action[i][t].erase(0,1)；_$5())，$)；_$5())，将action[i][t]转换为整型action[i][t].insert(0,"S");t(0)=='r'){@/10口[1]压].6「@$6(0,1)；_$宜())，$)；_$5())，将action[i][t]转换为整型action[i][t].insert(0,"r")；//将r添加回action[i][t]}}elseif(action[i][t]=="0"){cout<<"\tError"<<endl；break；}elseif(action[i][t]=="acc"){Output(s)；cout<<"acc"<<"\t分析成功"<<endl；break；}}elseif(flag==false)break；}}intmain(){strings；cout<<"************************LR(1)分析*************************”<<endl；cout<<"本分析文法产生式为"<<endl；for(intj=0;j<6;j++)cout<<Production[j]<<endl;cout<<"************************LR(1)分析*************************”<<endl;charT;do{cout<<"输入字符串"<<endl;。也>公;//输入要分析的字符串cout<<"************************现进行如下分析*************************”<<