編譯原理課程設(shè)計(jì)報(bào)告-預(yù)測(cè)分析程序的設(shè)計(jì)

1、<p><b>　　課程設(shè)計(jì)任務(wù)書(shū)</b></p><p>　　學(xué)生姓名： 專(zhuān)業(yè)班級(jí)： </p><p>　　指導(dǎo)教師： 工作單位： </p><p>　　題 目: 預(yù)測(cè)分析程序的設(shè)計(jì)</p><p><b>　　初始條件：

2、</b></p><p>　　程序設(shè)計(jì)語(yǔ)言:主要使用C語(yǔ)言的開(kāi)發(fā)工具，或者采用LEX、YACC等工具，也可利用其他熟悉的開(kāi)發(fā)工具。算法：可以根據(jù)《編譯原理》課程所講授的算法進(jìn)行設(shè)計(jì)。</p><p>　　要求完成的主要任務(wù): （包括課程設(shè)計(jì)工作量及其技術(shù)要求，說(shuō)明書(shū)撰寫(xiě)等具體要求）</p><p>　　明確課程設(shè)計(jì)的目的和重要性，認(rèn)真領(lǐng)會(huì)課程設(shè)計(jì)的題目，

3、讀懂課程設(shè)計(jì)指導(dǎo)書(shū)的要求，學(xué)會(huì)設(shè)計(jì)的基本方法與步驟，學(xué)會(huì)如何運(yùn)用前修知識(shí)與收集、歸納相關(guān)資料解決具體問(wèn)題的方法。嚴(yán)格要求自己，要獨(dú)立思考，按時(shí)、獨(dú)立完成課程設(shè)計(jì)任務(wù)。</p><p>　　課設(shè)任務(wù)：對(duì)教材P94中的上下文無(wú)關(guān)文法，實(shí)現(xiàn)它的預(yù)測(cè)分析程序，給出符號(hào)串i+i*i的分析過(guò)程。（參考教材P93～96）</p><p>　　主要功能：對(duì)于這個(gè)給的LL（1）文法，假設(shè)所有非終結(jié)符號(hào)P的F

4、IRST集合和FOLLOW集合都是已知的，構(gòu)造其預(yù)測(cè)分析表，程序顯示輸出預(yù)測(cè)分析表，同時(shí)用這個(gè)預(yù)測(cè)分析程序?qū)斎氪M(jìn)行分析，并給出了棧的變化過(guò)程。</p><p>　　進(jìn)行總體設(shè)計(jì)，詳細(xì)設(shè)計(jì)：包括算法的設(shè)計(jì)和數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)。系統(tǒng)實(shí)施、調(diào)試，合理使用出錯(cuò)處理程序。</p><p>　　設(shè)計(jì)報(bào)告：要求層次清楚、整潔規(guī)范、不得相互抄襲。正文字?jǐn)?shù)不少于0.3萬(wàn)字。包含內(nèi)容：</p>&

5、lt;p>　?、僬n程設(shè)計(jì)的題目。 ②目錄。</p><p>　?、壅模喊ㄒ?、需求分析、總體設(shè)計(jì)及開(kāi)發(fā)工具的選擇，設(shè)計(jì)原則（給出語(yǔ)法分析方法及中間代碼形式的描述、文法和屬性文法的設(shè)計(jì)），數(shù)據(jù)結(jié)構(gòu)與模塊說(shuō)明（功能與流程圖）、詳細(xì)的算法設(shè)計(jì)、軟件調(diào)試、軟件的測(cè)試方法和結(jié)果、有關(guān)技術(shù)的討論、收獲與體會(huì)等。</p><p>　　④結(jié)束語(yǔ)。 ⑤參考文獻(xiàn)。 ⑥附錄：軟

6、件清單（或者附盤(pán)）。</p><p><b>　　時(shí)間安排：</b></p><p>　　消化資料、系統(tǒng)調(diào)查、形式描述1天</p><p>　　系統(tǒng)分析、總體設(shè)計(jì)、實(shí)施計(jì)劃3天</p><p>　　撰寫(xiě)課程設(shè)計(jì)報(bào)告書(shū)1天</p><p>　　指導(dǎo)教師簽名： 2010

7、年 6月 11日</p><p>　　系主任（或責(zé)任教師）簽名： 2010年 6月 11日 </p><p><b>　　目 錄</b></p><p><b>　　1引言4</b></p><p><b>　　2需求分析5</b></p>

8、<p>　　2.1問(wèn)題的提出5</p><p>　　2.2問(wèn)題的解決5</p><p>　　2.3解決步驟5</p><p><b>　　3總體設(shè)計(jì)6</b></p><p>　　3.1概要設(shè)計(jì)6</p><p>　　3.1.1設(shè)計(jì)原理6</p>&

9、lt;p>　　3.1.2構(gòu)造LL（1）分析表7</p><p>　　3.2詳細(xì)設(shè)計(jì)10</p><p>　　3.2.1程序流程圖10</p><p>　　3.2.2設(shè)計(jì)要求12</p><p>　　3.2.3設(shè)計(jì)原理12</p><p>　　3.2.3.1 FIRST(X)(XVNVT)的構(gòu)

10、造12</p><p>　　3.2.3.2 函數(shù)getFIRST() (=X1X2X3…Xn)的構(gòu)造12</p><p>　　3.2.3.3 FOLLOW(A) (AVN)的構(gòu)造13</p><p>　　3.2.3.4 分析表M【A,a】的構(gòu)造13</p><p>　　3.2.3.5 匹配過(guò)程的實(shí)現(xiàn)13</p>

11、<p>　　3.3程序設(shè)計(jì)14</p><p>　　3.3.1總體方案設(shè)計(jì)14</p><p>　　3.3.2各模塊的實(shí)現(xiàn)14</p><p>　　4開(kāi)發(fā)工具的選擇23</p><p><b>　　5程序測(cè)試23</b></p><p>　　6有關(guān)技術(shù)的討論25

