1、河南大學(xué)2007屆本科畢業(yè)論文自頂向下語法分析教學(xué)輔助軟件的開發(fā)development of a teaching aid software of top-down syntax analysis論文作者姓名：韓罡 所在學(xué)院：計算機與信息工程學(xué)院 所學(xué)專業(yè)：計算機科學(xué)與技術(shù) 導(dǎo)師姓名職稱：張連堂(教授)袁彩虹(助教) 論文完成時間：2007年5月20日 2007年5月20日河南大學(xué)2007屆畢業(yè)論文（設(shè)計、創(chuàng)作）開題報告（由學(xué)生本人認真填寫）學(xué)號03023192姓名韓罡導(dǎo)師姓名職稱張連堂(教授)袁彩虹(助教)開題時間2006年12月1日課題題目自頂向下語法分析教學(xué)輔助軟件的開發(fā)課題來源導(dǎo)師指定

2、 自定 其他來源課題的目的、意義以及和本課題有關(guān)的國內(nèi)外現(xiàn)狀分析：1、目的：開發(fā)一個自頂向下語法分析教學(xué)輔助軟件。2、意義：自頂而下的語法分析是編譯原理課程中的一個核心理論，由于理論的抽象性，常規(guī)的教學(xué)手段很收到理想的教學(xué)效果，而教學(xué)輔助軟件能以更形象化的方式把內(nèi)容表達出來。因此，自頂向下語法分析教學(xué)輔助軟件的開發(fā)有利于提高教學(xué)質(zhì)量，幫助學(xué)生自學(xué)。3、現(xiàn)狀：隨著大學(xué)教育的改革，更多課程采用了先進教學(xué)手段，教學(xué)軟件的開發(fā)在學(xué)校教育領(lǐng)域成為了一種潮流和趨勢。研究目標、研究內(nèi)容和準備解決的問題：自頂而下的語法分析是編譯原理課程中一個十分重要的部分，同時它也是考試的重點和難點。因此，本著輔助教學(xué)的目的

3、，軟件總體上要有友好的界面，良好的交互性，較強的實用性。內(nèi)容方面，ll（1）文法是一種能夠進行確定、無回溯自頂而下語法分析的描述工具，軟件要能夠把整個ll（1）的分析過程清晰、準確、直觀的展示出來。給定一個文法，首先應(yīng)實現(xiàn)first集合和follow集合的求解，實現(xiàn)預(yù)測分析表的構(gòu)造，然后進行l(wèi)l（1）文法確定性的判斷，最后，給定輸入串，進行預(yù)測分析。擬采取的方法、技術(shù)或設(shè)計（開發(fā)）工具：在設(shè)計過程中，擬采用隊列幫助first集合和follow集合的求解，采用棧作為自頂向下語法分析過程中核心的數(shù)據(jù)結(jié)構(gòu)。擬采用的開發(fā)工具：visual studio 2005預(yù)期成果：1、畢業(yè)設(shè)計成果自頂向下語法分

4、析教學(xué)輔助軟件2、畢業(yè)論文自頂向下語法分析教學(xué)輔助軟件的開發(fā)進度計劃：2006.12.1 - 2007.4.1：查找資料、搜集相關(guān)素材2007.4.2 - 2007.4.11：完成總體界面部分的設(shè)計2007.4.12 - 2007.4.21：完成first和follow的程序?qū)崿F(xiàn)部分的設(shè)計2007.4.22 - 2007.4.30：完成預(yù)測分析表和分析過程部分的設(shè)計2007.5.1 - 2007.5.20：整理資料、撰寫畢業(yè)論文2007.5.20 - 2007.5.25：根據(jù)導(dǎo)師要求，完善畢業(yè)設(shè)計和論文指導(dǎo)教師對選題報告的意見： 同意開題 指導(dǎo)教師簽名： 2006年12月 1日河南大學(xué)2007

