中南大學編譯原理實驗報告

中南大學編譯原理

實驗報告班級:計科1205姓名:趙越學號:0909122209實驗ー詞法分析程序設計與實現(xiàn)ー、實驗目的加深對詞法分析器的工作過程的理解;加強對詞法分析方法的掌握;能夠采用一種編程語言實現(xiàn)簡單的詞法分析程序；能夠使用自己編寫的分析程序?qū)唵蔚某绦蚨芜M行詞法分析。二、實驗內(nèi)容自定義ー種程序設計語言,或者選擇已有的?種高級語言,編制它的詞法分析程序。詞法分析程序的實現(xiàn)可以采用任何一種編程語言和編程工具。從輸入的源程序中,識別出各個具有獨立意義的單詞,即關鍵字、標識符、常數(shù)、運算符、界符。并依次輸出各個單詞的內(nèi)部編碼及單詞符號自身值。（遇到錯誤時可顯示“Error”,然后跳過錯誤部分繼續(xù)顯示）三、實驗要求:.對單詞的構(gòu)詞規(guī)則有明確的定義；.編寫的分析程序能夠正確識別源程序中的單詞符號；.識別出的單詞以く種別碼,值〉的形式保存在符號表中,正確設計和維護符號表;.對于源程序中的詞法錯誤,能夠做出簡單的錯誤處理,給出簡單的錯誤提示,保證順利完成整個源程序的詞法分析；四、實驗步驟.定義目標語言的可用符號表和構(gòu)詞規(guī)則；.依次讀入源程序符號,對源程序進行單詞切分和識別,直到源程序結(jié)束;.對正確的單詞,按照它的種別以〈種別碼,值〉的形式保存在符號表中；.對不正確的單詞,做出錯誤處理。五、設計思路和實現(xiàn)過程本實驗是詞法分析器,我是用的是MFC實現(xiàn)的,我的設計思路就是按照書上提示的算法,先將兒個詞法分析器所需的基本函數(shù)用C++的形式實現(xiàn),然后使用循環(huán)語句讀入輸入串的每ー個字符,然后用if…else…語句實現(xiàn),具體判斷方式如下:1、如果讀入的是字母,那么繼續(xù)讀入，知道讀入的字符不是字母或者數(shù)字為止,對照標識符表,如果是標識符,則顯示該串及對應標識符；如果不是,則顯示該串和“$ID”；2、如果讀入的是數(shù)字,則繼續(xù)讀入,知道不是數(shù)字為止,并顯示該串和“$INT”；3、如果讀入的是“則分別輸出該串和"ASSIGN”，”$PLUS”,'SEMICOLON","$LPAR","$RPAR","$LBRACE","$RBRACE”；4、如果讀入的是那么繼續(xù)讀入,如果下ー個是則輸出該串和"$POWER〃;否則輸出該串和‘'$STAR",并將指針回退;5、如果獨到輸入串末尾,則退出。六、錯誤處理創(chuàng)建一個鍵,如果讀岀的字符不屬于以上任何情況,則把此鍵置為真,通知程序退出循環(huán),從而實現(xiàn)對錯誤的處理。七、關鍵代碼voidCWordanalysisDlg::GetChar()(ch=minput.GetAt(pointer);pointer++;voidCWord_analysisDlg::Concat()(strToken+=ch;}voidCWord_analysisDlg::GetBC()(while(ch==1')GetChar();voidCWord_analysisDlg::Retract(){pointerーー;ch二’'；intCWordanalysisDlg::Reserve()(//if(strcmp(stricken,))inti;for(i=l;iく15;i++)if(strcmp(strToken,Token[i])==0)returni;return0;boolCWord_analysisDlg::IsLetter(){if(ch〉ニ'a'&&ch<='z'||ch>='A'&&ch<='Z')returntrue;elsereturnfalse;I7ヽboolCWordanalysisDlg::IsDigit(){if(ch>=O'&&ch<='9')returntrue;elsereturnfalse;voidCWord_analysisDlg::0nAnalysis()(//TODO:Addyourcontrolnotificationhandlercodeherem_list.DeleteAllItems();pointer=0;UpdateDataO;m_input+='\0';while(pointer<m_input.GetLength()-1)(if(end)break;Analysis();)voidCWord_analysisDlg::Analysis()strToken=;GetCharO;GetBC();if(IsLetterO){while(IsLetter()|IlsDigitO){ConcatO;GetCharO;}Retract();code=Reserve();if(code==0)(mlist.InsertItem(index,strToken);m_list.SetltemText(index,1,〃$ID");index++;return;)else(m_list.Insertltem(index,strToken);m_list.SetltemText(index,1,Token[code]);index++;return;elseif(IsDigit())(while(IsDigit()){Concat();GetCharO;}Retract();m_list.InsertItern(index,strToken);m_list.SetltemText(index,1,*$INT*);index++;return;)elseif(ch=='二’)Insertltem(index,strToken);mlist.SetltemText(index,1,"$ASSIGN");index++;return;)elseif(ch=='+')(mlist.InsertItem(index,strToken);m_list.SetltemText(index,1,"$PLUS");index++;return;)elseif(ch=='*')(GetCharO;if(ch=='*')(m_list,InsertItem(index,strToken);m_list.SetltemText(index,1,”$POWER〃)；index++;return;)else(Retract();(m_list.InsertItem(index,strToken);m_list.SetltemText(index,1,”$STAR");index++;return;)elseif(ch==';)lnsertltem(index,strToken);mlist.SetltemText(index,1,?z$SEMIC0L0N*);index++;return;)elseif(ch=='(')(mlist.InsertItem(index,strToken);m_list.SetltemText(index,1,*$LPAR#);index++;return;)elseif(ch==')')(m_list.InsertItem(index,strToken);m_list.SetltemText(index,1,*$RPAR/Z);index++;return;)else if(ch=='{')(m_list.InsertItem(index,strToken);m_list.SetltemText(index,1,ZZ$LBRACE/Z);index++;return;)elseif(ch=='}')(m_list.InsertItem(index,strToken);mlist.SetltemText(index,1,”$RBRACE");index++;return;)elseif(ch=='\0,)end=l;return;else(AfxMessageBox("出入錯誤”)；pointer=rainput.GetLengthO;return;)實驗二LL(1)文法語法分析設計一.實驗目的.熟悉判斷LL(1)文法的方法及對某輸入串的分析過程。.學會構(gòu)造表達式文法的預測分析表。二.實驗內(nèi)容編寫ー個語法分析程序,對于給定的輸入串,能夠判斷識別該串是否為給定文法的句型。三.實驗步驟從鍵盤讀入輸入串,并判斷正誤;若無誤,由程序自動構(gòu)造FIRST、FOLLOW集以及SELECT集合,判斷是否為LL(1)文法;若符合LL(1)文法,由程序自動構(gòu)造LL(1)分析表;由算法判斷輸入符號串是否為該文法的句型【源代碼】#include“stdio.h"#include"stdlib.h"#defineMaxRuIeNum8defineMaxVnNum5defineMaxVtNum5defineMaxStackDepth20defineMaxPLength20defineMaxStLength50structpRNode/?產(chǎn)生式右部結(jié)構(gòu)?/(intrCursor;/?右部序號?/structpRNode*next;｝；structpNode/?產(chǎn)生式結(jié)點結(jié)構(gòu)*/(intICursor;/?左部符號序號?/intrLength;/?右部長度?//?注當rLength=1時,rCursor=T為空產(chǎn)生式?/structpRNode*rHead;/?右部結(jié)點頭指針?/)；charVn[MaxVnNum+1];/*非終結(jié)符集?/intvnNum;charVt[MaxVtNum+1];/?終結(jié)符集?/intvtNum;structpNodeP[MaxRuIeNum];/?產(chǎn)生式?/intPNum;/?產(chǎn)生式實際個數(shù)?/charbuffer[MaxPLength+1];charch;/*符號或stringch;*/charst[MaxStLength];/*要分析的符號串?/structcolIectNode/?集合元素結(jié)點結(jié)構(gòu)*/(intnVt;/?在終結(jié)符集中的下標?/structcolIectNode*next;);structcoIIectNode*first[MaxVnNum+1];"first集?/structcoIIectNode*follow[MaxVnNum+1];"follow集?/intanaIyseTabIe[MaxVnNum+1][MaxVtNum+1+1];"預測分析表存放為產(chǎn)生式的編號,+1用于存放結(jié)束符,多+1用于存放#(T)*/intanaIyseStack[MaxStackDepth+1];"分析棧?/inttopAnalyse;"分析棧頂?/"intreverseStack[MaxStackDepth+1];"顛倒順序棧?/"inttopReverse;"倒敘棧頂?/voidInit();"初始化?/intIndexCh(charch);"返回Vn在Vn表中的位置+100、Vt在Vt表中的位置,7表示未找到?/voidInputVt();"輸入終結(jié)符?/voidInputVnO;/?輸入非終結(jié)符?/voidShowChArray(char*collect,intnum);"輸出Vn或Vt的內(nèi)容?/voidInputP();/?產(chǎn)生式輸入?/boolCheckP(char*st);/?判斷產(chǎn)生式正確性?/voidFirst(intU);/?計算first集,LH>xx...*/voidAddFirst(intU,intnCh);"加入first集?/boolHaveEmpty(intnVn);"判斷first集中是否有空(T)*/voidFollow(intV);"計算千〇IIow集?/voidAddFolIow(intV,intnCh,intkind);"加入follow集,kind=0表加入follow集,kind=1加入first集?/voidShowCoIIect(structcolIectNode**collect);"輸出first或follow集?/voidFirstFollow()；/?計算first和folIow*/voidCreateAT();/?構(gòu)造預測分析表?/voidShowAT();"輸出分析表?/voidIdentify(char*st);"主控程序,為操作方便?/"分析過程顯示操作為本行變換所用,與教程的顯示方式不同?/voidInitStackO;/?初始化棧及符號串?/voidShowStack();/?顯示符號棧中內(nèi)容?/voidPop();"棧頂出棧?/voidPush(intr);/?使用產(chǎn)生式入棧操作?/#incIude"LL1.hvoidmain(void)chartodo,ch;Init();InputVn();InputVt();InputPO;getchar();FirstFollow();printf("所得first集為:");ShowCoIlect(first);printf(“所得follow集為:つ;ShowCoIlect(foIIow);CreateAT0;ShowAT();todo二'y'；whiIeCy*=todo)(printf("\n是否繼續(xù)進行句型分析?(y/n):");todo=getchar();whileCy'!=todo&&'n'!=todo)(printf("\n(y/n)?");todo=getchar();}if('y'=todo)(inti;InitStackO;printf("請輸入符號串(以#結(jié)束)：“)；ch=getchar();i=0;while，#'!=ch&&i<MaxStLength)(ifC'!=ch&&''n'!=ch)(st[i++]=ch;}ch=getchar();)ifC#'=ch&&i<MaxStLength)(st[i]=ch;Identify(st);eIseprintf("輸入出錯!\n");1}getchar();}voidInit()(inti,j;vnNum=0;vtNum=0;PNum=0;for(i=0;i<=MaxVnNum;i++)Vn[i]ハ(X;for(i=0;i<=MaxVtNum;i++)Vt[i]=](X；for(i=0;i<MaxRuleNum;i++)(P[i].ICursor=NULL;P[i].rHead=NULL;P[i].rLength=0;}PNum=0;for(i=0;i<=MaxPLength;i++)buffer[i]=1\0,;for(i=0;i<MaxVnNum;i++)(first[i]=NULL;follow[i]=NULL;)for(i=0;i<=MaxVnNum;i++)(for(j=0;j<=MaxVnNum+1;j++)analyseTable[i][j]=-1;)}/?返回Vn在Vn表中的位置+100、Vt在Vt表中的位置,7表示未找到*/intIndexCh(charch)(intn;n=0;/*isVn?*/while(ch!=Vn[n]&&‘、〇’!=Vn[n])n++;ifC\0*!=Vn[n])return100+n;n=0;/*isVt?*/while(ch!=Vt[n]&&'、〇’!=Vt[n])n++;if('、〇'!=Vt[n])returnn;return-1;)/?輸出Vn或Vt的內(nèi)容?/voidShowChArray(char*collect)(intk=0;whiIe(''〇'!=collect[k])(printfC%c’、coIIect[k++]);}printf("'n");)/?輸入非終結(jié)符?/voidInputVn()(intinErr=1;intn,k;charch;whiIe(inErr)(printf("'n請輸入所有的非終結(jié)符,注意:“);printf("請將開始符放在第一位,并以#號結(jié)束:'n〃)；ch='';n=0;/?初始化數(shù)組?/whiIe(n<MaxVnNum)[Vn[n++]='\0';)n=0;while(('r!=ch)&&(n<MaxVnNum))(if(''!=ch&&''n'!=ch&&-1=IndexCh(ch))Vn[n++]=ch;vnNum++;ch=getchar()：)Vn[n]=，#，；/?以“ダ標志結(jié)束用于判斷長度是否合法?/k=n;/*k用于記錄n以便改Vn[n]='、0’*/if('#'!=ch)(if('#'!=(ch=getchar()))(while('#'!=(ch=getchar()))printf("\n符號數(shù)目超過限制!'n");inErr=1;continue;))/?正確性確認,正確則,執(zhí)行下下面,否則重新輸入?/Vn[k]='、〇';ShowChArray(Vn);ch='';while('y'!=ch&&'n'!=ch)Iif('\n"!=ch)Iprintf("輸入正確確認?(y/n):");)scanf("%c”,&ch);)if('n'=ch)(printf("錄入錯誤重新輸入!'n");inErr=1;)eIse[inErr=0;/?輸入終結(jié)符?/voidInputVt()(intinErr=1;intn,k;charch;while(inErr)(printf("\n請輸入所有的終結(jié)符,注意:")；printf("以#號結(jié)束:、n");ch='';n=0：/?初始化數(shù)組?/whiIe(n<MaxVtNum)(Vt[n++]='\0';)n=0：while(C#'!=ch)&&(n<MaxVtNum))(ifC'!=ch&&'\n'!=ch&&-1=IndexCh(ch))(Vt[n++]=ch;vtNum++;)ch=getchar();)Vt[n]= ;/?以u#n標志結(jié)束?/k=n;/*k用于記錄n以便改Vt[n]='、0'*/if('#'!=ch)(if('#'!=(ch=getchar()))(whileC#'!=(ch=getchar()))printf(''、n符號數(shù)目超過限制!、n");inErr=1;continue;))/*正確性確認,正確則,執(zhí)行下下面,否則重新輸入*/Vt[k]='、〇';ShowChArray(Vt);chゴ’；whileCy'!=ch&&'n'!=ch)(if('\n'!=ch)(printf("輸入正確確認?(y/n):");}scanfぐ’％c",&ch);}ifCn*=ch)(printf("錄入錯誤重新輸入!'n〃)；inErr=1;1eIse(inErr=0;}}1/?產(chǎn)生式輸入?/voidInputPO(charch;inti=0,n,num;printf(“請輸入文法產(chǎn)生式的個數(shù):")；scanf("%d",&num);PNum=num;getchar();/?消除回車符*/printf("\n請輸入文法的%d個產(chǎn)生式,并以回車分隔每個產(chǎn)生式:“，num);printf("\n");whiIe(iくnum)(printf("第%d個:“，i);/?初始化?/for(n=0;n<MaxPLength;n++)buffer[n]二‘、。';/?輸入產(chǎn)生式串?/ch二',;n二。;while,'n'!=(ch二getchar())&&n<MaxPLength)(if(''!=ch)buffer[n++]二ch;)buffer[n]二，'〇';/*printf("%s",buffer);*/if(CheckP(buffer))(/?填寫入產(chǎn)生式結(jié)構(gòu)體?/pRNode*pt,*qt;P[i].ICursor二|ndexCh(buffer[0]);pt=(pRNode*)maIloc(sizeof(pRNode));pt->rCursor=IndexCh(buffer[3]);pt->next=NULL;P[i].rHead=pt;n=4;while(‘、〇’!=buffer[n])Iqt=(pRNode*)maIIoc(sizeof(pRNode));qt->rCursor=IndexCh(buffer[n]);qt->next=NULL;pt->next=qt;pt=qt;n++;}P[i].rLength=n-3;i++；/?調(diào)試時使用?/)eIseprintf(〃輸入符號含非法在成分,請重新輸入!、バ)；})/?判斷產(chǎn)生式正確性?/booICheckP(char*st)(intn;if(100>IndexCh(st[0]))returnfalse;ifCコ!=stロ])returnfalse;ifO'!=st[2])returnfalse;for(n=3;'、〇'!=st[n];n++)(if(-1==IndexCh(st[n]))returnfalse;)returntrue;)/*=========ニニ=first&f〇||ow二======ニニニニニ二=ニニ*//?計算fjrst集,U->xx...*/voidFirst(intU)inti,j;for(i=0;i<PNum;i++)(if(P[i].ICursor=U)(structpRNode*pt;pt=P[i].rHead;j=0；while(j<P[i].rLength)(if(100>pt->rCursor)(/?注:此處因編程出錯,使空產(chǎn)生式時rlength同樣是!,故此處同樣可處理空產(chǎn)生式?/AddFirst(U,pt->rCursor);break;)eIse(if(NULL=first[pt->rCursor-100])(First(pt->rCursor);)AddFirst(U,pt->rCursor);if(!HaveEmpty(pt->rCursor))(break;)eIse(pt=pt->next;))j++；)if(j>=P[i].rLength)/?當產(chǎn)生式右部都能推出空時?/AddFirst(U,-1);/?加入first集?/voidAddFirst(intU,intnCh)/?當數(shù)值小于100時nCh為Vt*//?當處理非終結(jié)符時,AddFirst不添加空項(-1)*/structcolIectNode*pt,*qt;intch;/?用于處理Vn*/pt=NULL;qt=NULL;if(nCh<100)(pt=first[U-100];whiIe(NULL!=pt)(if(pt->nVt==nCh)break;eIse(qt=pt;pt=pt->next;})if(NULL=pt)(pt=(structcollectNode*)maIIoc(sizeof(structcolIectNode));pt->nVt=nCh;pt->next=NULL;if(NULL=first[U-100])(first[U-100]=pt;}eIse(qt->next=pt;/*qt指向first集的最后ー個元素?/)pt=pt->next;eIse(pt=first[nCh-100];while(NULL!=pt)(ch=pt->nVt;if(-1!=ch)[AddFirst(U,ch);pt=pt->next;)/?判斷first集中是否有空(T)*/booIHaveEmpty(intnVn)(if(nVn<100)/?為終結(jié)符時(含ー1),在follow集中用到?/returnfalse;structcolIectNode*pt;pt=first[nVn-100];whiIe(NULL!=pt)(if(-1==pt->nVt)returntrue;pt=pt->next;)returnfalse;I/?計算follow集,例:U->xVy,U->xV.(注:初始符必含#——"-1")*/voidFollow(intV){inti;structpRNode*pt;if(100=V)/?當為初始符時?/AddFollow(V,-1,0);for(i=0;i<PNum;i++)(pt=P[i].rHead;while(NULL!=pt&&pt->rCursor!=V)/?注此不能處理:Uー〉xVyVz的情況?/pt=pt->next;if(NULL!=pt)(pt=pt->next;/*V右側(cè)的符號?/if(NULL=pt)/*當V后為空時Vー〉xV,將左符的follow集并入V的follow集中?/(if(NULL=follow[P[i].ICursor-100]&&P[i].ICursor!=V)(Follow(P[i].ICursor);}AddFoIIow(V,P[i].ICursor,0);)else/?不為空時Vー〉xVy,(注意:y-??調(diào)用AddFollow加入Vt或y的first集?/(while(NULL!=pt&&HaveEmpty(pt->rCursor))AddFollow(V,pt->rCursor,1)：/*y的前綴中有空時,加如first集?/pt=pt->next;}if(NULL=pt)/?當后面的字符可以推出空時?/(if(NULL=follow[P[i].ICursor-100]&&P[i],ICursor!=V)(Follow(P[i].ICursor);)AddFoIIow(V,P[i].ICursor,0);}else/?發(fā)現(xiàn)不為空的字符時?/(AddFollow(V,pt->rCursor,1);))))}/?當數(shù)值小于100時nCh為Vt*//*#用T表示,kind用于區(qū)分是并入符號的first集,還是follow集kind=〇表加入follow集,kind=1加入first集?/voidAddFollow(intV,intnCh,intkind)(structcoIIectNode*pt,*qt;intch;/?用于處理Vn*/pt=NULL;qt=NULL;if(nCh<100)/?為終結(jié)符時?/Ipt=follow[V-100];while(NULL!=pt)(if(pt->nVt==nCh)break;eIse(qt=pt;pt=pt->next;}Iif(NULL=pt)pt=(structcolIectNode*)ma11oc(sizeof(structcolIectNode));pt->nVt=nCh;pt->next=NULL;if(NULL=follow[V-100])(follow[V-100]=pt;}eIseIqt->next=pt;/*qt指向follow集的最后ー個元素?/}pt=ptー〉next;))else/?為非終結(jié)符時,要區(qū)分是加first還是follow*/Iif(0=kind)(pt=follow[nCh-100]：whiIe(NULL!=pt)(ch=pt->nVt;AddFollow(V,ch,0);pt=pt->next;))eIse(pt=first[nCh-100];whiIe(NULL!=pt)(ch=pt->nVt;if(-1!=ch)(AddFoIIow(V,ch,1);)pt=pt->next;)/?輸出first或follow集?/voidShowCo11ect(structcolIectNode**coIIect)structcolIectNode*pt;i=0；while(NULL!=collect[i])(pt=coIIect[i];printf("\n%c:\t",Vn[i]);whiIe(NULL!=pt)(if(-1!=pt->nVt)[printf("紀”,Vt[pt->nVt]);)eIseprintf("#");pt=pt->next;)i++；}printf("\n");)/?計算first和f011ow*/voidFirstFollow()(inti;i=0；whileC\0'!=Vn[i])(if(NULL=first[i])First(100+i);i++；]i=0;whileC\0'!=Vn[i])(if(NULL=follow[i])Follow(100+i);i++;}}/*==== ===構(gòu)造預測分析表,例:U::xyz */voidCreateAT()(inti;structpRNode*pt;structcolIectNode*ct;for(i=0;i<PNum;i++)pt=P[i].rHead;whiIe(NULL!=pt&&HaveEmpty(pt->rCursor))(/?處理非終結(jié)符,當為終結(jié)符時,定含空為假跳出?/ct=first[pt->rCursor-100];whiIe(NULL!=ct)[if(-1!=ct->nVt)analyseTable[P[i],(Cursor-100][ct->nVt]=i;ct=ct->next;}pt=pt->next;)if(NULL=pt)(/*NULL=pt,說明xyz->,用到follow中的符號?/ct=follow[P[i].ICursor-100];whiIe(NULL!=ct)(if(-1!=ct->nVt)analyseTable[P[i],ICursor-100][ct->nVt]=i;else/?當含有#號時?/analyseTable[P[i],ICursor-100][vtNum]=i;ct=ct->next：))eIse(if(100<=pt->rCursor)/?不含空的非終結(jié)符?/(ct=first[pt->rCursor-100];whiIe(NULL!=ct)(analyseTable[P[i].ICursor-100][ct->nVt]=i;ct-ct->next;))else/?終結(jié)符或者空?/Iif(-1=pt->rCursor)/*-1為空產(chǎn)生式時?/ct=follow[P[i],ICursor-100];whiIe(NULL!=ct)(if(-1!=ct->nVt)analyseTable[P[i].ICursor-100][ct->nVt]=i;else/?當含有#號時?/analyseTable[P[i].ICursor-100][vtNum]=i;ct=ct->next;))else/?為終結(jié)符?/(analyseTable[P[i].ICursor-100][pt->rCursor]=i;)))))/*輸出分析表?/voidShowAT()(inti,j;printf("構(gòu)造預測分析表如下:'n");printf("\t|Vt");for(i=0;i<vtNum;i++)(printf("%c\t”,Vt[i]);1printf("#\t\n");printf \t| \t");for(i=0;i<=vtNum;i++)printfぐ’ \t");printf("\n");for(i=0;i<vnNum;i++)(printf("%c\tI\t",Vn[i]);for(j=0;j<=vtNum;j++)(if(-1!=analyseTable[i][j])printf("R(%d)\t",analyseTable[i][j]);elseprintf("error、ピ);)printf("\n");))/*============主控程序=============*/voidIdentify(char*st)(intcurrent,step,r;/*r表使用的產(chǎn)生式的序號?/printf("\n%s的分析過程:、n”,st);printf("步驟ゝt分析符號棧、t當前指示字符、t使用產(chǎn)生式序號、n");step=0;current=0;/?符號串指示器?/printf("%d\t”,step);ShowStack();printf(z/\t\t%c\t\t \n”,st[current]);while。#'!=st[current])(if(100>anaIyseStack[topAnaIyse])/?當為終結(jié)符時?/(if(anaIyseStack[topAnaIyse]=IndexCh(st[current]))(/?匹配出棧,指示器后移?/Pop0;current++;step++;printf("%d\t”,step);ShowStack();printf("\t\t%c\t\t出棧、后移、n〃,st[current]);eIse(printf("%c-%c不匹配!”，anaIyseStack[topAnaIyse],st[current]);printf(〃此串不是此文法的句子!'n");return;11else/?當為非終結(jié)符時?/(r=anaIyseTabIe[anaIyseStack[topAnaIyse]-100][IndexCh(st[current])];if(-1!=r)(Push(r);/?產(chǎn)生式右部代替左部,指示器不移動?/step++;printf("%d\t",step);ShowStack();printf(，，\t\t%c\t\t%d\n，，1st[current],r)：1else(printf("無可用產(chǎn)生式,此串不是此文法的句子!'n");return;)))if('#'==st[current])(if(O==topAnaIyse&&'#'=st[current])(step++;printfぐ‘％d\t”,step);ShowStack();printf("\t\t%c\t\t分析成功!\n”,st[current]);printf("%s是給定文法的句子!'n”,st);eIse{while(topAnaIyse>0){if(100>anaIyseStack[topAnaIyse])/?當為終結(jié)符時?/{ printf(“無可用產(chǎn)生式,此串不是此文法的句子!'n〃)；return;1eIse{r=anaIyseTabIe[anaIyseStack[topAnaIyse]-100][vtNum];if(-1!=r){Push(r);/?產(chǎn)生式右部代替左部,指示器不移動?/step++;printf("%d't",step);ShowStack();if(0==topAnaIyse&&'#'=st[current]){printf("'t't%c't't分析成功!'n”,st[current]);printf("%s是給定文法的句子!'n”,st);)eIseprintf("\t\t%c\t\t%d\n",st[current],r); }eIse{printf(〃無可用產(chǎn)生式,此串不是此文法的句子!'n");return;}1)))/*初始化棧及符號串?/voidInitStack()Iinti;/?分析棧的初始化?/for(i=0;i<MaxStLength;i++)st[i]=[0,；analyseStack[O]=-1;/*#(-1)入棧*/analyseStack[1]=100;/?初始符入棧*/topAnaIyse=1;)/?顯示符號棧中內(nèi)容*/voidShowStack(){inti;for(i=0;i<=topAnaIyse;i++){if(100<=analyseStack[i])printf(，z%cz，,Vn[anaIyseStack[i]-100]);eIse{if(-1!=anaIyseStack[i])printf(/z%czz,Vt[anaIyseStack[i]]);elseprintf(/z#zz);11)/?棧頂出棧*/voidPop(){topAnaIyse—;1/?使用產(chǎn)生式入棧操作?/voidPush(intr){inti;structpRNode*pt;Pop()；pt=P[r].rHead;if(-1==pt->rCursor)/?為空產(chǎn)生式時?/return;topAnaIyse+=P[r].rLength;for(i=0;i<P[r].rLength;i++){/?不為空產(chǎn)生式時?/anaIyseStack[topAnaIyse-i]=ptー〉rCursor;/?逆序入棧*/pt-pt->next;レ?循環(huán)未完時pt為空,則說明rLength記錄等出錯?/四.實驗結(jié)果請輛人所有的非終結(jié)符,汪怠:請將開始存放在弟一包,幵以4號結(jié)兎:SHMAttSHNA輸入正確確認?<y/n>：V輸入正確確認?<y/n>：y請輸入所有的終結(jié)符,注意:以苗號結(jié)束:adbe輸入正破確認?(y/n):y看輸入受法產(chǎn)生式的個數(shù)」?jié)n輸入文法的7個產(chǎn)生式，并以回車分隔每個產(chǎn)生式:第0個:S->aH第1個:H->aMd第2個:H->d第3個:M->Ab第4個:M->第5個:A->aM第6個:A->e所得￡i?st集為:所得fol103集為:adbeItSR<0>errorerrorerrorerrorR<1>R<2>errorerrorerrorMR<3>R<4>R<4>R<3>errorAR<5>errorerrorR<6>errory■■是構(gòu)造預測分析表如下:SHMA請輸入符號串（以?結(jié)束）:■N的，分析過程,步彝 分析符號棧 當前指示字符 使用產(chǎn)生式序號無可用產(chǎn)生式,此串不是此文法的句子!是否繼續(xù)進行句型分析?<y/n>：<y/n>?V<y/n>?<y/n>?y請輸入符號串（以?結(jié)束）:aaabdttaaabd*的分;步驟則..棧程號過符當前指示字符使用產(chǎn)生式序號。 USa——1 UHca02 MHa出棧、后移3 ItdMaa14 ttdh1a出棧、后移5 ttdbAa36 ttdbMaa57 ttdbMb出棧、后移8 Vdl)b4dユ0 nA中氯易物UabdJt是ム定文法的句子!n分柝戰(zhàn)功!是否繼續(xù)進行句型分析?<y/n>：五.實驗總結(jié)通過這次的實驗,我深入了解了詞法分析器和LL（1）文法預測分析法設計和實現(xiàn),增強了我的自學能力和獨立思考能力,也讓我對程序設計有了更大的興趣,自己通過查找資料、復習課本、編程調(diào)試，寫實驗報告等環(huán)節(jié),進ー步掌握了以前學到的知識，并且還對編譯原理應用有了更深入的認識與掌握。在完成這個程序后，真的很開心，也了使我解到編譯原理的魅カ所在，激發(fā)了我要解決更多更難問題的決心。實驗ーLR分析器設計與實現(xiàn)第一章概述本課程設計完成了以下內(nèi)容:.實現(xiàn)了對任意給定的文法G,識別文法活前綴的OE4、。必的狀態(tài)轉(zhuǎn)化矩陣及ムマ(0)項目集規(guī)范族的構(gòu)造;.判斷該文法是否為厶Z?(0)文法,實現(xiàn)了以?(0)分析表的構(gòu)造,并輸出到指定文件中;.實現(xiàn)了厶/?(0)分析器總控程序,對輸入的表達式進行文法分析。第二章 設計的基本原理本課程設計的核心算法”主要有三點:L識別文法活前綴的OFA、。必的狀態(tài)轉(zhuǎn)化矩陣及ムR(0)項目集規(guī)范族的構(gòu)造;2.厶/?(0)分析表的構(gòu)造;3.厶7?(0)分析器總控程序的構(gòu)造。識別文法的LR(O)項目集規(guī)范族的構(gòu)造采用e-QLOSURE(閉包)的構(gòu)造ー個文法G的ムZ?(0)項目規(guī)范簇。假定，是文法G，的任一項目集,定義和構(gòu)造，的閉包。厶。SURE")的算法:/的任何項目都屬于CLOSURE^)；(2)若A-aB0屬于CLOSURE⑴,那么,對任何關于5的產(chǎn)生式8fア,項目8fア也屬于CLOSURE(I)；(3)重復執(zhí)行上述兩個步驟直至CLOSURE^)不再增大。其中初始，={S，fE},5，為對文法G進行拓廣構(gòu)造G,而引進的不出現(xiàn)在G中的非終結(jié)符。定義狀態(tài)轉(zhuǎn)換函數(shù)GO,GO(/,X)的第一個變元/是一個項目集,第二個變元X是ー個文法符號。函數(shù)值GO(/,X)定義為GOa,X)=CLOSURE(1/)。其中J={任何形如AfaXタ的項目丨AraXタ屬于/}LR(O)分析表的構(gòu)造假定C={/°,ム,…/“}。令每個項目集ム的下標作為分析器的狀態(tài)。特別是,令那個包含項目S->S的集合人的下標k為分析器的初態(tài)。分析表的AC77ON子表和GOT。子表可按如下方法構(gòu)造:(1)若項目Afa。タ屬于ム且GO(4，a)=/,，a為終結(jié)符,則置ACTIONlk?為“把(j,a)移近?！?簡記為“5ノ”。(2)若項目Afa屬于/*,那么對于任何終結(jié)符a(或結(jié)束符#),置AC77ON伙,a］為“用產(chǎn)生式Afタ進行規(guī)約”,簡記為“ゲ(假定產(chǎn)生式Afa是文法G"的第j個產(chǎn)生式)⑶若項目SIS屬于/*,則置AC77ON伙,a］為“接受”,簡記為“acc”。(4)若GO(/*,A)=ム,則置ACTION伙,A］=j.(5)分析表中凡不能用規(guī)則1?4填入信息的空白處均置上“報錯標志”。如果分析表中任何ー項被重復填入，則說明分析表的入口不是唯一的,項目集中存在沖突項目，該文法不是厶R(0)文法。LR(O)分析器總控程序構(gòu)造ムR(0)分析表包括量部分，“動作”AC77ON表和“狀態(tài)轉(zhuǎn)換”GOTO表。ん。7y。y中,0規(guī)定了當狀態(tài)5面臨輸入符號。時應采取什么動作。GOTO［s,X］規(guī)定了狀態(tài)s面對文法符號X時下ー狀態(tài)是什么。每ー項ACTION［s,a］所規(guī)定的動作不外乎是下述四種可能之ー。(1)移進把(s,a)的下一狀態(tài)s，=GOTQs,X］和輸入符號。推進棧,下ー輸入符號變成現(xiàn)行輸入符號。(2)歸約指用某ー產(chǎn)生式A-タ進行規(guī)約。假若月的長度為「,規(guī)約的動作是,去除棧頂?shù)膔個項,使狀態(tài)s,?變成棧頂狀態(tài),然后把0-4)的下ー狀態(tài)『=GOTO［s吁八川推進棧。規(guī)約動作不改變現(xiàn)行輸入符號。規(guī)約動作不改變現(xiàn)行輸入符號。(3)接受宣布分析成功,停止分析器工作(4)報錯發(fā)現(xiàn)源程序含有錯誤,調(diào)用出錯處理程序。第三章 程序設計程序總體構(gòu)架本課程設計開發(fā)的程序主要由4張表組成,分別為:符號表Sig〃一List、產(chǎn)生式表Formula_List>L/?(0)表LRO_Table和項目集規(guī)范簇表Closure_List〇同時,項目集規(guī)范簇表包含ー個分析棧作為ムZ?(0)分析器總控程序。產(chǎn)生式表包含符號表作為子表,項目集規(guī)范簇表包含產(chǎn)生式表、ZJ?(O)表作為子表。程序工作流程:.讀取含有文法規(guī)則的文件，為該文法中的每一個不同的文法符號(終結(jié)符和非終結(jié)符分配ー個編號),記錄文法符號的屬性(終結(jié)符/非終結(jié)符)，存儲于ー,張符號表Sign_List中;.再次讀取文件,將產(chǎn)生式存儲于產(chǎn)生式表ド。/厶ぶ中;.根據(jù)產(chǎn)生式構(gòu)建厶Z?(0)項目集規(guī)范族,存儲于表Closure_List中;.根據(jù)構(gòu)建的ン?(0)項目集規(guī)范族構(gòu)建厶/?(0)分析表,填寫厶/?(0)分析表同時檢查該文法是否為厶Z?(0)文法;.對于輸入的表達式，レ?(0)分析器根據(jù)構(gòu)建的n?(0)分析表進行文法分析,給出分析結(jié)果。

程序存儲結(jié)構(gòu)符號表存儲結(jié)構(gòu)Ararry_Index動態(tài)數(shù)組下標,同時作為符號的編號Identity標識符Is_Vn是否為非終結(jié)符產(chǎn)生式表存儲結(jié)構(gòu)Formula_Num產(chǎn)生式標號Vn_Name非終結(jié)符標號（與Sign_Lisi中的Ararry_Index一致）Formula指示當前非終結(jié)符V〃ーName的產(chǎn)生式Formula_Length當前非終結(jié)符い〃ーName產(chǎn)生式的長度,用于幫助區(qū)分一個產(chǎn)生式的不同項目,即項目個數(shù)等于Formula_Length+1Next_Vn指示下ー個非終結(jié)符Sign_Name一個產(chǎn)生式中的標識符名（與Sign_List中的Ararry_Index一致）Next_Signー個產(chǎn)生式中的下ー個標識符1)定義二兀組:Item_Name_Type=<Formula_Num,Formula_Item>Formula_Num:產(chǎn)生式標號,與Formula一List中的Formula_Num一致Formula_Item:ー個產(chǎn)生式的第,個項目,可由Z7。ケ%か。_Lis/中的Formula_Length幫助確定如:產(chǎn)生式Wー>E：W->E<1,1>,W->E<1,2>Closure_List結(jié)構(gòu):Current_State當前狀態(tài)編號Next_State指示下一狀態(tài)Item指示閉包中的項目Item_Name閉包中的項目名Destination當前項目的GotoSet產(chǎn)生的新狀態(tài)的編號,即狀態(tài)轉(zhuǎn)移的目的地狀態(tài)編號Next_Item閉包中的下ー個項目GoToSet_Parent待構(gòu)造的GoTo項目的閉包的ParentGoToSet_Child待構(gòu)造的GoTo項目的閉包Current_Parent待構(gòu)造狀態(tài)的ParentCurrent_Child待構(gòu)造狀態(tài)的項目LRQ_Table_Child指示表頭的孩子結(jié)點LRO_Table_Parent指示表頭的后繼結(jié)點Operation指示該表項的操作Oprand指示該表項的操作數(shù)Has_Been_Filled指示該表項是否被填寫過,用于判斷文法是否為レ?(0)文法3.3程序算法3.1項目集規(guī)范族的構(gòu)造(初始化)將初始條件作為該狀態(tài)頭結(jié)點的第一個孩子結(jié)點,并構(gòu)造該孩子結(jié)點的閉包,連接其后,GoToSejPare〃，指向第一個狀態(tài)頭結(jié)點,GoToSet_Child指向第一個狀態(tài)頭結(jié)點的第一個孩子結(jié)點;查看GoToSet_Parent,若為空,停止;若不為空,轉(zhuǎn)3；查看GoToSet_Child,若為空，轉(zhuǎn)4；若不為空,構(gòu)造GoToSef_C/n/"的GoToSet,檢査該狀態(tài)與之前構(gòu)造的狀態(tài)有無重復,若重復,則停止構(gòu)造,GoToSerー。J〃イ的。esガ〃両沁〃填寫重復的已存在的狀態(tài)的編號；若不重復,則作為ー個新狀態(tài),連接于arre〃f_Pare而，并構(gòu)造其閉包連接其后，GoToSet_Child指向Next_State。轉(zhuǎn)2；GoToSet_Pare〃，指向下ー狀態(tài),若下一狀態(tài)為空,則結(jié)束,否則,GoToSet_Child指向下ー狀態(tài)頭結(jié)點的第一個孩子結(jié)點,轉(zhuǎn)3〇具體細節(jié):設GoToSer_C7n7d所指項目為<，">,因為要對其構(gòu)造閉包,該項目一定不是終態(tài)，所以區(qū)分項目的圓點符號位于第，個標識符的左側(cè)?，F(xiàn)在構(gòu)造<"/>的閉包,分兩個步驟實現(xiàn):.構(gòu)造GoToSet_Child的GoToSet：查看Formula_Length中編號為i的產(chǎn)生式，取得該產(chǎn)生式的長度屬性Formula_Length若j之Formula_Length+1,則停止構(gòu)造當前閉包（已是終態(tài)）,此時GoToSet_Child的Destination項填ー1;2）否則,將+ 作為該閉包的第一個項目設機,此時GoToSejCが，d的Destination項填該新狀態(tài)的狀態(tài)編號。.構(gòu)造該孩子結(jié)點的閉包:查看Formula_List中編號為i的產(chǎn)生式的第，+1個標識符,取得該標識符的Sign_Name,查看Sign_Lisi中該標識符的類別屬性/3）若為1（非終結(jié)符）,則查看ドorm”ルーLisf非終結(jié)符Sig”的所有產(chǎn)生式,記這些產(chǎn)生式的編號為Sig〃.,將所有的<Sign_Name_i,1>加入閉包4）否則,結(jié)束.檢查該狀態(tài)與之前構(gòu)造的狀態(tài)有無重復:斷言:任意兩個狀態(tài),只要G%5々不同,則即為不同狀態(tài)。3.3.2LR（O）分析表構(gòu)造對于編號為，?的狀態(tài),現(xiàn)依據(jù)其項目＜「國〉填寫ン?（0）分析表:.如果該項目形如Xf…丫…,查看該項目的Destination屬性,k=Destinationi）若丫為終結(jié)符,則在表的狀態(tài)，對應行,對應列,填寫s*,表示將把伏,わ移進棧2）若y為非終結(jié)符,則在表的狀態(tài)i對應行,’「對應列，填寫ス,表示狀態(tài)轉(zhuǎn)移至え狀態(tài).如果該項目形如xfy1）若ド為起始符號,則置在表的狀態(tài)i對應行,#對應列,填寫acc,表示接受。2）否則,對任何終結(jié)符或結(jié)束符#,則在表的狀態(tài)i對應行,’「對應列,填寫（,表示用產(chǎn)生式p進行規(guī)約。第四章程序測試以文法G為例:W-￡E^aAElbBAfcAAfdBtcBBid程序模塊輸入:含上述文法的文件,下面展示個模塊的輸出結(jié)果1符號表測試continue11010100k01234567ooooooooNNNNNNNNPcontinue11010100k01234567ooooooooNNNNNNNNP輸出F-3KWJZr4-H3443(=1圖6符號表測試與預期結(jié)果相同產(chǎn)生式表測試drC：\VmOYS\systea32\cad.exe|e<w>ー）!《e〉1<E>->2<a>3<A>1<E>>>4<b>5<B>3<A>->6<c>3<A>□<A>->7<d>5<B>->6<c>5<B>5<B>->7<d>?i*essanykeytocontinue...圖7產(chǎn)生式表測試輸出結(jié)果與讀入的文件中的產(chǎn)生式相同,且產(chǎn)生式中符號的編號正確項目集規(guī)范族表測試 e01r012345678911P?>yeXZ1KZVZ10H11__k! e01r012345678911P?>yeXZ1KZVZ10H11__k!14711-11-，，**********33y1222322322，,n**********46a1123245367くく<<<<<<<<<<s::s<4,1,5>,く<4,1,5>く6,1，8>.tocont

