基于LR1的語法分析程序報告

/基于LR<1>的語法分析程序1.設(shè)計目的：設(shè)計、編制和調(diào)試一個典型的LR<1>分析器,進(jìn)一步掌握LR<1>語法分析方法,掌握用預(yù)測分析方法分析LR<1>文法的具體過程,加深對LR<1>文法和預(yù)測分析方法的理解。2.設(shè)計要求：根據(jù)LR<1>分析法編寫一個語法分析程序,.輸入已給定文法,直接輸入根據(jù)己知文法構(gòu)造的LR<1>分析表。對于輸入的符號串,所編制的語法分析程序應(yīng)能正確判斷此串是否為文法的句子,并要求輸出分析過程。3.設(shè)計過程：3.1LR<1>文法的含義：LR分析法的規(guī)約過程是規(guī)范推倒的逆過程,所以LR分析過程是一種規(guī)范規(guī)約的逆過程,L表示從左到右掃描輸入串,R表示最左規(guī)約〔即最右推導(dǎo)的逆過程,括號中的1表示向右查看輸入符號數(shù)為1。LR〔1項(xiàng)目可以看成兩個部分組成,一部分和LR〔0項(xiàng)目相同,這部分成為心,另一部分為向前搜索符集合。所以只有當(dāng)面臨的輸入符屬于向前搜索符的集合,才做規(guī)約動作,其他情況均出錯。LR〔1方法恰好解決SLR〔1方法在某些情況下存在的無效規(guī)約問題。3.2設(shè)計思想：根據(jù)自身實(shí)際情況,給定了編譯原理書中的一個LR<1>文法,求出其項(xiàng)目集合轉(zhuǎn)換函數(shù),從而得出此LR<1>文法的分析表,在程序中直接輸出此分析表,并根據(jù)分析表中的內(nèi)容可對輸入的符號串進(jìn)行分析,判斷是接受還是出錯,從而得出該輸入的符號串是否為文法的一個句子。3.3算法描述：1.CLOSURE<I>的構(gòu)造CLOSURE<I>表示和I中項(xiàng)目可以識別同樣活前綴的所有項(xiàng)目的集合。它可以有以下方法得到：<1>I中的所有項(xiàng)目都屬于CLOSURE<I>；<2>若項(xiàng)目[A→a.Bβ,a]屬于CLOSURE<I>,B→ξ是一個產(chǎn)生式,那么,對于FIRST<βa>中的每一個中介符b,如果[β→.ξ,b]原來不在CLOSURE<I>中,則把它加進(jìn)去；<3>重復(fù)執(zhí)行步驟〔2,直到CLOSURE<I>不再增大為止。2.GO<I,X>的構(gòu)造GO<I,X>=CLOSURE<J>其中J={任何形如[A→aX.Β,a]的項(xiàng)目[A→a.X.Β,a]屬于I}3.FIRST集合的構(gòu)造在這個程序中使用的是FIRST<βa>,這基于每一個非終結(jié)符的FRIST集合〔終結(jié)符的FIRST就是它本身。所以需要對每一個非終結(jié)符構(gòu)造其FIRST集合。方法如下：連續(xù)使用下面的規(guī)則,直到每個集合FIRST不再增大為止。若X屬于VT,則FIRST<X>={X}?！?若X屬于VN,且有產(chǎn)生式X→a…,則把A加入到FIRST<X>中；若X→ξ也是一條產(chǎn)生式,則把ξ也加入到FIRST中。4.LR<1>分析表的構(gòu)造在實(shí)現(xiàn)GO<I,X>時,記錄下狀態(tài)的轉(zhuǎn)化。得到分析表中的移進(jìn)部分。然后再掃描所有的項(xiàng)目集,找到其中包含歸約項(xiàng)目的哪些項(xiàng)目集,根據(jù)其中項(xiàng)目,得到分析表中那些鬼月的部分。4設(shè)計內(nèi)容4.1主要變量說明：#defineSIZE20//宏定義,定義sSIZE為12#definesSIZE12//宏定義,定義sSIZE為12#defineaSIZE6//宏定義,定義aSIZE為6#definegSIZE2//宏定義,定義gSIZE為2#definegeSIZE6//宏定義,定義geSIZE為6typedefstructGe{charhead;//文法規(guī)則左部chargen[5];//文法規(guī)則右部}Generate;//生成符號串的基本數(shù)據(jù)結(jié)構(gòu)體typedefstructA{intst[aSIZE];//遇到終結(jié)符時下一個動作狀態(tài)intre[aSIZE];//遇到非終結(jié)符時進(jìn)行規(guī)約}Action;//動作表的基本數(shù)據(jù)結(jié)構(gòu)體typedefstructG{charhead[gSIZE];//狀態(tài)轉(zhuǎn)換時遇到的非終結(jié)符intgt[gSIZE];//標(biāo)記下一個狀態(tài)}GOTO;//GOTO表的基本數(shù)據(jù)結(jié)構(gòu)體intstatus[SIZE];//狀態(tài)棧intsta_Index;//狀態(tài)棧棧頂標(biāo)記charsymbol[SIZE];//符號棧intsym_Index;//當(dāng)前符號棧的標(biāo)記charexpression[SIZE];//輸入的符號串intexp_Index;//輸入符號串的標(biāo)記intexp_top;//輸入符號串的棧頂元素intstep;//計算步驟intIsAccept=0;//初始化接受狀態(tài)標(biāo)志置為0Generategene[geSIZE+1];Actionact[sSIZE];GOTOgo[sSIZE];4.2程序流程圖：開始開始輸入一個待判斷的符號串輸入一個待判斷的符號串進(jìn)行分析進(jìn)行分析分析成功分析成功NY進(jìn)行歸約分析進(jìn)行歸約分析輸出分析結(jié)果輸出分析結(jié)果結(jié)束結(jié)束4.3運(yùn)行結(jié)果：運(yùn)行后進(jìn)入界面：上圖是編譯運(yùn)行后進(jìn)入的主界面,給出了給定文法、分析表,要求出入一個要進(jìn)行分析的符號串。輸入錯誤字符串beD：上圖中含有非終結(jié)符,不符合要輸入指定的幾個非終結(jié)符的要求,所以提示錯誤。輸入字符串a(chǎn)ed：上圖輸入的符號串符合要求,可見結(jié)果為接受狀態(tài),為該文法的句子。輸入字符串bcd:上圖輸入的符號串符合要求,但是進(jìn)行分析時發(fā)現(xiàn)不能進(jìn)行規(guī)約,結(jié)果錯誤,不是該文法的句子。5程序關(guān)鍵代碼：voidInitlize<void>//將終結(jié)符規(guī)約時所對應(yīng)的要使用的{文法規(guī)則gene[1].head='S';strcpy<gene[1].gen,"aAd">;gene[2].head='S';strcpy<gene[2].gen,"bAc">;gene[3].head='S';strcpy<gene[3].gen,"aec">;gene[4].head='S';strcpy<gene[4].gen,"bed">;gene[5].head='A';strcpy<gene[5].gen,"e">;voidReduce<intsta,charsymb,intcol>//執(zhí)行規(guī)約過程的函數(shù){inti=0;for<i=0;i<strlen<gene[act[sta].re[col]].gen>;i++>{symbol[sym_Index--]='\0';}symbol[++sym_Index]=gene[act[sta].re[col]].head;for<i=0;i<strlen<gene[act[sta].re[col]].gen>;i++>{status[sta_Index-i]='\0';}sta_Index-=i;GOTOTable<status[sta_Index],symbol[sym_Index]>;}voidActionTable<intsta,charsymb,intcol>//動作表{if<sta==1&&col==5>{printf<"ACCEPT\n">;IsAccept=1;return;}if<act[sta].st[col]!=0>{printf<"Action\n">;status[++sta_Index]=act[sta].st[col];symbol[++sym_Index]=symb;exp_top++;}elseif<act[sta].re[col]!=0>{printf<"Reduce\n">;Reduce<sta,symb,col>;}else{printf<"ERROR\n">;getchar<>;exit<1>;}}voidGOTOTable<intsta,charsymb>//GOTO表{inti=0;for<i=0;i<sSIZE;i++>{if<go[sta].head[i]==symb>{status[++sta_Index]=go[sta].gt[i];return;}}}voidLaunch<void>//輸出對符號串的狀態(tài)分析表的函數(shù){ints=status[sta_Index];charexp=expression[exp_top];charsym=symbol[sym_Index];while<IsAccept!=1>{s=status[sta_Index];exp=expression[exp_top];sym=symbol[sym_Index];printf<"%d\t",step++>;PrintStatus<>;printf<"%s\t\t",symbol>;PrintRestExp<>;switch<exp>{case'a':ActionTable<s,exp,0>;break;case'b':ActionTable<s,exp,1>;break;case'c':ActionTable<s,exp,2>;break;case'd':ActionTable<s,exp,3>;break;case'e':ActionTable<s,exp,4>;break;case'#':ActionTable<s,exp,5>;break;}}}6心得體會：此次課程設(shè)計中受益良多,從一開始的不知道從何入手,再到?jīng)Q定用的編程語言、設(shè)計程序流程、調(diào)試,最后到程序運(yùn)行成功。較好