5、屆畢業(yè)論文（設(shè)計、創(chuàng)作）任務(wù)書學(xué)號03023192姓名韓罡導(dǎo)師姓名張連堂（教授）袁彩虹（助教）任務(wù)書起止日期2006年12月8日 至 2007年5月20日論文提要：在完成課題調(diào)研的基礎(chǔ)上，論文打算分四部分來介紹：第一部分介紹本軟件的開發(fā)背景、開發(fā)目標，以及開發(fā)平臺。第二部分介紹自頂向下語法分析中的一些相關(guān)理論，如ll(1)文法的概念、預(yù)測分析程序等。第三部分介紹軟件的具體開發(fā)過程，包括界面設(shè)計、核心算法的實現(xiàn)和相關(guān)類的介紹。最后，介紹測試結(jié)果。課題任務(wù)要求：1、深刻理解自頂向下語法分析中的理論。2、應(yīng)實現(xiàn)first集合和follow集合的求解，實現(xiàn)預(yù)測分析表的構(gòu)造，然后進行l(wèi)l（1）文法確定性

6、的判斷，最后給定輸入串，進行預(yù)測分析。3、軟件要有友好的界面，良好的交互性，較強的實用性。主要參考文獻：1陳火旺、劉春林編著，編譯原理，國防工業(yè)出版社，2000年1月2(英)john sharp 著，周靖譯，visual c# 2005從入門到精通，清華大學(xué)出版社，2006年6月3陳志泊、李冬梅等著，數(shù)據(jù)庫原理及應(yīng)用教程，人民郵電出版社，2002年3月4張敬和著，編譯原理實用教程，清華大學(xué)出版社，2005年4月5嚴蔚敏著，數(shù)據(jù)結(jié)構(gòu)，清華大學(xué)出版社，2002年3月河南大學(xué)2007屆畢業(yè)設(shè)計（論文、創(chuàng)作）中期檢查表學(xué)院名稱：計算機與信息工程學(xué)院題目名稱自頂向下語法分析教學(xué)輔助軟件的設(shè)計學(xué)號0302

7、3192所學(xué)專業(yè)計算機科學(xué)與技術(shù)指導(dǎo)教師姓 名張連堂袁彩虹姓名韓罡一、畢業(yè)設(shè)計進展情況截止4月10日為止：1、查找資料、搜集相關(guān)素材已經(jīng)完成2、軟件的總體框架和思路已確定3、軟件界面也已經(jīng)完成 二、存在問題1、沒有很好的理解相關(guān)算法的精髓，阻礙了設(shè)計進度2、界面的設(shè)計效果不是特別的理想三、下一階段的研究方法或設(shè)計思路1、根據(jù)總體設(shè)計流程和框架結(jié)構(gòu)，進行核心部分的實現(xiàn)。2、重點研究first集和follow集的算法實現(xiàn)問題，3、利用比較合理的數(shù)據(jù)結(jié)構(gòu)，設(shè)計好的實現(xiàn)方法。四、指導(dǎo)教師對學(xué)生設(shè)計（論文、創(chuàng)作）進展等方面的評語該生能按計劃完成資料、素材的收集，并進行了界面設(shè)計，但是，對算法本身理解不透

8、，設(shè)計的界面不夠友好，應(yīng)注意改進，并注意進度。 指導(dǎo)教師簽字： 2007年4月10日 此表除第四項外由學(xué)生填寫指導(dǎo)教師簽名河南大學(xué)2007屆畢業(yè)論文（設(shè)計、創(chuàng)作）綜合成績表（一）學(xué)院名稱：計算機與信息工程學(xué)院學(xué) 號03023192姓名韓罡專業(yè)計算機科學(xué)與技術(shù)指導(dǎo)教師張連堂（副教授）、袁彩虹（助教）綜合得分82論文題目自頂向下語法分析教學(xué)輔助軟件的開發(fā)指導(dǎo)教師評語及得分指導(dǎo)教師評語該生論文結(jié)構(gòu)清晰，邏輯合理，描述準確，符合本科生畢業(yè)論文標準。評分項目分值指導(dǎo)教師對畢業(yè)論文（設(shè)計、創(chuàng)作）評分撰寫開題報告、文獻綜述15調(diào)查研究查閱整理資料10學(xué)習(xí)態(tài)度與規(guī)范要求10數(shù)據(jù)處理、文字表達10論文（設(shè)計、創(chuàng)

