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

1、编译原理课程设计报告SLR(1 )分析得实现计算机科学与技术计算机科学与技术指导教师姓名2015年12月 26日目录1. 设计得目得与内容？错误!未定义书签。1、1课程设计得目得？错误!未定义书签。1、2设计内容错误！未定义书签。1、3设计要求？错误!未定义书签。1、4理论基础错误！未定义书签。2算法得基本思想错误！未定义书签。2、1主要功能函数？错误!未定义书签。2、2算法思想？错误!未定义书签。错误！未定义书签。S LR文法构造分析表得主要思想解决冲突得方法:错误！未定义书签。SLR语法分析表得构造方法：?错误!未定义书签。错误！未定义书签。3主要功能模块流程图错误！未定义书签。3、1主函

2、数功能流程图4系统测试错误！未定义书签。5结论？错误！未定义书签。错误！未定义书签。附录程序源码清单1. 设计得目得与内容1、1课程设计得目得编译原理课程设计就是计算机专业重要得教学环节，它为学生提供了一个既动手又动脑课本上得理论知识与实际有机得结合起来，独立分析与解决实际问题得机会。进一步巩固与复习编译原理得基础知识。培养学生结构化程序、模块化程序设计得方法与能力.提高学生对于编程语言原理得理解能力。加深学生对于编程语言实现手段得印象.1、2设计内容构造了解LR(K)分析方法就是严格得从左向右扫描，与自底向上得语法分析方法1、3设计要求1)SL R (1)分析表得生成可以选择编程序生成，也可

3、选择手动生成;2)程序要求要配合适当得错误处理机制;3)要打印句子得文法分析过程1、4理论基础由于大多数适用得程序设计语言得文法不能满足LR( 0)文法得条件，即使就是描述一个实数LR (1)分析程序，利用它进行语法分析 ，判断给出得符号串就是否为该文法识别得句子变量说明这样简单得文法也不一定就是LR(0)文法。因此对于LR(0规范族中有冲突得项目集(状态)用向前查瞧一个符号得办法进行处理，以解决冲突。这种办法将能满足一些文法得需要，因为只对有冲突得状态才向前查瞧一个符号，以确定做那种动作，因而称这种分析方法为简单得LR( 1)分析法，用 SLR(D 表示。2算法得基本思想2、1主要功能函数c

4、 1 ass W FWF( chars1 :,c ha r s2 : , int x , int y )W F (const string& s 1 ,conststri n g & s 2 ,i n tX ,inty)bo 0 l operator< (co n stWF & a) c 0 nstbool o p e r at orvoid prin t ()class C losu reV oid prb o ol o pV oidmake iteV oidvoidbo ov o idv oivo ivo ivoidvovo l(co n st WF&

5、 a )nt ( s tri ngs t r)era tor(coCl osurea)co nstd dfs ( const str ing & x )make fappendi rst ()(c o nst s trec k ( cons te f ollow ()mak e _set ()m a ke_ V ()mak e_cm p ( vectmake_go ()i d make table()i ng & stV e c torconstg& s tr2 )vin t>& id ,o nsstri ngst r)or WF >&mpl

6、 ,intc har c h)d pr l nt ( strin,strn g s2 ,st ring s 3, str in g s 4, stri ng s 5, stri ng s6s7 )stri ng get_ste ps(is t rin g get_st(vector < Tst k)st r in g g etshif t ( W F & temp )V oidan alys e( stri n g sr c )2算法思想S LR文法构造分析表得主要思想许多冲突性得动作都可能通过考察有关非终结符得FOLLD W集而获解决。解决冲突得方法:2、解决冲突得方法就是分析

7、所有含A与B得句型，考察集合FO LLOW(A)与FOLLOW(B),如果这两个集合不相交，而且也不包含b,那么当状态I面临输入符号a时，我们可以使用如下策略: 若a= b，则移进.若a FOL LOW(A ),则用产生式Aa进行归约;若a FOL LOW(B),则用产生式 Ba进行归约； 此外，报错* SL R得基本算法:假定L R (0)规范族得一个项目集I中含有m个移进项目Alfa? a1 31, A2fa? a2 3 2，,Amfa? am3 m;同时含有n个归约项目B la? ,B2a?,B3a?, 如果集合 al ,am ,FOLLO W(B1),，F OLLOW(B n)两两不相

8、交(包括不得有两a 属于上述个FO LLO W集合有#)，则隐含在I中得动作冲突可以通过检查现行输入符号 n+1 个集合中得哪个集合而活得解决: 若a就是某个ai ,i=1 , 2,m,则移进.若a FOLL OW(Bi ), i=1, 2，m,则用产生式 Bifa进行归约； 此外，报错这种冲突得解决方法叫做SLR( 1)解决办法 。SLR语法分析表得构造方法:首先把G拓广为 G',对G'构造LR(0 )项目集规范族C与活前缀识别自动机得状态转换函数GO。函数ACTI ON与GOTO可按如下方法构造:若项目 Aa? b 3 属于 Ik ,GO(I k,a )= I j,a为终结

9、符，置ACT IONk, a 为“把状态j与符号 a 移进栈” ,简记为“ sj”若项目Afa ?属于I k，那么，对任何非终结符a,a FOLL OW (A)，置 ACT IO N k ,a 为“用产生式Afa进行归约”，简记为“ rj”；其中，假定Afa为文法G'得第 j个产生式若项目S'f S?属于Ik，则置A CTIO Nk, #为可“接受”，简记为“ ac c” 若 GO(Ik , A) = Ij,A 为非终结符 则置G OTOk , A： =j;分析表中凡不能用规则 1至4填入信息得空白格均填上“出错标志”。语法分析器得初始状态就是包含S' 7 ? S得项目

10、集合得状态SLR解决得冲突只就是移进一规约冲突与规约-规约冲突3主要功能模块流程图3、1主函数功能流程图图3、1程序主要流程4系统测试S->E S->Ep->E+rE->T E->T r->T*K r->T*F- ?->F r->F r->CE) r->CE) r->i r->i图4、1输入I3->$E back;0 idzO3->E：$ back:0 id:lE->$E+TE->E1$+TE->E+$T E->E+T$back :1 back :1 back:l back:Lid

11、:2 id：3 icl：4 id:5E->$T back;2 id：6 £->?$ back:2 id;7 r->$T*K r->r$*F r->T$K r->w$back:3 back:3 back:3 back:3id:B id:9 id:10 id:llT-顒 back:4 id:12-丹$ back;4 id;13L$® fr->C$£) F-血) F->tE)$back:5back:5back:5back:5id:14 id:15 id：10 id:17P->$i bael?;6 Ld:lS F-)$

