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、如果遇到错误的表达式，应输出错误提示信息。3

2、、程序输入/输出实例：输入一以#结束的符号串(包括+*/ ()i#):在此位置输入符号串 输出过程如下：步骤 状态栈 符号栈剩余输入串动作10# i+i*i#移进i+i*i的LR分析过程步骤状态 栈符号栈输 入串动作说明10#i+ i*i#ACTION0,i=S 5,状态 5 入栈205#i+i*i#re: F i 归约,GOTO(O,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#ACTION1,+=Se,状态 6 入栈6016#E+i*ACTION6,i=S 5

3、,状态 5 入栈i#70165#E+i*i#：F f i 归约,GOTO(6,F)=3 入 栈80163#E+F*i#5： T f F 归约,GOTO(6,T)=9 入 栈90169#E+T*i#ACTION9,*=S 7,状态 7 入栈1001697#E+T*i#ACTION7,i=S 5,状态 5 入栈11016975#E+T*i#：F f i 归约,GOTO(7,F)=10 入 栈120169710#E+T*F#a: T f T*F 归约,GOTO(6,T)=9 入栈130169#E+T#r 1：E f E+T,GOTO(0,E)=1 入栈1401#E#Acc：分析成功实验报告正文的内容

4、：描述LR(1)语法分析程序的设计思想：定义项目的一般形式是A f , a aak，这样的一个项目称为一个LR(k)项目。项目中的aia2-ak称为它的向前搜索符串(或展望串)， 令K=1,即为LR(1)语法分析程序。在此，重新定义 CLOSURED的算法：项目集I的闭包CLOSURED构造方法：1.1的任何项目都属于 CLOSURE(I)2. 若项目Af B , a属于CLOSURE(I) B- 是一个产生式， 那么，对于FIRST( a)中的每个终结符b,如果Bf , b原来不在 CLOSURE(I中，则把它加进去。3. 重复执行步骤2,直至CLOSURE(I不再增大为止。GO()的算法保

5、持与LR语法分析程序一样，通过以下方法构造文法分 析表：动作ACTIONS状态转换GOTO造如下：1. 若项目A fa , b属于Ik且GO(Ik, a) = Ij，a为终结符，则置 ACTIONk, a为 “sj ”。2. 若项目Af，a属于 Ik，则置 ACTIONk, a为 “rj ” ；其中假定Af 为文法G的第j个产生式。3. 若项目S fS- , #属于 Ik,则置 ACTIONk, #为 “acc”。4. 若 GO(Ik，A) = j 则置 GOTOk, A=j。5. 分析表中凡不能用规则1至4填入信息的空白栏均填上“出错标 志”。当具体面对输入串时，通过查表进行分析该进行何种动

6、作。程序结构描述：函数调用格式、参数含义、返回值描述、函数功能 均在程序源代码出注释出来，在此不再赘述，详细含义请参照源代码cpp文件。详细的算法描述(程序执行流程图)：(1) 总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同 的。(2) 分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表(ACTION和状态转换(GOTO表两个部分，它们都可用二维数组表示。(3) 分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。LR分析器由三个部分组成:LR分析器结构：输入#

7、总控程愉出ACTION其中:SP为栈指针，Si为状态栈，Xi为文法符号栈。状态转 换表用GOTOi, X=j表示，规定当栈顶状态为i ，遇到当前文法符号为X 时应转向状态j，X为终结符或非终结符。ACTIONi, a规定了栈顶状态为i时遇到输入符号a应执行。动作有四种可能：(1)移进：actioni，a= Sj :状态j移入到状态栈，把a移入到文法符号栈，其中i,j表示状态号。归约：actioni，a=rk :当在栈顶形成句柄时，则归约为相应的非终结符A，即文法中有A- B的产生式，若B的长度为R(即|B|=R)，则从状态栈和文法符号 栈中自顶向下去掉R个符号，即栈指针SP减去R,并把A移入文

8、法符号栈内， j=GOTOi,A移进状态栈，其中i为修改指针后的栈顶状态。(3)接受 acc:当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是#，则为分析成功。报错：当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入端不是该文法能接受的符号串。四、实验要求本程序原本的设计思想与实验二相仿，但由于此种设计思想会导致程 序灵活性大大降低，故对设计思想进行优化，在此，不在对原程序设计思 想进行阐述，仅对改良后的程序设计思想进行阐述。该文法的LR(1)分析表：算术表达式文法的LR分析表状 态ACTIONGOTOi+*()#ETF0S5S121S6acc2

9、2S722344444SbS823 j5rerere66S5S93 j7SbS1038S3Sn9r 1S7r1r 1103r3r33115555狀态栈符号栈苻号栈ttttF ndKE tt ttF itT MEttF (IT U ttE+ UF+i 1IE+F ttE*T E+T* 1E+T*1 UE+T*F E*T121314早川TF- L樹入字符串L +1*1JtKMSCMKMX)分卜析曲7翼11兀就抑*直 Wit*昶餐 未分析文法产生式为 E-E+TE-Tr-T*FT-PF-XEF-1HM1 U f *l .j_ . 癒蓉 快态呂入桟Gota4,F?=3A.KGorD=2XH 心虫4*劭

10、=8入快 1-S11,H 入栈,SdId=3入彳立 corj=2AfS aorD=tAteaU4b34334248 kf4Hll 333231继续分析弄或/怜LHg Pt 理 Jt IB f 弭 it MT 理 KX JT Jt ： JT 35砧3201316BlfiS31G3316fH169?31&975 31&9?ie 31G991继续分析或诞傑缝、分 t| :鼻* jtE覽耳但 JW 哇為皿 耳 Jt JH :憶耳: : : Jt : S朗作说明fiCH0hltftX=fi4flCnL0Kt4,i)G rb；F-i 归约 r4：T-Fhl r2TE-M归约ACT LONflrb :F-；

11、归约 f4：TF：闩药 i2 : E-M 归约 T 就.分册成功1J=S5,；态5入桟j, Garc,FAS 日约CnTcfTW入赭 日釣,入桟 廳绸召斤:週賈貳直出ltN匱 !M： H!K 动作说明 flCILONLtt r6 :F-i归约 r4:T-5F!j 品:E-ijflClION,+1=6 fiC7I0Nt,il=GE _ _vf ：F-llJ3 Cuf u“ ”F$=3入桟 M：T_M 归约，Gorn 入楞 fiC71 OH 4-d -ST,悅志”苹 fiCTIONLiJJb,狀态 5 人栈 r6 :P-iB约.Gori=10 A1 r3 iT-T*F归约，QoTdT=9 A.7：

12、 MmE-ET 归红 QuTd -1 入桟 口井希成功同I53同 S3本程序根据给出的LR文法分析表，构造string 类的 actio n12 6=S5,0,0,S4,0,0, rT Eitj dyPP舸译題E? ebugeaiH2. exe5B3 PXstu切RPF編译J原春DebugX改进比exe同 S3M2B4BM811阴HT4 A n n 41nr2：E-T0约，Go-人桟 mniongj】=si状总li入栈 r5：F-XE归约.血T旅0.FX3入栈 MtT-F归约，&叫溼入林 f2：E-T口约，Gurtj-lTj 分舟剜Jj入宇符串C1*OMiiMJeiltMLaCJtXKJCMK

13、MLKJmKJCJtJCJlJCEJI状态栈394B45H43342S4833&2327firr-orucUi ttF MCIUE ttHF ht ttT*折符号栈*on*i*#*(#OH动作说明山才、“CT IONtaA) -64,吠态 4 入喝 OGTI OK 14 G =S 5 ,伙态5 入楞 r6：F-iJz|约，GoIoC4,F=3Att r4=T-F归约.Coro=2A!：i t2 : E-、1 归的 p Go tn 1 :麦fiGHONa, )-511,.状态丄上入栈 rb :P-XE归谷J, CinIo =3AP4i r4：T-F闩细.Gorc2A桟ACH ON 17 Q-B

14、“氏态“權津沓绅续笄析段或诞陈纽en gth()-3;for(i nt j=O;jN;j+)t(O)v)=;(Productio ni-1.at(O);t(O)=S)actio nit.erase(0,1);_str(),s);_str() ，将actio n it转换为整型actio nit.i nsert(0,S);t(0)=r)actio nit.erase(0,1);_str(),s);_str()，将actio n it转换为整型actionit.insert(0,广);/将 r 添加回actio nitelse if(actio nit=0)coutvtErrorve ndl;break;else if(actio nit=acc)Output(s);coutvaccvvt分析成功endl;break;else if(flag=false)break;int mai n()6string s;7coutf*LR(1)分析endl;*、cout 本分析文法产生式为 endl;for(int j=0;j6;j+)coutProductionjendl;coutf*LR(1)分析endl;*、char T;doco