輸出結(jié)果為く狀態(tài)編號〉:く產(chǎn)生式編號,產(chǎn)生式項目編號,項目轉(zhuǎn)移的目標狀態(tài)〉與預期結(jié)果相同LR(0)分析表測試,|D|x|state計010020

ard006926539746ssrsrrsrrrC005825538746ssrsrrsrrrB0001

0001000

gb300020530746srrrrrr0

A004001000000

state計010020

ard006926539746ssrsrrsrrrC005825538746ssrsrrsrrrB0001

0001000

gb300020530746srrrrrr0

A004001000000

9gtoa200020530746

s1*rrrrrynsse0000000000r圖9レ?(0)分析表測試輸出結(jié)果為厶/?(0)分析表,與預期結(jié)果相同LR(O)分析器測試以輸入字符串a(chǎn)cccd#和acad#為例|caC：\fIID0fS\syste?32\cad.exeLccdttNoerrorfoundacadtterrorat3pressanykeytocontinue.表達式的分析結(jié)果正確第五章 總結(jié)和展望完成了編譯原理課程設計之后,我感到十分的疲憊,但是那ー份富有成就感的欣喜卻勝過了那十分的疲憊。由于本次選題匆忙,選了一道比較有難度的題目,在做課程設計的過程中,我翻閱了很多相關資料,對課本中點到即止的知識進行了更加深入的學習,有了更加深入的理解。做課程設計的過程是痛苦的,我在這ー個星期內(nèi)多次熬夜戰(zhàn)斗,有時甚至顧不上吃飯,只為了揪出程序中的錯誤,只為了精益求精的完成這個課程設計。就在我寫這份總結(jié)的時候,我發(fā)現(xiàn)自己我ー點也不累了,反而很興奮,很有成就感。通過本次課程設計，我發(fā)現(xiàn)實踐是檢驗學習深度、學習成果的唯一途徑，課本上的知識點都是濃縮的精華,在理論闡述上不可能做到面面俱到,學到的知識當然也不可能直接運用到實際情況上。在實踐的過程中,我們需要將我們學習到的知識進行ー定程度的擴充,本次課程設計涉及到算法,LR分析器自動構(gòu)造程序的機制原理以及C++語言。在用C++語言實現(xiàn)本次課程設計的過程中,我更加熟悉了C++語言的語法機制，語言規(guī)范;在實現(xiàn)LR分析器自動構(gòu)造程序的過程中,我更加熟悉了其構(gòu)造程序的原理以及與之相關的算法。由于時間匆忙,我完成的課程設計還有很多不足之處,很多工作還可以繼續(xù)完善，在提交作業(yè)之后,我不會把它放在那里一看不看的,我會繼續(xù)完善它,讓它更加人性化,具有可操作性,比如做個可視化的界面出來,豐富它的功能,相信以后的工作將更加多彩豐富,更加有成就感!參考文獻[1]陳火旺,劉春林,譚慶平,趙克佳,劉越程序設計語言編譯原理國防エ業(yè)出版社2006[2]譚浩強C++程序設計清華大學出版社2007附錄說明:本附錄中包含了本次課程設計的所有代碼ClosureList.h#ifndefCLOSURE_LIST_HttdefineCLOSURE，IST_H#include"FormulaList,h”#include"LR0_Table.h"structItem_Name_Type{intFormula_Num;intFormula_Item;};structClosure_ChiIdNode(Item_Name_TypeItemName;intDestination;Closure_Child_Node*Next」tem;};structClosure_Parent_Node(intCurrent_State;C1osure_Parent_Node*Next_State;C1osure_Chi1d_Node*Item;};classClosureListprivate:C1osure_Parent_Node*Closure_List_head;Closure_Parent_Node*GoToSet_Parent;ClosureParentNode*CurrentParent;Closure_Child_Node*GoToSet_ChiId;ClosureChildNode*Current_Child;intAmountOfState;Formula_Listsub_Formula_List;LROTablesubLROTable;public:ClosureList():subFormulaList(),subLROTable()(Closure_List_head=NULL;GoToSetParent=NULL;Current_Parent=NULL;GoToSetChild=NULL;Current_Child=NULL;AmountOf_State=0;Create_Closure_List(););、Closure_List();voidprint_Closure_List();voidmake_LR0_Table();voidprintLROTable();voidOutput_LRO_Table_ToFile();boolSentence_Analyse(constcharSentence[50]);private:voidAdd_Clousure();boolAddGoToSet();voidSet_Initial_State();voidCreate_Closure_Ust();boolIs_Same_State_Exist(constintFormula_Num,constintFormula」tem,int&Same_State_Num);voidDestroy_Closure_List();};#endifFormula_List.h#ifndefFORMULALISTII^defineFORMULA，IST_H#include*Sign_List.h*structFormulaListChilditem(intSignName;Formu1a_List_Childltem*Next_Sign;)；structFormulaListParentitem(intFormulaNum;intVn_Name;intFormulaLength;Formu1a_List_Parentitem*Next_Vn;FormulaListChilditem*Formula;}；classFormula_List{private;Formu1a_List_Parentltem*Formu1a_List_head;Formula_List_ChiIdltern*current_Formula_Itern;Formula_List_ParentItem*current_VnNode;Sign_ListSub_Sign_List;public:Formula_List():Sub_Sign_List()(Formu1a_List_head=NULL;current_Formula_Item=NULL;current_VnNode=NULL;Create_Formula_Ust(););Formula_List();voidprint_Formula_List();intint_checkSignName(constcharword);charchar_check_Sign_Name(constintSign_Name);intGetFormulaLength(constintFormulaNum);intGet_Sign_Name(constintFormula_Num,constintItem_Num);intGetFormulaLeftVn(constintFormulaNum);boolIs_Sign_Name_Vn(constintSignName);intGetAmountOf_Identity();private:voidDestroy_Formula_List();voidCreateFormulaList0;｝；ttendifLR0_Table.h#ifndefLROTABLE_H^defineLRO_TABLE_H#include<iostream>#include<fstream>usingnamespacestd;^include"ConstValue.h"structLRO_Table_Child(charOperation;intOprand;boolHas_Been_Filled;LRO_Table_ChiId*Next_Table_ChiId;｝；structLR0_Tab1e_Parent(LRO_Table_Child*Table_Child;.RO_Table_Parent*Next_Tab1e_Parent;｝；classLR0_Tableprivate:LROTableParent*LROTablehead;LRO_Table_Parent*Current_Parent;LROTableChild*CurrentChild;public:LROTable0;"LRO_Table();voidinitial(constintAmountOfState,constintAmountOfIdentity);boolFill_In_Table(constintState_Num,constintIdentity_Num,constcharcharOpration,constintintOprand);void_OutputToFile();voidprintLROTableO;voidVisit_LRO_Tab1e(constintState_Num,constintIdentity_Num,char&charOpration,int&intOprand);private:voidDe