9、作）質(zhì)量和創(chuàng)新意識55合計100得分128874681指導(dǎo)教師簽名 2007年5月20日評閱教師評語及評分評閱教師評語該生論文語言通順，表達清晰、準確，結(jié)構(gòu)合理，符合本科生畢業(yè)論文標準。評分項目分值評閱畢業(yè)論文（設(shè)計、創(chuàng)作）評分撰寫開題報告、文獻綜述15調(diào)查研究查閱整理資料10學(xué)習(xí)態(tài)度與規(guī)范要求10數(shù)據(jù)處理、文字表達10論文（設(shè)計、創(chuàng)作）質(zhì)量和創(chuàng)新意識55合計100得分138874783評閱教師簽名 2007年5月22日此表由教師填寫河南大學(xué)2007屆畢業(yè)論文（設(shè)計、創(chuàng)作）綜合成績表（二）學(xué)號03023192姓名韓罡所在學(xué)院計算機與信息工程學(xué)院答辯委員會評語及評分答辯委員會評語該生回答問題思路

10、清晰，表達準確。 答辯委員簽字： 2007年5月26日評分 項目 分值論文答辯小組評分答辯情況論文質(zhì)量合計（100）內(nèi)容表達情況（15）答辯問題情況（25）規(guī)范要求與文字表達（20）論文（設(shè)計、創(chuàng)作）質(zhì)量和創(chuàng)新意識（40）得分1220153582答辯委員會主任簽字： 2007年5月26日畢業(yè)論文（設(shè)計、創(chuàng)作）成績綜合評定： 82 分綜合評定等級：良備注：一、論文的質(zhì)量評定，應(yīng)包括對論文的語言表達、結(jié)構(gòu)層次、邏輯性理論分析、設(shè)計計算、分析和概括能力及在論文中是否有新的見解或創(chuàng)新性成果等做出評價。從論文來看學(xué)生掌握本專業(yè)基礎(chǔ)理論和基本技能的程度。二、成績評定采用結(jié)構(gòu)評分法，即由指導(dǎo)教師、評閱教師和

11、答辯委員會分別給分（以百分計），評閱教師得分乘以20%加上指導(dǎo)教師得分乘以20%加上答辯委員會得分乘以60%即綜合成績。評估等級按優(yōu)、良、中、差劃分，優(yōu)90-100分；良76-89分；中60-75分；差60分以下。三、評分由專業(yè)教研室或院組織專門評分小組（不少于5人），根據(jù)指導(dǎo)教師和答辯委員會意見決定每個學(xué)生的分數(shù)，在有爭議時，應(yīng)由答辯委員會進行表決。四、畢業(yè)論文答辯工作結(jié)束后，各院應(yīng)于6月20日前向教務(wù)處推薦優(yōu)秀論文以匯編成冊，推薦的篇數(shù)為按當年學(xué)院畢業(yè)生人數(shù)的1.5%篇。五、各院亦可根據(jù)本專業(yè)的不同情況，制定相應(yīng)的具有自己特色的內(nèi)容。須報教務(wù)處備案。六、書寫格式要求：1、目錄；2、內(nèi)容提要

12、須書寫200左右漢字，開題報告（文科除外）的內(nèi)容要根據(jù)不同專業(yè)的課題任務(wù)要求，闡述查閱文獻、文案論證、解題思路、工作步驟等；3、正文（含引言、結(jié)論等）；4、參考文獻（或資料）河南大學(xué)本科生畢業(yè)論文（設(shè)計、創(chuàng)作）承諾書論文題目自頂向下語法分析教學(xué)輔助軟件的開發(fā)姓 名韓罡所學(xué)專業(yè)計算機科學(xué)與技術(shù)學(xué) 號03023192完成時間2007年5 月20日指導(dǎo)教師姓名職稱張連堂（教授）、袁彩虹（助教）承諾內(nèi)容：1、本畢業(yè)論文（設(shè)計、創(chuàng)作）是學(xué)生韓罡在導(dǎo)師張連堂、袁彩虹的指導(dǎo)下獨立完成的，沒有抄襲、剽竊他人成果，沒有請人代做，若在畢業(yè)論文（設(shè)計、創(chuàng)作）的各種檢查、評比中被發(fā)現(xiàn)有以上行為，愿按學(xué)校有關(guān)規(guī)定接受處

