《編譯原理》教學大綱.doc

編譯原理教學大綱大綱說明課程代碼：3225003 總學時：64學時（講課48學時，實驗16學時）總學分： 4課程類別：學科基礎(chǔ)課適用專業(yè): 計算機科學與技術(shù)（專業(yè)）預修要求：C語言程序設(shè)計、C+程序設(shè)計、數(shù)據(jù)結(jié)構(gòu) 課程的性質(zhì)、任務及地位 ： 編譯原理是計算機科學與技術(shù)專業(yè)的一門重要基礎(chǔ)課。通過對該課程的學習，使學生掌握編譯過程中的相關(guān)原理和編譯技術(shù)，讓學生能初步進行編譯程序的開發(fā)和維護，同時促進提高學生開發(fā)軟件的能力。教學目的與基本要求：本課程的目的，通過向?qū)W生講述編譯系統(tǒng)的結(jié)構(gòu)、工作流程及編譯程序各部分的設(shè)計原理和實現(xiàn)技術(shù)，使學生既掌握編譯技術(shù)理論的基礎(chǔ)與基本知識，也具有設(shè)計、實現(xiàn)、分析和維護編譯程序等方面的初步能力。本課程理論性較強。因授課對象為工科學生，所以在強調(diào)編譯系統(tǒng)的構(gòu)造原理和實現(xiàn)方法的同時，為培養(yǎng)學生的實際工作能力，通過上機實踐進一步加深學生對課堂教學內(nèi)容的理解。目的是要使學生牢固掌握相關(guān)的基本理論和基本方法，并能初步利用上述理論和方法解決簡單實際問題。教學方法和教學手段的建議：在教學方法上，貫徹理論聯(lián)系實際、“精講、多練”的原則，進行案例式、啟發(fā)式的教學，對于一些實際性較強的問題要多采用課堂討論等方式 ，以提高學生的思辨能力和學習的主動性；引導學生讀書、理解、體悟、運用相結(jié)合；提高學生的學習興趣與熱情，培養(yǎng)與發(fā)揮學生的提出、分析及解決問題的能力。教學手段：運用多媒體教學手段+黑板+上機實驗的手段。采取課堂講授、課堂討論、課后練習與自學等形式。大綱的使用說明：大綱對課程性質(zhì)、目的等作簡單說明，同時列出各章節(jié)要學習的知識點、重點、難點，便于教學時教授重點的安排和學生自學安排。大綱正文第一章 引論 學時：4學時（講課4學時，實驗0學時）了解編譯的概念；理解編譯程序的各組成部分及功能。本章講授要點：介紹程序設(shè)計語言與編譯程序間的關(guān)系，主要內(nèi)容包括：各級程序設(shè)計語言的定義、源程序的執(zhí)行、編譯程序的構(gòu)造、編譯程序的分類、形式語言理論與編譯實現(xiàn)技術(shù)的聯(lián)系。重點：程序設(shè)計語言的定義，語法圖及BNF表示法，編譯程序的各階段功能。難點：程序執(zhí)行的方式、編譯程序“趟”的概念。第一節(jié) 程序設(shè)計語言與編譯程序的聯(lián)系一、 源程序、程序設(shè)計語言的執(zhí)行二、 編譯程序的兩種方式：解釋與編譯三、 編譯程序的定義第二節(jié) 編譯程序構(gòu)造及有關(guān)概念四、 程序設(shè)計語言的四個方面：語法、語義、語用、語境五、 語法的定義：語法圖、BNF表示法、口語六、 程序執(zhí)行的過程七、 編譯程序的組成模塊：詞法分析、語法分析、語義分析、代碼優(yōu)化、目標代碼生成八、 “趟”的概念九、 編譯程序的分類第三節(jié) 形式語言與編譯實現(xiàn)技術(shù)思考題：1 編譯原理的定義是什么？2 編譯原理由幾部分構(gòu)成？各部分完成哪些工作？3 在編譯過程中“趟”的概念是指什么？第二章 文法與語言 學時：8學時（講課6學時，實驗2學時）理解字母表的定義及閉包、符號串的基本知識及其運算、符號串集合概念及運算；掌握文法的形式定義、Chomsky語言的分類、文法等價及其等價變換方法、語法分析樹與句型分析。本章講授要點：字母表的定義及閉包、符號串的基本知識及其運算、符號串集合概念及運算、文法的形式定義、Chomsky語言的分類、文法等價及其等價變換方法、語法分析樹與句型分析。重點： Chomsky文法的定義、文法和語言之間的關(guān)系、規(guī)范推導和規(guī)范規(guī)約、文法的二義性判定；文法的化簡。難點：句型分析、文法的文法的二義性判定、文法等價及其等價變換方法。第一節(jié) 符號串與符號串集合一、 字母表的定義、字母表的閉包與正閉包二、 符號串及其運算第二節(jié) 文法與語言的形式定義一、 文法的形式定義、重寫規(guī)則的表示形式二、 文法的定義、應用文法產(chǎn)生語言的句子三、 語言的形式定義第三節(jié) 語言的分類一、Chomsky語言分類法二、Chomsky的文法定義三、上下文無關(guān)的討論 第四節(jié) 文法等價與等價變換一、文法等價二、壓縮文法等價變換三、消去單規(guī)則等價變換四、消去左規(guī)則等價變換第五節(jié) 語法分析樹與句型分析一、語法分析樹二、句型分析思考題：1 弄清字母表、字符串集合、字符串閉包及正閉包的定義。2 弄清文法、重寫規(guī)則與語言之間的關(guān)系。3 Chomsky語言類有幾類？各有什么特點？4 什么是無用規(guī)則，如何消除？5 弄清在推導語法樹中，弄清句型、短語、簡單短語、句柄以及句子的概念。第三章 詞法分析 學時：14學時（講課10學時，實驗4學時）了解詞法分析的目標和實現(xiàn)方法、詞法分析器的目標是識別源程序中的各個單詞。理解確定有限自動機的組成和非確定有限自動機的組成。掌握狀態(tài)轉(zhuǎn)換圖、狀態(tài)轉(zhuǎn)換圖與正則文法的相互轉(zhuǎn)換、確定有限自動機和非確定有限自動機、NFA轉(zhuǎn)DFA、DFA的最小化、正則表達式與正則集、正規(guī)式轉(zhuǎn)DNF。本章講授要點：詞法分析器的目標是識別源程序中的各個單詞。詞法分析可以通過確定有限自動機來完成。：狀態(tài)轉(zhuǎn)換圖、狀態(tài)轉(zhuǎn)換圖與正則文法的相互轉(zhuǎn)換、確定有限自動機和非確定有限自動機、NFA轉(zhuǎn)DFA、DFA的最小化、正則表達式與正則集。詞法分析程序的實現(xiàn)與編寫，以及詞法掃描程序的算法。重點：狀態(tài)轉(zhuǎn)換圖、正則文法與狀態(tài)轉(zhuǎn)換圖的互換、NFA轉(zhuǎn)DFA、DFA的最小化。正則表達式與狀態(tài)轉(zhuǎn)換圖。 難點：NFA轉(zhuǎn)DFA、DFA的化簡、正則文法與正則表達式。第一節(jié) 引言一、 詞法分析的任務、詞法分析程序二、 符號的識別與重寫規(guī)則的關(guān)系三、 詞法分析的實現(xiàn)方式第二節(jié) 正則表達式與有窮狀態(tài)自動機一、 狀態(tài)轉(zhuǎn)換圖、狀態(tài)轉(zhuǎn)換系統(tǒng)二、 確定有窮狀態(tài)自動機DFA三、 非確定有窮狀態(tài)自動機NFA四、 DFA的化簡五、 正則表達式第三節(jié) 詞法分析程序的實現(xiàn)一、 單詞與屬性字二、 標識符的處理三、 詞法分析程序的編寫第四節(jié) 詞法分析程序的自動生成一、 基本思想二、 掃描程序與構(gòu)造程序三、 自動生成系統(tǒng)LEX思考題：1 詞法分析的功能是什么？2 什么是狀態(tài)轉(zhuǎn)換圖、NFA、DFA？3 如何將NFA轉(zhuǎn)換為DFA？4 如何簡化DFA？5 正則表達式與DFA有何關(guān)系？第四章 語法分析自頂向下的語法分析技術(shù) 學時：6學時（講課6學時，實驗0學時）了解語法分析的功能和兩中大的分析方法：自頂向下的語法分析法和自下而上的語法分析。理解自上而下的分析方法-從文法的開始符號推導出句子本身的分析方法，自下而上的分析方法從語句歸約為文法開始符號的分析原理。掌握FELLOW（）和FIRST（）的算法、預測分析表的構(gòu)造和預測分析過程。 本章講授要點：自頂向下的語法分析法帶回溯自頂向下分析技術(shù)、無回溯頂向下分析技術(shù)及其算法、遞歸下降分析法和預測分析法，預測分析法的文法要求、分析表的構(gòu)造方法、預測分析方法。 重點：無回溯的遞歸下降分析技術(shù)與預測分析法。難點：LL（1）文法的判定、預測分析法、遞歸下降分析法。第一節(jié) 引言一、 自頂向下分析技術(shù)及識別算法二、 討論的前提三、 要解決的基本問題第二節(jié) 帶回溯的自頂向下分析技術(shù)一、 基本思想二、 實現(xiàn)算法及舉例三、 問題及其解決第三節(jié) 無回溯的自頂向下分析技術(shù)一、 先決條件二、 遞歸下降分析技術(shù)三、 預測分析技術(shù)思考題：1 何為自頂向下分析技術(shù)？2 如何區(qū)別帶回溯自頂向下分析技術(shù)與無回溯頂向下分析技術(shù)？3 什么是分析表的構(gòu)造方法？4 什么是預測分析方法？第五章 語法分析自底向上分析技術(shù) 學時：16學時（講課10學時，實驗6學時）理解自底向上的語法分析法及算法、自底向上的語法分析的基本實現(xiàn)方法；掌握LR分析原理及組成、LR（0）項目集規(guī)范族的構(gòu)造、LR（0）分析表的構(gòu)造、SLR（k）分析表構(gòu)造方法、LAL（k）分析表構(gòu)造方法、識別程序的自動構(gòu)造。本章講授要點：自底向上的語法分析法及算法、自底向上的語法分析的基本實現(xiàn)方法； LR（k）分析技術(shù)、SLR（k）分析表構(gòu)造方法、LALR（k）分析表構(gòu)造方法、識別程序的自動構(gòu)造。重點：簡單優(yōu)先分析技術(shù)的實現(xiàn)、LR（k）分析技術(shù)。難點： LR（1）分析表的構(gòu)造、消除文法的左遞歸。第一節(jié) 概述一、 自頂向下分析技術(shù)及識別算法二、 討論的前提三、 要解決的基本問題第二節(jié) 簡單優(yōu)先分析技術(shù)（自學）一、 優(yōu)先關(guān)系與優(yōu)先文法二、 簡單優(yōu)先分析技術(shù)三、 優(yōu)先函數(shù)第三節(jié) 算符優(yōu)先分析技術(shù)（自學）一、 算符文法二、 算符優(yōu)先關(guān)系與算符優(yōu)先文法三、 算符優(yōu)先文法句型的識別四、 算符優(yōu)先技術(shù)與簡單優(yōu)先技術(shù)的比較第四節(jié) LR(K)分析技術(shù)四、 LR(K)文法與LR(K)分析技術(shù)五、 SLR(K)分析表構(gòu)造方法六、 LALR(K)分析表構(gòu)造方法七、 識別程序的自動構(gòu)造思考題：1 什么是自底向上的語法分析法？2 LR（k）分析技術(shù)是什么？3 SLR（k）分析表構(gòu)造方法是什么？4 LAL（k）分析表構(gòu)造方法是什么？第六章 語義分析與目標代碼生成 學時：12學時（講課8學時，實驗4學時）了解語義分析的概念；理解屬性文法和屬性翻譯文法的概念、抽象語法樹、逆波蘭表示法、四元式序列、三元式序列；掌握算術(shù)表達式的翻譯、布爾表達式的翻譯、條件語句和循環(huán)語句的翻譯。了解說明部分的翻譯；數(shù)組的翻譯、過程語句和過程調(diào)用的翻譯來闡述語法制導翻譯模式和如何生成之間代碼。本章講授要點：屬性文法、語義分析的概念、說明部分的翻譯；目標代碼的生成：虛擬機、控制語句的翻譯；源程序的內(nèi)部中間表示：抽象語法樹、逆波蘭表示法、四元式序列、三元式序列。、數(shù)組的翻譯、過程語句和過程調(diào)用的翻譯來闡述語法制導翻譯模式和如何生成之間代碼。重點：屬性文法、屬性翻譯文法、簡單算術(shù)表達式和賦值語句的翻譯、布爾表達式的翻譯、條件語句的翻譯、循環(huán)語句的翻譯、數(shù)組的翻譯、過程語句和過程調(diào)用的翻譯。難點：語句的語法制導翻譯、屬性文法和屬性翻譯文法、常見的中間語言簡介、簡單算術(shù)表達式和賦值語句的翻譯、布爾表達式的翻譯、各種語句的翻譯。第一節(jié) 概述一、 語義分析二、 屬性文法三、 類型體制與語義分析第二節(jié) 說明部分的分析一、 常量定義的翻譯二、 變量定義的翻譯三、 函數(shù)定義的翻譯四、 結(jié)構(gòu)體類型的翻譯第三節(jié) 目標代碼的生成一、 概況二、 控制語句的翻譯第四節(jié) 源程序的內(nèi)部中間表示一、 抽象語法樹二、 逆波蘭表示法三、 四元式序列四、 三元式序列思考題：1 弄清相關(guān)概念：注釋分析樹、綜合屬性、繼承屬性、依賴圖等。2 控制語句的翻譯要點十什么？3 類型表達式及其等價性是指什么？4 四元式序列與三式序列有何區(qū)別？第七章 運行環(huán)境 （自學2學時）了解運行環(huán)境的相關(guān)問題；理解存儲分配策略：靜態(tài)存儲分配，棧式存儲分配，堆式存儲分配。本章講授要點：運行環(huán)境的相關(guān)問題；存儲分配策略：靜態(tài)存儲分配，棧式存儲分配，堆式存儲分配；符號表的引進、組織及數(shù)據(jù)結(jié)構(gòu)；運行時刻支持系統(tǒng)。自學要求：在學習該章節(jié)內(nèi)容時應該將實踐環(huán)節(jié)中所用的相關(guān)存儲技術(shù)加以考慮。重點：運行時的內(nèi)存的劃分、活動記錄、運行時的分配策略。難點：棧式存儲分配和堆式存儲分配、存儲組織、運行時的分配策略。第一節(jié) 引言第二節(jié) 存儲分配策略一、 靜態(tài)存儲分配二、 棧式存儲分配三、 堆式存儲分配第三節(jié) 符號表一、 符號表的組織二、 符號表的數(shù)據(jù)結(jié)構(gòu)第四節(jié) 運行時刻支持系統(tǒng)思考題：1 運行時內(nèi)存如何劃分？2 弄清各各存儲分配策略。3 弄清概念：環(huán)境、狀態(tài)、結(jié)合、懸空引用、運行時刻支持環(huán)境。第八章：代碼優(yōu)化 學時：4學時（講課4學時，實驗0學時）了解代碼優(yōu)化的含義。理解從語法制導階段的優(yōu)化方法到相對中間代碼的優(yōu)化方法：強度削弱、常數(shù)合并和常數(shù)傳播、無用變量和無用代碼刪除。掌握以基本信息塊和循環(huán)體內(nèi)的代碼優(yōu)化來進行。本章講授要點：代碼優(yōu)化的分類、代碼優(yōu)化程序的結(jié)構(gòu)；基本塊的優(yōu)化、線性窺孔優(yōu)化方法、基本信息塊優(yōu)化、循環(huán)塊的劃分、循環(huán)內(nèi)的優(yōu)化。重點：線性窺孔優(yōu)化，基于結(jié)構(gòu)信息的優(yōu)化、循環(huán)塊的劃分和循環(huán)優(yōu)化。難點：基于結(jié)構(gòu)信息的優(yōu)化、循環(huán)塊的劃分。語法制導階段的優(yōu)化、線性窺孔優(yōu)化及基本信息塊的優(yōu)化。第一節(jié) 概述一、 優(yōu)化分類二、 代碼優(yōu)化程序的結(jié)構(gòu)第二節(jié) 基本塊與流圖一、 基本塊優(yōu)化的種類二、 基本塊優(yōu)化的實現(xiàn)第三節(jié) 與循環(huán)有關(guān)的優(yōu)化一、 循環(huán)優(yōu)化的種類二、 循環(huán)優(yōu)化的實現(xiàn)第四節(jié) 窺孔優(yōu)化一、 冗余指令刪除二、 控制流優(yōu)化三、 代數(shù)化簡思考題：1 代碼優(yōu)化分哪幾類？2 弄清相關(guān)概念：基本塊、流圖、無環(huán)路有向圖dag、公共子表達式、窺孔優(yōu)化等。3 代碼優(yōu)化程序由幾部分組成？各功能是什么？本課程對學生自學的要求：由于本課程理論比較抽象，它是計算機專業(yè)課中教難學的課程。課堂上不一定能將問題完全弄懂，而課程內(nèi)容前后相關(guān)，要求學生課后要進行復習。同時，該課程有上機實踐，要求學生自己去復習C語言和數(shù)據(jù)結(jié)構(gòu)方面的知識，獨立完成4個上機實踐。故該課程對學生自學能力要求較高。課時數(shù)分配表：章節(jié) 內(nèi) 容 學時數(shù)第一章引論 4第二章前后文無關(guān)文法和語言 8（6+2）第三章詞法分析 14（10+4）第四章語法分析（自頂向下） 6（6+0）第五章語法分析（自底向上） 16（10+6）第六章語義分析 12（8+4）第七章遠行環(huán)境 0（自學）第八章代碼優(yōu)化 4（4+0）合計64（48+16）考核方式與要求：考核由平時成績和期末考試綜合評價。其中，期末考試占成績的70%，平時成績占30%，平時成績由作業(yè)、上機實驗、課堂問答等3部分組成。參考書目：1張幸兒 編計算機編譯原理 科學出版社 2003年第2版2蔣立源、康慕寧 編編譯原理 西北工業(yè)大學出版社 2002年第2版3陳火旺、劉春林 等編編譯原理 國防工業(yè)出版社 2001年第3版4呂映芝、張素琴 等編編譯原理 清華大學出版社 2001年第15版5伍春香 編編譯原理-習題與解析 清華大學出版社 2001年第1版編譯原理實驗大綱一、總則1本大綱的適用范圍1）大綱相關(guān)的課程名稱及課程屬性數(shù)據(jù)結(jié)構(gòu)，C語言程序設(shè)計，專業(yè)基礎(chǔ)課2）本大綱的適用范圍計算機科學技術(shù)專業(yè)3）實驗總課時16學時2本大綱的實驗目的和要求性質(zhì)： 編譯程序課程的必須實踐環(huán)節(jié)目的和要求：在弄懂編譯原理理論的基礎(chǔ)上，通過與課文內(nèi)容的同步實驗，訓練學生分析、設(shè)計編譯程序的動手能力，從而加深對編譯程序課程各個部分學習和理解。3本實驗課程的重點和內(nèi)容1）從文件中讀一行并將字符依次存入字符指針變量中；2）將一行字符串根據(jù)空格將單詞分開；3）看單詞中是否包含某些保留單詞用；4）根據(jù)文法描述語言進行單詞分類，并用狀態(tài)轉(zhuǎn)換圖描述單詞的識別過程；5）根據(jù)狀態(tài)轉(zhuǎn)換圖編寫詞法分析程序；6）驗證賦值語句中算術(shù)表達式的語法分析程序，條件語句或循環(huán)語句中的布爾表達式的LR分析程序；7）設(shè)計程序語句的LR分析程序；8）根據(jù)語言的文法寫出它的屬性翻譯文法；9）根據(jù)屬性翻譯文法在語法分析的基礎(chǔ)上添加動作代碼；4本大綱所需的實驗設(shè)備奔騰PII以上、內(nèi)存32MB以上、WINDOWS 2000、TUBRO-C 。二、實驗項目及學時安排1. 實驗項目一 簡單的單詞識別程序1） 實驗類型：驗證性與設(shè)計性實驗2） 實驗開設(shè)屬性：必開實驗3）學時數(shù) ： 2課時4）實驗目的：熟悉C操作環(huán)境，分析驗證性實驗程序的代碼結(jié)構(gòu)，了解如何從文件中逐行讀數(shù)據(jù)到字符串變量中；掌握對符號串進行掃描以識別單詞的編程技巧。5）實驗要求： 熟悉 TUBRO-C系統(tǒng)環(huán)境。 能夠設(shè)計簡單的單詞識別器2. 實驗項目二詞法分析器的設(shè)計1）實驗類型：驗證性與設(shè)計性實驗2）實驗開設(shè)屬性：必開實驗3）學時數(shù) ： 4課時4）