編譯原理課程設(shè)計報告---first、follw求解報告書

1、<p>　　編譯原理課程設(shè)計報告</p><p>　　選題名稱: FIRST、FOLLOW求解 </p><p>　　系（院）: 計算機工程學院</p><p>　　專 業(yè):計算機科學與技術(shù)（軟件工程方向）</p><p>　　班 級: 軟件1082

2、 </p><p>　　姓 名: 學 號: </p><p>　　指導教師: </p><p>　　學年學期: 2011 ~ 2012 學年 第 1 學期</p><p>　　2012 年 01 月 07 日</p><p><b>　

3、　設(shè)計任務(wù)書</b></p><p><b>　　摘要：</b></p><p>　　編譯原理是計算機科學與技術(shù)專業(yè)最重要的一門專業(yè)基礎(chǔ)課程，內(nèi)容龐大，涉及面廣，知識點多。由于該課程教、學難度都非常大，往往費了大量時間而達不到預(yù)期教學效果俗語說：學習的最好方法是實踐。本次課程設(shè)計的目的正是基于此，力求為學生提供一個理論聯(lián)系實際的機會，通過布置一定難度的課題

4、，要求學生獨立完成。我們這次課程設(shè)計的主要任務(wù)是編程實現(xiàn)對給定文法的FIRST集和FOLLOW集的求解。通過實踐，建立系統(tǒng)設(shè)計的整體思想，鍛煉編寫程序、調(diào)試程序的能力，學習文檔編寫規(guī)范，培養(yǎng)獨立學習、吸取他人經(jīng)驗、探索前言知識的習慣，樹立團隊協(xié)作精神。同時，課程設(shè)計可以充分彌補課堂教學及普通實驗中知識深度與廣度有限的缺陷，更好地幫助學生從全局角度把握課程體系。</p><p>　　關(guān)鍵詞：編譯原理；FIRST集；

5、FOLLOW集</p><p><b>　　目錄</b></p><p><b>　　1 課題綜述1</b></p><p>　　1.1 課題來源1</p><p>　　1.2 課題意義1</p><p>　　1.3 預(yù)期目標1</p><p&g

6、t;　　1.4 面對的問題1</p><p>　　1.5 需解決的關(guān)鍵技術(shù)1</p><p><b>　　2 系統(tǒng)分析2</b></p><p>　　2.1 基礎(chǔ)知識2</p><p>　　2.1.1 FIRST集定義2</p><p>　　2.1.2FIRST集求解算法錯誤！未定義書

7、簽。</p><p>　　2.1.3FOLLOW集的定義4</p><p>　　2.1.4 FOLLOW集算法4</p><p>　　2.2 解決問題的基本思路4</p><p>　　2.3 總體方案4</p><p><b>　　3 系統(tǒng)設(shè)計5</b></p><p

8、>　　3.1 算法實現(xiàn)5</p><p><b>　　3.2 流程圖6</b></p><p><b>　　4 代碼編寫10</b></p><p><b>　　5 程序調(diào)試15</b></p><p>　　6 運行與測試15</p><p&

9、gt;<b>　　1 課題綜述 </b></p><p><b>　　1.1 課題來源</b></p><p>　　文法：包含若干終結(jié)符，非終結(jié)符，由終結(jié)符與非終結(jié)符組成的產(chǎn)生式。本次課程設(shè)計就是對產(chǎn)生式進行左遞歸分析，待無左遞歸現(xiàn)象后進行FIRST集與FOLLOW集的求解。</p><p><b>　　1.2

10、課題意義</b></p><p>　　由文法產(chǎn)生的若干個句子有可能是合法的或者不合法的，也有可能產(chǎn)生歧義，所以要消除歧義先消除文法左遞歸，然后根據(jù)求得的FIRST集與FOLLOW集構(gòu)造分析表，分析給定句子的合法性。</p><p><b>　　1.3 預(yù)期目標</b></p><p>　　編寫程序，實現(xiàn)對文法的讀取，判定是否含左遞歸