13、理，并承擔(dān)相應(yīng)的法律責(zé)任。2、學(xué)校有權(quán)保留并向上級有關(guān)部門送交本畢業(yè)論文（設(shè)計、創(chuàng)作）的復(fù)印件和磁盤。備注：學(xué)生簽名： 指導(dǎo)教師簽名： 2007年5月20日 2007年5月20日說明：學(xué)生畢業(yè)論文（設(shè)計、創(chuàng)作）如有保密等要求，請在備注中明確，承諾內(nèi)容第2條即以備注為準。目 錄摘 要iabstractii第1章 緒論11.1 開發(fā)背景11.2 開發(fā)目標11.3 開發(fā)平臺2第2章 基本原理概述32.1 基本知識32.2 ll(1)文法的概念32.3 預(yù)測分析程序4第3章 軟件設(shè)計與實現(xiàn)53.1 界面設(shè)計53.2 核心算法的實現(xiàn)73.2.1 first集合求解算法實現(xiàn)73.2.2 follow集合求

14、解算法實現(xiàn)83.2.3 select集合求解算法實現(xiàn)93.2.4 ll(1)文法的判定實現(xiàn)93.2.5 語法正確性判斷實現(xiàn)103.2.6 預(yù)測分析表構(gòu)造和分析過程實現(xiàn)103.3 相關(guān)類的介紹11第4章 系統(tǒng)的運行與測試124.1 界面的運行效果124.2 系統(tǒng)的測試14結(jié) 論17參考文獻18摘 要自頂而下語法分析是編譯原理課程中的一個核心理論，由于理論的抽象性，常規(guī)的教學(xué)手段很難收到理想的教學(xué)效果，而教學(xué)輔助軟件能以更形象化的方式把內(nèi)容表達出來，因此教學(xué)輔助軟件的開發(fā)十分必要。本論文以介紹該教學(xué)輔助軟件的開發(fā)為核心，首先介紹開發(fā)背景、開發(fā)目標、開發(fā)平臺及軟件的基本功能；然后簡單介紹軟件開發(fā)中用

15、到的基礎(chǔ)理論，其中包括ll（1）文法等概念；接下來詳細闡述軟件的具體開發(fā)過程，其中，first集合、follow集合算法的實現(xiàn)是核心，這個實現(xiàn)的過程中用到了隊列，在進行語法分析時用到了棧；最后對軟件進行簡單的測試，檢查是否達到了預(yù)期目的。關(guān)鍵詞 自頂向下語法分析，first集合，follow集合，預(yù)測分析表abstracttop-down syntax analysis is a core theory in the compiler principle . because this theory is abstract , conventional teaching means can no

16、t receive very good teaching results. but, teaching aid software can be a more figurative way to convey the content of expression.so development of a teaching aid software is very necessary.this paper mainly introduces the process of development. firstly, it introduces the background, the objective,

17、 the platform and the basic functions.secondly, basic theory, such as ll(1) syntax analysis concepts ,etc, which is used in this paper is simply introduced.thirdly, it elaborates specific process of the development, in which implementation of the algorithm of first sets and follow sets is the core.

18、queue is used to it and in the process of syntax analysis stack is applied. finally, it is a simple test,which can check the effect of the teaching aid software.keywords top-down syntax analysis,first sets, follow sets, predicting and analyzing table第1章 緒論自頂而下的語法分析是編譯原理課程中的一個重要內(nèi)容，其教學(xué)輔助軟件的開發(fā)對編譯原理教學(xué)有著

19、重要作用。本章介紹本軟件的開發(fā)背景、開發(fā)目標，以及開發(fā)平臺。1.1 開發(fā)背景隨著計算機的迅速普及，計算機軟件的發(fā)展也正是方興未艾，它已經(jīng)滲透到社會的各個領(lǐng)域和各個行業(yè)，并率先應(yīng)用于大學(xué)教學(xué)領(lǐng)域。考慮到讓這些現(xiàn)代化教育資源的投資發(fā)揮應(yīng)有的作用，大家都很重視計算機輔助教學(xué)的推廣和應(yīng)用。教師和學(xué)生都希望能得到高質(zhì)量、使用方便的教學(xué)軟件。而廠商也看到計算機教學(xué)輔助軟件將會形成有潛力的市場，而積極投入了教學(xué)軟件的開發(fā)和經(jīng)營。教學(xué)輔助軟件正是在這個大環(huán)境下逐漸有了一定的市場的，正因為它具有良好的圖形界面，交互性更強，更容易被人們所接受，所以受到了教育界的普遍歡迎。在計算機專業(yè)課的學(xué)習(xí)過程中，由于所涉及的內(nèi)