12、</p><p>　　7收獲與體會(huì)26</p><p><b>　　8參考文獻(xiàn)26</b></p><p><b>　　引言</b></p><p>　　一個(gè)編譯程序在對(duì)某個(gè)源程序完成了詞法分析工作之后，就進(jìn)入了語(yǔ)法分析階段，分析檢查源程序是否語(yǔ)法上正確的程序，并生成相應(yīng)的內(nèi)部中間表供下一階

13、段使用。程序設(shè)計(jì)語(yǔ)言是一般形式語(yǔ)言的特例，程序語(yǔ)法正確性的檢查時(shí)語(yǔ)法句子的識(shí)別，語(yǔ)法分析問(wèn)題也就是句型識(shí)別問(wèn)題。按照識(shí)別句子語(yǔ)法樹(shù)建立的方式，有自頂向下與自底向上兩大類(lèi)分析技術(shù)。本課程討論自頂向下的情況。</p><p>　　本次課程設(shè)計(jì)所做的工作是對(duì)已知FIRST集合和FOLLOW集合的LL(1)文法構(gòu)造其預(yù)測(cè)分析表，程序顯示輸出預(yù)測(cè)分析表，同時(shí)用這個(gè)預(yù)測(cè)分析程序?qū)斎氪M(jìn)行分析，并給出了棧的變化過(guò)程。<

14、/p><p><b>　　需求分析</b></p><p><b>　　問(wèn)題的提出</b></p><p>　　語(yǔ)法分析是編譯過(guò)程的核心部分。他的任務(wù)是在詞法分析識(shí)別單詞符號(hào)串的基礎(chǔ)上，分析并判斷程序的的語(yǔ)法結(jié)構(gòu)是否符合語(yǔ)法規(guī)則。語(yǔ)言的語(yǔ)法結(jié)構(gòu)是用上下文無(wú)關(guān)文法描述的。因此語(yǔ)法分析器的工作的本質(zhì)上就是按文法的產(chǎn)生式，識(shí)別輸入符

15、號(hào)串是否為一個(gè)句子。對(duì)于一個(gè)文法，當(dāng)給你一串符號(hào)是，如何知道它是不是該文法的一個(gè)句子，這是這個(gè)課程設(shè)計(jì)所要解決的一個(gè)問(wèn)題。</p><p><b>　　問(wèn)題的解決</b></p><p>　　其實(shí)要知道一串符號(hào)是不是該文法的一個(gè)句子，只要判斷是否能從文法的開(kāi)始符號(hào)出發(fā)推導(dǎo)出這個(gè)輸入串。語(yǔ)法分析可以分為兩類(lèi)，一類(lèi)是自上而下的分析法，一類(lèi)是自下而上的分析法。自上而下的主旨

16、是，對(duì)任何輸入串，試圖用一切可能的辦法，從文法開(kāi)始符號(hào)出發(fā)，自上而下的為輸入串建立一棵語(yǔ)法樹(shù)。或者說(shuō)，為輸入串尋找一個(gè)最左推倒，這種分析過(guò)程的本質(zhì)是一種試探過(guò)程，是反復(fù)使用不同產(chǎn)生式謀求匹配輸入串的過(guò)程我主要是自上而下的過(guò)程。</p><p><b>　　解決步驟</b></p><p>　　在自上而下的分析法中，主要是研究LL(1)分析法。它的解決步驟是首先接收到用

17、戶(hù)輸入的一個(gè)文法，對(duì)文法進(jìn)行檢測(cè)和處理，消除左遞歸，得到LL(1)文法，這個(gè)文法應(yīng)該滿(mǎn)足：無(wú)二義性，無(wú)左遞歸，無(wú)左公因子。當(dāng)文法滿(mǎn)足條件后，再分別構(gòu)造文法每個(gè)非終結(jié)符的FIRST和FOLLOW集合，然后根據(jù)FIRST和FOLLOW集合構(gòu)造LL（1）分析表，最后利用分析表，根據(jù)LL(1)語(yǔ)法分析構(gòu)造一個(gè)分析器。當(dāng)然本課設(shè)只是針對(duì)FIRST和FOLLOW集合都以知的任意輸入的LL（1）文法。LL（1）的語(yǔ)法分析程序包含了三個(gè)部分，總控程序，

18、預(yù)測(cè)分析表函數(shù)，先進(jìn)先出的語(yǔ)法分析棧。</p><p><b>　　總體設(shè)計(jì)</b></p><p><b>　　概要設(shè)計(jì)</b></p><p><b>　　設(shè)計(jì)原理</b></p><p>　　所謂LL（1）分析法，就是指從左到右掃描輸入串（源程序），同時(shí)采用最左推導(dǎo)，且對(duì)

19、每次直接推導(dǎo)只需向前看一個(gè)輸入符號(hào)，便可確定當(dāng)前所應(yīng)當(dāng)選擇的規(guī)則。實(shí)現(xiàn)LL（1）分析的程序又稱(chēng)為L(zhǎng)L（1）分析程序或LL1（1）分析器。</p><p>　　我們知道一個(gè)文法要能進(jìn)行LL（1）分析，那么這個(gè)文法應(yīng)該滿(mǎn)足：無(wú)二義性，無(wú)左遞歸，無(wú)左公因子。當(dāng)文法滿(mǎn)足條件后，再分別構(gòu)造文法每個(gè)非終結(jié)符的FIRST和FOLLOW集合，然后根據(jù)FIRST和FOLLOW集合構(gòu)造LL（1）分析表，最后利用分析表，根據(jù)LL(1)