11、，然后消除左遞歸，并對消除左遞歸的文法進行拆分得到其所有終結(jié)符與非終極符。最后對每一個非終結(jié)符和產(chǎn)生式右部進行FIRST集與FOLLOW集的求解。</p><p><b>　　1.4 面對的問題</b></p><p>　　如何讀取文法，并判斷是否含有左遞歸，怎么得到每一個非終結(jié)符與產(chǎn)生式右部，消除左遞歸，F(xiàn)IRST集與FOLLOW集的求解算法。</p>

12、<p>　　1.5 需解決的關(guān)鍵技術(shù)</p><p>　　本次課程設(shè)計中的關(guān)鍵是：FIRST集與FOLLOW集的求解算法，終結(jié)符 V和V’，多了個帶 ’ 的終結(jié)符，但是它在處理的時候只能當一個符號來識別，而用程序設(shè)計語言表示時它能表示成兩個字符，如果處理不當?shù)脑?，V’就可能被認為是終結(jié)符號V和非終結(jié)符‘。這無疑給處理過程添加了難度。還有一些自認為理所當然能實現(xiàn)的，卻實際并不可取的方法。如：本來JAVA

13、 API有個方法String.split(String s);用于以s 為分割字符，將指定的字符分成字符數(shù)組。但是s 為括號時（無論左右括號，大小括號，方框括號），都不能分割，并且拋異常。這是個很難理解的問題。迫不得已，我不得不想其他的方法來實現(xiàn)分割算法。再有就是對編譯原理中First Follow算法設(shè)計時，采取何種策略效率最高的問題以及如何編寫、調(diào)試、修改代碼。還要了解一個題目有許多種解決方法。鍛煉我們的思維能力。 </p&

14、gt;<p><b>　　2 系統(tǒng)分析</b></p><p><b>　　2.1 基礎(chǔ)知識</b></p><p>　　2.1.1 FIRST集定義</p><p>　　一、關(guān)系圖法求解FIRST：</p><p>　?、僖来螔呙栉姆恳粭l產(chǎn)生式</p><p&g

15、t;　　I．刪除所有右部含終結(jié)符的產(chǎn)生式。若使得以某非終結(jié)符為左部的所有產(chǎn)生式都被刪除，則置該非</p><p>　　終結(jié)符的標記為“否”。</p><p>　　II．若某非終結(jié)符存在一條右部為ε的產(chǎn)生式，則置該非終結(jié)符的標志為“是”，并刪除該非終結(jié)符的所有產(chǎn)生式。</p><p>　?、趻呙璁a(chǎn)生式右部的每一符號</p><p>　　I．若

16、某非終結(jié)符標志為“是”，則刪去該非終結(jié)符，若進而使得某產(chǎn)生式右部為空，則置該式左部的非終結(jié)符標志為“是”，并刪除該非終結(jié)符為左部的所有產(chǎn)生式，如“S”。</p><p>　　II．若某非終結(jié)符標志為“否”，則刪去該產(chǎn)生式，若使得左部為該非終結(jié)符的產(chǎn)生式都被刪去，則置該非終結(jié)符標志為“否”。</p><p>　?、壑貜?fù)上述步驟，直到掃描完一遍文法的產(chǎn)生式，非終結(jié)符標志位不再改變?yōu)橹埂?lt

17、;/p><p>　　按下述步驟從關(guān)系圖求解FIRST。</p><p>　?、俜彩菑腇IRST(A)結(jié)點有路徑可到達的終結(jié)符點所標記的終結(jié)符為FIRST(A)的成員。</p><p>　?、谌裟撤墙K結(jié)符能夠 ε，則將ε加入該非終結(jié)符的FIRST集中。</p><p>　　根據(jù)通用算法構(gòu)造FIRST</p><p>　?。?

18、）文法符號的FIRST</p><p>　　對于文法中的每一個符號X（VN∪VT），構(gòu)造FIRST（X）時，只要連續(xù)使用下列步驟，直至FIRST集不再擴大為止。</p><p>　　步驟1．若XVT，則FIRST（X）＝{X}；</p><p>　　步驟2．若XVN，則考查以X為左部的每一條產(chǎn)生式：</p><p>　?、?若X→是一條產(chǎn)生式

