LR(1)实验报告(附代码)

1、实验三lr(1)分析法实验学时：4实验类型：验证实验要求：必修一、实验目的构造lr(1)分析程序，利用它进行语法分析，判断给岀的符号串是否为该文 法识别的句子，了解lr(k)分析方法是严格的从左向右扫描，和自底向上的语 法分析方法。实验内容对下列文法，用lr(1)分析法对任意输入的符号串进行分析:(产生式有误, 进行修改)(1) e- e+t(2) e et(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#移进j +門的lr分析过程步骤状态栈符号栈输入 串动作说明10#actionozi = 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#action",+二s®状态 6 入栈6016#e+i*i#a

3、ction6j=s5/状态 5 入栈70165#e+i引#佐ft归约,goto(6,f)=3入栈80163#e+f*i#r4： t->f 归约zgoto(6zt)=9 入栈90169#e+t*i#action9/=s7z状态 7 入栈1001697#e+t*i#action7j=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#e+t#ri：e->e+t,goto(0,e)“ 入栈1401#e#acc :分析成功实验报告

4、正文的内容:描述lr语法分析程序的设计思想：定义项目的一般形式是a->oc|3, aia2.ak,这样的一个项目称为一个lr(k) 项目。项目中的aia2.ak称为它的向前搜索符串(或展望串)，令k二1,即为 lr语法分析程序。在此，重新定义closure的算法：项目集i的闭包closure构造方法：1.1的但可项目都属于closure(i)。2.若项目arrbh间属于closure(i) , b-g是一个产生式，那么， 对于first(阴 中的每个终结符b，如果b&切原来不在closure 中，则把它加进去。3.重复执行步骤2 ,直至closure(i)不再增大为止。g0()的

5、算法保持与lr语法分析程序一样,通过以下方法构造文法分析动作action和状态转换goto构造如下：1.若项目a->oca3,切属于ik且go(ik/ a)二ij, a为终结符，则置 actionk, a为 sj"。2若项目a-oc间属于ik ,则置actionkz a为rj ；其中假定a-oc 为文法g的第j个产生式。3. 若项目sjs,#属于 ik,则置 actionkz #为 acc"。4. 若 go(k , a) = ij ,则置 gotokf a=jo5. 分析表中凡不能用规则1至4填入信息的空白栏均填上出错标志。 当具体面对输入串时,通过查表进行分析该进行

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

7、器结构其中:sp为栈指针z si为状态栈，xi为文法符号栈。状态转换表用 gotoi , x=j表示，规定当栈顶状态为i ,遇到当前文法符号为x时应 转向状态j ” x为终结符或非终结符。 actions a规定了栈顶状态为i时遇到输入符号a应执行。动作有四 种可能：移进：actioni , a二sj :状态j移入到状态栈，把a移入到文法符号栈，其中ij表示状态号。归约：actioni , a = rk :当在栈顶形成句柄时，则归约为相应的非终结符a ,即文 法中有a- b的产生式,若b的长度为r(即|b|二r),则从状态栈和文法符号栈中 自顶向下去掉r个符号,即栈指针sp减去r ,并把a移入

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

9、2344444s5s48235666re6s5s4937s5s4108s6s119ris7riri10r3r3115555本程序根据给出的lr文法分析表,构造string类的 action126=hs5,7,0nz,0,s4,7,0,7,0n/action 表n0n/"s6"/n0,"0"0,/"accn/” s5tot0ts4toto；,0,7，r3,/"r3,/,0n/,r3,*/,r3n/“s5totots4toto：h0,7r6n/mr6,/n0n；,r6,hr6n/ “s5t0t0ts4toto；.0 .r5 .r5(. .

10、on ,.r5. .r5;/goto 表int 类的 gotoarr123 =1,2z3,0,0,0,0q0,oqo,823,oqo,0,930q10,oqo,oqo,oqo,oqo,用以记录lr(1)分析表的内容。定义终结符集vt,非终结符集vn产生式集合production狀态栈 status,用int类的数组status记录栈的内容,符号栈stack ,用string 类的stacktd记录栈的内容，定义移进函数shift()zgoto函数gotoqjja约函数reduction。具体的分析函数analyseq ,对于给定的字符串，读取状态栈的栈顶元素及字符串当前的首字母，先通过函数ju

11、dge判断符号栈栈顶元素是否在文法终结符集中，若不在，则输岀error,结束程序,若在其中，则返回字符串首字母在终结符vt的下表，再通过查action 表，执行相对应的操作，执行移进函数shift()或归约函数reductiono , 同时若执行归约操作，再通过查找goto表判断应转到的状态,执行相应的goto函数goto(),重复进行以上步骤，直至分析执行至输出acc或 error,程序结束。给出软件的测试方法和测试结果：根据程序的提示,输入一由该文法的终结符组成的字符串”程序即会进行分析,具体的测试实例如下:正确的输入:八 we:studyppt. 译原理debug做进 2.exe”t-&

12、gt;t*ft->ff-xe fi输入字符串lrd分析i+i*i步骤12346?91011121314毘否继续xmxxxxmmxxxxmxxxf 耶 j 井彳 丁女 q 下"分 析'状态栈符号栈剩余输入串0tt05#ii*i#03#f*i*i#02#t01tte016#e+i*itt0165#e*i*i#0163#e+f*i#0169#e*t*i#01697#e+t*itt016975#e+t*itt0169710#e+t*f#0169#e*ttt01tteu分析畑继续il 333 33 0 ln/dn/d7 1 6 jn/dn/ .1 f t .1 f 去 n>

13、>>nn>> o - 一 一 o o 一一 乍i f t e i i f t 力 c 6 4 2 c c 6 4 -arrraarr栈=3=2=1體=3=9 入f>t>e>入入f>t>入入f>s 5 "65 . 75 * < < 态<0<0<0态态<6<6态态<7toto 我otootooto来otooto来otogogo功 5ggg65gg75g ,戈 =s: ,=s=s:=s=s，约约硕 i约约约*i约约*1约归鼎3 4/>iy>t>e+f-t-e-c 2

14、;焉u)'回 22 e:studyppt 编译原淫debug做逬 2.exe"xxx其 mxxx其mxxxxmmxxxxmxxxlrc1 )个亍、丰斤xxxx>o<xxxxxx xxxxxxxxxxxxx 未分析文法产生式为e->e+te_>tt->t*f-f-><e>_>i输入字符串<i>lr<1)、丰斤xxxxxxxxxxxmxxxxxxxxxxxmxm xxx m x xxmm x xxmmm xxmmm mxm步骤状态栈0符号栈#ib<i>tti>tt043tt<f042#

15、<t>tt048#<e>#04811 tt<e> tt045#<i>tt否10是ttttte动作说明action0,<=s4/.k acti0n4.ij=s5，k _ r6：f->i归约,goto<4,f>=3入桟日约，goto<4,t>=2入:戋 日约,goto<4,e>=8/栈 action8,>1=s11,状态 11 入栈 r5：f-xe>归约，goto<0,f>=3入栈 r4：t->f归约，goto<0,t>=2入桟 f2：e->t归剤 got

16、o<0,e>=l入栈 acc分析成功r4：t->flr2：e->t(错误的输入:042tt<t048#<e#704811#<e>tt803#fn902#tu1001#en e:stu dyppt. 译原debugs遇 2.exe是否继续分析段或y继续扁入字符串u2：e->t归约，goto4.e=8人栈 action8,>=s11,状态 11 入栈 r5：f-xe>归约，goto<0,f>=3?栈 f4：t->f归约,goto<0,t>=2入核 f2：e->t归約，goto<0,e>

17、=l入栈 acc 分析成功goto<0x m x x 貝 x xxx 貝 x xxx m m xxx x m xxx 土弘1 卄彳丁卫口步骤状态栈符号栈剩余输入10tt204»<i>*<>#3045#<i4043#<f>*<>#5042tt<t>*<>«6048tt<e>*<>»704811tt<e>*<>#803#f*<>#902#t*<>#10027 error#t*<>#昱否继续分析段或y继续

18、动作说明actionl0,acti0nc4,r6：f->ilr4：t->f(j r2：e->t归约,goto<4,e>=8入栈 action8,>=s11,状态“入栈 r5：f-xe>归约，goto<0,f>=3入栈状态？入桟、<=s4j态4入找i"s5.状态5入栈i, goto<4,f>=3入桟i, goto<4,t=2入找acti0n8,>=sil,状态 11 入栈】 r .r4：t->f归约,goto<0,t>=2入栈act ion 2态 7 入找acti0n7,<=s4

19、.状态 4 入栈实验总结(设计的特点.不足.收获与体会):本程序摒弃了原设计思想,改使用构造action及goto表来存储lr(1) 分析表的内容，对于不同的产生式，只需修改其对应的action表，goto 表，终结符及非终结符表即可，大大提高了程序分析的灵活性，但由于时 间有限，测试实例不足，程序可能存在未知错误，在此需进一步改善，通 过本次实验，进一步加深了对于lr分析法的理解与应用z同时关于本 次实验，有几点深刻的体会：程序的设计思想是程序的灵魂，在程序编写 之前，一定要仔细阅读实验要求，正确理解实验要求，并综合考虑程序的 算法优化，灵活性等诸多方面，作岀正确的设计思想。程序的实际编写工

20、 作是一门细致的工作，编写过程中一定要认真仔细，因为程序中的一个小 错误可能会引起一连串的错误，同时编写时务必详细仔细，避免程序的逻 辑错误，因为程序的逻辑错误调试是们十分复杂耗时的工作z对于程序编 写中的一个小的逻辑错误，需要耗费大量时间调试，而本实验在编写完成 后，即消耗接近两天的时间进行调试,所以程序的编写务求认真、仔细、 准确。ps:实验源代码请参照cpp文件。#include<iostream>#include<stack> #include<string>using namespace std;string action126=ms5,7,0hf

21、,0mf,s4 ,fn0'7'0mf /action 表”0ts6t0t0t0tacc 鳥0. r6 r6. 0 r6. r6."s5tot0ts4to：o：/goto 表存放终结符/府彌e终结符int gotoarr12 3=lf2ff3,006600006&230060,9,3,0f0f10f600006ofo,of0,0,0; charvt6=ciy + y*7c；)7#1; charvn3=,e7t；f,;stringproduction6=,e->e+t,fme->tmf,t->t*f,；,t->f,f,f->(e),f

22、mf->im;/产生式集合int count"/记录当前进行处理的输入字符串字符位置 int line"/记录处理的步骤数 bool flag=false; int statusnumber=l;栈中状态数 string stacktd#'/记录符号栈中内容 int status50=0;记录状态栈 stack <char> stack;/创建一个符号栈 stack <int> status;/创建一个状态栈 void judge(int &irint jfchar arrfchar chrstring s)/判断输入串是否由文

23、 法终结符组成flag=false;for(int l=0;l<j;l+) if(ch=arrl) flag=true;i=l； break;if(flag = =false)cout< v "xterror" <<endl; count=s.size(); void outputstatus()输出状态集 for(int i=o;i<statusnumber;i + +) cout<<statusi;void outputstring(string s)/输出未处理的字符串 for(int i=count;i<s.size(

24、);i+) coutv vs.at(i);void output(string s)输出步骤.状态集、符号集、输入串coutaa-ineca.<； ourputstauls® 8sa a =<=八八 stacldd a a <.=ou1:putsting(s)aosaa=<<=-=rle+;)void shift(int laring s)w、st園磐 s output(s)；hosa a action【 a a stanls.topo aa-<-aa s.aacoum)aa.h sa"aiaa=statuspush(一)<、茜芽谢

25、s(atus【s(a(usnumberv<、s(atusa»l并ehssikis(ackpush(sa(coun§、llitslp3:><iidmbf<iidaacktd haacldd+sa(count<、staclctdajall苹(1|033朝cou¥+、11ki5-iii一s(atusnumber+<、$b聲吕void goto(s(ack aintv stlmtack acharv st2string s)/、gotonma intjyl;int chlustl.topoj char ch2hst2(op(rjudge

26、(j3vnch2s)<、38ins 亩皿 ejss苹m-&3sfmif (gofoarrnhl=j】n hox8sa a ettort a cens: coun(hssize()；)e-se(aa(uspush(go-oamchl=jm、wskf »atus【statusnumber_ hgotoartnhls； statusnumber+void reduftiontt laz.ng s)/、s13園磐 routpu(srnosa a =.= a a - a a = a a a a =ss - goto(.= int nhproduftionnll 一 engthow

27、; fomnt sa z + aatus.popoj s(acl<pop()； s(a(usnumbe7j. s(acl<tderase(s(acldd-engh?l)； cou-a attatus.topo aa-aa production 宇匕at(o) aa=t 打 svacigpushkproductiontll.aao)、® aacktd n stacked+stacrspoj goto(statusstacl<s)； cou 穴 as-anls.-opo a a =>s? a aendb n*u+nmrd£ i h*u+ *>>

28、;、i v rc-u* cpu void ana 一 yse(string s)/、w$希騙薯stacfpushf#)、 statuspush(o)iim tflwajellch 甫磬囲 vtskfnwhi-e(countcssize()(infihs-auls.fopo; char chusat(counq;judgekpvlch.s)； if(f-aghhque)宀 if (action 3 一 n ac°5r?r?a2on h 0)(if (action m3at(0tu s 二action m3erase(0l)；、崖黑 aftionmssm+jibsshift(a(oi(actioni=qclsto)、s)；、asi(actionmecls?()、茜action it转换为整型actionitinsert(vs”); 将 s 添加else if (action i t .at(0) = = 'r') actionit.erase(ofl);/u 除 actionit的首字母 rreduction(atoi(actionit.c_str(),s);/