20、容比較抽象，理解起來比較困難，教學(xué)輔助軟件可以把抽象化的概念用更加形象的方式表達出來，從而激發(fā)學(xué)生的學(xué)習(xí)興趣，提高學(xué)習(xí)效率。1.2 開發(fā)目標自頂而下的語法分析是編譯原理課程中一個十分重要的部分，同時它也是考試的重點和難點。因此，本著輔助教學(xué)的目的，軟件總體上要有友好的界面，良好的交互性，較強的實用性。內(nèi)容方面，ll（1）文法是一種能夠進行確定、無回溯自頂而下語法分析的描述工具，軟件要能夠把整個ll（1）的分析過程清晰、準確、直觀的展示出來。給定一個文法，首先應(yīng)實現(xiàn)first集合和follow集合的求解，實現(xiàn)預(yù)測分析表的構(gòu)造，然后進行l(wèi)l（1）文法確定性的判斷，最后給定輸入串，進行預(yù)測分析。1.

21、3 開發(fā)平臺在開發(fā)的過程中使用了visual studio 2005開發(fā)平臺。visual studio 2005是.net 2003的優(yōu)化版和改進版，具有改進的可視化設(shè)計器。因為ll(1)分析器的核心內(nèi)容是一些復(fù)雜算法的實現(xiàn)，選擇這個平臺可以方便界面設(shè)計，把精力集中于算法實現(xiàn)。另外visual studio 2005自帶打包工具，在開發(fā)出來一個軟件以后更加利于后期的管理，無需使用專門的打包軟件，就可以進行打包。只要安裝了framework sdk v2.0就可以直接運行打過包的軟件，使用起來方便、簡單。隨著c#2.0的問世，語言新增了幾個重要的特性，例如arraylist類、迭帶器以及正則表

22、達式，本設(shè)計中就用到了這些。第2章 基本原理概述本章介紹自頂向下語法分析中的基本原理和概念，為后面的具體開發(fā)打下基礎(chǔ)。2.1 基本知識在進行軟件的設(shè)計過程中，需要了解以下基本的知識和概念。1、終結(jié)符號：是組成語言的基本符號，終結(jié)符號是一個語言的不可再分的基本符號，即單詞符號，一般用英文小寫字母表示。終結(jié)符號集通常用vt表示。2、非終結(jié)符號：一個非終結(jié)符號代表一個一定的語法概念，是一個類記號，它表示一定符號串的集合，通常用大寫英文字母表示。非終結(jié)符號集通常用vn表示。3、開始符號：是一個特殊的非終結(jié)符號，是進行分析的入口。4、產(chǎn)生式：是定義語法范疇的一種書寫規(guī)則。5、上下文無關(guān)文法：是文法的一種

23、，用來定義語言的語法結(jié)構(gòu)，所定義的語法范疇完全獨立于這種范疇可能出現(xiàn)的環(huán)境。表示為（vt, vn,s,p），其中vt代表終結(jié)符號集，vn代表非終結(jié)符號集，s代表開始符號，p代表產(chǎn)生式集合，一個產(chǎn)生式的形式是“a”，其中a是非終結(jié)符號，是由終結(jié)或非終結(jié)符號組成的字符串，即（vtvn）*。2.2 ll(1)文法的概念在自頂向下語法分析中，會出現(xiàn)回溯以及虛假匹配問題，并且由于文法的左遞歸性，會造成死循環(huán)。為避免以上問題，進行確定的、無回溯的自上而下分析，引入了ll(1)文法。它屬于上下文無關(guān)文法的范疇，該文法滿足以下特點：1、文法不含左遞歸；2、對于文法中每一個非終結(jié)符號a的各個產(chǎn)生式的侯選首符集兩