19、，則FIRST（X）；</p><p>　　② 若X→Y1Y2…Yn是產(chǎn)生式：</p><p>　　(I)若Y1, …, Yi-1都?VN且都能（其中1≤i≤n），則FIRST(Y1)-{}，F(xiàn)IRST(Y2)-{}，…，F(xiàn)IRST(Yi-1)-{}和FIRST(Yi)都包含在FIRST(X)中；</p><p>　　(II)若所有的FIRST(Yi)均能，i＝

20、1, 2, …, k，則把加到FIRST(X)中。</p><p>　　2.1.3FOLLOW集的定義</p><p>　　FOLLOW(A)={a|Z?μAβ且a∈Vt,a∈FIRST(β),μ∈Vt*,β∈V+}A∈Vn</p><p>　　若Z μAβ ,且β ε，則#∈FOLLOW(A)</p><p>　　該集合稱為A的后繼符號集

21、合 </p><p>　　或定義為：FOLLOW(A)={a| Z?…Aa…，a∈Vt}A∈Vn,Z識別符號 </p><p>　　特殊地：若Z ..A 則 #∈FOLLOW(A)</p><p>　　2.1.4 FOLLOW集算法</p><p>　　設(shè)S, A, B∈Vn , </p><p>　　算法：連續(xù)使用以

22、下規(guī)則，直至FOLLOW集合不再擴大。</p><p>　　(1)若S為識別符號,則把“#”加入FOLLOW(S)中 ； </p><p>　　(2)若A→αBβ (β≠ε)，則FIRST(β)-{ε}加入FOLLOW(B) 。</p><p>　　(3)若A→αB 或A→αBβ， 且β?ε，則把FOLLOW(A)加 </p><p>　　入

23、FOLLOW(B) 。</p><p>　　2.2 解決問題的基本思路</p><p>　　根據(jù)課程設(shè)計的要求，程序應(yīng)具有如下功能：對輸入的文法進行分析并判斷是否為左遞歸文法。如果是則先消除左遞歸。然后求解FIRST集和FOLLOW集。</p><p><b>　　2.3 總體方案</b></p><p><b&g

24、t;　　3 系統(tǒng)設(shè)計</b></p><p><b>　　3.1 算法實現(xiàn)</b></p><p><b>　　具體過程如下：</b></p><p>　　首先將文法顯示在RichTextBox1上</p><p>　　若有左遞歸，將之消除左遞歸顯示在RichTextBox2上</

25、p><p>　　3、對RichTextBox2上文法調(diào)用First類求FIRST集，顯示在ListView1上。</p><p>　　4、對RichTextBox2上文法調(diào)用Follow類求FOLLOW集，顯示在ListView2上。</p><p><b>　　3.2 流程圖</b></p><p>　　1).UI用戶

26、操作界面控制流圖</p><p>　　2).識別非終結(jié)符集和終結(jié)符集</p><p>　　3).計算各個非終結(jié)符的First集</p><p>　　說明：在求First集合時，主要用的思想是遞歸求解。</p><p>　　4. 計算各個非終結(jié)符的Follow集</p><p><b>　　4 代碼編寫<

