編譯程序原理與實現(xiàn)：第1章 編譯程序介紹

1、第1章 編譯程序概述問卷對編譯程序的了解程度?有沒有接觸過編譯器？可不可以不用編譯器？編譯器可以幫助我們做什么？編程過程中遇到過哪些編譯錯誤? 出現(xiàn)非法字符；標識符未聲明的錯誤;標識符未定義的錯誤;標識符使用和聲明不匹配的錯誤;單詞拼寫錯誤;符號使用錯誤;第1章 編譯程序概述1.1 程序設計語言1.2 程序設計語言的實現(xiàn)方式1.3 編譯程序的伙伴程序1.4 編譯程序的功能結構分解1.5 編譯程序的設計與實現(xiàn)1.1 程序設計語言1.1 程序設計語言歷史1800，第一個程序：Jacquard loom 第一個程序員：Analytical engine,Ada Lovelace; Grace Hop

2、per;董鐵寶張綺霞1950，第一個程序設計語言 (FORTRAN; COBOL; Algol60; LISP)1960，涌現(xiàn)了上百種程序設計語言 (特殊目的語言; 通用語言)1970，簡化, 抽象 (PASCAL; C; )1980，面向對象語言 (Ada; Modular; Smalltalk; C+ )1990，網絡語言 (Java), Libraries, 腳本語言 (Perl; Javascript)2000，說明語言(XML,UML,Z)1.1 程序設計語言分類（幾千種程序設計語言）功能科學計算(Fortran); 商業(yè)數(shù)據處理(Cobol); 表處理(Lisp); 格式處理(La

3、tex); 數(shù)據庫語言(SQL); 抽象級別低級機器語言 & 匯編語言高級 (不同范例paradigms)劃代(ith-Generation Language，iGL)1GL：機器語言2GL：匯編語言3GL：高級程序設計語言，如FORTRAN，ALGOL，BASIC，LISP等； 4GL：為特定應用設計的語言，如數(shù)據庫查詢語言SQL,文本排版Postscript等； 5GL：指基于邏輯和約束的語言，如Prolog，OPS51.1 程序設計語言高級程序語言 (不同范例paradigms)過程式(Procedural programming languages-imperative)程序中指明如何

4、完成一個計算任務FORTRAN, PASCAL, C, C+, C#, Java函數(shù)式(Functional programming languages-declarative)程序中指明要進行哪些計算LISP, HASKELL, ML邏輯式(Logical programming languages-declarative)事實+推理規(guī)則PROLOG對象式(Object-oriented programming languages)支持面向對象編程Smalltalk, Java, C+機器語言和匯編語言的例子 機器語言語句：匯編語言語句：C7 06 0000 0002MOV X,2表示在IB

5、M PC上使用的Intel 8x86處理器將數(shù)字2移至地址0000(16進制)假設X的存儲地址是0000過程式和函數(shù)式程序設計語言過程式語言(C語言)：#define TYPE intvoid square(TYPE x, int n) for(int i=0; in; i+) *(x+i)*=*(x+i);求n個數(shù)的平方。函數(shù)式語言(Haskell)：fun square()= | square(a:x)= a*a : square(x)邏輯式程序設計語言domains person, another = symbolpredicates likes(person, another). cl

6、auses likes(jack, sussan). likes(john, marry). likes(tom, cathy). likes(mark, ellen). likes(bob, tom). likes(richard, ellen). likes(tom, ellen). likes(jack, X) if likes(tom, X).【事實】 Jack 喜歡 Sussan John 喜歡 Marry Tom 喜歡 Cathy Mark 喜歡 Ellen Tom 喜歡 Ellen【規(guī)則】 如果Tom喜歡X，那么Jack喜歡Xlikes(jack, ellen)?1.1 程序設計

7、語言不同的程序設計語言機制(函數(shù)式、過程式、邏輯式、對象式)，需要采用不同的技術編寫編譯程序過程式語言的編譯是對象式語言編譯的基礎本課程重點關注過程式程序設計語言編譯程序的構造原理和技術第1章 編譯程序概述1.1 程序設計語言1.2 程序設計語言的實現(xiàn)方式1.3 編譯程序的伙伴程序1.4 編譯程序的功能結構分解1.5 編譯程序的設計與實現(xiàn)1.2 程序設計語言的實現(xiàn)方式1.2 程序設計語言的實現(xiàn)方式編譯器(Compiler)：編譯器將某種語言(源語言)編寫的程序翻譯成 語義等價的另一種語言(目標語言)編寫的程序。目標程序若是可執(zhí)行的機器語言程序，則可以被用戶調用，處理輸入并產生輸出。目標程序若是

