遞歸下降分析方法和LR分析方法

實(shí)驗(yàn)二：語法分析一、實(shí)驗(yàn)?zāi)康模豪斫庹Z法分析程序的主要任務(wù)和實(shí)現(xiàn)技術(shù)。二、實(shí)驗(yàn)內(nèi)容：為無二義性表達(dá)式文法G[E]構(gòu)造語法分析程序G[E]:E->E+T|TT->T*F|FF->(E)|i變?yōu)長L(1)文法：E->TE'E'->+TE'|eT->FT'T'->*FT'|eF->(E)|iLR⑴項(xiàng)目集規(guī)范族：三、實(shí)驗(yàn)要求：用遞歸下降分析方法和LR(1)分析方法分別實(shí)現(xiàn)，要求能夠?qū)φ_的和錯誤的輸入串進(jìn)行分析，給出分析結(jié)果(accept/error)。程序輸入為形如i+i*i#或者ii#的串，(1)對于遞歸下降分析，輸出為推導(dǎo)所用的產(chǎn)生式序列；(2)對于LR(1)分析，輸出為包括分析步驟、分析棧情況、剩余輸入串以及分析動作在內(nèi)的分析過程，并考慮增加語義分析生成中間代碼功能的程序擴(kuò)展。以小組形式(3-5人，自由結(jié)組)提交兩份(遞歸下降分析/LR(1)分析)紙質(zhì)實(shí)驗(yàn)報(bào)告，每份實(shí)驗(yàn)報(bào)告應(yīng)包括：

a）程序流程圖，遞歸下降分析要畫出每個分程序的結(jié)構(gòu);b）程序運(yùn)行截圖（正確的和錯誤的各一）；c）實(shí)驗(yàn)過程中遇到的問題和解決辦法，以及實(shí)驗(yàn)過程中的收獲。LR⑴語法分析實(shí)驗(yàn)報(bào)告一.程序運(yùn)行截正確的輸入串i+i*i#:匚|c'"D：\tetporaryALR(1)\LR(1).eze*|-|n|2<請您輸入一個由字符…二組成的字符串，并以tt結(jié)尾步驟狀態(tài)棧符號棧輸入串0：0tti+i*i#1：05#i+i*i#2：03ttF+i*i#3：02#T+i*i#4：01#E+i*i#5:PH6#E+i*i#6：0165#E+i*i#7：016<14>#E+F*i#8：016<13>#E+T*i#9：016<13>7#E+T*i#10：016<13>75#E+T*i#11：016<13>7<15>#E+T*F#12：016<13>#E+T#13：01#Ettacc請按任意鍵繼續(xù)..?▲錯誤的輸入串ii#：-|n|x|cT*D:\.tenporaryYLR(1)\LR(1).exe請您輸入一個由字符組成的字符串，并以訴結(jié)底iitt步朦狀態(tài)棧符號棧-|n|x|0=0ttiitt1：05ttiitt請按任意鍵繼續(xù)...■程序流程圖三.實(shí)驗(yàn)過程中遇到的問題和解決辦法，以及實(shí)驗(yàn)過程中的收獲對文法進(jìn)行LR⑴分析需要求出該文法的action表和goto表首先需要求該文法的LR⑴項(xiàng)目集。LR項(xiàng)目集。LR⑴項(xiàng)目集：10：S'->E,#E->E+T,#1+E->-T,#1+T->-T*F,#1+1*T->F,#1+I*F->-(E),#1+1*F->-I,#1+1*II：S'->E?，#E->E?+T,#1+12：E->T-,#1+T->T?*F,#1+I*13：T->F-,#|+|*14：F-X-E),#|+|*E->-E+T,)1+E->-T,)1+T->T*F,)1+I*T->-F,)|+|*F->-(E),)1+1*)|+|*15：F->i-,#|+|*16：E->E+-T,#1+T->T*F,#|+|*T->-F,#1+1*F->-(E),#|+|*F->-I,#1+1*17：T->T*-F,#|+|*F->?(E),#|+|*F->-I,#|+|*18：F-XE-),#1+1*E->E-+T,)1+19：E->T-,)1+T->T-*F,)|+|*110：T->F?，)1+I*Hl：F-X-E),)1+hE->E+T,)1+E->-T,)1+T->T*F,)1+IT->?F,)1+I*F->-(E),)1+1*F->-(E),)1+1*F->-i,)|+|*112：F->i-,)|+|*113：E->E+T-,#1+T->T-*F,#1+1*114：T->F-,#|+I115：T->T*F?,#|+IU6：F->-(E),)1+1*E->E-+T,)1+117：F-XE)-,)|+|*118：E->E+-T,)1+T->T*F,)1+I*T->-F,)|+I*F->-(E),)1+1*F->-I,)|+|*F->?I,)|+|*121：T->T*F?,)1+I*122：F-XE)?,#1+I*119：E->E+T-,)1+T->T-*F,)1+I*120：120：T->T*-F,)|+|*action表和goto表:F->?(E),)1+I*狀態(tài)actiongoto.1+*()#ETF0S5S41231S6acc

