編譯原理課程設(shè)計報告-預(yù)測分析程序的設(shè)計

1、課程設(shè)計任務(wù)書學(xué)生姓名：專業(yè)班級：指導(dǎo)教師：工作單位： 題目:預(yù)測分析程序的設(shè)計 初始條件：程序設(shè)計語言:主要使用 C 語言的開發(fā)工具，或者采用 LEX、YACC 等工具，也可利用其他熟悉的開發(fā)工具。算法：可以根據(jù)編譯原理課程所講授的算法進行設(shè)計。要求完成的主要任務(wù): （包括課程設(shè)計工作量及其技術(shù)要求，說明書撰寫等具體要求）明確課程設(shè)計的目的和重要性，認真領(lǐng)會課程設(shè)計的題目，讀懂課程設(shè)計指導(dǎo)書的要求，學(xué)會設(shè)計的基本方法與步驟，學(xué)會如何運用前修知識與收集、歸納相關(guān)資料解決具體問題的方法。嚴格要求自己，要獨立思考，按時、獨立完成課程設(shè)計任務(wù)。課設(shè)任務(wù)：對教材 P94 中的上下文無關(guān)文法，實現(xiàn)它的預(yù)

2、測分析程序，給出符號串i+i*i 的分析過程。（參考教材 P9396）主要功能：對于這個給的L（L 1）文法，假設(shè)所有非終結(jié)符號P 的FIRST 集合和FOLLOW集合都是已知的，構(gòu)造其預(yù)測分析表，程序顯示輸出預(yù)測分析表，同時用這個預(yù)測分析程序?qū)斎氪M行分析，并給出了棧的變化過程。進行總體設(shè)計，詳細設(shè)計：包括算法的設(shè)計和數(shù)據(jù)結(jié)構(gòu)設(shè)計。系統(tǒng)實施、調(diào)試，合理使用出錯處理程序。設(shè)計報告：要求層次清楚、整潔規(guī)范、不得相互抄襲。正文字數(shù)不少于0.3 萬字。包含內(nèi)容：課程設(shè)計的題目。目錄。正文：包括引言、需求分析、總體設(shè)計及開發(fā)工具的選擇，設(shè)計原則（給出語法分析方法及中間代碼形式的描述、文法和屬性文法的

3、設(shè)計），數(shù)據(jù)結(jié)構(gòu)與模塊說明（功能與流程圖）、詳細的算法設(shè)計、軟件調(diào)試、軟件的測試方法和結(jié)果、有關(guān)技術(shù)的討論、收獲與體會等。結(jié)束語。參考文獻。附錄：軟件清單（或者附盤）。時間安排：消化資料、系統(tǒng)調(diào)查、形式描述1 天系統(tǒng)分析、總體設(shè)計、實施計劃3 天撰寫課程設(shè)計報告書1 天指導(dǎo)教師簽名：2010 年 6 月 11 日系主任（或責任教師）簽名：2010 年 6 月 11 日編譯原理課程設(shè)計說明書 PAGE 26目錄 HYPERLINK l _TOC_250021 引言5 HYPERLINK l _TOC_250020 需求分析5 HYPERLINK l _TOC_250019 問題的提出5 HYPE

4、RLINK l _TOC_250018 問題的解決5 HYPERLINK l _TOC_250017 解決步驟6 HYPERLINK l _TOC_250016 總體設(shè)計6 HYPERLINK l _TOC_250015 概要設(shè)計6 HYPERLINK l _TOC_250014 設(shè)計原理6構(gòu)造 LL（1）分析表7 HYPERLINK l _TOC_250013 詳細設(shè)計10 HYPERLINK l _TOC_250012 程序流程圖10 HYPERLINK l _TOC_250011 設(shè)計要求12 HYPERLINK l _TOC_250010 設(shè)計原理12 HYPERLINK l _TOC