8、匯編語言的程序，則須經匯編器匯編后方可執(zhí)行。編譯器的重要任務之一是報告它在翻譯過程中發(fā)現(xiàn)的源程序中的錯誤。編譯器輸入源程序目標程序目標程序輸出(結果)錯誤1.2 程序設計語言的實現(xiàn)方式解釋器(Interpreter)：解釋器直接利用用戶提供的輸入執(zhí)行源程序中指定的操作。解釋過程中若發(fā)現(xiàn)錯誤，則返回修改源程序，修改后重新解釋執(zhí)行。解釋器輸入程序輸出（結果）1.2 程序設計語言的實現(xiàn)方式編譯器和解釋器的比較相同點使用相同的實現(xiàn)技術區(qū)別實現(xiàn)機制: 翻譯 (程序 to 程序)vs. 解釋(指令 to 指令序列)執(zhí)行效率: 高 vs. 低存儲代價: 少 vs. 多錯誤診斷：差 vs. 好 解釋器相對于編

9、譯器的優(yōu)勢可移植性好: Java支持交互式程序設計錯誤診斷效果好編譯器的優(yōu)勢在于：目標程序的執(zhí)行速度比解釋器快很多最大區(qū)別/根本區(qū)別：目標程序1.2 程序設計語言的實現(xiàn)方式程序設計語言的實現(xiàn)方式編譯方式解釋方式轉換方式：編譯器的開發(fā)代價是非常昂貴的，在可能的情況下，可以將一種語言的程序轉換成另一種語言的程序，利用另一種語言的編譯器進行編譯前提條件：兩種語言在語法和語義上很近似，或者一種語言是另一種語言的擴展實例：C+ CL源程序轉換器L源程序L編譯器目標程序第1章 編譯程序概述1.1 程序設計語言1.2 程序設計語言的實現(xiàn)方式1.3 編譯程序的伙伴程序1.4 編譯程序的功能結構分解1.5 編譯

10、程序的設計與實現(xiàn)1.3 編譯程序的伙伴程序1.3 編譯程序的伙伴程序EditorPreprocessorCompilerAssemblerLinkerLoader Skeletal Source ProgramPreprocessorCompilerTarget Assembly ProgramAssemblerRelocatable Machine Code Loader/LinkerAbsolute Machine CodeEditorSource Program 編輯器 (editor) 除一般的文本編輯功能外，還可以對正在編輯的文本進行分析、提示、自動提供關鍵字匹配等功能；預處理器(p

11、reprocessor) 刪除源程序中的注釋、執(zhí)行宏替換以及包含文件的嵌入等；匯編程序(assembler) 將編譯程序生成的匯編代碼匯編成機器代碼；連接程序(linker) 將不同的目標文件連接到一個可執(zhí)行的文件中；裝入程序(loader) 將程序加載到內存中以便執(zhí)行；1.3 編譯程序的伙伴程序第1章 編譯程序概述1.1 程序設計語言1.2 程序設計語言的實現(xiàn)方式1.3 編譯程序的伙伴程序1.4 編譯程序的功能結構分解1.5 編譯程序的設計與實現(xiàn)1.4 編譯程序的功能結構分解1.4 編譯程序的功能結構分解編程問題為高級程序設計語言開發(fā)編譯器就是一個編程問題How?需要弄清已知情況：源語言、目

12、標語言和實現(xiàn)語言的詞法、語法、語義規(guī)則需要解決的問題Input ：源語言的程序 = 字符序列Output：目標語言的程序 = 目標指令序列Data structure + algorithm考慮 “自然語言翻譯”過程：從中文到英文翻譯的一般過程:你能夠通過自己的努力實現(xiàn)你的夢想!識別單詞檢查語法檢查語義翻譯你能夠通過自己的努力實現(xiàn)你的夢想!Youcanput your dreams into realitythrough your efforts!1.4 編譯程序的功能結構分解自然語言翻譯過程總結掌握源語言和目標語言：詞法、語法和語義翻譯過程包括：分析源句子是否正確拼寫，包括識別單詞及其屬性依

13、據源語言的語法建立語法結構檢查句子是否有意義將句子翻譯成目標語言翻譯每個語法部分將其組合成有意義的目標語言句子I eat sky in dog.1.4 編譯程序的功能結構分解如何將一種程序設計語言的程序翻譯成另一種程序設計語言的程序1.4 編譯程序的功能結構分解表 處 理 錯 誤 處 理 目標代碼生成中間代碼優(yōu)化中間代碼生成語義分析語法分析詞法分析目標程序源程序分析綜合1.4 編譯程序的功能結構分解詞法分析掃描源程序的字符流；整理成有意義的單詞(token)序列;識別并報告詞法錯誤語法分析掃描token序列；確定程序的語法結構；將分析結果表示成分析樹或語法樹;識別并報告語法錯誤語義分析建立符號

