1、編譯原理課程教學(xué)大綱課程編號：20411110總學(xué)時數(shù)：48總學(xué)分?jǐn)?shù)：3課程性質(zhì)：必修課程適用專業(yè)：計算機(jī)科學(xué)與技術(shù)一、課程的任務(wù)和基本要求：編譯原理是計算機(jī)科學(xué)與技術(shù)專業(yè)的一門專業(yè)必修課，在計算機(jī)本科教學(xué)中占有重要地位。本課程主要講解詞法分析、語法分析、語義分析、代碼優(yōu)化、運行時存儲空間組織等基本內(nèi)容，了解目標(biāo)代碼生成、符號表、錯誤處理等。通過本課程的學(xué)習(xí)，使學(xué)生對編譯過程中的基本概念、基本原理和基本實現(xiàn)方法有一個較全面、直觀的認(rèn)識，為后續(xù)課程的學(xué)習(xí)打下必要的基礎(chǔ)。二、基本內(nèi)容和要求：1 緒論教學(xué)內(nèi)容：編譯和解釋，編譯程序、編譯過程概述，編譯程序的結(jié)構(gòu)，編譯程序與程序設(shè)計環(huán)境，編譯階段的組合

2、。教學(xué)要求：（1）熟悉編譯程序的概念；（2）了解編譯程序工作的基本過程及其各階段的基本任務(wù)；（3）熟悉編譯程序總框。2文法和語言的基本知識教學(xué)內(nèi)容：語言語法結(jié)構(gòu)的形式描述，文法和語言的定義，文法的類型，上下文無關(guān)文法，語法分析樹與文法二義性的判斷。教學(xué)要求：（1）熟悉文法的形式化表示；（2）掌握根據(jù)文字?jǐn)⑹鰰鴮懸恍┹^典型的文法的方法；（3）熟悉形式語言的分類；（4）掌握正規(guī)文法及正規(guī)表達(dá)式與上下文無關(guān)文法的相互轉(zhuǎn)換；（5）掌握規(guī)范推導(dǎo)、短語、直接短語、句柄、素短語、語法樹、文法的二義性等基本概念；（6）掌握利用語法樹尋找句型的短語、直接短語和句柄的方法；（7）掌握消除文法的二義性的方法。3.

3、詞法分析教學(xué)內(nèi)容：詞法分析器任務(wù)；正則表達(dá)式；確定有窮自動機(jī)；非確定有窮自動機(jī)；自動機(jī)的確定化；從正則表達(dá)式到DFA的構(gòu)造；由正規(guī)文法構(gòu)造有窮自動機(jī)。教學(xué)要求：（1）熟悉詞法分析器的任務(wù)及輸出形式；（2）了解運用狀態(tài)轉(zhuǎn)換圖進(jìn)行詞法分析器的設(shè)計；（3）掌握正規(guī)表達(dá)式、DFA、NFA的形式定義，能根據(jù)文字?jǐn)⑹鰰鴮懴鄳?yīng)的正規(guī)表達(dá)式；（4）掌握正規(guī)表達(dá)式與NFA的相互轉(zhuǎn)換；（5）掌握NFA確定化為DFA的方法；（6）掌握DFA的化簡方法；（7）了解詞法分析器的自動生成。4. 語法分析自上而下分析教學(xué)內(nèi)容：語法分析器的功能，自上而下語法分析（遞歸下降分析法，預(yù)測分析程序），LL（1）文法的定義和判別，非