24、兩不相交。即若a1|2|n，則first(i)first(j)=；3、對于文法的每個非終結(jié)符號a,若它存在某個侯選首符集含（空字）,則first (a)follow(a)=。2.3 預(yù)測分析程序預(yù)測分析表是一個ma,a形式的矩陣。其中a為非終結(jié)符，a是終結(jié)符或#，#不是文法符號，我們總是把它當成輸入串的結(jié)束符。矩陣元素ma,a中也存放著一條關(guān)于a的產(chǎn)生式，指出當a面臨輸入符號a時應(yīng)采用的侯選。ma,a中也可能存放一個“出錯標志”，指出a根本不該面臨輸入符號a。預(yù)測分析過程的每一步，都是取出棧頂符號和當前輸入符號，并查看預(yù)測分析表進行的。預(yù)測分析器結(jié)構(gòu)如圖2-1所示。第3章 軟件設(shè)計與實現(xiàn)本章主

25、要介紹軟件的具體開發(fā)過程，包括界面設(shè)計、核心算法的實現(xiàn)和相關(guān)類的介紹。3.1 界面設(shè)計按照軟件的設(shè)計流程，首先進行界面的設(shè)計。作為教學(xué)輔助軟件，界面應(yīng)簡明、小巧、實用，軟件總體界面如圖3-1所示。圖3-1 系統(tǒng)總體界面1、界面中的“幫助說明”以電子書(chm格式)的形式展現(xiàn)出，需要先設(shè)計一個chm文檔，以便作為模版使用。system.diagnostics.process.start(path);/打開幫助說明文檔軟件的輸入界面，用一個tabepage控件來進行設(shè)計，分別是終結(jié)符和非終結(jié)符、文法規(guī)則、自頂而下的語法分析三個頁面。2、在輸入終結(jié)符和非終結(jié)符的頁面中用到了兩個textbox的文本框

26、，分別用來顯示終結(jié)符號和非終結(jié)符號，或者可以自行編輯，在打開文件的過程中需要用流來讀取文件，它的實現(xiàn)方法如下。private void btnloadsymbols_click(object sender, eventargs e)/打開文件的單擊事件。tryusing (streamreader sr=new streamreader(ofiledlg.filename)textboxendall.appendtext(strtaskitem + rn);symbolset.getinstance().endallset.add(strtaskitem) sr.colse()在輸入終結(jié)符號和

27、非終結(jié)符號的時候規(guī)定一個字符占一行，這樣使格式更加清晰。3、在文法規(guī)則的頁面上用了一個listbox控件來顯示文法，可以把編輯好的文法保存到一個文件中，保存操作的實現(xiàn)方法如下。private void btnsaveproducts_click(object sender, eventargs e) /存文件的單擊事件。sfiledlg.filter = (*.txt)|*.txt|*.*|*.*;sfiledlg.showdialog();if (sfiledlg.filename != )using (streamwriter sw = new streamwriter(sfiledlg.

28、filename)sw.close();/實現(xiàn)保存文件操作4、運行頁面的設(shè)計過程和上面的相同，最大的特點就是運用到了一個webbrower的組件。它可以把網(wǎng)頁模版和最后結(jié)果顯示在到這個控件上，使得界面效果更加的美觀。outresult(arrayfirst,arrayfollow,arraysellect,hashanalysis) /輸出結(jié)果3.2 核心算法的實現(xiàn)程序的核心是first集合和follow集合的構(gòu)造算法以及預(yù)測分析表的實現(xiàn)問題。3.2.1 first集合求解算法實現(xiàn)1、若xvt，則first(x)=x；2、若xvn，且有產(chǎn)生式xa，avt，則afirst(x)；3、若xvn，且

29、有產(chǎn)生式x，則first(x)；4、若xvn， y1，y2，yi都屬于vn，且有產(chǎn)生式xy1y2yn，當y1,yi-1=(1in)時，則把 first(yi) 去掉后的部分（first(yi)中有的話）放入first(x)中，記為first(yi)/first(x)；當y1,yn*=時，則最終把放入first(x)，即first(x)。在實現(xiàn)的過程中最主要的是第四步的判定，前三步容易實現(xiàn)，不做介紹。在第四步的實現(xiàn)過程中，首先判斷第一個字符是否為非終結(jié)符，設(shè)定一個布爾型掃描標志flag，賦初值true，然后就要掃描后面的每一個字符了，可能會出現(xiàn)以下幾種情況。1、yi如果是非終結(jié)符號，并且能推出空

30、字符串，那么就把first(yi)/加入到first(x)中。2、yi如果是非終結(jié)符號，并且不能推出空字符，那么就把first(yi)直接加入到first(x)中。并且停止對后面字符串的掃描工作。3、yi如果是最后一個符號，那么不管它能否能推出空字符，直接把first(yi)加入到first(x)中。在實現(xiàn)的過程中，為了記錄first(x)用到了哪些其他非終結(jié)符號的first集，引入隊列這種數(shù)據(jù)結(jié)構(gòu)，同時設(shè)置一組布爾型變量記錄first集是否完成，也就是說是否還需要用到其它非終結(jié)符的first集。把那些已經(jīng)完成集合求解的非終結(jié)符號的first集放入到?jīng)]有完成集合求解的非終結(jié)符號的first集中