20、語(yǔ)法分析構(gòu)造一個(gè)分析器。LL（1）的語(yǔ)法分析程序包含了三個(gè)部分，總控程序，預(yù)測(cè)分析表函數(shù)，先進(jìn)先出的語(yǔ)法分析棧，本程序也是采用了同樣的方法進(jìn)行語(yǔ)法分析，也是采用了C++語(yǔ)言來(lái)編寫(xiě)。</p><p>　　LL（1）預(yù)測(cè)分析程序的總控程序在任何時(shí)候都是按STACK棧頂符號(hào)X和當(dāng)前的輸入符號(hào)a做哪種過(guò)程的。對(duì)于任何（X，a），總控程序每次都執(zhí)行下述三種可能的動(dòng)作之一：</p><p>　　（１）

21、若X = a =‘#’，則宣布分析成功，停止分析過(guò)程。</p><p>　?。ǎ玻┤鬤 = a ‘#’，則把X從STACK棧頂彈出，讓a指向下一個(gè)輸入符號(hào)。</p><p>　　（３）若X是一個(gè)非終結(jié)符，則查看預(yù)測(cè)分析表M。若M[A，a]中存放著關(guān)于X的一個(gè)產(chǎn)生式，那么，首先把X彈出STACK棧頂，然后，把產(chǎn)生式的右部符號(hào)串按反序一一彈出STACK棧（若右部符號(hào)為ε，則不推什么東西進(jìn)STA

22、CK棧）。若M[A，a]中存放著“出錯(cuò)標(biāo)志”，則調(diào)用出錯(cuò)診斷程序ERROR。</p><p>　　事實(shí)上，LL（1）的分析是根據(jù)文法構(gòu)造的，它反映了相應(yīng)文法所定義的語(yǔ)言的固定特征，因此在LL（1）分析器中，實(shí)際上是以L(fǎng)L（1）分析表代替相應(yīng)方法來(lái)進(jìn)行分析的。</p><p>　　構(gòu)造LL（1）分析表</p><p>　　在構(gòu)造LL(1)預(yù)測(cè)分析表之前，首先要構(gòu)造該文

23、法的每個(gè)非終結(jié)符的FIRST和FOLLOW集合，按照下面描述的算法來(lái)構(gòu)造這兩個(gè)集合。</p><p>　?、貴IRST集合的構(gòu)造算法：</p><p>　　（1）若X∈VT，則FIRST（X）={X}。</p><p>　?。?）若X∈VN，且有產(chǎn)生式X→a……，則把a(bǔ)加入到FIRST(X)中；若X→ε也是一條產(chǎn)生式，則把ε也加到FIRST(X)中。</p&g

24、t;<p>　?。?）若X→Y……是一個(gè)產(chǎn)生式且Y∈VN，則把FIRST(Y)中的所有非ε-元素都加到FIRST(X)中；若X→Y1Y2…Yk是一個(gè)產(chǎn)生式，Y1，…，Yi-1都是非終結(jié)符，而且，對(duì)于任何j，1≤j≤i-1，F(xiàn)IRST(Yj)都含有ε（即Y1…Yi-1* ε），則把FIRST(Yj)中的所有非ε-元素都加到FIRST(X)中；特別是，若所有的FIRST(Yj)均含有ε，j=1,2,…，k，則把ε加到FIRST

25、(X)中。</p><p>　　連續(xù)使用上面的規(guī)則，直至每個(gè)集合FIRST不再增大為止。</p><p>　?、贔OLLOW集合的構(gòu)造算法：</p><p>　?。?）對(duì)于文法的開(kāi)始符號(hào)S，置#于FOLLOW(S)中；</p><p>　?。?）若A→αBβ是一個(gè)產(chǎn)生式，則把FIRST(β)| {ε}加至FOLLOW(B)中；</p&g

26、t;<p>　?。?）若A→αB是一個(gè)產(chǎn)生式，或A→αBβ是一個(gè)產(chǎn)生式而β ε（即ε∈FIRST(β)），則把FOLLOW(A)加至FOLLOW(B)中。</p><p>　　連續(xù)使用上面的規(guī)則，直至每個(gè)集合FOLLOW不再增大為止。</p><p>　　根據(jù)以上描述的算法，可以構(gòu)造文法G［A］的FIRST和FOLLOW集合如下：</p><p>　　

27、構(gòu)造預(yù)測(cè)分析表，設(shè)計(jì)預(yù)測(cè)分析表的存儲(chǔ)結(jié)構(gòu)（構(gòu)造算法）。</p><p><b>　　總體的框圖：</b></p><p>　　句子分析過(guò)程的框圖：</p><p><b>　　詳細(xì)設(shè)計(jì)</b></p><p><b>　　程序流程圖</b></p><p&g

28、t;　　在對(duì)程序各個(gè)模塊分析之前。先給出整個(gè)程序的流程圖。以便于在分析過(guò)程中更好的對(duì)各個(gè)模塊之間的聯(lián)系進(jìn)行了解。</p><p><b>　　程序的流程圖如下：</b></p><p><b>　　設(shè)計(jì)要求</b></p><p>　　1. 實(shí)現(xiàn)FIRST(X) (XVNVT)；</p><p>　

29、　2. 根據(jù)FIRST(X) (XVNVT)，實(shí)現(xiàn)getFIRST() (=X1X2X3…Xn)；</p><p>　　3. 實(shí)現(xiàn)FOLLOW(A) (AVN)；</p><p>　　4. 根據(jù)getFIRST()以及FOLLOW(A)構(gòu)造LL(1)分析表M【A,a】；</p><p>　　5. 根據(jù)分析表M【A,a】，對(duì)任一輸入字符串進(jìn)行匹配，判斷是否合法，并且顯

30、示其匹配過(guò)程。</p><p><b>　　設(shè)計(jì)原理</b></p><p>　　FIRST(X)(XVNVT)的構(gòu)造</p><p>　　連續(xù)使用下面的規(guī)則，直至每個(gè)集合FIRST不再增大為止：</p><p>　　(1). 若XVT，則FIRST(X)={X};</p><p>　　(2).

