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

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁(yè)數(shù)：23 大小：206.00KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

編譯原理課程設(shè)計(jì)報(bào)告---first、follw求解報(bào)告書_第1頁(yè)

已閱讀1頁(yè)，還剩22頁(yè)未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說(shuō)明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、　　編譯原理課程設(shè)計(jì)報(bào)告　　選題名稱: FIRST、FOLLOW求解 　　系（院）: 計(jì)算機(jī)工程學(xué)院　　專業(yè):計(jì)算機(jī)科學(xué)與技術(shù)（軟件工程方向）　　班級(jí): 軟件1082

2、 　　姓名: 學(xué) 號(hào): 　　指導(dǎo)教師: 　　學(xué)年學(xué)期: 2011 ~ 2012 學(xué)年第 1 學(xué)期　　2012 年 01 月 07 日

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

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

5、FOLLOW集　　目錄　　1 課題綜述1　　1.1 課題來(lái)源1　　1.2 課題意義1　　1.3 預(yù)期目標(biāo)1<p&g

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

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

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

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

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

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

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

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

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

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

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

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

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

19、，則FIRST（X）；　?、?若X→Y1Y2…Yn是產(chǎn)生式：　　(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)中；　　(II)若所有的FIRST(Yi)均能，i＝

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

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

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

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

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

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

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

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

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

29、e ArrayList blist = new ArrayList();　　private ArrayList phresultstringlist = new ArrayList();　　public Form1()　　{　　Ini

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

47、#39;));　　listView1.Items.Add(item);　　}　　}　　}　　private void

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

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

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

51、gt;　　}　　else if (str.Length == 0)　　{　　MessageBox.Show("沒(méi)?有瓺文?件t讀á入?!");　　}

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

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

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

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

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

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

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

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

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

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

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

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

64、ist()　　{　　return blist;　　}　　public void setBlist(ArrayList blist)　　{

65、　　this.blist = blist;　　}　　public ArrayList getClist()　　{　　return cl

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

67、t;　　}　　public String getStr()　　{　　return str;　　}　　public void setSt

68、r(String str)　　{　　this.str = str;　　}　　public ArrayList getFirstlist()

69、;　　{　　return firstlist;　　}　　public void setFirstlist(ArrayList firstlist)　　{

70、　　this.firstlist = firstlist;　　}　　public ArrayList getPointfirstlist()　　{　　return pointfi

71、rstlist;　　}　　public void setPointfirstlist(ArrayList pointfirstlist)　　{　　this.pointfirstlist = poi

72、ntfirstlist;　　}　　public ArrayList getResultfirstlist()　　{　　return resultfirstlist;<

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

74、t;　　}　　public ArrayList getResultfollowlist()　　{　　return resultfollowlist;　　}&

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

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

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

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

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

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

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

眾賞文庫(kù)> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無(wú)特殊說(shuō)明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

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

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

編譯原理課程設(shè)計(jì)報(bào)告---first、follw求解報(bào)告書

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載

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