編譯原理課程教學(xué)大綱-東南大學(xué)計算機科學(xué)與工程學(xué)院

1、編譯原理課程教學(xué)大綱(課程編號711302 學(xué)分-學(xué)時-上機4.0-64-16 )東南大學(xué)計算機科學(xué)與工程學(xué)院一、課程的性質(zhì)與目的本課程是軟件工程專業(yè)必修的專業(yè)核心課。本課程的教學(xué)目的， 是使學(xué)生在學(xué)習(xí)程序設(shè)計基礎(chǔ)及語言和數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上，進一步理解程序及程序設(shè)計語言的本質(zhì)，掌握程序詞法分析和句法分析的基本原理和方法。學(xué)會構(gòu)造一個編譯程序， 用以將一種語言所編寫的程序(如，用C語言編寫的程序)等價變換為另一種語言所編寫的程序(如，用匯編語言編寫的程序)，并能對變換過程中所生成的中間代碼程序及變換所得的程序進行優(yōu)化，以培養(yǎng)良好的程序設(shè)計優(yōu)化思維，提高學(xué)生的編程能力，為學(xué)習(xí)有關(guān)專業(yè)課程和進行大型軟

2、件實踐打 下必要的基礎(chǔ)。二、課程內(nèi)容的教學(xué)要求1 .編譯原理及編譯程序構(gòu)造引論(1)開設(shè)編譯原理課程的主要作用：讓學(xué)生理解開設(shè)編譯原理課程的意義和作用，編譯原理課程在計算機專業(yè)課程體系中的地位，學(xué)習(xí)編譯原理課程應(yīng)采用的方法，編譯原理課程知識體系結(jié)構(gòu)，讓學(xué)生初步認識學(xué)習(xí)編譯原理課程的重要性和潛在的使用價值。(2)編譯程序及其構(gòu)造過程概述：介紹編譯程序的基本含義、作用和結(jié)構(gòu)，簡述編譯程序構(gòu)造的基本過程，以讓學(xué)生形成編譯程序構(gòu)造的總體印象。2 .(程序設(shè)計)語言和語法描述(1)語言描述體系結(jié)構(gòu)： 了解語言的語法、語義和語用的基本含義及相互作用，掌握 描述語言語法的基本方法和過程， 使學(xué)生清楚語言語法

3、描述應(yīng)包括由字符構(gòu)造單詞的詞法描 述，及由單詞構(gòu)造句子的句法描述。(2)語言和文法的基本概念： 掌握語言與文法的相關(guān)基本概念，如，串、句子、句型、 文法、產(chǎn)生式、推導(dǎo)與歸約等，語言文法對語言語法描述的作用，文法的形式化描述方法和過程，Chomsky形式語言文法體系及其在語言語法描述中的應(yīng)用、特別是正規(guī)文法及上下 文無關(guān)文法在語言語法描述中的應(yīng)用。(3)從語言構(gòu)造文法：了解常見語言句子構(gòu)造模式，掌握從典型語言句子模式構(gòu)造對應(yīng)無產(chǎn)生式文法的方法，使學(xué)生能夠理解由語言構(gòu)造文法的重要性。(4)語法樹、分析樹與二義文法：掌握語法樹、分析樹及二義文法的基本概念，如，語法樹、分析樹、短語、句柄、二義文法，語

4、法樹在語言語法分析過程中的作用，語法樹構(gòu) 造方法和過程，二義文法對語言文法的簡化描述的作用。3 .詞法分析(1)詞法分析程序的作用和基本構(gòu)造過程：讓學(xué)生掌握詞法分析程序的作用和基本構(gòu)造過程，了解詞法分析程序構(gòu)造的關(guān)鍵問題，如，詞法描述方法、由詞法描述構(gòu)造相應(yīng)詞法分析程序的思想方法。(2)正規(guī)表達式、正規(guī)語言與正規(guī)文法：掌握正規(guī)表達式對單詞模式表達的作用，由基本字符構(gòu)造正規(guī)表達式的方法和過程，識別一個正規(guī)表達式的方法， 以及正規(guī)語言的基本概念，理解正規(guī)表達式、正規(guī)語言、正規(guī)文法三者之間的等價關(guān)系和轉(zhuǎn)換方法。(3)有限自動機：讓學(xué)生了解有限自動機對正規(guī)表達式識別(也就是單詞識別)的作用，掌握有限自