31、若XVN，且有產(chǎn)生式X—>a…，則把a(bǔ)加入到FIRST(X)中；若X—>$(表示空字符串)也是一條產(chǎn)生式，則把$也加到FIRST(X)中。</p><p>　　(3)若X—>Y…是一個(gè)產(chǎn)生式且YVN，則把FIRST(Y)中的所有非$元素都加到FIRST(X)中；若X—>Y1Y2…Yk是一個(gè)產(chǎn)生式，Y1,…,Yi-1都是非終結(jié)符，而且，對(duì)于任何j,1<=j<=i-1，F(xiàn)IRST(

32、Yj)都含有$(即Y1…Yi-1=>$)，則把FIRST(Yj)中的所有非$元素都加到FIRST(X)中；特別是，若所有的FIRST(Yj)均含有$,j=1,2,…,k,則把$加到FIRST(X)中。</p><p>　　如上可得到FIRST(X) (XVNVT)。</p><p>　　函數(shù)getFIRST() (=X1X2X3…Xn)的構(gòu)造</p><p>

33、　　之前已經(jīng)實(shí)現(xiàn)了FIRST(X) (XVNVT)，現(xiàn)在我們能夠?qū)ξ姆℅的任何符號(hào)串=X1X2…Xn構(gòu)造集合FIRST(a)。</p><p>　　首先，置FIRST()=FIRST(X1)\{$};若對(duì)任1<=j<=i-1,$FIRST(Xj),則把FIRST(Xi)\{$}加至FIRST()中；特別是，若所有FIRST(Xj)均含有$,1<=j<=n,則把$也加至FIRST()中。顯然

34、，若=$,則FIRST()={$}。</p><p>　　如上可得到getFIRST() (=X1X2X3…Xn)。</p><p>　　FOLLOW(A) (AVN)的構(gòu)造</p><p>　　對(duì)于文法G的每個(gè)非終結(jié)符A構(gòu)造FOLLOW(A)的辦法是，連續(xù)使用下面的規(guī)則，直至每個(gè)FOLLOW不再增大為止。</p><p>　　(1). 對(duì)于

35、文法的開(kāi)始符號(hào)S，置#于FOLLOW(S)中；</p><p>　　(2). 若A—>B是一個(gè)產(chǎn)生式，則把FIRST()\{$}加至FOLLOW(B)中；</p><p>　　(3). 若A—>B是一個(gè)產(chǎn)生式，或A—>B是一個(gè)產(chǎn)生式而=>$(即$FIRST()),則把FOLLOW(A)加至FOLLOW(B)。</p><p>　　如上可得到F

36、OLLOW(A) (AVN)的構(gòu)造。</p><p>　　分析表M【A,a】的構(gòu)造</p><p>　　在對(duì)文法G的每個(gè)終結(jié)符A及其任意候選a都構(gòu)造出FIRST(a)(2.2節(jié)的getFIRST(a)),和FOLLOW(A)(2.3節(jié)的FOLLOW(A))之后,我們現(xiàn)在可以用它們來(lái)構(gòu)造G的分析表M【A,a】。</p><p>　　構(gòu)造分析表M的算法是：</p&

37、gt;<p>　　(1). 對(duì)文法G的每個(gè)產(chǎn)生式A—>執(zhí)行第2步和第3步；</p><p>　　(2). 對(duì)每個(gè)終結(jié)符aFIRST(),把A—>加至M【A,a】中；</p><p>　　(3). 若$FIRST(),則對(duì)任何aFOLLOW(A)把A—>加至M【A,a】中；</p><p>　　(4). 把所有無(wú)定義的M【A,a】標(biāo)上“

38、出錯(cuò)標(biāo)志“。</p><p>　　如上可得到M【A,a】。 </p><p><b>　　匹配過(guò)程的實(shí)現(xiàn)</b></p><p>　　對(duì)于任何(A,a),總控程序每次都執(zhí)行下述三種可能的動(dòng)作之一：</p><p>　　(1). 若X=a=’#’,則宣布分析成功，停止分析過(guò)程。</p><p>　　

39、(2). 若X=a!=’#’,則把X從stack棧頂逐出，讓a指向下一個(gè)輸入符號(hào)。</p><p>　　(3). 若X是一個(gè)非終結(jié)符，則查看分析表M。若M【A,a】中存放著關(guān)于X的一個(gè)產(chǎn)生式，那么把X逐出stack棧頂，然后，把產(chǎn)生式的右部符號(hào)串按反序一一推進(jìn)stack棧(若右部符號(hào)為$,則意味不推什么東西進(jìn)棧)。若M【A,a】中存放著“出錯(cuò)標(biāo)志“，則中斷匹配，顯示出錯(cuò)信息。</p><p&g

40、t;<b>　　程序設(shè)計(jì)</b></p><p><b>　　總體方案設(shè)計(jì)</b></p><p>　　(1). Main()調(diào)用input(),讀入文法G的有關(guān)內(nèi)容：G(VT,VN,S,&);</p><p>　　(2). Main()調(diào)用createFIRST(),實(shí)現(xiàn)FIRST(X),(XVTVN);<

41、/p><p>　　(3). 內(nèi)部程序中通過(guò)調(diào)用getFIRST(string)得到字符串的FIRST終結(jié)符；</p><p>　　(4). Main()調(diào)用createFOLLOW(),實(shí)現(xiàn)FOLLOW(A),(AVN);</p><p>　　(5). Main()調(diào)用createTABLE(),創(chuàng)建LL(1)分析表M【A,a】；</p><p>

42、;　　(6). Main()調(diào)用match (string)對(duì)任一輸入的字符串進(jìn)行匹配，判斷其是否合法，并且顯示匹配過(guò)程；</p><p><b>　　各模塊的實(shí)現(xiàn)</b></p><p>　　(1). void input()</p><p>　　VT,VN都是以字符存儲(chǔ)的，numVT表示VT的數(shù)目，numVN表示VN的數(shù)目。VT標(biāo)號(hào)0—nu