12、 back:6 id: 1Q图4、2项目表卡素*北 *此*卩R y *盘北 *盘*?|7士*北 卡素*北FIRST® = C 11FIRST (?) = (,!kirstCITC 1FIR酊OK i图 4、3FIRST集MLLE (E> ETOLLOl CK> FOLLOW CS> EOLLOW (T)fl J,十 花人记+ fl!爲），啊十图 4、4 FOLLD W 集"CLO SURE cI<jsure-IOE->$E+TE->$TF-$（E）S->$E T-$F T->$T+FcLosure-ILE->JE+TE-

13、>JTF-$（町F-$iF->（$町T->$FT-$Tclosure-12E->E3+TS->E3clgure-I3T-F$closure-14E->T$T-T 豺 FcIcsuTQ-ISF-i$cksureTSE->E3+TF->（EJ）closure-I?E->E+$T F-$（叮 F-$i T-$FT->$T=rclosure-13F->$（E） F-$i T->T+?FcL<JSure-I9F->（E）$closure-IIOE->E+T$T-T$*Fclosure-111T->T+K$图4

14、、5 CLOSU田表EDGE'IOE12IOK1310T1410I15ILCIlrir13ILi15riz1612 -1714 半一18IS一+17IO-) ISITCIlI?F13I?L15I?Tno13 CT113i1515 fTIll nora图 4、6 EDGE表ft I0 11 n 1111311411 11SI 11161311412 i1 11ST1111 1511 1KI嗣1£1111 1411 1R£SS 11111 1511 1R6R6 1R61111 16 i1 1S&1E71111 17 11 £1 1111311 10 1

15、B 11 £1 1111 1111 1q 11 1K5RF 1KS111 110 11 1KISB 1Pl111 111 11 1ILSR3 1ES1111 1p图 4、7 LR (0)表咒IIS5 IIIuIIMIIK2IIE6IRF I El IR3 IL吐-Stadkinput*i *jiezatirxn shiftIstjts-Et矶k10iCTlDKSIOTTO2壮shift|01s吁3it (Irediice1015Rb34肌？reduice1613t4ishi I t|ei4we(HT+shiftllOHSS5HiirTPduc-*(F->T)11!HT*p+it

16、fT pckicF J101431113*&)+1 tfr(J - >T|01.4R2alU吃)+iffshiftlOLdILBCa)山陶t5312KFrsduc»(T->P)loat13(fTredust|Q4z14*lFshzi i|O2E7lb应+sJiii t|02TIGITraducwQ >1)10275s17厅F聊ITro如灯-丹10273u10fltfF+TITrAtJdCfl fF-沖弋、loano319Accept|02acc图4、8文法分析步骤5结论L R分析法就是一种自下而上进行规范归约得语法分析方法。这里L就是指从左到右扫描输入符号串

17、。R就是指构造最右推倒得逆工程。这种分析法比递归下降分析法、预测分析法与算符优先分析法对文法得限制要少得多。附录程序源码清单# i n cl ude <i ostream#i ncludcs t dio # inc 1 ude <alg orithm># inc 1u d ec s t ring#i n#i nc1 ud e<v ec tude < s tri ncct ype#i nc# inclde<map# i n c lu< set#in clude <s stea m>#d e fi nM AX 5 0 7q ue/ #de f

18、ine DEBUG us i ng nam esp ace st d ；#pr a gma w a r nin g ( d isa b le : 4 9 9 6 )c lass WFp ubli c :strin g left,rightWFint backint id(ch a r:,in t x , i n t yle f ts1 ;righs2 ;bac kWF ( co ns tstri ng& s1 ,co n sts tri ng & s2left=s 1;r i ght = s2;b ack =X ;id =y ;boolop e rat or<(const

19、WF&a ) constif(l eft=a、left)ret ur nright< a、r igh t ;r eturn1 eft< a、left ;b 0o 1 opera tor=：=(co n stW F& a )c onstreturn(l eft=a、left )&&(rightvoidp r int()=a、r i ght )；i n t x, int y )c 1 assCIOpu blpri ntfs ur("%s >% sn " , leftc strvec tor< W F > e 1e m

20、ent ;V oid pri nt(st r ings t r)prin tf("%-15s%n”，"",:fo r(inti = 0;i e 1e ment、eleme nt : i 、pr in t ();1 cssize ()；t r、 cb oolop erator=(constiffortru c tinstintCoCo(),re & a ) const(a、el(inte lsme nt、siontypnum ；0; it en tnt ent ()n tent (i n(eleme nte t u rnrn trut yp ef a lse

21、a , int b )pe ( a ) , num ( b)r i g h t 、 c_s!= el em en t、sizee lemen t、size ()；str()=a、elem e nt i )()；+ +)r etui + +)co n tinut r();n falsev e ct o r < WFwf;map<s t ring , vector < int> d i c;ma p < s tr i n g,vecto rintVNma p < str ing ,b oo lvi s;stri n g st art="S ” ;v e