5、動機的基本概念， 熟悉由正規(guī)表達式構(gòu)造非確定有限自動機的方法與過程，掌握 將非確定有限自動機確定化的理由、 方法與過程， 熟悉確定有限自動機最小化的理由、 方法和過程，了解正規(guī)文法（正規(guī)表達式、正規(guī)語言）與有限自動機之間的相互轉(zhuǎn)換方法、以及由確定有限自動機構(gòu)造相應(yīng)詞法分析程序的方法和過程。（ 4）詞法分析程序生成工具Lex ： 了解 Lex 的基本思想和使用方法。4. 語法（句法）分析（ 1）語法分析基本過程和方法概述： 進一步理解上下文無關(guān)文法與語言語法描述的關(guān)聯(lián)， 了解利用下推自動機進行語法分析的基本過程， 熟悉典型語法分析方法的基本思想， 深 刻理解“推導(dǎo) 匹配” 、 “移進 歸約”的語

6、法分析的思想。（ 2）自頂向下語法分析： 理解自頂向下語法分析方法的基本思想和基本過程，了解基于遞歸下降分析法構(gòu)造語法分析程序的基本思想和基本過程，掌握預(yù)測分析法LL（1） 的基本思想和基本技巧、特別是左遞歸消除、首符集First 和隨符集 Follow 構(gòu)造的技巧，能夠由上下文無關(guān)文法構(gòu)造 LL（1）分析表，了解基于 LL（1）分析表進行具體句子的分析過程。（ 3）自底向上語法分析： 理解自底向上語法分析方法的基本思想和基本過程，重點掌握 LR 分析法的基本思想和基本過程， 能夠由上下文無關(guān)文法構(gòu)造簡單的 LR 分析表 （SLR（1）分析表 ）和規(guī)范的 LR 分析表 （LR（1） 分析表 ）

7、， 了解由 LR（1） 構(gòu)造 LALR（1） 分析表的基本思想和基本過程。（ 4）二義文法的語法分析： 掌握語法分析過程解決文法二義性的基本思想，能夠通過二義文法的附加條件構(gòu)造相應(yīng)的SLR（1）或LR（1）分析表。（ 5）語法分析程序生成工具YACC ： 了解 YACC 的基本思想和應(yīng)用過程。5. 語義分析（ 1）屬性文法： 了解引入符號屬性對語言語義描述的作用，理解將上下文無關(guān)文法轉(zhuǎn)換為屬性文法的意義、 過程和關(guān)鍵， 掌握屬性文法中語義規(guī)則的使用方法， 理解邊進行語法分析、邊進行語義分析的語義屬性值計算的基本思想。（ 2）屬性文法中的綜合屬性值計算方法： 能夠由只具有綜合屬性的屬性文法構(gòu)造一

8、個句子的加以屬性標注的分析樹。（ 3）類型檢查： 了解類型作為一種特殊的屬性時的屬性計算過程和方法，即，類型檢查的基本思想和方法。6. 中間代碼生成（ 1） 常見中間代碼形式： 了解常見中間代碼形式， 掌握三地址碼和四元式的基本思想。（ 2） 型語句生成三地址碼的方法： 掌握表達式、基本賦值語句、含有數(shù)組元素的語句、 If 語句、 While 語句翻譯成三地址碼的方法，能夠?qū)⒁欢魏猩鲜稣Z句的程序翻譯成三地址碼語句序列。（ 3） 典型語句生成四元式的方法： 掌握表達式、 基本賦值語句、 含有數(shù)組元素的語句、If 語句、 While 語句翻譯成四元式的方法，能夠?qū)⒁欢魏猩鲜稣Z句的程序翻譯成四元

9、式序列，熟悉翻譯過程中拉鏈回填的基本技巧。7. 運行時環(huán)境（ 1）程序執(zhí)行過程與激活樹： 了解程序在計算機系統(tǒng)中執(zhí)行過程，掌握激活樹概念。（ 2）程序運行時數(shù)據(jù)存儲空間分配策略： 了解程序運行時數(shù)據(jù)存儲空間分配策略，重點理解棧式存儲分配策略。（ 3）棧式存儲分配策略： 掌握活動記錄的基本概念，理解C 語言程序運行過程中基于活動記錄的數(shù)據(jù)存儲分配策略，能夠構(gòu)造一個C 語言程序?qū)?yīng)的數(shù)據(jù)存儲棧圖。8. 程序優(yōu)化（ 1） 程序分塊與程序流圖： 了解程序優(yōu)化的一般方法和過程， 掌握程序基本塊的概念，能夠?qū)⒁欢纬绦騽澐譃榛緣K、并構(gòu)造以基本塊為結(jié)點的程序流圖。（ 2）塊內(nèi)優(yōu)化： 能夠構(gòu)造表示一個基本塊所

