第一章引論重點：教學目的，教學要求，學習方法，課程的基本內(nèi)容，編譯系統(tǒng)的結構，編譯程序的生成。難點：編譯程序的生成。

SchoolofComputerScience&TechnologyHarbinInstituteofTechnology2024/2/512024/2/52第1章

引論1.1程序設計語言1.2程序設計語言的翻譯1.3編譯程序的總體結構1.4編譯程序的組織1.5編譯程序的生成1.6本章小結2024/2/531.1程序設計語言機器語言(MachineLanguage)與匯編語言(AssembleLanguage)0、1代碼與助記符：更接近于計算機硬件指令系統(tǒng)的工作高級語言(HighLevelLanguage)其表示方法更接近于待解問題的表示方法定義數(shù)據(jù)、描述運算、控制流程、傳輸數(shù)據(jù)如：C、FORTRAN、PASCAL、C++、JAVA、SQL(數(shù)據(jù)定義、數(shù)據(jù)操作)命令語言(CommandLanguage)控制系統(tǒng)的工作——以功能封裝為特征如UNIX上的shell101110000010101100010101(B82B15)1000111011011000(8ED8)101000010000000000000000(A10000)10001011000111100000001000000000(8B1E0200)101110010000000000000000(B90000)0000001111001000(03C8)0000001111001011(03CB)10001011000011100000010000000000(8B0E0400)101110000000000001001100(B8004C)1100110100100001(CD21)intmain{ inta,b,c; a=1234h; b=5678h; c=a+b; return0;}assumecs:code,ds:datadatasegment dw1234h,5678hdataendscodesegmentstart: movax,data movds,ax movax,ds:[0] movbx,ds:[2] movcx,0 addcx,ax addcx,bx movcx,ds:[4] movax,4c00h int21h codeendsendstart程序設計語言的分類強制式（命令式）語言(ImperativeLanguage)通過指明一系列可執(zhí)行的運算及運算的次序來描述計算過程的語言；FORTRAN(段結構)、BASIC、Pascal(嵌套結構)、C……程序的層次性和抽象性不高2024/2/54程序設計語言的分類申述式語言（DeclarativeLanguage）著重描述要處理什么，而非如何處理的非命令式語言函數(shù)(應用)式語言(FunctionalLanguage)基本運算單位是函數(shù)，如LISP、ML……邏輯式(基于規(guī)則)語言(LogicalLanguage)基本運算單位是謂詞，如Prolog，Yacc……2024/2/55程序設計語言的分類面向?qū)ο笳Z言(Object-OrientedLanguage)以對象為核心，如Smalltalk、C++、Java、Ada(程序包)……具有識認性（對象）、類別性（類）、多態(tài)性和繼承性2024/2/561.2程序設計語言的翻譯翻譯程序(Translator)將某一種語言描述的程序(源程序——SourceProgram)翻譯成等價的另一種語言描述的程序(目標程序——ObjectProgram)的程序。翻譯程序源程序目標程序(*.C/*.PAS)(*.OBJ/*.EXE)2024/2/572024/2/581.2程序設計語言的翻譯解釋程序(Interpreter)一邊解釋一邊執(zhí)行的翻譯程序口譯與筆譯（單句提交與整篇提交）源程序輸入數(shù)據(jù)計算結果解釋程序2024/2/591.2程序設計語言的翻譯編譯程序(Compiler)將源程序完整地轉(zhuǎn)換成機器語言程序或匯編語言程序，然后再處理、執(zhí)行的翻譯程序高級語言程序→匯編/機器語言程序源程序目標程序編譯程序2024/2/5101.2程序設計語言的翻譯SP Compiler

S-Source O-Object OP P-ProgramInput RS

RS-RunSys. Output 編譯系統(tǒng)(CompilingSystem)編譯系統(tǒng)=編譯程序+運行系統(tǒng)支撐環(huán)境、運行庫等2024/2/5111.2程序設計語言的翻譯其它翻譯程序：匯編程序(Assembler)交叉匯編程序(CrossAssembler)反匯編程序（Disassembler)交叉編譯程序（CrossCompiler)反編譯程序（piler）可變目標編譯程序（RetargetableCompiler)并行編譯程序（ParallelizingCompiler）診斷編譯程序（DiagnosticCompiler)優(yōu)化編譯程序（OptimizingCompiler)2024/2/5121.2程序設計語言的翻譯—匯總解釋程序數(shù)據(jù)結果編譯系統(tǒng)機器語言程序機器語言程序機器語言程序……匯編語言程序高級語言程序匯編語言程序匯編語言程序……高級語言程序高級語言程序……匯編程序反匯編程序編譯程序反編譯程序匯編程序反匯編程序編譯程序反編譯程序匯編程序編譯程序交叉匯編程序交叉編譯程序可變目標編譯程序圖1.5主要翻譯程序匯總運行系統(tǒng)編譯程序的工作，從輸入源程序開始，到輸出目標程序結束，與自然語言之間的翻譯有很多相似之處。一段英文翻譯成中文，需經(jīng)下列步驟：識別出句子中的單詞分析句子的語法結構根據(jù)句子的含義進行初步分析對譯文進行修飾寫出最后的譯文編譯程序代碼優(yōu)化語法分析語義分析及中間代碼生成目標代碼生成IamaexperienceteacherMain(){printf(“hello”)}構成編譯程序各個階段詞法分析1.3編譯程序總體結構2024/2/5141.3編譯程序總體結構目標代碼生成器代碼優(yōu)化器語義分析與中間代碼生成器語法分析器表格管理出錯處理中間代碼中間代碼目標代碼語法單位單詞符號詞法分析器源程序2024/2/5151、詞法分析例：sum=(10+20)*(num+square);結果(標識符，sum)(賦值號，=)(左括號，()(整常數(shù)，10)(加號，+)(整常數(shù)，20)(右括號，))(乘號，*)(左括號，()(標識符，num)(加號，+)(標識符，square)(右括號，))(分號，;)2024/2/5161、詞法分析詞法分析由詞法分析器(LexicalAnalyzer)完成，詞法分析器又稱為掃描器(Scanner)詞法分析器從左到右掃描組成源程序的字符串，并將其轉(zhuǎn)換成單詞(記號—token)串；同時要：查詞法錯誤，進行標識符登記——符號表管理。輸入：字符串 輸出：(種別碼，屬性值)——序?qū)傩灾怠猼oken的機內(nèi)表示2024/2/5172、語法分析語法分析由語法分析器(SyntaxAnalyzer)完成，語法分析器又叫Parser。功能：Parser實現(xiàn)“組詞成句”將詞組成各類語法成分：表達式、因子、項，語句，子程序…構造分析樹指出語法錯誤指導翻譯輸入：token序列輸出：語法成分2024/2/5182、語法分析sum=(10+20)*(num+square);2024/2/5193、語義分析語義分析(semanticanalysis)一般和語法分析同時進行，稱為語法制導翻譯(syntax-directedtranslation)功能：分析由語法分析器識別出來的語法成分的語義對于說明語句,獲取標識符的屬性：類型、作用域等對于可執(zhí)行語句，語義檢查：運算的合法性、取值范圍等，生成中間代碼變量的靜態(tài)綁定：數(shù)據(jù)的相對地址2024/2/5204、中間代碼生成中間代碼(intermediateCode)例:sum=(10+20)*(num+square);中間代碼表示形式：

T1=10+20

T2=num+square

T3=T1*T2sum=T3

2024/2/5214、中間代碼生成中間代碼的常用表示形式后綴表示(逆波蘭Anti-PolishNotation)sum1020+numsquare+*=前綴表示(波蘭PolishNotation)=sum*+1020+numsquare

四元式表示(三地址碼)(+，10，20，T1)(+，num，square，T2)(*，T1，T2，T3)(=，T3

，，sum)

三元式表示(+，10，20)(+，num，square)(*，⑴，⑵)(=，sum，⑶)

語法樹2024/2/522波蘭表示問題——Lukasiewicz1929年發(fā)明

中綴表示(Infixnotation):(a+①b)*(-c+②d)+③e/f波蘭表示（Polish/Prefix/Parenthesis-free/Lukasiewicznotation）——也就是前綴表示+③*+①ab+②@cd/ef逆波蘭表示(ReversePolish/Suffix/Postfixnotation)——也就是后綴表示

ab+①c@d+②*ef/+③運算順序從左向右2024/2/5234、中間代碼生成中間代碼的特點簡單規(guī)范與機器無關易于優(yōu)化與轉(zhuǎn)換三地址碼的另一種表示形式：

T1=10+20

T2=num+square

T3=T1*T2sum=T3

其它類型的語句例：printf(“hello”)x:=s （賦值）paramx （參數(shù)）callf （函數(shù)調(diào)用）注釋s是hello的地址f是函數(shù)

printf的地址2024/2/524代碼優(yōu)化(optimization)是指對中間代碼進行優(yōu)化處理，使程序運行能夠盡量節(jié)省存儲空間，更有效地利用機器資源，使得程序的運行速度更快，效率更高。當然這種優(yōu)化變換必須是等價的。

與機器無關的優(yōu)化與機器有關的優(yōu)化5、代碼優(yōu)化2024/2/525與機器無關的優(yōu)化局部優(yōu)化常量合并：常數(shù)運算在編譯期間完成，如8+9*4公共子表達式的提取:在基本塊內(nèi)進行的循環(huán)優(yōu)化強度削減用較快的操作代替較慢的操作代碼外提將循環(huán)不變計算移出循環(huán)2024/2/526與機器有關的優(yōu)化寄存器的利用將常用量放入寄存器，以減少訪問內(nèi)存的次數(shù)體系結構MIMD、SIMD、SPMD、向量機、流水機存儲策略根據(jù)算法訪存的要求安排：Cache、并行存儲體系——減少訪問沖突任務劃分按運行的算法及體系結構，劃分子任務(MPMD)2024/2/5276、目標代碼生成將中間代碼轉(zhuǎn)換成目標機上的機器指令代碼或匯編代碼確定源語言的各種語法成分的目標代碼結構（機器指令組/匯編語句組）制定從中間代碼到目標代碼的翻譯策略或算法目標代碼的形式具有絕對地址的機器指令匯編語言形式的目標程序模塊結構的機器指令（需要鏈接程序）2024/2/5287、表格管理管理各種符號表(常數(shù)、標號、變量、過程、結構……)，查、填（登記、查找）源程序中出現(xiàn)的符號和編譯程序生成的符號，為編譯的各個階段提供信息。輔助語法檢查、語義檢查完成靜態(tài)綁定、管理編譯過程Hash表、鏈表等各種表的查、填技術“數(shù)據(jù)結構與算法”課程的應用符號表是一個數(shù)據(jù)結構.每個標識符在符號表中都有一條記錄名字記號類型種屬……addrid1(25)id2(25)

b

a例：inta,b;int簡變

0

4int簡變7、表格管理2024/2/5308、錯誤處理進行各種錯誤的檢查、報告、糾正，以及相應的續(xù)編譯處理(如：錯誤的定位與局部化)詞法：拼寫……語法：語句結構、表達式結構……語義：類型不匹配、參數(shù)不匹配……2024/2/531模塊分類分析：詞法分析、語法分析、語義分析綜合：中間代碼生成、代碼優(yōu)化、目標代碼生成輔助：符號表管理、出錯處理8項功能對應8個模塊2024/2/532語句sum=(10+20)*(num+square);的翻譯過程2024/2/5331.4編譯程序的組織根據(jù)系統(tǒng)資源的狀況、運行目標的要求……等，可以將一個編譯程序設計成多遍（Pass）掃描的形式，在每一遍掃描中，完成不同的任務。如：首遍構造語法樹，二遍處理中間表示，增加信息等。遍可以和階段相對應，也可以和階段無關單遍代碼不太有效2024/2/5341.4編譯程序的組織編譯程序的設計目標規(guī)模小、速度快、診斷能力強、可靠性高、可移植性好、可擴充性好目標程序也要規(guī)模小、執(zhí)行速度快編譯系統(tǒng)規(guī)模較大，因此可移植性很重要為了提高可移植性，將編譯程序劃分為前端和后端2024/2/5351.4編譯程序的組織前端與源語言有關、與目標機無關的部分詞法分析、語法分析、語義分析與中間代碼生成、與機器無關的代碼優(yōu)化后端與目標機有關的部分與機器有關的代碼優(yōu)化、目標代碼生成2024/2/5361.5編譯程序的生成如何實現(xiàn)編譯器？直接用可運行的代碼編制——太費力！自舉-使用語言提供的功能來編譯該語言自身。“第一個編譯器是怎樣被編譯的？”2024/2/5371.T形圖表示語言翻譯的T形圖源語言實現(xiàn)語言目標語言功能2024/2/538問題一：如何直接在一個機器上實現(xiàn)C語言編譯器？解決：用匯編語言實現(xiàn)一個C子集的編譯程序(P0)用匯編程序處理該程序,得到(P2:可直接運行)用C子集編制C語言的編譯程序(P3)用P2編譯P3，得到P42.自展2024/2/5394.用P2編譯P3，得到P4Ｃ語言機器語言機器語言P4Ｃ子集機器語言機器語言P2獲得一個工具Ｃ子集匯編語言機器語言P01.用匯編語言實現(xiàn)一個C子集的編譯程序(P0)匯編語言機器語言機器語言Ｃ子集機器語言機器語言P1P22.用匯編程序(P1)處理該程序,得到(P2:可直接運行)Ｃ語言Ｃ子集機器語言P33.用C子集編制C語言的編譯程序(P3)2024/2/5403.移植問題二：A機上有一個C語言編譯器，是否可利用此編譯器實現(xiàn)B機上的C語言編譯器？條件：A機有C語言的編譯程序目的：實現(xiàn)B機的C語言的編譯Ｃ語言A編譯Ｂ機器Ｃ語言B編譯Ｂ機器要完成的任務2024/2/541Ｃ語言Ｃ語言Ｂ機器Ｃ語言Ａ機器Ｂ機器Ｃ語言Ｂ機器Ｂ機器Ｃ語言Ｃ語言Ｂ機器Ｃ語言Ａ機器A機器Ｃ語言A機器Ｂ機器要完成的任務要完成的任務需要一個工具需要一個工具1)問題的分析2024