SLR(1)文法分析实验报告

1、编译原理课程设计报告SLR(1)分析的实现院计算机科学与技术业计算机科学与技术指导教师姓名2015年12月26日目录1.设计的目的与内容1.1课程设计的目的1.2设计内容1.3设计要求1.4理论基础 2算法的基本思想2.1主要功能函数2.2算法思想SLR文法构造分析表的主要思想: 解决冲突的方法:SLR语法分析表的构造方法:3主要功能模块流程图3.1主函数功能流程图 4系统测试11125结论 附录程序源码清单2)程序要求要配合适当的错误处理机制;3)要打印句子的文法分析过程。1.设计的目的与内容1.1课程设计的目的编译原理课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将

2、课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。进一步巩固和复习编译原理的基础知识。培养学生结构化程序、模块化程序设计的方法和能力。提高学生对于编程语言原理的理解能力。加深学生对于编程语言实现手段的印象。1.2设计内容构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子, 了解LR( K)分析方法是严格的从左向右扫描，和自底向上的语法分析方法。1.3设计要求1)SLR(1分析表的生成可以选择编程序生成，也可选择手动生成;1.4理论基础由于大多数适用的程序设计语言的文法不能满足LR(O文法的条件，即使是描述一个实数变量说明这样简单的文法也不一定是

3、LR(O)文法。因此对于 LR(O规范族中有冲突的项目集(状 态)用向前查看一个符号的办法进行处理，以解决冲突。这种办法将能满足一些文法的需 要，因为只对有冲突的状态才向前查看一个符号，以确定做那种动作，因而称这种分析方 法为简单的LR(1)分析法，用SLR(1表示。2算法的基本思想2.1主要功能函数classWFWF (char s1 ,char s2 ,int x,int yWF (const string& s1 , const stri ng& s2bool op erator (con st WF & a )con stbool op erator=(con st WF & a )c

4、on stvoidp ri nt()int x ,int y )；class Closure1-bool op erato)r= (const Closure& a )con st；voidmake_item()voiddfs (conststri ng& x )voidmake_first()voidappend (const string& str1 ,conststri ng& str2bool_check (const vector & id,con ststri ng strvoidmake_follow()voidmake_set()voidmake_V ()voidmake_c

5、mp(vector& cmp1 ,int i ,charch )voidmake_go ()voidmake_table()voidprint( string s1,string s2,stri ng s3stri ng s4string s6, string s7)stri ng get_ste ps(intx )stri ng get_stk(vector stk )stri ng get_shift(WF& temp )voidp ri nt(string str),string s5这种冲突的解决方法叫做SLR(1解决办法。void analyse ( string src )2.2算

6、法思想SLR文法构造分析表的主要思想:许多冲突性的动作都可能通过考察有关非终结符的FOLLOW集而获解决。解决冲突的方法:解决冲突的方法是分析所有含A和B的句型，考察集合 FOLLOW(A)和FOLLOW(B)如果这两个集合不相交，而且也不包含b那么当状态I面临输入符号a时，我们可以使用如下策略:若a=b,则移进。若a FOLLOW(A),则用产生式Afa进行归约;若a FOLLOW(B,则用产生式Bfa进行归约;此外，报错* SLR的基本算法:假定LR(0规范族的一个项目集I中含有m个移进项目A1 fa? a1 3 1, A2fa? a2 3 2,，Ama? am 3 m ;同时含有n个归约

7、项目B1fa ?, B2 fa ?, B3fa ?, 如果集合 a1,am, FOLLOW(B1)，FOLLOW(Bn两两不相交(包括不得有两个FOLLOW集合有#)，则隐含在I中的动作冲突可以通过检查现行输入符号a属于上述n+1 个集合中的哪个集合而活的解决: 若a是某个ai, i=1,2,m,则移进。若a FOLLOW(Bi) i=1,2,m，则用产生式 Bifa进行归约;此外，报错SLR语法分析表的构造方法:首先把G拓广为G,对G构造LR(O项目集规范族C和活前缀识别自动机的状态转换函 数GO。函数ACTION和GOTO可按如下方法构造:若项目Aa? b 3属于Ik, GO(lk,a)=

8、 lj,a为终结符，置 ACTIONk,a为“把状态j和符号a移 进栈”,简记为“ sj”若项目Afa ?属于Ik,那么，对任何非终结符a, a FOLLOW(A),置ACTIONk,a为“用产 生式Afa进行归约”，简记为“ rj”；其中，假定 Afa为文法G的第j个产生式 若项目Sf S?属于Ik,则置ACTIONk,#为可“接受”，简记为“ acc”； 若 GO(Ik, A)= Ij, A 为非终结符，则置 GOTOk, A=j;分析表中凡不能用规则 1至 4填入信息的空白格均填上“出错标志”。语法分析器的初始状态是包含S f?S的项目集合的状态SLR解决的冲突只是移进-规约冲突和规约-

9、规约冲突3主要功能模块流程图3.1主函数功能流程图图3.1程序主要流程4系统测试7S-ES-E r-K+r E-E+?S-T E-T r-T+r r-T*F- ir-K r-K F- K-XE)图4.1输入3-$E back:O id:O S-E$ baekzO id:l E-$E+TE-E：+$TE-E-HT$back :1 back ：1 back:l back :1id:2 id:2 icl:4 id:5E-$T back;2 id:& -?$ back:2 id:7 r-$T+F r-?$+F r-T*$F r-w$back:3back:3back:3 back:3id:B id:9

10、id:10 id:llr-$F back;4 id:12r-F$ back:4- id：13-tE)$back:5 back:5 back:5 back:5id:14 id:15 id:10 id:17-$i bael?;6 Ld:lS -i$ back:6 id:15图4.2项目表拓 *4c4*4?|c 牡 4*f牡 4*4?|c 牡 4*4?|c 牡站?|cFIRST = (41FIRST(F)二(, iriRST(S) = C, ilFIR (?) = (, 1图 4.3 FIRST集F0LL0M(E) EOLLOi FOLLOW CS)KOLLO* CT棉J,先+ flMX 也+图 4

11、.4 FOLLOW集CLOSUREclosurs-IOE-$E4TE-$T F-$(E) F-Ji S-$E T-$F T-$T+Fclosure-IlE-JE-hT E-JT F-$(E) F-洱iT-$F T-$mcLosureTSE-E$-HTS-E$closure-13T-F$closi3re-14E-T$clo3ure-I5F-i$closureTSE-E$-TF-(E$)closure-!了E-E+$TF-$(E) F-$i T-JFT-$T*FclosureTSF-$(E) F-$i T-T+$Fclosuire-19F-(E)$closure-IIOE-E+T$T-T$=i=r

12、closure-IllT-T+K$图 4.5 CLOSURE表EDGE10E1210K1310T1410I15ILCIlrir13ILi15riz1612 -1714 半一18IS一+17IO-) ISITCIlI?F13I?L15I?Tno13 CT113i1515 fTIll nora图 4.6 EDGE表ft I0 11 n 1111311411 11SI 11161311412 i1 11ST1111 1511 1KI嗣11111 1411 1RSS 11111 1511 1R6R6 1R61111 16 i1 1S&1E71111 17 11 1 1111311 10 1B 11 1

13、 1111 1111 1q 11 1K5RF 1KS111 110 11 1KISB 1Pl111 111 11 1ILSR3 1ES1111 1p咒IIS5 IIIuIIMIIK2IIE6IRF I El IR3 I图 4.7 LR(0)表pfrs tacitinsAjt对erationiCTl 加GOTO(i*L)*iirchi ft10Sshift|0155+i+i*reduce10153*i+icreduce (T-FJ|0L3t4iITahi I t|G146nT+iM(rshiftlOl ISS5TBIT航+诃TPduc*(K-i|OHfl5耐115ff (T*F)+!TEtiuc

14、p (T-T*K)bl嗣仃E3t-&fftT)+led-ce|0L4K261U)+iflshift|OLdE91LfCl)*lPreduieCF-XB)IQL旳R5312SF+iFiwduc(T-P3|O3t13(fT+iereduct|04赵214KE*lFshift|O2E7lbKE*iflEhili|O2TE51G(KE珀Hrckice (K|02?SR6S17扯fITri3CKlCO(T-P)10273El10tfF+TFAdtics F+T)102711)R1219#EffAccept|02acc图4.8文法分析步骤5结论LR分析法是一种自下而上进行规范归约的语法分析方法。这里L是指

15、从左到右扫描输入符号串。R是指构造最右推倒的逆工程。这种分析法比递归下降分析法、预测分析法和算符优先分析法对文法的限制要少得多。附录程序源码清单#in elude #in elude #in elude #in elude #in elude #in elude #in elude #in elude #in elude #in elude #in elude #defi ne MAX 507/#defi ne DEBUGusing n ames pace std ;#p ragma warnin g(disable:4996)class WFpublicstri ng left,righti

16、nt backint idWF (chars1 , char s2 , int x , int y )left=s1 ;right=s2 ;backidWF (const string & s1 , conststring& s2 , int x , int y )left=s1 ;right=s2 ;backidboolop erator (constWF& a )con stif(left=a . leftreturnright .rightreturn left%sn eleme ntprint ( string str,left.c str(),right . c_str ();(%1

17、5s%-15snHHstr.c_str ();for ( int i0; i element.size (); i +)eleme nti . print ();bool op erator(con stClosure & a ) constif(a. element . size()!= eleme nt.size () return falsefor(int i0； ia . element.size (); i +)if ( element=a . elementi )continueelsereturnfalsereturntrue；structContentinttypeintnum

18、 ;stri ng outContent()type1;Content(intint:type ( a),num ( b);vector wf ;map stri ng,vectordicmap stri ng,vectorVN setmap stri ngboolvisstri ng startS;vector collecti onvector itemschar CH$int go MAX MAX;int to MAX;vector VJbool used MAX;Content acti onMAXMAX;int Goto MAXMAX;map string, set first;ma

19、p string, set follow;void make_item()memset (to ,-1, sizeof (- 1);for ( int i=0; i wf . size ();i +)VN_set wf i .left . push_back(i );for ( int i=0; i wf . size ();i +)for ( intj =0; j = wf i .rightstri ng temp=wf i . rightItemp.in sert(temp . begin ()+ jdiewf i .left .push_back.length(); j +),CH);(

20、items.size()；toitemsif(j)items . size()1=items.size();.push_back ( WF( wf i .lefttemp ,i , items . size ();#ifdef DEBUGputs(项目表);for ( int i0; i %s back:%d id:%dn,items i . left . c_str (),items i . right.c_str (), items i .back , items i . id );puts();#en difvoid dfs (conststring& x )visx=1;vector&

21、 id =VN_set X;for(int i = 0; i id . size ()；i +)stri ng& left=wf id i .left ;stri ng& right=wf id i .right ;for(int j = 0;j right.length(); jif ( isupper(right j )dfs(right.substr (j，1)；set& temp = first right .set:iterator it=temp .bool flag=true ;for (; it!= temp .end (); it +)if (*it =)flag= fals

22、e+)substr (j ,1);begi n ();firstleft . insert (*it );(vis x) returnifif(flag)break ;elsefirstleft . insert ( rightj )；break ;voidmake first()vis.clear ();mapvstring , vectorVint :iterator it2=dic . begin ();for(;it2!= die.end()；it2 +)if (visit2 -first)con ti nueelse dfs(it2 - first）；#ifdef DEBUGputs

23、(*f|rst集 *）；mapvstring , set :iterator it=first . beg in ();for（；it != first . end()；it +)#en difvoidprintfsetsetboolforprintfflagputsappend(FIRST(%s)=vehar & tempvchar : iterator it1flagfalseit,it - first- second ;=temp.c_str ();.begin ();（；ifit1 != temp . end (); it1(flag ) printf(）；(con st(,）；(%c

24、 , *it1 );truestri ng & str1con st+)stri ng & str2 )setvchar& from= followstr1setvchar& to = followstr2 setvchar:iterator it=from；.beg in()；for(；it!= from . end (); it +)to.insert(* it );boolCheck (constvector& id , conststring strfor(int i0; i Vid . size()；i +)intX = idi ；if(wf X.right=str )return

25、truereturnfalsevoidmakefollow()while (true )bool goonfalsemapiterator it2=VN_set . begin ();for(;it2!=VNset.end()；it2 +)vectorVint& id=it2second ;for(int i0；i V idsize (); i +)WFbool flag& tt = wftrueid i ；stri ng& left=tt . leftconst stri ng& right = tt . rightfor (int j=right . length()1；=0； j -)i

26、f(isupper ( right j )if (flag )1)；1).inttx = follow right . substr(j ,1).size ();append(left,right . substr (j ,inttx1follow right . substr(j ,size ();if(tx1 tx ) goontrueif(Check(id , )flagfalse1)；1).size()；1).size()；for(int k=j+ 1; k right.length()；k +)if (isupper(right k)stri ng idd=right. substr

27、 ( k,1)；set& from= firstidd ;set& to = followright.substr (jset:iterator it1=from . beg in (inttx =:follow right.substr(j，for(；it11!= from . end (); it1+)if (*it1!=)to.insert(* it1）；inttx1=follow right.substr(j ,if(tx1 tx ) goon =true ;if(Check(id , )break ;elseinttx = follow right.substr(j ,1).size

28、()；followright . substr (j1).in sert(rightk);int tx1=follow right.substr (j ,1). size();if (tx1 tx ) goontruebreak ;else flagfalseif(!goon)break ;#ifdef DEBUGputsmap (*follow集 *).begi n:string,set :iterator it=followfor(;it!= follow. end ();it +)p ri ntf(FOLLOW(%s)=,it - first.c_str ();set & temp =

29、it- second ;tempinsert ( #);set: iterator it1=temp .begin ();boolflagfalse();for(;it1!= temp . end (); it1 +)if(flag ) printf(,);printf(%c , * it1 );trueflagputs(丁 );#en difvoidmake set()bool hasMAX;for ( int0； i items.size();i +)if (itemsi .left 0S& items i . right 0= CH )Closure tempstri ng& str=i

30、temsi .rightvector& eleme nt=temp . elementeleme nt.push_back ( items i );size tx = 0;for(x = 0; x str . length (); x +)memsethasifqueuestri ng uvectorif(str x=CH )break ;(has ,0,sizeof (has );i1;!= str . length ()stri ng.push ( str.substr ( xwhile (! q.empty ().pop ();=q . front1)1);();& id = dicu;

31、for (size_t j0; j temp ;for (size_t0; j V collection.size ();i +)stri ng str=collecti onstrstrWFi .eleme ntsize_tx =0；for（；x Vstr.length()；x +)if(strx=CH )break ;if(x=strlen gth()-1)con ti nueJinty=strx+ 1；ii.erase ( str . beg in.insert ( str . beginelement . sizej. rightcmp=WF ( collectionfor(

32、)()+ x );+ x + 1, CH );i . element j . left , str(size_t k = 0; k items . size (); k +)()；j +),-1, - 1)；iiif(items k = cmp )break ;memsetvectoreleme nthasii+if(has, 0, sizeof (has);& element= temp y. element ;.push_back ( items ii );=1;!= str . length ()1)queuestri ng.push ( str.substr ( x1);stri ng

33、vectorwhile (! q.empty ().pop ();& id = dicu;0; j=id j ;(items tx .rightifif(has txtx (isupper: iterator it=temp . beg in()；for（；it!= temp . end (); it+)collecti on.push_back(it- second );for(size_t0;collecti on.size();sort(collectioni .eleme nt.begin (),collecti oni . element . end();for(size_t i0;

34、collecti on.size();+)for (size_t j+ 1; j collection.size();j +)if ( collectioni = collectionj )collecti on.erase ( collection.begin ()+ j );#ifdef DEBUGputs(CLOSURE);stri ngstream sinfor (size_t i0; i collecti on.size();i +)sin.clear ();stri ng outsinclosure-Ioutcollecti oni . print(out );puts (“);#

35、en difvoid make V()memset ( used ,0, sizeof ( used );for (size_t i0; i wf . size (); i +)stri ng& str=wfi .leftfor(size_t0； j str . length();j +)if(usedstrj )con ti nueusedstrj .push_back ( str j );stri ng& str1=wf i .rightfor(size_t0; j str1 . length();j +)if(usedstr1 j )con ti nueusedstr1j 1;.push

36、_back ( str1 j );sortvoid(V. begin (), V . end ();.push_backmake_c mpfor (size_tstri ng strsize tfor (if(#)；(vector & cmp1 , int i , charch )0; j collection=collecti oni . element . size (); j +)i . element j . right0; k str . length (); k +)(str k = CH )break ;if(k!= str.length ()& str k+ 1= ch )str.erase(str .begin ()+ k )；str.in sert(str.begin ()+ k+ 1, CH)；cmp1.push_back(WF( collectioni . element j . left,str ,-11)；sort(cmp1 . begin(),cmp1 . end ();void make_go ()memset