22、 cto r < C losure>c o 1 lectio nJv e c t or WF > it ems;c h ar CH = ' $'.Jig o MAX MAX;nsetinto MAX;vector < c ha r > V ;boolu sed MAX；Conten ta ctio n MA X： MAXint Goto MAX MAX;m ap <str i n g , set < char>fo1 lowIvo id ma k e_item ()m emse t(to , - 1 ,sizeof(-1);f o

23、r ( inti =0;i< wf、siz e();i + +)V N _s et wf i 、left 、p u shba c k( i );for(inti=0 ； i<wf、siz e ();i+)for(intj=0 ；j < =wf:i 、r i gstr ing tempwf i :、rig ht ;firsmap sta r>begin ()t emin sert(t emp、P、h t 、 le nr i n g , set < c hgth (); j + + )ifsize ();+ J , CH );dic w f (j )to it e m

24、s、left、P ush b ack(i tems、size()it ep usms、 s ize()-1 :i tems、siz e();h _ba c k (WF ( w f : i、l e ft , tempi , item s、#if d ef DEBUGputs(“项目表一一(int i = 0; i item s、size()；i +)print f (" % s->%sback: % d id:%dnms i 、leftc str (),、r ig h t、 C Str () , items、back,items i 、i d );p ut# e ndiV oid

25、fs ( c on st st r in gif(vis x ) re t urn ;1；e ctor<int(intn g&lestngrifor(intif(iset-”）；VNS e t X;< i d、size (); i:i di >le f t ；g ht = wfsu p p er ( r igf s (right 、substrchar >&s e tvb o olf 1 agforitid i 、r igr ight 、length(j , 1 )ht()；j +)）；：mp = fir i g h t、 s ubstr(j ,1)；i

26、 te r atortr ue ;te m p、t em p、be gd ( ); it + +)' / )lagfalsei n();fi rs t left 、 in ser t ( * i t );elV oidm akeV is 、 clearmap sf or (；ifelseif ( f l ag ) brebreast ()t ri nit 2ak ;()；r s t left 、e ctor <int =dic 、e nd ();(v is it2 first(it 2 >first)in sertit 2c ontiter+)1 nur ight j );

27、a t o r i t2i fde f D E B UGputs ("* * * F I RS T 集 * * *d ic、begin* * * *()；*m ap <string , set <char > ： iterator itf irst、be g in();for (; it!= first、 e nd ();it + +)printf("Fl RST(% s )=”，i t >first、c stset< c h ar& t e mpit-> s e c o nd ;se t <ch a ri t eratoi

28、t1te m p、be g in ();fool flag(flag!=temn d(); it1 + +)printf(”，”printf(”c",* it1 );flapu#en difvo id ap p endsetboolvoiegit <ch a rg = t ruet s (” ");(con>& fe tv cha r >&chforema(;(ininturnwhiln ();forSts tring& str1con st stri ngs tr2 )a r >: itera toins e rtfoloo

29、lfrom 、(*it );(c onstvec0;X 、righ1 se ；1 ow ()(tr u e)goonlsp <st r ing ,(;it2!=1 lo w str1 ；1 lo w s t r2 ;e n d()t or v if rom、begi n()；nt & idc onststing str )=strect o r v ize ( ) ; i + +) r et ur n t ruent > >:i t erator itVN set 、 bVN_se t、 e nd () ; it2i +)fo1 )、size ()1):、siz e(

30、)+)(j ,ec t orbool<in t& id = it2 - >se c ond ;0; i < id 、s ize ();flagW F & ttst r incon stfor(iwf& lefttringfosuif:i d i ;=tt 、le f t ;=riP per(flifsei ght = ttg ht 、 le na g)intapp(tx1(_C hntser ightgt h（）g ht j )t X = followe nd (le f t ,=follgooeckflag(iu pp(rightngiddc har

31、 & fr1; j >= 0; jr i g ht、subsi g h t、sub s tr (jw r ight 、substr”）t r (j ,1 );t rue;r ight 、length(); kk)t <c h ar& to = fos ubf irst1 lows tr ( k,1);id d ；righ t、subss et < c har >:itera t or it1e gin ();i nt t x=f o llo w r ig h tbstr1 )、si ze ()；fo r (; it1fr o m、en d()；+ +)i

32、 f (* i t1intsi z()；ifsestr(j1 门、si z e();foin serti ght k )intto 、insert(* i t1 );tx1 = f o ll owright 、s ubstr(j,1)、f ( t x1 >Check (id ,break ;tx1ow rig=f o IIs i ze ();f (tx1 brea k ;if(! go o n)e lse1 agfa 1 se ;br e ak;x) goon = tr ue ;=f ollo w right、 su bht 、 subs tr ( j ,1)、o w right、s u

33、bstr(j , 1 门、#ifdef DEBUGputs(”* * * * * * * foll o w集* * *);#envoidmap< strin g, set ch a r >: : ite rat oritfoow、be gi n();for=folioend ()it +)printf (”FO LLOW(% s)=”it>firststr）；setcha r & teite conteetins e r t< char lagi t1('#')；iterait1e mp、be gin()；fa 1se ；!= temp(f 1a

34、putsd ifmafo rC H)printff lag(”")；e set()” c"=truehant:MAX：;i = 0；t em sit:i 、丨 etemp ;stri ng & strvector < WF>& e lnd()r intf1)；;it1+)(”e ms、sizeft : 0=item s ie me nt()；)s/:、rt e mpi +)&&ite m se le m ent ;e 1 e me nt、pu s h _ b a ck ( i tems i );:i 、right :0s iz e

35、t x = 0;1 )；for (xstr 、length ();x +)if(s t r : xb r ea k ；C H)memset ( hash as i =0, size of ( has );(X ! = st r、lengt h()- 1)qu eue<strinq、p ush ( str 、subs t1 );while(! q、empt y0)colring ufro n、P o p();v e ctor intorin& idi c u;1 ection(size_tid 、 s i z e(); jtxi dj :iftemstx 、right0:= CH)

36、if(ha s txc ontinues txq 、 pushu pp e r (it em s t x 、ri(1 te m s tx 、rig ht、e l e me n t、push_back(items、pus h _back ( t emp);g ht 1 ：)subs tr ( 1 ,:t x)；(size_ti0; icollectio n、s ize (); i+ + )mapin t,cl 0s u retem p;f 0r ( size _t j=0 ； j< c0 llection i 、ele me n t、size ()；st ringstr=colleicti

37、on i 、elemen t j :、right ;s ize_tX=0 ；for(;Xstr、leng th()；x+ +)i f(str:X=CH)b r eaik ;i f(X-=str 、lengt h()1)c0 ntinue ；in ty :=st r X+ 1；i ntii5s tr、erase (s t r、beg in ()+X);str、inse r t ( st r、.beg in () +X +1, CH)5WZFcm p=W F(colle(ctioni 、 e1 e me nt : j :、lef t ,forj +)s tr , ,1 )；fo r(siz<

38、 it ems、 s iz e0； k+ +)if(ite:k=cmp )x + ；re ak ；if (X != str、length ()me ms et (ha s,0,size0 f(h a s );ve c t 0 rWF>& element=temp y、el e mente le m ent、p u sh_b a ck (items ii)；h as ii 1 ；m apint , C 1 osu r e> : : ite ra t or it=temp、begi n();for(;it !=t emp、end () ; it +)collecti on、pu

39、sh_back ( it -second）；fo r(s i ze_ti= 0 ；i < co 11ection 、size()；i +)s0 r t (c 0l 1 ection:i、e 1 ement、begin (),co11ectioni :n t、end ();f or(siz e _t i= C）；i < c olle cti 0 1n、size ()；i+)f 0 r (s ize_ t j=i+ 1 ； j< collect ion 、size()；j+ +)e lem e1);qu e ue stringwh istrip ush ( str 、sule(!

40、 q、emptypop ();ve ctorf or (intb st r()ints izetxi f ( itemsh asif（X+ 1,1 )；frontt X()；0;dj :;、r ight(has tx )t x = 1;if ( isu p perq 、p us h (ie 1 ement 、c : u;0cont(itemsem s tpush_backd、si z e( ) ; jC H)nue ;tx 、right 1)X 、right 、s u bstr(itemstx :)；+)i f (co 1 le c tion i = c olle c ti on j )# i

41、fdefDEBUGuts(”forc ol 1 ection、era s e( collec tion、b e gin ()+ j );LOSUREput# e ndifoirin gstrstrinsincollece am sin ；ze t i、cle ar();co1 lecti on、s i z e (); i + + )ngoutIIclosur e "iooutP rit (oud m ak e _ V ()m em s e t ( use d ,sizeof(usd)；for(sizewf、size ();i + )strin g&s tr=wfleforfori ze.t js tr 、1 e ngth () ； j + )ifse(us eV、 push_bacng & str1(s i z e_tr j k ( strj J = 0;);co nght ;t in ue ；s t r 1、leng t h ( ) ; j + +)s ortif (us eu se d、push_bacV、 push_id m akeorJ + +)sizft ,trV oid str1 j ) c o ntinues tr1 j = 1;k (str1 : j )；、be gin () ,