《編譯原理-計算機科學技術系.ppt》由會員分享，可在線閱讀，更多相關《編譯原理-計算機科學技術系.ppt（24頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、2020/8/31,華東師大信息學院計算機科學技術系,1,編譯原理,華東師大計算機科學技術系 楊宗源 2008年,Principles of Compiler,2020/8/31,華東師大信息學院計算機科學技術系,2,課程目的、學習方法和基本要求,性質(zhì) 專業(yè)基礎課程，是計算機科學技術的基礎 前導課程 離散數(shù)學、程序設計語言、數(shù)據(jù)結構、操作系統(tǒng) 目的 編譯程序是計算機系統(tǒng)的基本系統(tǒng)軟件，本課程主要介紹設計、實現(xiàn)編譯程序時所涉及的基本原理、基本方法和基本技術。通過本課程的學習和上機實踐使學生掌握構造高級程序設計語言編譯程序的基本原理、結構、設計與實現(xiàn)技術，培養(yǎng)學生了解和掌握編譯原理的基本原理及典型
2、技術并具備相當?shù)膽媚芰Α?2020/8/31,華東師大信息學院計算機科學技術系,3,課程目的、學習方法和基本要求,知識 形式語言與形式語言處理、自動機理論、形式描述方法、程序自動生成方法、數(shù)據(jù)流和控制分析方法 方法 系統(tǒng)性：前后的連接、融會貫通，避免孤立化 實踐性：可實現(xiàn)的系統(tǒng)軟件，理論與實踐相結合 多樣性：實現(xiàn)技術多樣、表示形式多樣 基本性：舉一反三，在掌握多種方法、算法和表 示形式的同時正確把握基本性,2020/8/31,華東師大信息學院計算機科學技術系,4,課程目的、學習方法和基本要求,本專業(yè)人員4種基本的專業(yè)能力 計算思維能力 算法的設計與分析能力 程序設計和實現(xiàn)能力 計算機軟硬件系
3、統(tǒng)的認知、分析、設計與應用能力 計算思維能力 邏輯思維能力和抽象思維能力 構造模型對問題進行形式化描述 理解和處理形式模型,2020/8/31,華東師大信息學院計算機科學技術系,5,課程目的、學習方法和基本要求,主要特點 抽象和形式化、理論證明和構造性 前半部分（詞法、語法分析） 實現(xiàn)技術、形式化 后半部分（語義分析、代碼優(yōu)化、生成） 希望,2020/8/31,華東師大信息學院計算機科學技術系,6,教材及主要參考書目,教材 胡倫駿等 編譯原理電子工業(yè)出版社 2005年 參考書目 侯文永、張冬茉 編譯原理 電子工業(yè)出版社 2002年 楊宗源編譯原理習題精選分析與解答清華大學出版社 2003 徐國
4、定 楊宗源 編譯程序構造 華東師范大學出版社 1989.10 Kenneth C. Loudon Compiler Construction: Principles and Practice Pws Publishing Company 1997 Alfred V. Aho Ravi Sethi Jeffrey D. Ullman Compilers Principles, Techniques, and Tools Addison-Wesley, Reading, Mass, 1986 Charles N. Fischer Richard J. LeBlanc, Jr. Crafting A
5、 Compiler The Benjamin/Cummings Publishing Company 1988 Dick Grune, Henri E Bal, Ceriel J H Jacobs,Koen G Langendoen, Modern Compiler Design John Wiley & Sons, Ltd, 2000,2020/8/31,華東師大信息學院計算機科學技術系,7,第一章 編譯概述,1.1 語言處理與編譯程序 1.1.1 程序設計語言的引入是解決人機對話鴻溝的一個里程碑,2020/8/31,華東師大信息學院計算機科學技術系,8,語言處理與編譯程序,1.1.2 程序
6、設計語言分類 程序設計語言是遵守一定規(guī)范的、描述“計算”（Computing）過程的形式語言。一般可以劃分 ： 低級語言 低級語言是面向機器的語言，它是為特定的計算機系統(tǒng)設計的語言。如：機器指令、匯編語言是低級語言。 高級語言 高級語言是與具體計算機無關的“通用”語言，它更接近于人類的自然語言和數(shù)學表示。如：FORTRAN、Pascal、C、JAVA等等高級語言 。 其他語言 如：控制命令語言、查詢語言、腳本語言等。,2020/8/31,華東師大信息學院計算機科學技術系,9,語言處理與編譯程序,1.1.3 語言處理程序 翻譯程序(Translator) 翻譯程序是一種語言處理程序，它將輸入的用
7、程序設計語言（源語言）書寫的程序（源程序）轉換為等價的用另一種語言書（目標語言）寫的程序（目標程序）。 若源語言是匯編語言，目標語言是機器語言，稱這種翻譯程序為匯編程序。 若源語言是高級語言，目標語言是低級語言，稱這種翻譯程序為編譯程序 。 若源語言是高級語言，目標語言是另一種高級語言，稱這種翻譯程序為轉換程序 。,2020/8/31,華東師大信息學院計算機科學技術系,10,語言處理與編譯程序,解釋程序（Interpreter） 解釋程序是一種語言處理程序，它對源程序逐個語句地進行分析，并根據(jù)每個語句的含義執(zhí)行語句指定的功能。 編譯程序（翻譯程序）與解釋程序主要的不同是：編譯程序將先生成目標程
8、序，再執(zhí)行目標程序，而解釋程序不生成目標程序，邊翻譯、邊執(zhí)行。形象地說，這類似于自然語言中的“筆譯”與“口譯”。 翻譯與解釋相結合的方法是一種不錯的方法：即先將源程序翻譯為中間語言表示的代碼，然后再解釋執(zhí)行。例如，JAVA語言的源程序翻譯為一種稱為Bytecode的中間代碼，再通過JAVA虛擬機解釋執(zhí)行。,2020/8/31,華東師大信息學院計算機科學技術系,11,語言處理與編譯程序,編譯程序的一個實例 FACOM M-340的C語言編譯器,2020/8/31,華東師大信息學院計算機科學技術系,12,語言處理與編譯程序,相關說明 CV、CPP與語言、機器相關，ASM、LINK與機器相關，而CS
9、A、CSG組成了編譯程序的主體。 稱CSA為編譯器的前端獨立于目標語言，稱CSG為編譯器的后端面向目標語言。 遍 在編譯過程中，掃描一遍源程序（輸入文件），經(jīng)處理形成一個輸出文件，稱為一遍。 合理地決定“遍數(shù)”，可提高效率（時/空） LINK程序 linker：連接程序： 多個不同的目標文件 一個 可執(zhí)行文件 loader：裝配程序：相對地址 絕對地址,2020/8/31,華東師大信息學院計算機科學技術系,13,語言處理與編譯程序,編譯器所在的集成環(huán)境 編輯器（Editor) 調(diào)試器（Debugger) 描述器（Profiler) 項目管理器（Project Manager)等,2020/8/
10、31,華東師大信息學院計算機科學技術系,14,編譯程序概貌,1.2 編譯過程和編譯程序的基本結構 抽象地看：,2020/8/31,華東師大信息學院計算機科學技術系,15,這是一個邏輯模型,獨立于具體的語言和機器,2020/8/31,華東師大信息學院計算機科學技術系,16,以賦值語句 pos:=init+rate*60 為例來了解編譯的全過程 詞法分析 (Lexical Analysis) 功能： a) 掃描源程序的字符串，識別出意義獨立的最小的詞法單位單詞（Token）。 b) 刪除注解、空格、回車及與輸入介質(zhì)有關的符號。 c) 報告詞法錯誤。 如上述賦值語句經(jīng)過詞法分析后輸出為如下單詞： (
11、ID,pos) (OP,:=) (ID,init) (OP,+) (ID,rate) (OP,*) (CONST,60),2020/8/31,華東師大信息學院計算機科學技術系,17,語法分析 (Syntax Analysis) 功能：對輸入的單詞串，按程序設計語言的語法規(guī)則，檢查源程序句法正確性。 例如某語言關于賦值語句的語法規(guī)則是： 賦值語句是：ID:=EXP ID、CONST是EXP 若EXP1和EXP2是EXP，則EXP1+EXP2、 EXP1*EXP2、 (EXP1)是EXP。 可以通過自頂向下或自底向上的句法分析方法，建立分析樹（又稱 句法樹、推導樹）進行句法分析。,2020/8/3
12、1,華東師大信息學院計算機科學技術系,18,對此例，分析樹為：,2020/8/31,華東師大信息學院計算機科學技術系,19,語義分析 (Semantic Analysis) 功能：檢查語義的正確性，完成語義解釋及必要的轉換。 例如：此例中各變量的數(shù)據(jù)類型是float，由于rate與60的類型不同就應該進行轉換，即將60轉換為60.0。 中間代碼生成 （Intermediate Code Generation） 功能：將單詞串轉換為等價的中間代碼串。 常見的中間代碼有：四元組、三元組、 逆波蘭（后綴）表示等。 上例中的賦值語句可翻譯為（四元組形式）： (float， ，60，t1) (*，ID.
13、rate，t1，t2) (+，ID.init，t2，t3) (:=,t3, ,ID.pos) 其中t1，t2，t3是臨時變量、ID.x是x在符號表中的位置。,2020/8/31,華東師大信息學院計算機科學技術系,20,代碼優(yōu)化 (Code Optimization) 功能：以提高目標代碼運行的時/空間效率為目的 的對中間代碼進行等價變換。 常見的方法有：刪除無用賦值和多余運算、常量合并、運算強度削弱、代碼外提、復寫傳播等等。 此例中的中間代碼通過優(yōu)化可為： (*，ID.rate，60.0，t1) (+，ID.init，t1，t2) (:=，t2， ，ID.pos) 代碼生成 （Code Gen
14、eration） 功能：將中間代碼串轉換為匯編代碼或機器指令。,2020/8/31,華東師大信息學院計算機科學技術系,21,代碼生成,此例中優(yōu)化后的中間代碼可生成如下的匯編代碼： LOAD R0, drate(R3) LOAD R1, d60.0(R3) MULT R0, R1 LOAD R0, dinit(R3) ADD R0, R1 STORE R1, dpos(R3) 其中R3是基地址寄存器，dx是x的位移（相對于R3的內(nèi)容）。,2020/8/31,華東師大信息學院計算機科學技術系,22,出錯處理 (Error Handle) 功能：顯示出錯的位置、性質(zhì)，限制出錯的影響，為盡可能多地發(fā)現(xiàn)
15、錯誤做些恢復工作。 符號表管理 (Symbol-Table Management) 功能：管理源程序中各種數(shù)據(jù)對象及其各種屬性，提供包括生成、查詢、更新等各種功能。,2020/8/31,華東師大信息學院計算機科學技術系,23,編譯程序的生成方法,1.3 編譯程序的生成方法 1.3.1 手工生成 完全由人采用低級語言開發(fā)編譯程序，工作量很大。 1.3.2 自動生成 利用自動生成工具開發(fā)編譯程序。如： LEX 詞法分析程序的自動生成程序 YACC、LLgen 語法分析程序的自動生成程序 GAG、CGSS 代碼生成程序的自動生成程序,2020/8/31,華東師大信息學院計算機科學技術系,24,1.3.3 其他編譯模式 前面討論的編譯模式稱為“完全編譯”。 其他編譯模式有： 交互式編譯允許通過交互方式處理源程序中的錯誤，及時改錯。允許部分或逐步測試。 增量編譯允許在修改了部分程序結構后僅對該修改部分重新編譯，而不一定對整個程序進行編譯。 問題：如何實現(xiàn)？,
編譯原理-計算機科學技術系.ppt