31、去，沒有完成first集求解的非終結(jié)符號放入隊列。first集的實現(xiàn)用public arraylist firstset()方法：x屬于vt，則first(x)=x 。if (symbolset.getinstance().isinendset(product.leftitem) lstfirsti.add(product.leftitem); 若xvn，且有產(chǎn)生式xa，avt，則afirst(x)。if(symbolset.getinstance().isinendset(strfirstletter) if(!tools.isinlist(strfirstletter,lstfirsti)

32、 lstfirsti.add(strfirstletter) 若xvn，且有產(chǎn)生式x，則first(x)。if(!tools.isinlist(,lstfirsti)lstfirsti.add();上面所說的第四步出現(xiàn)的情況較多，但基本實現(xiàn)過程和前三步類似，使用了5個if語句，不再詳細列舉代碼。private bool checkemptysymbol(string strchar)/檢測空字符public arraylist finishfirst(arraylist firstlist,queue queuefirst)./完成first集的計算,把未求出first集的非終結(jié)符求出publ

33、ic void outfirst(arraylist arylst) /輸出first集3.2.2 follow集合求解算法實現(xiàn)在求follow集時按照以下步驟來進行：1、x是開始符號，把#加入到follow(x)；2、ab是一個產(chǎn)生式，則把first()/加到follow(b)；3、ab是一個產(chǎn)生式，或ab是一個產(chǎn)生式而=，則把follow(a)加入到follow(b)中。follow集合求解算法的實現(xiàn)和first集的類似。在求某個非終結(jié)符first集時先掃描產(chǎn)生式左部不同的產(chǎn)生式，然后掃描左部相同的產(chǎn)生式的每一個右部。而在求follow集的時候，則需要掃描每一個產(chǎn)生式，第一次掃描可以確定哪

34、些first集或follow集屬于所求的follow集，由于first集已經(jīng)求出，所以第一次掃描就可以把相應(yīng)的first集加入到follow集中，設(shè)置follow集完成標記位，設(shè)置隊列，把未完成的非終結(jié)符送入隊列，依次取出隊列元素，把求出follow集的非終結(jié)符的follow集加入到相應(yīng)的follow集中，把未求出的送回隊列。主要的實現(xiàn)方法如下所示：public arraylist followset(arraylist aryfirst)/得到follow集private arraylist followletter(string strchar,arraylistarylstfollow)

35、/ 返回所有產(chǎn)生式右部指定的字符后邊的字母public void outfollow(arraylist arylst)/輸出follow集public string outfirstfollow(arraylist irst,arraylist follow)/輸出first集和follow集到網(wǎng)頁表格3.2.3 select集合求解算法實現(xiàn)1、若是終結(jié)符，那么sellect(a)=。2、若是，則select(a)=follow(a)。3、若是非終結(jié)符那么 若*=，則select(a)= first()follow(a)。 若*=，select(a)=first()。主要的實現(xiàn)方法如下所示：public arraylist selectset(arraylist aryfirst, arraylist aryfollow)