5、_250009 FIRST(X)(XVNVT)的構(gòu)造12函數(shù)getFIRST( )( =X1X2X3Xn)的構(gòu)造 . 12 3.2.3.3FOLLOW(A)(A VN)的構(gòu)造13 HYPERLINK l _TOC_250008 分析表M【A,a】的構(gòu)造13 HYPERLINK l _TOC_250007 匹配過程的實現(xiàn)13程序設(shè)計14 HYPERLINK l _TOC_250006 總體方案設(shè)計14 HYPERLINK l _TOC_250005 各模塊的實現(xiàn)14 HYPERLINK l _TOC_250004 開發(fā)工具的選擇23 HYPERLINK l _TOC_250003 程序測試23

6、HYPERLINK l _TOC_250002 有關(guān)技術(shù)的討論25 HYPERLINK l _TOC_250001 收獲與體會25 HYPERLINK l _TOC_250000 參考文獻26引言一個編譯程序在對某個源程序完成了詞法分析工作之后，就進入了語法分析階段，分析檢查源程序是否語法上正確的程序，并生成相應(yīng)的內(nèi)部中間表供下一階段使用。程序設(shè)計語言是一般形式語言的特例，程序語法正確性的檢查時語法句子的識別，語法分析問題也就是句型識別問題。按照識別句子語法樹建立的方式，有自頂向下與自底向上兩大類分析技術(shù)。本課程討論自頂向下的情況。本次課程設(shè)計所做的工作是對已知 FIRST 集合和 FOLLO

7、W 集合的 LL(1)文法構(gòu)造其預(yù)測分析表，程序顯示輸出預(yù)測分析表，同時用這個預(yù)測分析程序?qū)斎氪M行分析，并給出了棧的變化過程。需求分析問題的提出語法分析是編譯過程的核心部分。他的任務(wù)是在詞法分析識別單詞符號串的基礎(chǔ)上，分析并判斷程序的的語法結(jié)構(gòu)是否符合語法規(guī)則。語言的語法結(jié)構(gòu)是用上下文無關(guān)文法描述的。因此語法分析器的工作的本質(zhì)上就是按文法的產(chǎn)生式， 識別輸入符號串是否為一個句子。對于一個文法，當給你一串符號是，如何知道它是不是該文法的一個句子，這是這個課程設(shè)計所要解決的一個問題。問題的解決其實要知道一串符號是不是該文法的一個句子，只要判斷是否能從文法的開始符號出發(fā)推導(dǎo)出這個輸入串。語法分析

8、可以分為兩類，一類是自上而下的分析法，一類是自下而上的分析法。自上而下的主旨是，對任何輸入串，試圖用一切可能的辦法，從文法開始符號出發(fā)，自上而下的為輸入串建立一棵語法樹。或者說，為輸入串尋找一個最左推倒，這種分析過程的本質(zhì)是一種試探過程，是反復(fù)使用不同產(chǎn)生式謀求匹配輸入串的過程我主要是自上而下的過程。解決步驟在自上而下的分析法中，主要是研究 LL(1)分析法。它的解決步驟是首先接收到用戶輸入的一個文法，對文法進行檢測和處理，消除左遞歸，得到LL(1) 文法，這個文法應(yīng)該滿足：無二義性，無左遞歸，無左公因子。當文法滿足條件后，再分別構(gòu)造文法每個非終結(jié)符的 FIRST 和 FOLLOW 集合，然后

9、根據(jù) FIRST 和 FOLLOW 集合構(gòu)造 LL（1）分析表，最后利用分析表，根據(jù) LL(1)語法分析構(gòu)造一個分析器。當然本課設(shè)只是針對 FIRST 和 FOLLOW 集合都以知的任意輸入的 LL（1）文法。LL（1）的語法分析程序包含了三個部分，總控程序，預(yù)測分析表函數(shù)，先進先出的語法分析棧?？傮w設(shè)計概要設(shè)計設(shè)計原理所謂 LL（1）分析法，就是指從左到右掃描輸入串（源程序），同時采用最左推導(dǎo)，且對每次直接推導(dǎo)只需向前看一個輸入符號，便可確定當前所應(yīng)當選擇的規(guī)則。實現(xiàn) LL（1）分析的程序又稱為LL（1）分析程序或LL1（1）分析器。我們知道一個文法要能進行 LL（1）分析，那么這個文法應(yīng)該

