計科150201516010118李杰-編譯原理試驗四

河南工業(yè)大學(xué)實驗報告課程名稱 編譯原理 一院 系 信息科學(xué)與工程學(xué)院姓 名 李杰 指導(dǎo)老師 閻娼 批改日期 實驗項目實驗四LR（1）分析法專業(yè)班級 計科F1505班 學(xué)號 201516010118 日期 2018.5.14 成績 一.實驗?zāi)康?掌握LR（1）分析法的基本原理.掌握LR（1）分析表的構(gòu)造方法.掌握LR（1）驅(qū)動程序的構(gòu)造方法二.實驗內(nèi)容及要求構(gòu)造LR（1）分析程序，利用它進行語法分析，判斷給出的符號串是否為該文法識別的句子，了解LR（K）分析方法是嚴格的從左向右掃描，和自底向上的語法分析方法。根據(jù)某一文法編制調(diào)試LR（1）分析程序，以便對任意輸入的符號串進行分析。本次實驗的目的主要是加深對LR（1）分析法的理解。程序輸入/輸出示例：對下列文法，用LR（1）分析法對任意輸入的符號串進行分析：（0）S’->E（1）E->E+T（2）E->E-T（3）E->T（4）T->T*F（5）T->T/F（6）T->F（7）F->（E）（8）F->i輸出的格式如下：班級 在此位置輸入符號串（1）LR（1）分析程序，編制人：班級 在此位置輸入符號串（2）輸入一以#結(jié)束的符號串（包括+-*/（）i#）：⑶輸出過程如下：步驟狀態(tài)棧符號棧剩余輸入串動作10#i+i*i#移進(4)輸入符號串為非法符號串(或者為合法符號串)備注：(1)在“所用產(chǎn)生式”一列中如果對應(yīng)有推導(dǎo)則寫出所用產(chǎn)生式；如果為匹配終結(jié)符則寫明匹配的終結(jié)符；如分析異常出錯則寫為'分析出錯”；若成功結(jié)束則寫為“分析成功”。(2)在此位置輸入符號串為用戶自行輸入的符號串。注意：1.表達式中允許使用運算符(+-*/)、分割符(括號)、字符i，結(jié)束符#；.如果遇到錯誤的表達式，應(yīng)輸出錯誤提示信息(該信息越詳細越好)；.對學(xué)有余力的同學(xué)，測試用的表達式事先放在文本文件中，一行存放一個表達式，同時以分號分割。同時將預(yù)期的輸出結(jié)果寫在另一個文本文件中，以便和輸出進行對照；.可采用的其它的文法。三.實驗過程Glr分析器由三個部分組成：(1)總控程序，也可以稱為驅(qū)動程序。對所有的LR分析器總控程序都是相同的。(2)分析表或分析函數(shù)，不同的文法分析表將不同，同一個文法采用的LR分析器不同時，分析表將不同，分析表又可以分為動作表(ACTION)和狀態(tài)轉(zhuǎn)換(GOTO)表兩個部分，它們都可用二維數(shù)組表示。(3)分析棧，包括文法符號棧和相應(yīng)的狀態(tài)棧，它們均是先進后出棧。分析器的動作就是由棧頂狀態(tài)和當前輸入符號所決定。LR分析器結(jié)構(gòu)：其中:SP為棧指針，S[i]為狀態(tài)棧，X[i]為文法符號棧。狀態(tài)轉(zhuǎn)換表用GOTO[i,X]=j表示，規(guī)定當棧頂狀態(tài)為i,遇到當前文法符號為X時應(yīng)轉(zhuǎn)向狀態(tài)j,X為終結(jié)符或非終結(jié)符。ACTION[i,a]規(guī)定了棧頂狀態(tài)為i時遇到輸入符號a應(yīng)執(zhí)行。動作有四種可能：移進，歸約，接受acc,出錯0LR⑴語法分析程序的設(shè)計思想：定義項目的一般形式是[A-a-B，a1a2…ak],這樣的一個項目稱為一個LR(k)項目。項目中的a1a2…ak稱為它的向前搜索符串(或展望串)，令K=1,即為LR(1)語法分析程序。在此，重新定義CLOSURE(I)的算法：項目集1的閉包CLOSURE(I)構(gòu)造方法：.I的任何項目都屬于CLOSURE(I)。.若項目用一a?B。，a］屬于CLOSURE(I),B一己是一個產(chǎn)生式，那么，對于FIRST(pa)中的每個終結(jié)符b,如果［Bf-1,b］原來不在CLOSURE(I)中，則把它加進去。.重復(fù)執(zhí)行步驟2,直至CLOSURE(I)不再增大為止。GO()的算法保持與LR語法分析程序一樣，通過以下方法構(gòu)造文法分析表：動作ACTION和狀態(tài)轉(zhuǎn)換GOTO構(gòu)造如下：.若項目用一&-。'b］屬于Ik且GO(Ik,a)=Ij,a為終結(jié)符，則置ACTION［k,a］為“sj”。.若項目用一a-,a］屬于Ik,則置ACTION［k,a］為“rj”；其中假定A-a為文法G的第j個產(chǎn)生式。.若項目￡'-S-，劃屬于Ik,則置ACTION［k,#］為“acc”。.若GO(Ik,A)=Ij,則置GOTO［k,A］=j。.分析表中凡不能用規(guī)則1至4填入信息的空白欄均填上“出錯標志”。當具體面對輸入串時，通過查表進行分析該進行何種動作。設(shè)計思想的流程圖為：Q該實驗文法對應(yīng)的LR⑴分析表狀態(tài)ACTIONGOTOi+*()#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r5Q數(shù)據(jù)結(jié)構(gòu)“ACTION表“ACTION表〃C〃 〃I-〃 〃I-〃 〃C〃 〃I-〃 〃I-〃10,r5,r5,0,r5,r5);intgotoarr[12][3]={1,2,3, 〃GOTO表0,0,0,0,0,0,0,0,0,8,2,3,0,0,0,0,9,3,0,0,10,0,0,0,0,0,0,0,0,0,0,0,0}；charvt[6]={'i','+','*','(',')','#'}; //存放終結(jié)符charvn[3]={'E','T','F'}; //存放非終結(jié)符stringProduction[6]={〃E->E+T〃，〃E->T〃，〃T->T*F〃，〃T->F〃，〃F->(E)〃，〃F->i〃};〃產(chǎn)生式集合intcount=0;//記錄當前進行處理的輸入字符串字符位置intline=1;//記錄處理的步驟數(shù)boolflag=false;intStatusNumber=1;//棧中狀態(tài)數(shù)stringstacktd="#";//記錄符號棧中內(nèi)容intStatus[50]={0};//記錄狀態(tài)棧stack<char>Stack;//創(chuàng)建一個符號棧stack<int>status;//創(chuàng)建一個狀態(tài)?！蚝瘮?shù)設(shè)計voidJudge(int&i,intj,chararr口，charch,strings)〃判斷輸入串是否由文法終結(jié)符組成voidOutputstatus()〃輸出狀態(tài)集voidOutputstring(strings)〃輸出未處理的字符串voidOutput(strings)〃輸出步驟、狀態(tài)集、符號集、輸入串voidShift(inti,strings)〃移進函數(shù)SvoidGoto(stack<int>st1,stack<char>st2,strings)//GoTo語句voidReduction(inti,strings)〃歸約函數(shù)RvoidAnalyse(strings)〃具體分析函數(shù)G分析函數(shù)的具體實現(xiàn)voidAnalyse(strings){//具體分析函數(shù)Stack.push('#');//初始化status.push(0);s=s+〃#〃；intt=-1;//記錄ch在數(shù)組vt的位置while(count<s.size()){inti=status.top();charch=s.at(count);Judge(t,6,vt,ch,s);if(flag==true){if(action[i][t]!="acc"&&action[i][t]!="0"){if(action[i][t].at(0)=='S'){