43、mVT-1，VN標(biāo)號(hào)numVT—numVT+numVN-1。函數(shù)findV(char)和V(int)分別實(shí)現(xiàn)字符索引和索引字符間的轉(zhuǎn)換($用nunVT+numVN索引)。</p><p>　　產(chǎn)生式&以字符串的方式讀入，經(jīng)過(guò)comsume()函數(shù)處理。產(chǎn)生式存在TT[i]的vector數(shù)組中(numVT<=i<numVT+numVN，i為VN標(biāo)號(hào))。每個(gè)T[i]都是一個(gè)string的vecto

44、r數(shù)組，存儲(chǔ)V[i]的所有產(chǎn)生式。</p><p>　　input ( )函數(shù)代碼如下：</p><p>　　void input() //存儲(chǔ)文法G的有關(guān)內(nèi)容</p><p><b>　　{</b></p><p>　　//memset:作用是在一段內(nèi)存塊中填充某個(gè)給定的值，它對(duì)較大的結(jié)構(gòu)體或數(shù)組進(jìn)行清零操作的一種最

45、快方法</p><p>　　memset(FIRST,0,sizeof(FIRST)); //把FIRST【】清零</p><p>　　memset(FOLLOW,0,sizeof(FOLLOW));//把FOLLOW【】清零</p><p><b>　　char cc;</b></p><p>　　string ss

46、;</p><p>　　int top=0;</p><p>　　cout<<"please input the set of VT(end by '0')"<<endl;//手動(dòng)輸入終結(jié)符，以結(jié)尾</p><p>　　while(cin>>cc&&cc!='0'

47、)</p><p>　　V[top++]=cc;</p><p>　　numVT=top;</p><p>　　cout<<"please input the set of VN(end by '0')"<<endl;//手動(dòng)輸入非終結(jié)符，以結(jié)尾</p><p>　　while(ci

48、n>>cc&&cc!='0')</p><p>　　V[top++]=cc;</p><p>　　numVN=top-numVT;</p><p>　　V[top]='$';</p><p>　　cout<<"please input the start VN&

49、quot;<<endl; //手動(dòng)輸入文法開(kāi)始符號(hào)</p><p>　　cin>>Start;</p><p>　　cout<<"please input the chanshengshi(end line by '0')"<<endl; //手動(dòng)輸入文法產(chǎn)生式，以結(jié)尾</p><p

50、>　　while(cin>>ss&&ss[0]!='0')</p><p>　　consume(ss);</p><p><b>　　}</b></p><p>　　(2). void createFIRST()</p><p>　　用布爾數(shù)組FIRST[i][j](0&

51、lt;=i,j<=numVT+numVN)來(lái)存儲(chǔ)VTVN的開(kāi)始終結(jié)字符信息。FIRST[i][j]==1表示V[j]FIRST[V[i]],否則表示V[j]FIRST[V[i]]。</p><p>　　先初始化FIRST[i][j](0<=i,j<=numVT+numVN)為false，然后while循環(huán)按3.2.2 1的構(gòu)造規(guī)則進(jìn)行構(gòu)造，用len[i](0<=i<numVT+nu

52、mVN)來(lái)記錄上一次循環(huán)處理后各個(gè)終結(jié)符與非終結(jié)符X的開(kāi)始終結(jié)字符數(shù)目(即FIRST(X))。每次循環(huán)結(jié)束檢測(cè)len[i]并更新。若檢測(cè)到任一0<=i<numVT+numVN,都有l(wèi)en[i]==num(FIRST(i)),則說(shuō)明已構(gòu)造完畢，跳出while循環(huán)，函數(shù)結(jié)束返回。</p><p>　　createFIRST( )代碼如下：</p><p>　　void create

53、FIRST() //存儲(chǔ)VT VN的開(kāi)始終結(jié)字符信息</p><p><b>　　{</b></p><p>　　int len[maxV];</p><p>　　memset(len,-1,sizeof(len));</p><p>　　int i,j,t,no;</p><p>　　for(

