2023年編譯原理實(shí)驗(yàn)報(bào)告LL分析法

課程編譯原理實(shí)驗(yàn)名稱實(shí)驗(yàn)二LL(1)分析法實(shí)驗(yàn)?zāi)康?１．掌握LL(1)分析法的基本原理；2．掌握LL(１)分析表的構(gòu)造方法；3.掌握LL（1）驅(qū)動(dòng)程序的構(gòu)造方法。實(shí)驗(yàn)內(nèi)容及規(guī)定根據(jù)某一文法編制調(diào)試LL（1）分析程序,以便對(duì)任意輸入的符號(hào)串進(jìn)行分析。本次實(shí)驗(yàn)的目的重要是加深對(duì)預(yù)測(cè)分析LL（1)分析法的理解。對(duì)下列文法，用LＬ（１）分析法對(duì)任意輸入的符號(hào)串進(jìn)行分析:（1)Ｅ－>TG（２）G->+TG(3）G-＞ε(4)T－>ＦS(5)S->*ＦS（６)S－>ε（7)F-＞(E)(8）F->i 程序輸入一以#結(jié)束的符號(hào)串(涉及＋＊（）i＃），如：i+i*i#。輸出過程如下:環(huán)節(jié)分析棧剩余輸入串所用產(chǎn)生式1Ei+i*i＃Ｅ->TG.．..．...．．..實(shí)驗(yàn)過程及結(jié)果代碼如下：#iｎｃlude<ｉｏｓtreａｍ>#incluｄe＂edge．h＂usiｎｇnamｅspａceｓtｄ；edge::edｇｅ(){?ｃｉｎ>＞left>>ｒight； rｌen=rｉｇht.leｎgtｈ(); iｆ（ＮOＤＥ.find(ｌefｔ)>NＯDＥ.ｌengtｈ()）?ＮODE+=left;｝sｔringｅｄge::ｇetｌf(){?reｔurnleｆt；｝strｉngedgｅ::geｔrg（){ rｅtuｒnｒigｈt；｝strｉｎgedｇｅ::getfirsｔ(){ rｅturnｆｉrsｔ;}stｒiｎｇedｇe::ｇetｆｏlｌow（)｛ returｎfollow；}ｓtｒinｇｅｄge::gｅtseｌｅct()｛ returnseｌect;｝striｎｇedge::gｅtro()｛?sｔｒiｎｇstr； ｓtｒ＋=right［0]; reｔurｎｓｔｒ；}ｉｎtedｇｅ:：ｇetrlｅn(){ returnriｇｈt.lenｇtｈ(）;}vｏideｄge::newｆiｒｓt(sｔriｎgw){ iｎｔi;?ｆor(ｉ=０；ｉ＜w.lｅnｇth();i+＋)? if(firsｔ.find(ｗ[ｉ])＞fiｒｓｔ.ｌenｇth())??fiｒｓt+＝w[i］;}voidedge::neｗｆolloｗ(ｓtringw){ intｉ;?for(ｉ=０;i<w.ｌenｇth();i+＋) iｆ(ｆollow.find(ｗ［ｉ])>ｆｏllow.ｌｅngｔｈ(）&＆w[i］!＝'@')??fｏｌloｗ+=w[i］;}vｏiｄeｄｇe：：newｓｅlect(stringw){?inｔｉ;?fｏr(i=0;i＜w.lenｇth（);i++)?if（seｌeｃt．finｄ(w［i］）>select．leｎgｔｈ()&&w[i]!='@') ?ｓelect+=w[i];}voidedｇｅ::dｅｌfiｒst(){ inti=fｉrｓt.fｉnd(＇@'）；?fｉrst.ｅrasｅ（i，１);}iｎｔSUＭ;strｉnｇNODE,ＥNOＤE;／/計(jì)算firstｖoiｄfirsｔ(eｄgeｎi，edge＊n，iｎtx){ ｉntｉ，ｊ;?for(j=0;j＜SUＭ;j+＋)?｛ ?ｉf(ni.ｇｅtlf（）==n[j].ｇetｌf()) {? ?if(NODE.fｉｎd(ｎ［j]．gｅtro())<NODE.lｅngth())? ?{ ??for(i=0；i<SUM;i＋＋）?? ｉｆ(ｎ［i].getlf()==ｎ[ｊ].getro())???ｆiｒｓt（n［i],n，x)；???}? ?else ?n[x].newfiｒst(n[ｊ]．geｔｒo()); ?｝?}}//計(jì)算folloｗvoidfoｌlow(ｅdgeｎi,edge*ｎ，inｔx)｛ inti，j,k，s；?strinｇstr;?ｆor(i＝0;ｉ＜ｎi．ｇetrlen();ｉ+＋) {? s=ＮＯDE.finｄ（ni．gｅｔrg（）［i])； ?if(s<NＯDE.leｎgth(）&&s>－1)//是非終結(jié)符??if（i<ｎi.ｇetｒlen()-１)/／不在最右 fｏr(j=0;ｊ<SUM;j++) if(n[j].getlｆ().fｉnd(ｎi.ｇetrｇ()[i])==０） {? if(NODＥ．find(ni．getrg(）[i+1])<NODE．lenｇth（))? ?｛?? for(k＝０;k<SＵＭ;k+＋) ? iｆ(n［ｋ].getlf(）.finｄ(ｎi．ｇetrg(）[i+1])==0) ?? ｛????n[ｊ].newfolloｗ（n[k].ｇetfiｒst（))；?? ?iｆ（ｎ[k].ｇｅtｆirsｔ()．fiｎｄ("@")<n[k].getｆirst().ｌeｎgth（）)? n[ｊ].newfolｌoｗ（ni.geｔｆolｌｏw（))；?? ?} ? } ? elｓｅ ? ｛? ??str.erase（); ? str+=ni.ｇeｔｒg()［i+1];? n[ｊ].ｎewｆollow(ｓtr）;? ?｝? }? }}／/計(jì)算seｌｅctｖoiｄselｅcｔ(edge&ni,edge＊n）{?inti，j;?if(EＮODE.find(ｎｉ.gｅtｒo(）)<ENOＤE.lengｔh（）) {? ｎi.ｎewseleｃt(ｎi.gｅtｒo()）;??ｉf(nｉ.ｇeｔro()＝="＠＂) ?ni.nｅwｓｅleｃｔ(ni.gｅtfolｌow()）;?} else?fｏr（i=0;i<ｎi.getrｌen()；i+＋)?{? ｆｏr（j=０;j<SUＭ;j＋+) ?iｆ(ｎｉ.getrg（）[i]＝=n[j].ｇｅtlｆ()[0]) ?{?? nｉ.newselect(n［j］.getfirsｔ(）);???iｆ(n[ｊ]．gｅtfirst().find(＇＠')>ｎ[ｊ].ｇetfｉrst()．ｌｅngtｈ())???return;? ｝ }}／／輸出集合voidout（strｉｎgp)｛ intｉ； iｆ(ｐ.leｎgｔｈ（）==0) ｒｅｔurｎ; couｔ<＜"{";?ｆor（i=0;ｉ<p.ｌength()-1；i++)?{?cout<＜p[ｉ]＜＜＂,"; ｝?cout<<ｐ［i]<<"}"；｝／/連續(xù)輸出符號(hào)ｖoidｏｕtfu（inｔa,sｔｒｉngc)｛?iｎｔi； fｏr(i=0；i<a;i++)?cout＜<c；}//輸出預(yù)測(cè)分析表vｏiｄouｔgrａｐｈ(edge*n,string(＊yc)[50]){?intｉ,ｊ,k; boolflａg;?ｆｏr(i＝0;i<ENＯDE.lｅｎgｔｈ();ｉ++)?{?if(ＥＮODE［ｉ]!=＇@＇) {?? outｆu(１0,""); ?cout＜＜EＮOＤE［i]; }?} outfu(10,""）;?cout＜<"#＂<<eｎｄl； inｔｘ; fｏr(i=0;i<NODＥ.lｅnｇtｈ();i++)?{ outfｕ(4,"＂);? cout<<NＯDE[ｉ]; ｏutfu(５,＂");? foｒ(ｋ＝0;k<EＮＯDE.ｌength(）；k++)? {???fｌag＝1; ?for(ｊ=0；j<SUＭ；ｊ++)???{?? ?if(NODＥ[i］＝＝ｎ[ｊ].geｔlf(）[0]） {?? ??ｘ＝n[j]．gｅtsｅleｃｔ().ｆｉnd(ＥNODE[k]); ? ?ｉf(ｘ<n[ｊ].gｅtseleｃｔ（）.ｌeｎgtｈ(）&&ｘ>－１)?? {? ? ?ｃout<<"->"<<n［ｊ]．getrｇ（); ｙc[i]［k]=ｎ[j]．gｅtｒg(); ?ouｔfu（９-n[j].getｒlen(),"");??? ?flａg=0；?? }?????ｘ=n［ｊ]．getselｅct(）．ｆind('＃'); ? ?if(k==ＥNOＤＥ.length()-１&&x＜ｎ[j］.ｇetｓelect（)．length()＆&x>-1) ?? {? ??ｃout<＜"->"<＜n［ｊ].geｔrg()； ? ? ?yｃ[ｉ][ｊ]=ｎ[j].gｅtｒg（）;???? } }? }?? if(ｆlａg&&ＥNODE[k]！=＇@')?? oｕtfu(11,""）;??} ?ｃoｕｔ＜＜endl;?}｝/／分析符號(hào)串intpiｐei(striｎg&chuan,stｒing＆fenxi,sｔriｎg（*yc）[５0]，ｉnt&ｂ){?chaｒch,a；?intｘ,i,j,ｋ; b++; coｕt＜<eｎｄｌ<<""<＜b;?if(b>9)?outfu（8，""）；?else outfu（9，""); cout<<fｅnxi； outｆu(２6－ｃｈuan．lengtｈ()-fｅnxi.ｌeｎgtｈ(）,＂"）； cｏut<＜ｃhuan; outfu(１0,＂");?a=chuaｎ[0];?ｃh=ｆenxｉ[fｅｎxi.ｌength()－1］; x=ＥNＯDE.find(cｈ); iｆ(x<ENODE.ｌenｇth()&&x＞－1）?{ if（ch==a) ｛ ?fｅnxi.ｅrase（fenxｉ．length（)-１,1);???ｃhuaｎ.erase(0，1）； cｏut<<＂＇"＜<a<<"'匹配";? ?if(pｉｐeｉ(ｃhuan,feｎxi,ｙc,b)) ??retｕrn１; ??ｅｌse ??return0；?} elｓe reｔｕrn0;?} else { if（cｈ==＇＃'） { ?if(ch=＝a) {? ?coｕt＜＜"分析成功"<＜enｄl;???rｅturn1; ｝??else? return０； }?else? if(ch=='＠'） {? fｅｎxi.erase(fｅnxｉ.lengｔh()-1，1）；? ?iｆ(pipｅi(chｕan,fenｘi,yc,b))? ?rｅtｕrn1;? ?eｌse? ｒｅｔｕrn０; }? eｌse? ｛? i=NODＥ.fｉｎd(ch); if(a=='#'） {?? x=ＥNODＥ．fｉnｄ('@'); ?iｆ（x<ＥNＯDＥ.ｌenｇth()&&x>-1) ? ｊ=ENOＤE.lenｇth()-1;? ?else???j＝ＥNODＥ.length()； ?}??elｓe ??ｊ=ENＯDＥ．fiｎｄ(a)；??if(yc［i］[j]．ｌｅnｇth(）) {? cｏut＜<ＮODE［i］<<＂->"<<yc[i][j］；? fenxi.eｒasｅ(fenxi.lengｔh(）－1,１);???ｆｏｒ(ｋ＝y(tǒng)c[i][j].length()-1;k＞-1;k--） ? if（yc[i]［j][k］!=＇@'）? ?fｅnxｉ+=ｙｃ[ｉ][j][k];???iｆ（pipei（ｃhuａn,ｆｅnxi，yc,b）) ??returｎ１;? ?ｅlse? ?rｅｔurn０；??｝ else? ?reｔurn0；? } }｝voｉdmain（){?edge＊n； strｉngstr,(*yc)[５０];?iｎｔi,j,k； booｌｆｌag=0； ｃouｔ<<"請(qǐng)輸入上下文無關(guān)文法的總規(guī)則數(shù):"＜<enｄl;?ciｎ>＞ＳUＭ; cｏut＜<＂請(qǐng)輸入具體規(guī)則（格式:左部右部，＠為空):＂<<endl;?n=newedgｅ[SUM];?foｒ(i＝0;i<SUM；ｉ++） foｒ(j=0；j<ｎ［i].gｅtｒlｅn(）;j+＋) {?? str＝n[ｉ]．ｇeｔrg()；? if(ＮOＤE．ｆind(ｓtｒ[j]）>NODE.lengtｈ（)＆&EＮODE.fiｎd(ｓｔr[j])>ENODE．ｌｅnｇｔh()) ?ＥNODE＋=ｓｔｒ[j]；?}?//計(jì)算fiｒst集合?ｆor(i=0;ｉ<SUM；i++)?{?ｆiｒst(n［i］,n,ｉ);?}?//ｏutfu（10，＂~*~");coｕt<<endl; foｒ（i=0;i＜SUM;i++)?if（n[i].ｇetfiｒｓt(）.find("@＂)<n[i].getfirst().lengtｈ（)） ｛? if(ＮＯＤＥ.fiｎd(ｎ[i].geｔro(）)<ＮOＤE.lengｔh())? ?{ ? for（k=1；k<n［i］.geｔrｌen();k+＋） ?｛??? if(NOＤE．find(ｎ[i].getｒg()［k])＜NＯDE.lenｇｔh()) ??{ ??fｏr(j=０；j<SUＭ;j++) ??? { ? ? if（n[i].geｔｒg()［k]＝=ｎ[j].geｔｌf()[0])? ? ???｛ ? ? ? n[i]．newfiｒｓｔ（n[j].ｇｅtｆirｓt(））; ??? ? bｒeak; ??? ? } ? ?} ? if(n[j].getfirst(）．finｄ("＠"）>n［ｊ].getｆｉrst().length()) ?? {?? ?n[i].dｅlfirsｔ();??? ? bｒeak；? ?? } ????}? ? ｝? ? }?｝ //計(jì)算follow集合 ｆｏr(ｋ=0；k<SUM;k++) ｛?ｆoｒ(i=０；i＜ＳＵＭ;i++)?｛?? if(n[ｉ].gｅtlf（）==n[０］.getlf()） ??n[i].newｆollow("＃＂);?? follow(n［i],n,i）; } ｆor(i=０;i＜SＵM;i＋+) {?? for（j＝0;j<ＳＵM;j＋＋)? ?if（ｎ［j].getｒｇ().ｆiｎｄ（n［ｉ].ｇetlf（)）＝＝n［j］.gｅtｒleｎ（)－1） n[i]．nｅｗfollow(ｎ[j].ｇetfｏlｌｏw（))； } } //計(jì)算ｓelecｔ集合?foｒ(i=0；i<ＳUM;i++)?｛?select(ｎ[ｉ］,n); ｝ for(i＝0;i<NＯＤE．lｅｎgth();i＋+)?{?str.eｒaｓe(); for(j=0;j<SUM；j++)? if(n［ｊ].geｔlf（）[０]=＝NODE[i])? {?? if（!stｒ.ｌength（)) ??str=n[j].ｇｅtｓｅleｃｔ()； ｅlsｅ ? ｛?? for(k=0;k<n[j].geｔseｌeｃt().lｅnｇth();k++）????if(str.find(ｎ[ｊ].getseｌeｃｔ()[ｋ］)<str．lｅｎgth()）? ?{? ? flag=1;? ｂreak; } ｝ } }?//輸出?cｏut<<endl＜<"非終結(jié)符"; ｏｕtfu（SUＭ,"");?cout＜＜＂Ｆｉrst＂;?outfｕ(SUM，""); cｏｕt<＜＂Ｆollow＂＜<endｌ; outfu(5+SUM,"-*-");?cｏuｔ<<eｎdl;?for（ｉ＝0;i＜ＮODE．leｎgｔｈ();i＋+)?{ for（j=0;ｊ＜SＵM；j++） iｆ(ＮODE[ｉ]＝=n[j]．ｇetlｆ（)［0]) ?{ ? outfu(3,""）;?? cｏut<<NＯＤE[i]； ｏutfu(SUM+4，""); ?ｏut(ｎ[ｊ].getfｉrｓt()）;???ｏutｆu(SUＭ+4-2*n[j].gｅtｆirst()