4、LL（1）文法的等價變換。教學(xué)要求：（1）熟悉自上而下分析的基本思想和PDA的概念；（2）掌握消除左遞歸及消除回溯的方法；（3）了解LL(1)分析器的基本結(jié)構(gòu)；（4）掌握FIRST集、FOLLOW集的概念，能根據(jù)給定文法求出相應(yīng)的首符集和隨符集；（5）掌握LL(1)文法的判別方法及LL(1)分析表的構(gòu)造方法；（6）掌握預(yù)測分析表的構(gòu)造；（7）了解遞歸下降分析器的構(gòu)造方法。5. 語法分析自下而上分析教學(xué)內(nèi)容：算符優(yōu)先分析，LR分析器，LR(0)項目集族和LR(0)分析表的構(gòu)造，SLR分析表的構(gòu)造，規(guī)范LR分析表的構(gòu)造。教學(xué)要求：（1）熟悉自下而上分析的基本思想；（2）掌握算符優(yōu)先分析的基本方法，

5、算符優(yōu)先分析表的構(gòu)造，查找最左素短語的方法；（3）了解優(yōu)先函數(shù)；（4）掌握LR分析器的基本結(jié)構(gòu)、工作原理，能根據(jù)LR分析表寫出給定語句的LR分析過程；（5）掌握LR(0)、SLR(1)及LR(1)分析表的構(gòu)造方法；（6）掌握SLR(1)沖突解決辦法；（7）了解二義文法的應(yīng)用。6語法制導(dǎo)翻譯和中間代碼產(chǎn)生教學(xué)內(nèi)容：屬性、語義規(guī)則、屬性文法；中間語言的表示形式；說明語句、簡單賦值語句、布爾表達(dá)式、控制語句的翻譯方法。教學(xué)要求：（1）熟悉語法制導(dǎo)翻譯基本原理；（2）了解自上而下語法制導(dǎo)翻譯基本思想和實現(xiàn)方法；（3）掌握幾種常見的中間語言：逆波蘭表示，三元式，四元式表示；（41）掌握各種語句到四元式的

6、翻譯方法，包括：簡單算術(shù)表達(dá)式、布爾表達(dá)式、控制語句等的翻譯；（5）了解數(shù)組元素，過程調(diào)用和說明語句的翻譯。7代碼優(yōu)化教學(xué)內(nèi)容：代碼優(yōu)化的分類，常用的優(yōu)化技術(shù)，局部優(yōu)化和循環(huán)優(yōu)化的概念及實現(xiàn)方法。局部優(yōu)化，基本塊，DAG表示，循環(huán)優(yōu)化，必經(jīng)結(jié)點集，刪除公共子表達(dá)式，復(fù)寫傳播，刪除無用賦值，代碼外提，強(qiáng)度削弱，刪除歸納變量，全局優(yōu)化。教學(xué)要求：（1）熟悉代碼優(yōu)化的定義；（2）掌握基本塊的DAG表示及基本塊優(yōu)化的基本思想，能根據(jù)給定的基本塊畫出相應(yīng)的DAG圖；（3）熟悉循環(huán)的定義；（4）掌握在程序流圖中循環(huán)的查找方法；（5）了解循環(huán)優(yōu)化所采用的方法。8 符號表教學(xué)內(nèi)容：符號表的作用和地位；符號的類

7、型和存儲類別；符號表的組織結(jié)構(gòu)，符號表總體組織的選擇原則；符號表的管理。教學(xué)要求：（1）掌握符號表的作用和組織方式；（2）了解名字的作用范圍；（3）了解常用的符號表結(jié)構(gòu)及其包含的內(nèi)容。9 目標(biāo)代碼生成教學(xué)內(nèi)容：目標(biāo)機(jī)器模型；一個簡單代碼生成器；寄存器分配；DAG目標(biāo)代碼；窺孔優(yōu)化。教學(xué)要求：（1）了解代碼生成過程的基本問題； （2）了解待用信息、寄存器描述和地址描述等概念；（3）熟悉簡單代碼生成算法、寄存器分配策略；三、實踐環(huán)節(jié)和要求：在學(xué)生掌握基本原理的基礎(chǔ)上，在總體結(jié)構(gòu)的導(dǎo)引下，通過設(shè)計出詞法分析器、語法分析器，語義分析與中間代碼生成器，構(gòu)建一個限定高級語言的翻譯器。要求學(xué)生完成相關(guān)算法和