27、/b></p><p><b>　　部分代碼如下：</b></p><p>　　public partial class Form1 : Form</p><p><b>　　{</b></p><p>　　Getlist gl = new Getlist();</p><

28、p>　　private ArrayList firstl = new ArrayList();</p><p>　　private ArrayList resultfollowlist = new ArrayList();</p><p>　　private ArrayList alist = new ArrayList();</p><p>　　privat

29、e ArrayList blist = new ArrayList();</p><p>　　private ArrayList phresultstringlist = new ArrayList();</p><p>　　public Form1()</p><p><b>　　{</b></p><p>　　Ini

30、tializeComponent();</p><p><b>　　}</b></p><p>　　private void Form1_Load(object sender, EventArgs e)</p><p><b>　　{</b></p><p><b>　　try</b

31、></p><p><b>　　{</b></p><p>　　StreamReader m_streamReader = new StreamReader("文?法ぁ?txt");</p><p>　　m_streamReader.BaseStream.Seek(0, SeekOrigin.Begin);</p

32、><p>　　string strLine = m_streamReader.ReadLine();</p><p>　　String tempstrline = "";</p><p>　　while (strLine != null)</p><p><b>　　{</b></p>&l

33、t;p>　　tempstrline += strLine + "\n";</p><p>　　strLine = m_streamReader.ReadLine();</p><p><b>　　}</b></p><p>　　m_streamReader.Close();</p><p>　　

34、this.listview.Text = tempstrline;</p><p><b>　　}</b></p><p><b>　　catch</b></p><p><b>　　{ }</b></p><p>　　//判D斷?是?否?含?有瓺左哩?遞蘗歸é<

35、;/p><p>　　if (!IsExitLeftRecur())</p><p><b>　　{</b></p><p>　　this.label2.Visible = true;</p><p>　　this.label3.Visible = true;</p><p>　　this.inputb

36、ox.Visible = true;</p><p>　　this.inputbox.Text = this.listview.Text;</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{ }</b></

37、p><p><b>　　}</b></p><p>　　private bool IsExitLeftRecur()</p><p><b>　　{</b></p><p>　　return false;</p><p><b>　　}</b></p&

38、gt;<p>　　private void button1_Click(object sender, EventArgs e)</p><p><b>　　{</b></p><p>　　listView1.Clear();</p><p>　　Getlist getset = new Getlist();</p>

39、<p>　　String str = inputbox.Text.ToString();</p><p>　　int palist;</p><p>　　First first = new First();</p><p>　　Follow follow = new Follo</p><p>　　if (str.Length &g

40、t;= 100000)</p><p><b>　　{</b></p><p>　　MessageBox.Show("文?件t內(nèi)ú容╕太?大洙?，?換?個?小?些?的?!");</p><p><b>　　}</b></p><p>　　else if (str.Len

41、gth == 0)</p><p><b>　　{</b></p><p>　　MessageBox.Show("沒?有瓺文?件t讀á入?!");</p><p><b>　　}</b></p><p><b>　　else</b></p&g

42、t;<p><b>　　{</b></p><p>　　getset = first.firstscan(str);</p><p>　　//顯?示?部?分?</p><p>　　alist = getset.getAlist();</p><p>　　blist = getset.getBlist();&

43、lt;/p><p>　　firstl = getset.getResultfirstlist();</p><p>　　resultfollowlist = follow.followscan(getset);</p><p>　　gl.setResultfirstlist(firstl);</p><p>　　gl.setResultfollo

44、wlist(resultfollowlist);</p><p>　　gl.setAlist(alist);</p><p>　　gl.setBlist(blist);</p><p>　　listView1.Columns.Add("非?終?結(jié)á符?".PadRight(4, ' '));</p><

45、;p>　　listView1.Columns.Add("first集ˉ".PadRight(6, ' '));</p><p>　　for (palist = 0; palist <= alist.Count - 1; palist++)</p><p><b>　　{</b></p><p>　

46、　ListViewItem item = new ListViewItem(alist[palist].ToString().PadRight(10, ' '));</p><p>　　item.Checked = true;</p><p>　　item.SubItems.Add(firstl[palist].ToString().PadRight(13, ' &

47、#39;));</p><p>　　listView1.Items.Add(item);</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　private void

48、 button2_Click(object sender, EventArgs e)</p><p><b>　　{</b></p><p>　　listView2.Clear();//清?空?現(xiàn)?有瓺項?</p><p>　　int palist;</p><p>　　Getlist getset = new Getl

49、ist();</p><p>　　String str = inputbox.Text.ToString();</p><p>　　First first = new First();</p><p>　　Follow follow = new Follow();</p><p>　　//判D斷?讀á取?的?文?件t是?否?超?過y

50、最?大洙?值μ以?及°是?否?為a空?</p><p>　　if (str.Length >= 100000)</p><p><b>　　{</b></p><p>　　MessageBox.Show("文?件t內(nèi)ú容╕太?大洙?，?換?個?小?些?的?!");</p><p&

51、gt;<b>　　}</b></p><p>　　else if (str.Length == 0)</p><p><b>　　{</b></p><p>　　MessageBox.Show("沒?有瓺文?件t讀á入?!");</p><p><b>　　}

52、</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　getset = first.firstscan(str);</p><p>　　alist = getset.getAlist();</p><p&g

53、t;　　blist = getset.getBlist();</p><p>　　firstl = getset.getResultfirstlist();</p><p>　　resultfollowlist = follow.followscan(getset);</p><p>　　gl.setResultfirstlist(firstl);</p>

54、;<p>　　gl.setResultfollowlist(resultfollowlist);</p><p>　　gl.setAlist(alist);</p><p>　　gl.setBlist(blist);</p><p>　　listView2.Columns.Add("非?終?結(jié)á符?".PadRight(6

55、, ' '));</p><p>　　listView2.Columns.Add("follow集ˉ".PadRight(13, ' '));</p><p>　　for (palist = 0; palist <= alist.Count - 1; palist++)</p><p><b>　　

56、{</b></p><p>　　ListViewItemitem=newListViewItem</p><p>　　(alist[palist].ToString().PadRight(4, ' '));</p><p>　　item.Checked = true;</p><p>　　item.SubItems

57、.Add(resultfollowlist[palist].ToString().PadRight(6, ' '));</p><p>　　listView2.Items.Add(item);</p><p><b>　　}</b></p><p><b>　　}</b></p><

58、;p><b>　　}</b></p><p><b>　　}</b></p><p>　　class Getlist</p><p><b>　　{</b></p><p>　　private String str;//存?放?算?術(shù)?表括?達?式?（輟?如?：阰A-&g

59、t;Sa）?</p><p>　　private ArrayList alist = new ArrayList(); //存?放?箭y頭?前°字?母?</p><p>　　private ArrayList blist = new ArrayList(); //存?放?箭y頭?后ó字?符?串?</p><p>　　private Array

60、List clist = new ArrayList(); //存?放?箭y頭?后ó字?符?串?首骸?地?址·</p><p>　　private ArrayList firstlist = new ArrayList();//存?放?first集ˉ的?表括?</p><p>　　private ArrayList pointfirstlist = new Array

61、List();//用?于?存?放?firstlist的?指?針?地?址·</p><p>　　private ArrayList resultfirstlist = new ArrayList();//存?放?最?終?結(jié)á果?字?符?串?鏈ⅰ?表括?</p><p>　　private ArrayList resultfollowlist = new ArrayLis

62、t();//存?放?最?終?結(jié)á果?字?符?串?鏈ⅰ?表括?</p><p>　　public ArrayList getAlist()</p><p><b>　　{</b></p><p>　　return alist;</p><p><b>　　}</b></p>&

63、lt;p>　　public void setAlist(ArrayList alist)</p><p><b>　　{</b></p><p>　　this.alist = alist;</p><p><b>　　}</b></p><p>　　public ArrayList getBl

64、ist()</p><p><b>　　{</b></p><p>　　return blist;</p><p><b>　　}</b></p><p>　　public void setBlist(ArrayList blist)</p><p><b>　　{

65、</b></p><p>　　this.blist = blist;</p><p><b>　　}</b></p><p>　　public ArrayList getClist()</p><p><b>　　{</b></p><p>　　return cl

66、ist;</p><p><b>　　}</b></p><p>　　public void setClist(ArrayList clist)</p><p><b>　　{</b></p><p>　　this.clist = clist;</p><p><b&g

67、t;　　}</b></p><p>　　public String getStr()</p><p><b>　　{</b></p><p>　　return str;</p><p><b>　　}</b></p><p>　　public void setSt

68、r(String str)</p><p><b>　　{</b></p><p>　　this.str = str;</p><p><b>　　}</b></p><p>　　public ArrayList getFirstlist()</p><p><b>

69、;　　{</b></p><p>　　return firstlist;</p><p><b>　　}</b></p><p>　　public void setFirstlist(ArrayList firstlist)</p><p><b>　　{</b></p>

70、<p>　　this.firstlist = firstlist;</p><p><b>　　}</b></p><p>　　public ArrayList getPointfirstlist()</p><p><b>　　{</b></p><p>　　return pointfi

71、rstlist;</p><p><b>　　}</b></p><p>　　public void setPointfirstlist(ArrayList pointfirstlist)</p><p><b>　　{</b></p><p>　　this.pointfirstlist = poi

72、ntfirstlist;</p><p><b>　　}</b></p><p>　　public ArrayList getResultfirstlist()</p><p><b>　　{</b></p><p>　　return resultfirstlist;</p><

73、p><b>　　}</b></p><p>　　public void setResultfirstlist(ArrayList resultfirstlist)</p><p><b>　　{</b></p><p>　　this.resultfirstlist = resultfirstlist;</p&g

74、t;<p><b>　　}</b></p><p>　　public ArrayList getResultfollowlist()</p><p><b>　　{</b></p><p>　　return resultfollowlist;</p><p><b>　　}&

75、lt;/b></p><p>　　public void setResultfollowlist(ArrayList resultfollowlist)</p><p><b>　　{</b></p><p>　　this.resultfollowlist = resultfollowlist;</p><p>&

76、lt;b>　　}</b></p><p><b>　　}</b></p><p>　　//還有求解FIRST集和FOLLOW集的詳細算法的代碼較多未能附上。</p><p><b>　　5 程序調(diào)試</b></p><p>　　程序中調(diào)用了許多函數(shù)，編寫代碼時會出現(xiàn)調(diào)用的錯誤，使在

77、程序運行時無法正確判斷以致程序運行出錯。在創(chuàng)建函數(shù)時會出現(xiàn)錯誤而無法得知，致使在程序運行時出錯，需要很細心的去編寫代碼，出現(xiàn)錯誤時，使用斷點調(diào)試的方法逐一對每個函數(shù)監(jiān)視。編程的時候一定要細心，對出現(xiàn)的錯誤要認真調(diào)整，反復(fù)修改，使函數(shù)前后相對應(yīng)。 </p><p><b>　　6 運行與測試</b></p><p><b>　　運行界面如下：</b&g

78、t;</p><p>　　得到產(chǎn)生式：消除左遞歸：</p><p>　　FIRST集和FOLLOW集：</p><p><b>　　總結(jié)</b></p><p>　　在經(jīng)過了一個星期的編譯原理課程設(shè)計，我獲益匪淺。本次課程設(shè)計是我們將所學理論知識形成系統(tǒng)的一個鍛煉的好機會，也是學校和老師檢驗我們學習成果

79、的一個方法。經(jīng)過一周的設(shè)計，F(xiàn)IRST集和FOLLOW集的算法可以了然于心。</p><p>　　這次的課程設(shè)計已經(jīng)結(jié)束了，通過編程基本實現(xiàn)了預(yù)期的目標，我們只有不斷的發(fā)現(xiàn)問題，不斷的解決問題，才能使一個程序盡可能的完善。由于經(jīng)驗不足，時間有限，雖然在一周的時間完成了系統(tǒng)的分析、設(shè)計和調(diào)試的工作，但是仍然有許多不足之處，會在以后的學習中努力改正。</p><p><b>　　致

80、謝</b></p><p>　　在這次的課程設(shè)計中，讓我深深地體現(xiàn)到編程不是一件簡單的事情，它需要設(shè)計者具有全面的專業(yè)知識、縝密的思維、嚴謹?shù)墓ぷ鲬B(tài)度以及較高的分析問題、解決問題的能力，而我在很多方面還有欠缺。.感謝各位老師以及同學給我的指導。</p><p><b>　　參 考 文 獻</b></p><p>　　1 編譯原理

81、（第2版）/張素琴，呂映芝，蔣維杜，戴桂蘭編著 北京：清華大學出版社，2008</p><p>　　2 編譯原理及實踐教程/黃賢英, 王柯柯編著 北京:清華大學出版社,2008</p><p>　　3 編譯原理學習輔導/張偉編著 北京:清華大學出版社,2005</p><p>　　4 編譯原理/主編胡延忠, 劉建舟, 林姍