2r2S7r23r4r4r44S12SU8910Lor6r6r66S5S413147S5S4158S18S229r2S20r210r4r4r411S12Sil1691012r6r6r613rlS7rl14r4r4r415r3r3r316S18S1717roror518S12Sil191019rlS20rl20S12Sil2121r3r3r322roror5h=—===========/****#iiiclude<iostieam>#iiiclude<sstream>#iiiclude<stiing>#iiiclude<stack>#iiiclude<map>#iiiclude<vector>#iiiclude<iomanip>usingnamespacestd;H/.LR(1)分析表是table表Z/initialize_datas用于存放初始化table的數(shù)據(jù)〃主要用于增強(qiáng)可讀性namespaceuutialize_datas(mtanay_temp[23][9]=((-1,-1,4,-1,5,-1,1,2,3},(6,-1,-1,-1,-1,200,-1,-1,-1},{102,7,-1,-1,-1,102,-1,-1,-1},(104,104,-1,-1,-1,104,-1,-1,-!},(-1,-1,-1,11,12,-1,8,940),(106,106.-1,-1,-1,106,-1,-1,-!},{-1,-1,4,-1,5,-1,-1,13,14},{-1,-1,4,-1,5,-1,-1,-1,15},(18,-1,-1,22,-1,-1,-1,-1,-!},(102,20,-1,102,-1,-1,-1,-1,-!},(104,104,-1,104,-1,-1,-1,-1,-!},(-1,-1,11,-1,12,-1,16,9,10),(106,106.-1,106,-1,-1,-1,-1,-!},(101,7,-1,-1,-1,101,-1,-1,-1},(104,104,-1,-1,-1,104,-1,-1,-!},(103,103,-1,-1,-1,103,-1,-1,-!},(18,-1,-1,17,-1,-1,-1,-1,-1),(105,105,-1,105,-1,-1,-1,-1,-!},{-1,-1,11,-1,12,-1,-1,19,10},(101,20,-1,101,-1,-1,-1,-1,-!},(-1,-141,-1,12,-1,-1,-1,21},(103,103,-1,103,-1,-1,-1,-1,-!},(105,105,-1,-1,-1,105,-1,-1,-!}};charch[9]=(甲,*，T",T,#,E,T,F};}//typedefvector<inap<chai;iiit>>Table;//typedefmap<chai;mt>:iteratorTable_Iteiator;Tabletable(23);〃對LR(1)分析表table表進(jìn)行初始化boolmitialize_table(Table&table){fbr(inti=0;i!=23;++i)ffor(mtj=0;j!=9;++j){table[i][initialize^datas::ch[j]]=mitialize_datas::anay_temp[i]Ij];)}}〃//Tablereduction(107);charsecond_subscript[107];boolmitialize_reduction(Table&reduction){reduction]100]['S']=1;second_subscript[l00]-Sf;reduction]101]['E']=3;second_subscript[101]=*E,；reduction]102]['E']=1;second_subsciipt[102]='E';reduction[103][Tf]=3;second_subscript[103]-T,;reduction]104][T]=1;second_subsciipt[104]=T;reduction]105]['F']=3;second_subscript[l05]-F;reduction]106]['F']=1;second_subscript[l06]='F;}//////狀態(tài)棧兼符號棧classmy_stack{public:my_stackQ{);my_stack(int,char){push(O,;stimggeCstatusQ;stimggecchaiacterQ;intpush(int,char);intpop(iiit);mttopQ；private:deque<pair<int,chai>>dp_i_c;stimgstr;stimgstreamssio;};mtmy_stack::push(mtstat.chai-terminator){dp_i_c?push_back(std::make_pau(staLtermniator));return0;}mtmy_stack::pop(intnum){dp_i_c.erase(dp_i_c?end()?nuni,dp_i_c.endO);return0;}hitmy_stack::top(){returndp_i_c[dp_i_c.size()?}stringmy_stack::get_statusQ{ssio.str(nH);ssio.clearQ;fbr(deque<pair<intxhar>>:iteratoriter=dp_i_c.begin();iter!=dp_i_c?endQ;++iter)if(iter->first<=9)(ssio?iter->first;)else(ssiovv”(”vviter->fkstvv”)”；)}ssio?str;ssio.str(n,r);ssio.clearQ;returnstr;}stringmy_stack::get_charactei(){ssio.str(n,r);ssio.clearQ;fbr(deque<pair<intxhar>>:iteratoriter=dp_i_c.begin();iter!=dp_i_c?end();-H-iter)ssio?iter->second;}ssio?str;ssio.str(n,r);ssio.clearQ;returnstr;}///hit{stimgstr;inttem(O),tem_StrSize;chaitenniiiator[5]={'i',},tem_ch,;〃/〃//〃〃/程序檢查段，主要用于檢查程序是否有誤，check:cout?”請您輸入一個由字符T、*、中、)組成的字符串，并以#結(jié)尾”?endl;ciii?str;//tem_StrSize=sti\sizeQiRstr[str.size()?l]!='#')gotoa;}while(tem<sti.sizeQ-l)if((su[tem]!=terniinator[0])&&(str[tem]!=terniuiator[1])&&(str[tem]!=ternunator[2])&&(str[tem]!=ternunator[3])&&(str[tem]!=ternunator[4]))(a:cout?”您輸入的字符串有誤!\n”vv”如果您想斷續(xù)運(yùn)行本程序請輸入y,”vv”如果您不想斷續(xù)運(yùn)行本程序請輸入任意鍵！”?endl:scanf(”％c\&tem_ch);scanf(”％c\&tem_ch);if(teni_ch=,y,)(gotocheck;}else(return0;)}tem++;}///〃//〃〃//〃程序檢查段結(jié)束?。。?！/〃〃//〃〃〃/〃/利用LR(1)分析表進(jìn)行分析的程序段??！!〃/〃//〃主要用于對輸入字符串進(jìn)行語法分析!!//TableIteratortabiter;my_stackstat_char(O,#);intcounter=0;intfi_subscript;charse_subsript;initialize_table(table);//initialize_reduction(reduction);inttemp1=str.size();cout?M步驟”vv”-?left?senv(20)?H狀態(tài)?！?senv(20)?H符號?！?iight?senv(20)?H輸入串”?endl;cout?sehv(2)?countei++?,t：”?left?setw(20)?stat_char.get_status0?senv(20)?stat_char.get_charactei()<<right<<senv(20)?str?endl;fbr(tem=O;tem<=temp1-1;)ftem-ch=str[tem];if(table[stat_char.topO][tem_ch]<=22&&table[stat_char.top()][tem_ch]>=0)(str.erase(OJ);temp1=str.size();stat_char.push(table[stat_chai-.top()][tem_ch],tem_ch);cout?setw(2)?counter++?n:H?left?setw(20)?stat_char.get_status0?senv(20)?stat_chai-.get_character()<<right<<setw(20)?sti?endl;)elseif(table[stat_char.top()][tem_ch]<=106&&table[stat_char.top()][tem_ch]>=l00)(fi_subsciipt=table[stat_char.topQ][tem_ch];se_subsript=second-subscript[fi_subsciipt];stat_char.pop(ieduction[fi_subscnpt][se_subsript]);stat_char.push(table[stat_chai-.top()][se_subsnpt],se_subsnpt);cout?setw(2)?counter++?n:H?left?setw(20)?stat_char.get_status0?senv(20)?stat_chai-.get_character()<<right<<setw(20)?sti?endl;}elseif(table[stat_chai;top()][tem_ch]=-l)(cout?nenorn?endl;exit(0);}else(if(table[stat_chai\top()][tem_ch]==200)cout?HaccM?endl;return0;))return0;}遞歸向下比較簡單，故只給程序!E.>TE'E，.>+TE，|et.>ftT，.>*FT|eF->(E)|iT=SE，=GE->TGG.>+TG-TG|￡T->FSS->*