10、滿足：無二義性，無左遞歸，無左公因子。當文法滿足條件后，再分別構(gòu)造文法每個非終結(jié)符的 FIRST 和 FOLLOW 集合，然后根據(jù) FIRST 和 FOLLOW 集合構(gòu)造 LL（1） 分析表，最后利用分析表，根據(jù) LL(1)語法分析構(gòu)造一個分析器。LL（1）的語法分析程序包含了三個部分，總控程序，預(yù)測分析表函數(shù)，先進先出的語法分析棧，本程序也是采用了同樣的方法進行語法分析，也是采用了 C+語言來編寫。LL（1）預(yù)測分析程序的總控程序在任何時候都是按 STACK 棧頂符號 X 和當前的輸入符號 a 做哪種過程的。對于任何（X，a），總控程序每次都執(zhí)行下述三種可能的動作之一：（）若 X = a =

11、#，則宣布分析成功，停止分析過程。（）若 X = a #，號。則把X 從 STACK 棧頂彈出，讓 a 指向下一個輸入符（）若 X 是一個非終結(jié)符，則查看預(yù)測分析表 M。若 MA，a中存放著關(guān)于 X 的一個產(chǎn)生式，那么，首先把 X 彈出 STACK 棧頂，然后，把產(chǎn)生式的右部符號串按反序一一彈出 STACK 棧（若右部符號為 ，則不推什么東西進STACK 棧）。若 MA，a中存放著“出錯標志”，則調(diào)用出錯診斷程序ERROR。事實上，LL（1）的分析是根據(jù)文法構(gòu)造的，它反映了相應(yīng)文法所定義的語言的固定特征，因此在 LL（1）分析器中，實際上是以LL（1）分析表代替相應(yīng)方法來進行分析的。構(gòu)造 LL

12、（1）分析表在構(gòu)造 LL(1)預(yù)測分析表之前，首先要構(gòu)造該文法的每個非終結(jié)符的 FIRST和 FOLLOW 集合，按照下面描述的算法來構(gòu)造這兩個集合。FIRST 集合的構(gòu)造算法：若 XVT，則 FIRST（X）=X。若 XVN，且有產(chǎn)生式 Xa，則把 a 加入到 FIRST(X)中；若 X 也是一條產(chǎn)生式，則把 也加到 FIRST(X)中。若 XY是一個產(chǎn)生式且 YVN，則把 FIRST(Y)中的所有非 -元素都加到 FIRST(X)中；若 XY1Y2Yk 是一個產(chǎn)生式，Y1，Yi-1 都是非終結(jié)符，而且，對于任何 j，1ji-1，F(xiàn)IRST(Yj)都含有 （即 Y1Yi-1* ），則把 FI

13、RST(Yj)中的所有非 -元素都加到 FIRST(X)中；特別是，若所有的FIRST(Yj)均含有 ，j=1,2,，k，則把 加到 FIRST(X)中。連續(xù)使用上面的規(guī)則，直至每個集合 FIRST 不再增大為止。FOLLOW 集合的構(gòu)造算法：對于文法的開始符號 S，置#于 FOLLOW(S)中；若 AB 是一個產(chǎn)生式，則把 FIRST()| 加至 FOLLOW(B)中；若 AB 是一個產(chǎn)生式，或 AB 是一個產(chǎn)生式而 （即 FIRST()），則把 FOLLOW(A)加至 FOLLOW(B)中。連續(xù)使用上面的規(guī)則，直至每個集合 FOLLOW 不再增大為止。根據(jù)以上描述的算法，可以構(gòu)造文法GA的