8、數(shù)據(jù)結(jié)構(gòu)的設(shè)計， 并用自己偏愛的語言完成實現(xiàn)，最后提交規(guī)范的實驗報告。通過實驗，使學(xué)生在掌握編譯程序基本構(gòu)造的基礎(chǔ)上，具有分析和實現(xiàn)現(xiàn)有編譯程序的初步能力，并且加深對程序設(shè)計語言原理的理解，提高中、大型程序的分析和開發(fā)能力。要求實驗前做好準(zhǔn)備，熟悉實驗相關(guān)的技術(shù)和原理，制定實驗方案，編寫相關(guān)的程序或文檔；實驗獨立完成，認(rèn)真觀察與思考；實驗后進(jìn)行分析小結(jié)，寫出實驗報告?；疽螅?編寫能識別標(biāo)識符、實數(shù)、整數(shù)、運算符和關(guān)鍵字正規(guī)式的簡單詞法分析程序。2從詞法分析器分析出的結(jié)果入手，通過查SLR(1)的分析表來進(jìn)行語法分析，在每一步的歸約調(diào)用語義分析程序，產(chǎn)生三地址碼或四元式。四、教學(xué)時數(shù)分配：理

9、論：40學(xué)時 實驗：學(xué)時 上機(jī)： 8學(xué)時 其它： 教學(xué)內(nèi)容學(xué)時分配教學(xué)內(nèi)容學(xué)時分配1引論2實驗一 簡單詞法分析程序22文法和語言6實驗二 自上而下的語法分析器的設(shè)計與實現(xiàn)43詞法分析5實驗三 三地址代碼（四元式）生成器的設(shè)計與實現(xiàn)24自上而下語法分析6 5自下而上語法分析7 6語法制導(dǎo)翻譯和中間代碼生成6 7代碼優(yōu)化4 8符號表2 9目標(biāo)代碼生成2 合計48學(xué)時五、其它項目（含課外學(xué)時內(nèi)容）：無。六、有關(guān)說明：1、教學(xué)和考核方式：本課程屬于考試課，考試方式為閉卷。其中，教師在實驗結(jié)束前，要注意現(xiàn)場驗收學(xué)生設(shè)計實現(xiàn)的系統(tǒng)，并給出現(xiàn)場評定。評定級別分優(yōu)秀、良好、合格、不合格，最后結(jié)合實驗報告給出實

10、驗成績。2、習(xí)題：每章布置一定的習(xí)題和課外思考題，通過對習(xí)題的練習(xí)加強(qiáng)對各章內(nèi)容的掌握和認(rèn)識。3、能力培養(yǎng)要求：通過本課程理論學(xué)習(xí)，使學(xué)生對編譯的基本概念、原理和方法有完整的和清楚的理解，并能正確地、熟練地運用。通過本課程的實驗教學(xué)加深學(xué)生對語言編譯器構(gòu)造的一般原理的理解，掌握編譯器的基本構(gòu)造，及以詞法分析程序和語法分析程序為核心的簡單編譯器的基本設(shè)計方法和實現(xiàn)技術(shù)。4、與其它課程和教學(xué)環(huán)節(jié)的聯(lián)系：先修課程和教學(xué)環(huán)節(jié)：離散數(shù)學(xué)，C語言程序設(shè)計，數(shù)據(jù)結(jié)構(gòu)后續(xù)課程和教學(xué)環(huán)節(jié)： 平行開設(shè)課程和教學(xué)環(huán)節(jié)：5、教材和主要參考書目：（1）教材：編譯原理（第二版）， 胡倫駿等。北京：電子工業(yè)出版社，2007（2）主要參考書目： 程序設(shè)計語言編譯原理，陳火旺編著，北京：國防工業(yè)出版社，2005； 編譯原理， 李冬梅等。