action[i][t].erase(0,1); 〃刪除action[i][t]的首子母SShift(atoi(action[i][t].c_str()),s);//atoi(action[i][t].c_str()),將action[i][t]轉(zhuǎn)換為整型action[i][t].insert(0,"S");//將S添加回action[i][t]}elseif(action[i][t].at(0)=='r'){action[i][t].erase(0,1);//刪除action[i][t]的首字母rReduction(atoi(action[i][t].c_str()),s);//atoi(action[i][t].c_str()),將action[i][t]轉(zhuǎn)換為整型action[i][t].insert(0,"r");//將r添加回action[i][t]}}elseif(action[i][t]=="0"){cout<<"\tError”<<endl;break;}elseif(action[i][t]=="acc"){Output(s);cout<<"acc"<<"\t分析成功“<<endl;break;}}elseif(flag==false)break;}}07接受acc的情況m"E:\cod?blocks'漏評總理國駛四世i叭口phug香臉四,ese11505JJIR(L)分析程序，編制人：李杰.20151601011B.1505JJI迪示:軻星序只能游由JL)構(gòu)成的字符串進行分析:口十i；呼ioo-ooo-o-o-o10111213141516171819o-5391_h_M0H6oo-ooo-o-o-o10111213141516171819o-5391_h_M0H6JI532nos88888444444444445771322n.oooo棧++i+F+T口「-.■4斗十4...JiF匚FiFTEEEEEEE*￥4fkfkfLfLFTT-TTTE■1■1-1■1+iDW>)+升粒1#討避述#4力■1十■1B1■!!1\l...牛牛"1■!■!t—(-1++++■!-J4ff#rocessreturned0(OxD)execution動作KTIONC.|]=M,狀態(tài)4A棧ACTION[4,1]=S5,狀態(tài)5人棧r6:F->i歸的，G口T口以FL?人袪i4:TCF歸約,G口T口3,T)=2人?；?上”歸約,GoT

ACTIONE8n-i：=S6,-hACTION[6,二]斐瓦伏否5人棧r日:F7i歸約,GciT□?F)=W.榜r4：T-2歸約三GciTog,T)=9人棧eLE->E+T歸約，G口R@E：-E入棧ACnQN[&)]=S1L狀態(tài)11人棧r5：”Mg歸約.丘口丁口(。/1三3棧r4:T->F歸為，GciTuCNT入棧ACTIONL2^.-S7,狀態(tài)7人棧ACTION[7,i]=g[狀態(tài)5人棧r6：F-：>i歸約]GciTob.F)-]。入棧:r3:T->T*F?歸約遞:EQT歸豹，@口T口&E)=l人棧acc 分析成功time：IE.S76s出錯情況■"F：\codcHcck式編譯案理庭晚四世in\Debugl實險叫ese,LR(1)jLR(1)jna，20151601011S,限示沐程序只能前由+ J),'i'構(gòu)成的字符串進行分析剩余輸入串樹限示沐程序只能前由+ J),'i'構(gòu)成的字符串進行分析剩余輸入串樹i十+1#率忖十+1#扇輸入要分析的字符串d++iACTIQNE0,i］=S5n狀態(tài)5人棧t$：F-：W￥勺，為T口QF)-認才玄r4:T-兄歸閡，G口T口9T)=2人棧乩T［口機2產(chǎn)］=5/狀態(tài)丫人棧time:time:6.128s四.實驗總結(jié)(心得).實驗體會通過本次實驗，掌握YLR⑴分析法的基本原理和LR⑴分析表