14、表，標識符的屬性表靜態(tài)語義檢查，如類型檢查識別并報告語義錯誤if (x=j) z=0; else z=1;EAssAssIf-stmtx: intz: intj: intz=0z=1if(idassid)idass0;elseidass1;1.4 編譯程序的功能結構分解代碼生成中間代碼生成：為優(yōu)化和移植考慮，不是必要的目標代碼生成：通常生成匯編代碼代碼優(yōu)化目的是提高目標程序的執(zhí)行效率中間代碼優(yōu)化目標代碼優(yōu)化表處理符號表、常量表等管理錯誤處理詞法錯誤、語法錯誤、語義錯誤的處理if (x=j) z=0; else z=1;(=,x,j,t1)(JMP0,t1,-,elseL)(=,0,-,z)(J

15、MP,-,-,outL)(Label, -,-,elseL)(=,1,-,z)(Label,-,-,outL)x=y*0 x=0 幾個相關術語前端(front end)：編譯程序中與源語言有關，與目標程序無關的部分，稱為前端。通常包括詞法分析、語法分析、語義分析、中間代碼生成，與目標機無關的中間代碼優(yōu)化部分。后端(back end)：編譯程序中與源語言無關，與目標程序有關的部分，稱為后端。通常包括與目標機有關的中間代碼優(yōu)化、目標代碼生成等部分。遍/趟(pass)：所謂“遍”就是對源程序或源程序的中間表示形式從頭到尾掃描一次，并作加工處理，生成新的中間結果或目標程序。可以詞法分析、語法分析、語義

16、分析等階段各作為單獨一遍；也可以詞法分析作為語法分析的子程序；還可以整個編譯程序一遍掃描完成 第1章 編譯程序概述1.1 程序設計語言1.2 程序設計語言的實現(xiàn)方式1.3 編譯程序的伙伴程序1.4 編譯程序的功能結構分解1.5 編譯程序的設計與實現(xiàn)1.5 編譯程序的設計與實現(xiàn)1.5 編譯程序的設計與實現(xiàn)Where do compilers come from?T型圖(T-diagram):與編譯程序相關的語言有3個，源語言S,目標語言T,實現(xiàn)語言I，T型圖表示如下：第一個編譯器是用機器語言或匯編語言寫的。機器語言/匯編語言不方便，效率低，不易維護。STISAA1.5 編譯程序的設計與實現(xiàn)-自展

17、法自展法：先用目標機的機器語言或匯編語言書寫源語言的一個子集的編譯程序，然后再用這個子集語言書寫源語言的編譯程序，當源語言很復雜，上述過程可能會分成若干步，就像滾雪球一樣，直至生成源語言的編譯程序為止，這樣的實現(xiàn)方式稱為自展技術。第1步：用A機器的機器語言或匯編語言A書寫L1語言的編譯程序C1, 第2步：用L1語言書寫L語言的編譯程序C2,第3步：在A機器上運行C2,即在A機器上實現(xiàn)了L語言的編譯。1.5 編譯程序的設計與實現(xiàn)-自展法自展法：如果把L分成L1,L2,L，即L2是L1的擴充，L是L2的擴充，則自展法可用下圖表示：AA1.5 編譯程序的設計與實現(xiàn)-移植法但是一個高級語言往往需要在不

18、同的目標機上實現(xiàn)，這就提出了如何把已在某機器上實現(xiàn)的一個高級語言的編譯程序能否移植到另一個目標機上。利用自展技術也可實現(xiàn) 。我們希望能利用A機器上已有的L語言的編譯程序，實現(xiàn)B機器上的編譯程序以縮短開發(fā)時間。移植的實現(xiàn)：(1) 開發(fā)一個A代碼到B代碼的翻譯程序(2) 重建L在A機器上的編譯器的后端，使之生成B機器上的代碼(3)交叉編譯：LLBB1.5 編譯程序的設計與實現(xiàn)-交叉編譯利用A機器上已有的L語言的編譯程序使其在B機器上也能實現(xiàn) 第1步： 我們用L語言書寫L語言的編譯程序C1, 產生B機器上的匯編語言或機器語言； 第2步：用A機器上已有的L語言的編譯程序編 譯器C1,得到用A語言書寫的L語言 在B機器上的編譯器C2(交叉編譯器)。第3步：用C2編譯C1,得到C3.經過以上3步得到L語言在B機器上的編譯器。1.5 編譯