【正文】 第一篇：編譯原理課程設(shè)計(jì) LL遞歸下降分析器仲愷農(nóng)業(yè)技術(shù)學(xué)院編譯原理課程設(shè)計(jì)課程設(shè)計(jì)題目 ：LL(1)遞歸下降分析器姓名 ： 院（系）：專業(yè)班級 ： 學(xué)號 ：指導(dǎo)教師 ：設(shè)計(jì)日期 ：目 錄需求分析...................................................................................................1概要設(shè)計(jì)...................................................................................................2詳細(xì)設(shè)計(jì)...................................................................................................3測試分析...................................................................................................8用戶手冊...................................................................................................9課程總結(jié)...................................................................................................9參考文獻(xiàn).................................................................................................10題目：LL（1）遞歸下降分析器需求分析語法分析是編譯過程的核心部分。語法分析器的任務(wù)是識別和處理比單詞更大的語法單位。如：程序設(shè)計(jì)語言中的表達(dá)式，各種說明和語句乃至全部源程序，指出其中的語法錯誤；必要時，可生成內(nèi)部形式，便于下一階段處理。我們知道，語言的語法結(jié)構(gòu)是用上下文無關(guān)文法描述的。按照語法分析樹的建立方法，我們可以粗略地把語法分析辦法分成兩類，一類是自上而下分析，另一類是自下而上分析法。而自上而下這種方法是帶“回溯”的，且存在許多困難和缺點(diǎn)。首先，是文法的左遞歸性問題。一個文法是含有左遞歸的，如果存在非終結(jié)符P且+P222。Pa，含有左遞歸的文法使上述的自上而下的分析過程陷入無限循環(huán)。即，當(dāng)試圖用P去匹配輸入串時，我們會發(fā)現(xiàn)，在沒有識別任何輸入符號的情況下，有得重新要求P去進(jìn)行新的匹配。因此，使用自上而下分析法必須消除文法的左遞歸性。其次，由于回溯，就碰到一大堆麻煩問題。如果我們走了一大段錯路，最后必須回頭，那么，就應(yīng)把已經(jīng)做的一大堆語義工作（指中間代碼產(chǎn)生工作和各種表格的簿記工作）推倒重來。這些事情既麻煩又費(fèi)時間，所以，最好應(yīng)設(shè)法消除回溯。第三，在自上而下分析過程中，當(dāng)一個非終結(jié)符用某一候選匹配成功時，這種成功可能僅是暫時的。第四，當(dāng)最終報(bào)告分析不成功時，我們難于知道輸入串中出錯的確切位置。最后，由于帶回溯的自上而下分析實(shí)際上采用了一種窮盡一切可能的試探法，因此，效率很低，代價極高。嚴(yán)重的低效使得這種分析法只有理論意義，而在實(shí)踐上價值不大。由于上述原因，我們需要把原算術(shù)表達(dá)式改寫為LL(1)文法，LL(1)文法的文法條件如下： 文法不含左遞歸。對于文法中每一個非終結(jié)符A的各個產(chǎn)生式的候選首集符兩兩不相交。即，若A174。a1|a2|K|an，則FIRST(ai)199。FIRST(aj)=f (i185。j)對文法中的每個非終結(jié)符A，若它存在某個候選首符集包含ε，則FIRS(TA)199。FOLLO(WA)=fLL(1)中的第一個L表示從左到右掃描輸入串，第二個L表示最左推導(dǎo)，1表示分析時每 一步只需向前查看一個符號。當(dāng)一個文法滿足LL(1)條件時，我們就可以為它構(gòu)造一個不帶回溯的自上而下分析程序，這個分析程序是由一組遞歸過程組成的，每個過程對應(yīng)文法的一個非終結(jié)符。這樣的一個分析程序稱為遞歸下降分析器。概要設(shè)計(jì)編程實(shí)現(xiàn)給定算術(shù)表達(dá)式的遞歸下降分析器。算術(shù)表達(dá)式文法如下： EE+T|ET|T TT*F|T/F|F F(E)| i 首先改寫文法為LL(1)文法；然后為每一個非終結(jié)符，構(gòu)造相應(yīng)的遞歸過程，過程的名字表示規(guī)則左部的非終結(jié)符；過程體按規(guī)則右部符號串的順序編寫。上述算法表達(dá)式文法屬于比較典型的遞歸下降語法分析。需要先將原算術(shù)表達(dá)式方法改寫為LL(1)文法為：ETE’E’+TE’|TE’| ε TFT’T’*FT’|/FT’| ε F(E)| i 然后再為每個非終結(jié)符設(shè)計(jì)一個對應(yīng)的函數(shù)，通過各函數(shù)之間的遞歸調(diào)用從而實(shí)現(xiàn)遞歸下降語法分析的功能。具體方法為：（1）當(dāng)遇到終結(jié)符a時，則編寫語句If(當(dāng)前讀到的輸入符號==a)讀入下一個輸入符號（2）當(dāng)遇到非終結(jié)符A時，則編寫語句調(diào)用A()。（3）當(dāng)遇到Aε規(guī)則時，則編寫語句If(當(dāng)前讀到的輸入符號不屬于Follow(A))error()（4）當(dāng)某個非終結(jié)符的規(guī)則有多個候選式時，按LL(1)：圖1遞歸下降子程序流程圖詳細(xì)設(shè)計(jì)include char inputstream[50]。//存儲輸入句子 int temp=0。//數(shù)組下標(biāo) int right。//判斷輸出信息 void e()。void e1()。void t()。void t1()。void f()。void main(){}void e(){}void e1()right=1。coutinputstream。coutTE39?！眪void t(){} if(inputstream[temp]==39。+39。){} else if(inputstream[temp]==39。39。){} else if(inputstream[temp]!=39。39。||inputstream[temp]!=39。)39。){} else right=0。cout^”TE39?！?TE39?！盕T39?！眎f(inputstream[temp]==39。*39。){} else if(inputstream[temp]==39。/39。){} else cout/FT39。”*FT39?！眪void f(){{} cout^”i”} } elseif(inputstream[temp]==39。(39。){cout(E)”} else } right=0。cout(E)”測試分析圖2 測試分析成功圖3 測試分析失敗用戶手冊開發(fā)工具：visual c++ 開發(fā)環(huán)境：windows XP操作系統(tǒng)運(yùn)行環(huán)境：windows 9x,windows NT,Windows 2000,windows XP 注意：輸入時，程序最多只能接受50個字符，輸入完算術(shù)表達(dá)式后要以“”號結(jié)束。課程總結(jié)通過一個星期的努力，終于把編譯原理課程設(shè)計(jì)給完成了。我覺得編譯原理這門課是一門非常難學(xué)的課程，它涉及文法、詞法分析、語法分析屬性文法和語義分析等等一系列內(nèi)容，課本里的內(nèi)容和定義也非常的抽象且枯燥。如果上課沒有好好的認(rèn)真聽課，自己獨(dú)自學(xué)習(xí)就感到非常的吃力，而且效果也不好。本人因?yàn)樯险n無法做到打醒十二分專心聽課，經(jīng)常會分神，所以學(xué)習(xí)的效果也不怎么好。這也給做編譯原理課程設(shè)計(jì)帶來了困難。本次課程設(shè)計(jì)，我選的課程設(shè)計(jì)題目是LL(1)遞歸下降分析器，這個題目涉及的內(nèi)容有關(guān)課本第四章 語法分析——自上而下分析里面的內(nèi)容。在開始動手對題目進(jìn)行設(shè)計(jì)和編程之前，我重復(fù)的仔細(xì)認(rèn)真的閱讀和理解課本第四章里面的內(nèi)容，弄懂自上而下分析面臨的問題、何謂左遞歸，搞清楚如何消除左遞歸、如何消除回溯、提左因子，理解構(gòu)造LL(1)文件需要什么條件。雖然這花費(fèi)了一定的時間和精力，但那點(diǎn)付出也是值得的，通過復(fù)習(xí)讓我加深理解了有關(guān)自上而下語法分析的內(nèi)容，而且也為用高級語言實(shí)現(xiàn)遞歸下降分析器帶來便利。在用C++編程時，基本上沒有遇到什么困難，只需把所有遞歸過程都寫出就行了。但是要注意的是，在編寫代碼時，要根據(jù)LL(1)文法的工作原理去設(shè)計(jì)。通過本次課程設(shè)計(jì)清楚地了解到遞歸下降分析法的優(yōu)缺點(diǎn)，其優(yōu)點(diǎn)是簡單、直觀，易于構(gòu)造分析程序。缺點(diǎn)是對文法要求高，必須是LL(1)文法，同時由于遞歸調(diào)用較多，影響分析器的效率。課程設(shè)計(jì)雖然只有短短的一周，但讓我認(rèn)識到學(xué)習(xí)好編譯原理，是對程序設(shè)計(jì)和編譯的一個很好的進(jìn)化橋梁和奠基石。今后學(xué)習(xí)的日子還很長，希望通過這次編譯原理的課程設(shè)計(jì)，不僅對編程語言的進(jìn)一步復(fù)習(xí)，還是對更深層次的學(xué)習(xí)作一個簡單的準(zhǔn)備。編程的能力不是一朝一夕能鍛煉出來，堅(jiān)持學(xué)習(xí)，堅(jiān)持編程的學(xué)習(xí)，多看，多編是最好的學(xué)習(xí)和提高方法。通過本次編譯原理課程設(shè)計(jì)，對面向?qū)ο蟮亩x又有了更深一步的理解，對編譯程序有了進(jìn)一步的理解，同時也認(rèn)識到自己各方面知識的薄弱點(diǎn)，以后在學(xué)習(xí)中也能有針對性對這方面進(jìn)行深入學(xué)習(xí)。學(xué)習(xí)更好的知識重在基礎(chǔ)，編譯原理的學(xué)習(xí)為我們提供非常好的橋梁和道路。參考文獻(xiàn)《編譯原理》 機(jī)械工業(yè)出版社出版Alfred Ravi Sethi Jeffrey D,Ullman著李建中 姜守旭等譯《程序設(shè)計(jì)語言 編譯原理（第三版）》 國防工業(yè)出版社出版陳火旺 劉春林 譚慶平趙克佳 劉越 著第二篇：《編譯原理》課程設(shè)計(jì)報(bào)告詞法分析器201X201X學(xué)年第x學(xué)期《編譯原理》課程設(shè)計(jì)報(bào)告院 系： 計(jì)算機(jī)科學(xué)與技術(shù) 班 級： XX級XX 班 學(xué)生姓名： XXXXXX 學(xué) 號： XXXXXXXX 指導(dǎo)老師： XXXXXX計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院監(jiān)制20XX年X月目錄 附件1：參考文獻(xiàn) 附件2：核心源代碼（1）編寫詞法分析器（2）加深對詞法分析器工作原理的了解和認(rèn)識編寫詞法分析器，詞法分析器能夠識別關(guān)系算符，詞法分析器能夠識別標(biāo)識符和關(guān)鍵字，詞法分析器能夠識別無符號數(shù)。構(gòu)成詞法分析器的一種簡單方法是用狀態(tài)轉(zhuǎn)換圖來描述源語言詞法記號的結(jié)構(gòu)，然后手工把這種狀態(tài)轉(zhuǎn)換圖翻譯成為識別詞法記號的程序。詞法分析器的任務(wù)是把構(gòu)成源程序的字符流翻譯成詞法記號流。把自然語言構(gòu)造成正規(guī)式，把正規(guī)式構(gòu)造成有限自動機(jī)NFA，然后根據(jù)子集構(gòu)造法把有限自動機(jī)構(gòu)造成無限自動機(jī)DFA，根據(jù)極小化DFA狀態(tài)數(shù)算法把DFA構(gòu)造成最簡DFA,其次根據(jù)最簡DFA畫出轉(zhuǎn)換表，根據(jù)轉(zhuǎn)換表畫出裝換圖，最后根據(jù)裝換圖就可以編寫詞法分析器。通過本次試驗(yàn)，不僅僅是我學(xué)會了C基礎(chǔ)知識，而且還是我對詞法分析器有了更深入的認(rèn)識，雖然在編寫詞法分析器過程中遇到了很多困難，例如：C語言不熟悉，對此法分析器的工作原理分析的不透徹，但在老師和同學(xué)的幫助下，我有了很大的提高，通過不斷的努力最終順利的完成了課程設(shè)計(jì)，很感謝幫助我的XX同學(xué)和XX老師。附件1：參考文獻(xiàn)《編譯原理（第2版）》 高等教育出版社； 《C程序設(shè)計(jì)及應(yīng)用教程（第2版）》 人民教育出版社。附件2：1．Code文檔截圖using System。using 。using 。using 。namespace LexicalAnalysis { class Program { static string[] keys = { “static”, “true”, “return”, “string”, “Length”, “break”, “Console”, “WriteLine”, “bool”, “false”, “ture”, “void”, “if”, “else”, “while”, “int”, “float”, “for”, “enum”, “default”, “case”, “double”, “do” }。static List key = new List()。//保存關(guān)鍵字static List bsf = new List()。//保存標(biāo)識符static List sz = new List()。//保存數(shù)字static List gx = new List()。//保存關(guān)系運(yùn)算符static List ys = new List()。//保存數(shù)字運(yùn)算符//數(shù)字，標(biāo)識符，空白，關(guān)系符,運(yùn)算符static void Main(string[] args){string[] date = (@“d:”)。//路徑，并存入datafor(int i = 0。i 。i++){ (“第” +(i + 1)+ “行code: ” + (i))。analysisByLine(date[i])。} //分別輸出存儲在四個List中的String(“關(guān)鍵字，輸入回車”)。//輸出所有的關(guān)鍵字 ()。foreach(string id in key){ (id)。}(“標(biāo)識符，輸入回車”)。//輸出所有的標(biāo)識符()。foreach(string id in bsf){ (id)。}(“數(shù)字，輸入回車”)。()。foreach(string id in sz){ (id)。}(“關(guān)系運(yùn)算符，輸入回車”)。()。foreach(string id in gx){ (id)。}(“算數(shù)運(yùn)算符，輸入回車”)。()。foreach(string id in ys){ (id)。}(“輸入回車退出”)。()。} static void analysisByLine(string code)//輸出所有的數(shù)字 //輸出所有的關(guān)系運(yùn)算符//輸出所有的算數(shù)運(yùn)算符{char a = 39。 39。string temp = “。int j = 0。while(j ){ a = code[j]。temp = ”“。if((a