14、FIRST 和 FOLLOW 集合如下：非終結(jié)符 AFIRST(A)FOLLOW(A)A (，i ), # B +, ), # C (，i +, ), # D * , +, ), # E (，i *, +, ), # 構(gòu)造預(yù)測分析表，設(shè)計預(yù)測分析表的存儲結(jié)構(gòu)（構(gòu)造算法）。i+*()#AACBACBBCCEDB+CBCEDBBDDD*EDDDEEiE(A)總體的框圖：句子分析過程的框圖：詳細設(shè)計程序流程圖在對程序各個模塊分析之前。先給出整個程序的流程圖。以便于在分析過程中更好的對各個模塊之間的聯(lián)系進行了解。程序的流程圖如下：開始輸入文法相關(guān)信息LL（1）文法構(gòu)造 FIRST 集構(gòu)造 FOLLOW

15、 集構(gòu)造預(yù)測分析表輸入產(chǎn)生式判斷句型是構(gòu)造句子的預(yù)測分析過程YContinue=“Y“結(jié)束設(shè)計要求實現(xiàn) FIRST(X) (XVN VT)；根據(jù) FIRST(X) (XVN VT)，實現(xiàn) getFIRST( ) ( =X1X2X3Xn)；實現(xiàn) FOLLOW(A) (AVN)；根據(jù) getFIRST( )以及 FOLLOW(A)構(gòu)造 LL(1)分析表 M【A,a】；根據(jù)分析表 M【A,a】，對任一輸入字符串進行匹配，判斷是否合法，并且顯示其匹配過程。設(shè)計原理FIRST(X)(XVN VT)的構(gòu)造連續(xù)使用下面的規(guī)則，直至每個集合 FIRST 不再增大為止： (1). 若 XVT，則 FIRST(X

16、)=X;(2). 若 XVN，且有產(chǎn)生式 Xa，則把 a 加入到 FIRST(X)中；若 X$(表示空字符串)也是一條產(chǎn)生式，則把$也加到 FIRST(X)中。(3)若 XY是一個產(chǎn)生式且 YVN，則把 FIRST(Y)中的所有非$元素都加到 FIRST(X)中；若 XY1Y2Yk 是一個產(chǎn)生式，Y1,Yi-1 都是非終結(jié)符，而且， 對于任何 j,1=j$)，則把 FIRST(Yj) 中的所有非 $元素都加到FIRST(X)中；特別是，若所有的FIRST(Yj)均含有$,j=1,2,k,則把$加到 FIRST(X)中。如上可得到 FIRST(X) (XVN VT)。函數(shù) getFIRST( )