54、i=0;i<numVT;i++)</p><p>　　FIRST[i][i]=1;</p><p>　　bool sign=1;</p><p>　　while(sign)</p><p><b>　　{</b></p><p>　　for(i=numVT;i<numVT+numVN;

55、i++)</p><p><b>　　{</b></p><p>　　for(j=0;j<TT[i].size();j++)</p><p><b>　　{ </b></p><p>　　int pp=findV(TT[i][j][0]);</p><p>　　if(p

56、p<numVT||TT[i][j][0]=='$')</p><p><b>　　{</b></p><p>　　FIRST[i][pp]=1;</p><p><b>　　continue;</b></p><p><b>　　}</b></p&g

57、t;<p>　　bool sign2;</p><p>　　for(t=0;t<TT[i][j].size();t++)</p><p><b>　　{</b></p><p><b>　　sign2=0;</b></p><p>　　no=findV(TT[i][j][t]);

58、</p><p><b>　　int iter;</b></p><p>　　for(iter=0;iter<numVT;iter++)</p><p>　　if(FIRST[no][iter]) FIRST[i][iter]=1;</p><p>　　if(FIRST[no][numVT+numVN])</

59、p><p><b>　　{</b></p><p><b>　　sign2=1;</b></p><p>　　if(t==TT[i][j].size()-1) FIRST[i][numVT+numVN]=1;</p><p><b>　　} </b></p>

60、<p>　　if(sign2==0) break; </p><p><b>　　} </b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　sign=0;</b><

61、/p><p>　　for(i=numVT;i<numVT+numVN;i++)</p><p><b>　　{</b></p><p>　　int plen=0;</p><p>　　for(j=0;j<numVT;j++)</p><p>　　if(FIRST[i][j]) plen++

62、;</p><p>　　if(FIRST[i][numVT+numVN]) plen++;</p><p>　　if(len[i]!=plen) sign=1;</p><p>　　len[i]=plen;</p><p><b>　　}</b></p><p><b>　　}</

63、b></p><p><b>　　}</b></p><p>　　(3). vector<char> getFIRST(string str)</p><p>　　對(duì)于字符串str，該函數(shù)返回str的開(kāi)始終結(jié)符數(shù)組。</p><p>　　可根據(jù)3.2.2 2的規(guī)則實(shí)現(xiàn)，對(duì)字符串的字符依次分析，將得到

64、的開(kāi)始</p><p>　　終結(jié)字符存儲(chǔ)到臨時(shí)vector<char>數(shù)組tmp中，函數(shù)結(jié)束返回tmp數(shù)組。</p><p>　　vector<char> getFIRST(string str)代碼如下：</p><p>　　vector<char> getFIRST(string str) //返回str的開(kāi)始終結(jié)符數(shù)組&l

65、t;/p><p><b>　　{</b></p><p>　　vector<char> tmp;</p><p>　　if(str.size()==0) return tmp;</p><p>　　if(str=="$")</p><p><b>　　{<

66、;/b></p><p>　　tmp.push_back('$');</p><p>　　return tmp;</p><p><b>　　}</b></p><p>　　int i,j,no;</p><p>　　bool sign;</p><p&g

67、t;　　for(i=0;i<str.size();i++)</p><p><b>　　{</b></p><p><b>　　sign=0;</b></p><p>　　no=findV(str[i]);</p><p><b>　　int iter;</b></

68、p><p>　　for(iter=0;iter<numVT;iter++)</p><p>　　if(FIRST[no][iter]) tmp.push_back(V[iter]);</p><p>　　if(FIRST[no][numVT+numVN])</p><p><b>　　{</b></p>

69、<p><b>　　sign=1;</b></p><p>　　if(i==str.size()-1) tmp.push_back('$');</p><p><b>　　}</b></p><p>　　if(!sign) break;</p><p><b>　

70、　}</b></p><p>　　return tmp;</p><p><b>　　}</b></p><p>　　(4). void createFOLLOW()</p><p>　　用布爾數(shù)組FOLLOW[i][j](numVT<=i<numVT+numVN,0<=j<numVT

71、)來(lái)存儲(chǔ)VN的緊接終結(jié)字符信息。FOLLOW[i][j]==1表示V[j]FOLLOW[V[i]],否則表示V[j]FOLLOW[V[i]]。</p><p>　　先初始化FOLLOW[i][j](0<=i,j<numVT+numVN)為false,然后先根據(jù)3.2.2 3的規(guī)則進(jìn)行構(gòu)造。接著while循環(huán)(3)規(guī)則用len[i](numVT<=i<numVT+numVN)來(lái)記錄上一次

72、循環(huán)處理后各個(gè)非終結(jié)符A的緊接終結(jié)字符數(shù)目(即FOLLOW(X))。每次循環(huán)結(jié)束檢測(cè)len[i]并更新。若檢測(cè)到任一numVT<=i<numVT+numVN,都有l(wèi)en[i]==num(FIRST(i)),則說(shuō)明已構(gòu)造完畢，跳出while循環(huán)，函數(shù)結(jié)束返回。</p><p>　　void createFOLLOW()代碼如下：</p><p>　　void createFOLL

73、OW() //求得文法G中每個(gè)終結(jié)符的FOLLOW集</p><p><b>　　{</b></p><p>　　int len[maxV];</p><p>　　memset(len,0,sizeof(len));</p><p>　　int i,j,t,no;</p><p>　　no=fi

74、ndV(Start);</p><p>　　FOLLOW[no][findV('#')]=1;</p><p>　　for(i=numVT;i<numVT+numVN;i++)</p><p><b>　　{</b></p><p>　　for(j=0;j<TT[i].size();j++)&

75、lt;/p><p><b>　　{</b></p><p>　　for(t=0;t<TT[i][j].size();t++)</p><p><b>　　{</b></p><p>　　no=findV(TT[i][j][t]);</p><p>　　if(no>=n

76、umVT&&no!=numVT+numVN)</p><p><b>　　{</b></p><p><b>　　int tt;</b></p><p>　　if(t<TT[i][j].size()-1)</p><p><b>　　{</b></p

77、><p>　　vector<char> tmp=getFIRST(TT[i][j].substr(t+1,TT[i][j].size()-t-1));</p><p>　　for(tt=0;tt<tmp.size();tt++)</p><p>　　if(tmp[tt]!='$') FOLLOW[no][findV(tmp[tt])]=

78、1;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b><

79、;/p><p>　　bool sign=1;</p><p>　　while(sign)</p><p><b>　　{</b></p><p>　　for(i=numVT;i<numVT+numVN;i++)</p><p><b>　　{</b></p>

80、<p>　　for(j=0;j<TT[i].size();j++)</p><p><b>　　{</b></p><p>　　for(t=0;t<TT[i][j].size();t++)</p><p><b>　　{</b></p><p>　　no=findV(TT[i]

81、[j][t]);</p><p>　　if(no>=numVT&&TT[i][j][t]!='$')</p><p><b>　　{</b></p><p><b>　　int tt;</b></p><p>　　if(t<TT[i][j].size()-

82、1) </p><p><b>　　{</b></p><p>　　vector<char> tmp=getFIRST(TT[i][j].substr(t+1,TT[i][j].size()-t-1));</p><p>　　for(tt=0;tt<tmp.size();tt++)</p><p>&l

83、t;b>　　{</b></p><p>　　if(tmp[tt]=='$')</p><p>　　{ </p><p><b>　　int iter;</b></p><p>　　for(iter=0;iter<numVT;iter++)</p>

84、<p>　　if(FOLLOW[i][iter]) FOLLOW[no][iter]=1;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}&l

85、t;/b></p><p><b>　　else</b></p><p><b>　　{</b></p><p><b>　　int iter;</b></p><p>　　for(iter=0;iter<numVT;iter++)</p><p

86、>　　if(FOLLOW[i][iter]) FOLLOW[no][iter]=1;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b><

87、;/p><p><b>　　}</b></p><p><b>　　sign=0;</b></p><p>　　for(i=numVT;i<numVT+numVN;i++)</p><p><b>　　{</b></p><p>　　int plen=

88、0;</p><p>　　for(j=0;j<numVT;j++)</p><p>　　if(FOLLOW[i][j]) plen++;</p><p>　　if(len[i]!=plen) sign=1;</p><p>　　len[i]=plen;</p><p><b>　　}</b>

89、</p><p>　　} </p><p><b>　　}</b></p><p>　　(5). void createTABLE()</p><p>　　用字符串?dāng)?shù)組M[i][j]來(lái)存儲(chǔ)棧內(nèi)符V[i]與輸入字符V[j]的匹配</p><p>　　產(chǎn)生式，若不匹配，則為

90、空。</p><p>　　按照3.2.2 4的規(guī)則進(jìn)行棧頂字符和字符串的字符的依次匹配，匹配</p><p>　　處理結(jié)束后，函數(shù)結(jié)束返回。</p><p>　　void createTABLE ( )代碼如下：</p><p>　　void createTABLE() //構(gòu)建預(yù)測(cè)分析表</p><p><

91、;b>　　{ </b></p><p>　　int i,j,t;</p><p>　　for(i=numVT;i<numVT+numVN;i++)</p><p><b>　　{ </b></p><p>　　for(j=0;j<TT[i].size();j++)</p>

92、;<p><b>　　{ </b></p><p>　　string tmp=TT[i][j];</p><p>　　vector<char> first=getFIRST(tmp);</p><p>　　bool sign=0;</p><p>　　for(t=0;t<first.s

93、ize();t++)</p><p><b>　　{</b></p><p>　　if(first[t]=='$') sign=1;</p><p><b>　　else </b></p><p><b>　　{</b></p><p>

94、　　string str(1,V[i]);</p><p>　　M[i][findV(first[t])]=str+"->"+TT[i][j];</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　if(si

95、gn)</b></p><p><b>　　{</b></p><p><b>　　int iter;</b></p><p>　　for(iter=0;iter<numVT;iter++)</p><p><b>　　{ </b></p>&l

96、t;p>　　string str(1,V[i]);</p><p>　　if(FOLLOW[i][iter]) M[i][iter]=str+"->"+TT[i][j];</p><p><b>　　}</b></p><p><b>　　}</b></p><p>

97、<b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　(6). bool match (string str)</p><p>　　用棧來(lái)實(shí)現(xiàn)匹配算法：</p><p>　　棧stac

98、k用來(lái)存放文法符號(hào)。分析開(kāi)始時(shí)，棧底先存放一個(gè)’#’,然后放入文法開(kāi)始符號(hào)。同時(shí)，假定輸入串之后也總有一個(gè)’#’,標(biāo)志輸入串結(jié)束。</p><p>　　預(yù)測(cè)分析程序的總控程序在任何時(shí)候都是按stack棧頂符號(hào)X和當(dāng)前的輸入符號(hào)a行事的。對(duì)具體情況根據(jù)規(guī)則3.2.2 5的3種處理方式之一進(jìn)行處理。處理完后，函數(shù)結(jié)束返回。</p><p>　　bool match (string str)代

99、碼如下：</p><p>　　bool match(string str) //用棧來(lái)實(shí)現(xiàn)匹配算法</p><p><b>　　{</b></p><p>　　str=str+"#";</p><p>　　cout<<"步驟\t"<<"符號(hào)棧\t

100、"<<"輸入串\t"<<"產(chǎn)生式"<<endl; </p><p>　　int num=0;</p><p>　　char stack[maxV];</p><p>　　int top=0;</p><p>　　stack[top++]='#'

101、;;</p><p>　　stack[top++]=Start;</p><p>　　cout<<num<<"\t"<<'#'<<Start<<"\t"<<str<<endl;</p><p>　　int i=0,j;</

102、p><p>　　while(i<str.size())</p><p><b>　　{</b></p><p>　　char A=stack[top-1];</p><p>　　if(A!='#'&&findV(A)==-1) return false;</p><p

103、>　　if(str[i]!='#'&&findV(str[i])==-1) return false;</p><p>　　string tmp;</p><p>　　if(A=='#')</p><p><b>　　{</b></p><p>　　if(A==str

104、[i]) return true;</p><p>　　else return false;</p><p><b>　　}</b></p><p>　　else if(findV(A)<numVT)</p><p><b>　　{</b></p><p>　　if(A

105、==str[i])</p><p><b>　　{</b></p><p><b>　　top--;</b></p><p><b>　　i++;</b></p><p><b>　　}</b></p><p>　　else ret

106、urn false;</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　tmp=M[findV(A)][findV(str[i])];</p><p>　　i

107、f(tmp!="ERROR")</p><p><b>　　{</b></p><p><b>　　top--;</b></p><p>　　if(tmp[3]!='$') </p><p><b>　　{</b></p>&l

108、t;p>　　for(j=tmp.size()-1;j>=3;j--)</p><p>　　stack[top++]=tmp[j];</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　else return false;</p>

109、<p><b>　　}</b></p><p>　　stack[top]='\0';</p><p>　　cout<<++num<<"\t"<<stack<<"\t"<<str.substr(i,str.size()-i)<<&

110、quot;\t"<<tmp<<endl;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　(7)int main()函數(shù)</p><p>　　程序的主要功能均在main（）函數(shù)里面實(shí)現(xiàn)，首先是輸入文法的相關(guān)信息，然

111、后是創(chuàng)建FIRST表和FOLLOW表（不輸出），再輸出預(yù)測(cè)分析表，最后提示輸入句子，判斷是否是該文法的句型，程序?qū)崿F(xiàn)了多次輸入：</p><p>　　int main() 函數(shù)代碼如下：</p><p>　　int main() //主函數(shù)</p><p><b>　　{ </b></p><p>　　cout<

112、<"**************預(yù)測(cè)分析程序**************"<<endl;</p><p><b>　　input();</b></p><p>　　createFIRST();</p><p>　　createFOLLOW();</p><p>　　createTAB

113、LE();</p><p><b>　　int i,j;</b></p><p>　　cout<<"**************預(yù)測(cè)分析表**************"<<endl;</p><p>　　cout<<"\t"<<"i\t"

114、<<"+\t"<<"*\t"<<"(\t"<<")\t"<<"#\t"<<endl;</p><p>　　for(i=numVT;i<numVT+numVN;i++)</p><p><b>　　{ &l

115、t;/b></p><p>　　cout<<V[i]<<'\t';</p><p>　　for(j=0;j<numVT;j++)</p><p><b>　　{</b></p><p>　　if(M[i][j].size()>0) cout<<M[i]

116、[j]<<"\t";</p><p>　　else cout<<"ERROR"<<"\t";</p><p><b>　　}</b></p><p>　　cout<<endl;</p><p><b>　

117、　} </b></p><p>　　string str;</p><p><b>　　char s;</b></p><p><b>　　bool bl;</b></p><p><b>　　do</b></p><p><b>

118、　　{</b></p><p>　　cout<<"**************分析輸入串**************"<<endl;</p><p>　　cout<<"please input the string"<<endl;</p><p><b>　

119、　cin>>str;</b></p><p>　　if(match(str)) cout<<"YES"<<endl;</p><p>　　else cout<<"NO"<<endl; </p><p>　　cout<<"continu

120、e? (y or n)"<<endl;</p><p><b>　　cin>>s;</b></p><p>　　}while(s=='y');</p><p>　　if (s=='n')</p><p>　　system("pause"

121、);</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　開(kāi)發(fā)工具的選擇</b></p><p>　　Visual studio2008</p><p><b>　　程序測(cè)

122、試</b></p><p>　　程序的調(diào)試結(jié)果如下：</p><p>　　程序的運(yùn)行結(jié)果如下：</p><p><b>　　有關(guān)技術(shù)的討論</b></p><p>　　本次課程設(shè)計(jì)主要實(shí)現(xiàn)了以下功能：實(shí)現(xiàn)對(duì)LL(1)文法預(yù)測(cè)分析表的構(gòu)造，使得該文法變的一目了然，從而為判斷輸入符號(hào)串是否是該文法的句型做鋪墊。&

123、lt;/p><p>　　總的來(lái)說(shuō)本次課設(shè)基本上實(shí)現(xiàn)了相應(yīng)的功能，但仍存在一定的問(wèn)題，需要進(jìn)一步的思考，由于時(shí)間限制和本人能力這方面，做的不是很完美，沒(méi)有實(shí)現(xiàn)程序自動(dòng)的求解FRIST集和FOLLOW集，在輸出預(yù)測(cè)分析表的時(shí)候沒(méi)有把對(duì)應(yīng)的非終結(jié)符列輸入進(jìn)去，那樣的話(huà)預(yù)測(cè)分析表會(huì)更加的直觀(guān)和美觀(guān)，此部分功能還有待改進(jìn)。如果以后能把此次課設(shè)程序的輸出用MFC界面做出來(lái)就更好了。</p><p><

124、;b>　　收獲與體會(huì)</b></p><p>　　通過(guò)這次實(shí)驗(yàn)，使我對(duì)LL(1)文法的預(yù)測(cè)分析程序更加了解了，對(duì)FIRST(X)與FOLLOW(A)的構(gòu)造和認(rèn)識(shí)更加深刻了，也掌握了LL(1)預(yù)測(cè)分析表的建立的方法，學(xué)會(huì)了總控程序的匹配過(guò)程，實(shí)現(xiàn)了對(duì)某一句子的分析，更讓我再次復(fù)習(xí)了編譯原理課程學(xué)過(guò)的知識(shí)，尤其是自頂向下語(yǔ)法分析方法的許多知識(shí)。</p><p>　　通過(guò)本次課

125、設(shè)，我明白了：1、學(xué)習(xí)一定要扎實(shí)，穩(wěn)扎穩(wěn)打，學(xué)好每一門(mén)功課，每一章節(jié)的知識(shí)，如果不掌握基本的書(shū)本知識(shí)，做出來(lái)的程序肯定實(shí)現(xiàn)不了太多的功能；2、要善于發(fā)現(xiàn)問(wèn)題，解決問(wèn)題，當(dāng)遇到障礙的時(shí)候，要學(xué)會(huì)放松，更要多思考，也許很快就會(huì)找到問(wèn)題的突破口；3、要多與他人交流，學(xué)會(huì)團(tuán)隊(duì)協(xié)作的能力，三人行必有我?guī)?，一個(gè)人思考問(wèn)題，可能會(huì)考慮不周，但是人多力量大，集思廣益，集體的智慧是廣大的；4、多動(dòng)手編寫(xiě)程序，養(yǎng)成良好的編程風(fēng)格，代碼要縮進(jìn)編排，變量的命名

126、規(guī)則要始終保持一致，最好多寫(xiě)注釋。</p><p>　　最后感謝在此次課程設(shè)計(jì)里幫助我的所有同學(xué)，也感謝老師平日里的勤勞教學(xué)和諄諄教導(dǎo)！?。?lt;/p><p><b>　　參考文獻(xiàn)</b></p><p>　　【1】《編譯原理》（第二版）,主編：呂映芝、張素琴、蔣維杜, 出版社：清華大學(xué)出版社,出版時(shí)間：2004年11月</p>&

127、lt;p>　　【2】《編譯原理課程設(shè)計(jì)》,主編：王雷、劉志成、周晶, 出版社：機(jī)械工業(yè)出版社, 出版時(shí)間：2005年3月</p><p>　　【3】《編譯原理學(xué)習(xí)指導(dǎo)》,主編：胡元義、柯麗芳, 出版社：西安電子科技大學(xué)出版社, 出版時(shí)間：2004年1月</p><p>　　【4】《編譯原理實(shí)踐教程》,主編：胡