10、涉及數(shù)據(jù)量及其關(guān)聯(lián)的有向無環(huán)圖，掌握基于有向無環(huán)圖的塊內(nèi)優(yōu)化方法，能夠?qū)σ粋€基本塊進行塊內(nèi)優(yōu)化并寫出優(yōu)化后的代碼序列。（ 3)循環(huán)優(yōu)化：掌握必經(jīng)結(jié)點集和回邊的基本概念，能夠找出程序流圖中的循環(huán)，了 解循環(huán)優(yōu)化的基本方法。（ 4)基于數(shù)據(jù)流分析的優(yōu)化：了解數(shù)據(jù)流分析的作用，理解變量引用定值鏈、定值到達數(shù)據(jù)流方程、活躍變量數(shù)據(jù)流方程的含義和作用。三、上機實習(xí)要求了解程序設(shè)計語言的詞法和語法(句法)的表示形式，理解詞法和語法分析程序的構(gòu)造方 法和過程，了解簡單的塊內(nèi)優(yōu)化方法。四、能力培養(yǎng)的要求1 .分析能力的培養(yǎng)： 主要是對程序結(jié)構(gòu)、編譯程序構(gòu)造方法和過程、程序優(yōu)化方法進 行分析的能力的培養(yǎng)，同時也

11、要注意培養(yǎng)針對具體程序設(shè)計語言構(gòu)造編譯程序的能力的培 養(yǎng)。2 .算法分析和實現(xiàn)能力的培養(yǎng)：要求學(xué)生通過本課程的學(xué)習(xí)，具備對各種相關(guān)算法進行實現(xiàn)的能力。3 .外文文獻閱讀能力的培養(yǎng)：該課程采用英文教材、英文課件和英文試卷，要求學(xué)生通過本課程的學(xué)習(xí)，能夠具備直接閱讀專業(yè)外文文獻的能力。4 .自學(xué)能力的培養(yǎng)： 通過本課程的教學(xué)，要培養(yǎng)和提高學(xué)生對所學(xué)知識進行整理、概 括、消化吸收的能力，以及圍繞課堂教學(xué)內(nèi)容，閱讀參考書籍和資料，自我擴充知識領(lǐng)域的 能力。5 .表達能力的培養(yǎng)：主要是通過作業(yè)，清晰、整潔地表達自己解決問題的思路和步驟的能 力。6 .創(chuàng)新能力的培養(yǎng)： 培養(yǎng)學(xué)生獨立思考、深入鉆研問題的習(xí)慣

12、，和對問題提出多種解 決方案、選擇不同方法，以及對方法進行簡化和舉一反三的能力。五、建議學(xué)時分配課程內(nèi)容講課習(xí)題課或課堂討論實驗上機編譯原理及編譯程序構(gòu)造引論3開設(shè)編譯原理課程的主要作用1編譯程序及其構(gòu)造過程概述2程序設(shè)計語言和語法描述92語言描述體系結(jié)構(gòu)2語言和文法的基本概念2從語言構(gòu)造文法32語法樹、分析樹與二義文法2詞法分析1024詞法分析程序的作用和基本構(gòu)造 過程1正規(guī)表達式、正規(guī)語言與正規(guī)文法2有限自動機724詞法分析程序生成工具Lex1語法分析15412語法分析基本過程和方法概述1自頂向下語法分析424自底向上語法分析728二義文法的語法分析2語法分析程序生成工具 YACC1語義分析52屬性文法2屬性文法中的綜合屬性值計算方 法22類型檢查1中間代碼生成62常見中間代碼形式1典型語句生成三地址碼的方法1典型語句生成四元式的方法42運行時環(huán)境52程序執(zhí)行過程與激活樹1程序運行時數(shù)據(jù)存儲空間分配策 略1棧式存儲分配策略32程序優(yōu)化92程序分塊與程序流圖2塊內(nèi)優(yōu)化32循環(huán)優(yōu)化2基于數(shù)據(jù)流分析的優(yōu)化2復(fù)習(xí)2六、考核方式總評成績=平時成績（包括作業(yè)和考勤）+上機實驗+期末考試成績平時成績占10%上機試驗占20%期末考試成績占70%七、教材及參考書1