17、 ( =X1X2X3Xn)的構(gòu)造之前已經(jīng)實現(xiàn)了 FIRST(X) (XVN VT)，現(xiàn)在我們能夠?qū)ξ姆?G 的任何符號串 =X1X2Xn 構(gòu)造集合 FIRST(a)。首先，置 FIRST( )=FIRST(X1)$;若對任 1=j=i-1,$FIRST(Xj),則把FIRST(Xi)$加至 FIRST( )中；特別是，若所有 FIRST(Xj)均含有$,1=j B 是一個產(chǎn)生式，則把 FIRST( )$加至 FOLLOW(B)中； (3). 若 A B 是一個產(chǎn)生式，或 A B 是一個產(chǎn)生式而 =$(即$FIRST( ),則把 FOLLOW(A)加至 FOLLOW(B)。如上可得到 FOLLO

18、W(A) (AVN)的構(gòu)造。分析表 M【A,a】的構(gòu)造在對文法 G 的每個終結(jié)符 A 及其任意候選 a 都構(gòu)造出 FIRST(a)(2.2 節(jié)的getFIRST(a),和 FOLLOW(A)(2.3 節(jié)的 FOLLOW(A)之后,我們現(xiàn)在可以用它們來構(gòu)造 G 的分析表 M【A,a】。構(gòu)造分析表 M 的算法是：(1). 對文法 G 的每個產(chǎn)生式 A 執(zhí)行第 2 步和第 3 步； (2). 對每個終結(jié)符 a FIRST( ),把 A 加至 M【A,a】中；(3). 若$ FIRST( ),則對任何 a FOLLOW(A)把 A 加至 M【A,a】中； (4). 把所有無定義的 M【A,a】標上“出

19、錯標志“。如上可得到 M【A,a】。匹配過程的實現(xiàn)對于任何(A,a),總控程序每次都執(zhí)行下述三種可能的動作之一：若 X=a=#,則宣布分析成功，停止分析過程。若 X=a!=#,則把 X 從 stack 棧頂逐出，讓a 指向下一個輸入符號。若 X 是一個非終結(jié)符，則查看分析表 M。若 M【A,a】中存放著關(guān)于 X 的一個產(chǎn)生式，那么把 X 逐出 stack 棧頂，然后，把產(chǎn)生式的右部符號串按反序一一推進 stack 棧(若右部符號為$,則意味不推什么東西進棧)。若 M【A,a】中存放著“出錯標志“，則中斷匹配，顯示出錯信息。3.3 程序設(shè)計總體方案設(shè)計Main()調(diào)用 input(),讀入文法

20、G 的有關(guān)內(nèi)容：G(VT,VN,S,&);Main()調(diào)用 createFIRST(),實現(xiàn) FIRST(X),(X VTVN);內(nèi)部程序中通過調(diào)用 getFIRST(string)得到字符串的 FIRST 終結(jié)符； (4). Main()調(diào)用 createFOLLOW(),實現(xiàn) FOLLOW(A),(A VN);Main()調(diào)用 createTABLE(),創(chuàng)建 LL(1)分析表 M【A,a】；Main()調(diào)用 match (string)對任一輸入的字符串進行匹配，判斷其是否合法，并且顯示匹配過程；各模塊的實現(xiàn)void input()VT,VN 都是以字符存儲的，numVT 表示 VT 的

21、數(shù)目，numVN 表示 VN 的數(shù)目。VT 標號 0numVT-1，VN 標號 numVTnumVT+numVN-1。函數(shù) findV(char)和 V(int)分別實現(xiàn)字符索引和索引字符間的轉(zhuǎn)換($用 nunVT+numVN 索引)。產(chǎn)生式&以字符串的方式讀入，經(jīng)過 comsume()函數(shù)處理。產(chǎn)生式存在 TTi 的 vector 數(shù)組中(numVT=inumVT+numVN，i 為 VN 標號)。每個 Ti都是一個string 的 vector 數(shù)組，存儲 Vi的所有產(chǎn)生式。input ( )函數(shù)代碼如下： void input()/存儲文法G的有關(guān)內(nèi)容/memset:作用是在一段內(nèi)存塊中

22、填充某個給定的值，它對較大的結(jié)構(gòu)體或數(shù)組進行清零操作的一種最快方法memset(FIRST,0,sizeof(FIRST);/把FIRST【】清零memset(FOLLOW,0,sizeof(FOLLOW);/把FOLLOW【】清零char cc;string ss; int top=0;coutplease input the set of VT(end by 0)cc&cc!=0)Vtop+=cc; numVT=top;coutplease input the set of VN(end by 0)cc&cc!=0)Vtop+=cc; numVN=top-numVT; Vtop=$;cou

23、tplease input the start VNStart;coutplease input the chanshengshi(end line by 0)ss&ss0!=0) consume(ss);void createFIRST()用布爾數(shù)組 FIRSTij(0=i,j=numVT+numVN)來存儲 VTVN 的開始終結(jié)字符信息。FIRSTij=1 表示 Vj FIRSTVi,否則表示 Vj FIRSTVi。先初始化 FIRSTij(0=i,j=numVT+numVN)為 false，然后 while 循環(huán)按3.2.2 1 的構(gòu)造規(guī)則進行構(gòu)造，用 leni(0=inumVT+num

24、VN)來記錄上一次循環(huán)處理后各個終結(jié)符與非終結(jié)符 X 的開始終結(jié)字符數(shù)目(即 FIRST(X)。每次循環(huán) 結(jié) 束 檢 測 leni 并 更 新 。 若 檢 測 到 任 一 0=inumVT+numVN, 都 有l(wèi)eni=num(FIRST(i),則說明已構(gòu)造完畢，跳出 while 循環(huán)，函數(shù)結(jié)束返回。createFIRST( )代碼如下：void createFIRST()/存儲VT VN的開始終結(jié)字符信息int lenmaxV;memset(len,-1,sizeof(len); int i,j,t,no; for(i=0;inumVT;i+)FIRSTii=1;bool sign=1; w

25、hile(sign)for(i=numVT;inumVT+numVN;i+)for(j=0;jTTi.size();j+)int pp=findV(TTij0);if(ppnumVT|TTij0=$)FIRSTipp=1;continue;bool sign2; for(t=0;tTTij.size();t+)sign2=0; no=findV(TTijt); int iter;for(iter=0;iternumVT;iter+) if(FIRSTnoiter) FIRSTiiter=1;if(FIRSTnonumVT+numVN)sign2=1;if(t=TTij.size()-1) FI

26、RSTinumVT+numVN=1;if(sign2=0) break;sign=0; for(i=numVT;inumVT+numVN;i+)int plen=0; for(j=0;jnumVT;j+)if(FIRSTij) plen+; if(FIRSTinumVT+numVN) plen+; if(leni!=plen) sign=1; leni=plen;vector getFIRST(string str)對于字符串 str，該函數(shù)返回 str 的開始終結(jié)符數(shù)組?？筛鶕?jù) 3.2.22 的規(guī)則實現(xiàn)，對字符串的字符依次分析，將得到的開始終結(jié)字符存儲到臨時 vector數(shù)組 tmp 中，函

27、數(shù)結(jié)束返回 tmp 數(shù)組。vector getFIRST(string str)代碼如下：vector getFIRST(string str)/返回str的開始終結(jié)符數(shù)組vector tmp; if(str.size()=0) return tmp; if(str=$)tmp.push_back($); return tmp;int i,j,no; bool sign;for(i=0;istr.size();i+)sign=0; no=findV(stri); int iter;for(iter=0;iternumVT;iter+) if(FIRSTnoiter) tmp.push_back

28、(Viter);if(FIRSTnonumVT+numVN)sign=1;if(i=str.size()-1) tmp.push_back($);if(!sign) break;return tmp;void createFOLLOW()用布爾數(shù)組 FOLLOWij(numVT=inumVT+numVN,0=jnumVT) 來存儲 VN 的緊接終結(jié)字符信息。FOLLOWij=1 表示 Vj FOLLOWVi,否則表示 Vj FOLLOWVi。先初始化 FOLLOWij(0=i,jnumVT+numVN)為 false,然后先根據(jù) 3.2.2 3 的規(guī)則進行構(gòu)造。接著while 循環(huán)(3)規(guī)則用

29、 leni(numVT=inumVT+numVN) 來記錄上一次循環(huán)處理后各個非終結(jié)符 A 的緊接終結(jié)字符數(shù)目 ( 即FOLLOW(X) 。 每 次 循 環(huán) 結(jié) 束 檢 測 leni 并 更 新 。 若 檢 測 到 任 一numVT=inumVT+numVN,都有 leni=num(FIRST(i),則說明已構(gòu)造完畢，跳出 while 循環(huán)，函數(shù)結(jié)束返回。void createFOLLOW()代碼如下：void createFOLLOW()/求得文法G中每個終結(jié)符的FOLLOW集int lenmaxV; memset(len,0,sizeof(len); int i,j,t,no; no=fi

30、ndV(Start); FOLLOWnofindV(#)=1;for(i=numVT;inumVT+numVN;i+)for(j=0;jTTi.size();j+)for(t=0;t=numVT&no!=numVT+numVN)int tt; if(tTTij.size()-1)vector tmp=getFIRST(TTij.substr(t+1,TTij.size()-t-1); for(tt=0;tttmp.size();tt+)if(tmptt!=$) FOLLOWnofindV(tmptt)=1;bool sign=1; while(sign)for(i=numVT;inumVT+n

31、umVN;i+)for(j=0;jTTi.size();j+)for(t=0;t=numVT&TTijt!=$)int tt;if(tTTij.size()-1)vector tmp=getFIRST(TTij.substr(t+1,TTij.size()-t-1);for(tt=0;tttmp.size();tt+)if(tmptt=$)int iter; for(iter=0;iternumVT;iter+)if(FOLLOWiiter) FOLLOWnoiter=1; break;elseint iter; for(iter=0;iternumVT;iter+)if(FOLLOWiite

32、r) FOLLOWnoiter=1;sign=0; for(i=numVT;inumVT+numVN;i+)int plen=0; for(j=0;jnumVT;j+)if(FOLLOWij) plen+; if(leni!=plen) sign=1; leni=plen;void createTABLE()用字符串數(shù)組 Mij來存儲棧內(nèi)符 Vi與輸入字符 Vj的匹配產(chǎn)生式，若不匹配，則為空。按照 3.2.24 的規(guī)則進行棧頂字符和字符串的字符的依次匹配，匹配處理結(jié)束后，函數(shù)結(jié)束返回。void createTABLE ( )代碼如下：void createTABLE()/構(gòu)建預(yù)測分析表int

33、i,j,t; for(i=numVT;inumVT+numVN;i+)for(j=0;jTTi.size();j+)string tmp=TTij;vector first=getFIRST(tmp); bool sign=0; for(t=0;t+TTij;if(sign)int iter; for(iter=0;iter+TTij;bool match (string str)用棧來實現(xiàn)匹配算法：棧 stack 用來存放文法符號。分析開始時，棧底先存放一個#,然后放入文法開始符號。同時，假定輸入串之后也總有一個#,標志輸入串結(jié)束。預(yù)測分析程序的總控程序在任何時候都是按 stack 棧頂符號

34、 X 和當前的輸入符號 a 行事的。對具體情況根據(jù)規(guī)則 3.2.2 5 的 3 種處理方式之一進行處理。處理完后，函數(shù)結(jié)束返回。編譯原理課程設(shè)計說明書bool match (string str)代碼如下：bool match(string str)/用棧來實現(xiàn)匹配算法str=str+#;cout步驟t符號棧t輸入串t產(chǎn)生式endl; int num=0;char stackmaxV; int top=0; stacktop+=#; stacktop+=Start;coutnumt#Starttstrendl; int i=0,j;while(istr.size()char A=stackto

35、p-1; if(A!=#&findV(A)=-1) return false;if(stri!=#&findV(stri)=-1) return false; string tmp;if(A=#)if(A=stri) return true; else return false;else if(findV(A)=3;j-) stacktop+=tmpj;編譯原理課程設(shè)計說明書else return false;stacktop=0;cout+numtstacktstr.substr(i,str.size()-i)ttmpendl;(7)int main()函數(shù)程序的主要功能均在main（）函數(shù)

36、里面實現(xiàn)，首先是輸入文法的相關(guān)信息， 然后是創(chuàng)建FIRST表和FOLLOW表（不輸出），再輸出預(yù)測分析表，最后提示輸入句子，判斷是否是該文法的句型，程序?qū)崿F(xiàn)了多次輸入：int main() 函數(shù)代碼如下：int main()/主函數(shù)cout*預(yù)測分析程序*endl; input();createFIRST(); createFOLLOW(); createTABLE(); int i,j;cout*預(yù)測分析表*endl; couttit+t*t(t)t#tendl; for(i=numVT;inumVT+numVN;i+)coutVit; for(j=0;j0) coutMijt; else coutERRORt;coutendl;strin