復(fù)試編譯原理課件chapter1

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

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

引論1.1程序設(shè)計(jì)語(yǔ)言1.2程序設(shè)計(jì)語(yǔ)言的翻譯1.3編譯程序的總體結(jié)構(gòu)1.4編譯程序的組織1.5編譯程序的生成1.6本章小結(jié)2024/2/531.1程序設(shè)計(jì)語(yǔ)言機(jī)器語(yǔ)言(MachineLanguage)與匯編語(yǔ)言(AssembleLanguage)0、1代碼與助記符：更接近于計(jì)算機(jī)硬件指令系統(tǒng)的工作高級(jí)語(yǔ)言(HighLevelLanguage)其表示方法更接近于待解問(wèn)題的表示方法定義數(shù)據(jù)、描述運(yùn)算、控制流程、傳輸數(shù)據(jù)如：C、FORTRAN、PASCAL、C++、JAVA、SQL(數(shù)據(jù)定義、數(shù)據(jù)操作)命令語(yǔ)言(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程序設(shè)計(jì)語(yǔ)言的分類強(qiáng)制式（命令式）語(yǔ)言(ImperativeLanguage)通過(guò)指明一系列可執(zhí)行的運(yùn)算及運(yùn)算的次序來(lái)描述計(jì)算過(guò)程的語(yǔ)言；FORTRAN(段結(jié)構(gòu))、BASIC、Pascal(嵌套結(jié)構(gòu))、C……程序的層次性和抽象性不高2024/2/54程序設(shè)計(jì)語(yǔ)言的分類申述式語(yǔ)言（DeclarativeLanguage）著重描述要處理什么，而非如何處理的非命令式語(yǔ)言函數(shù)(應(yīng)用)式語(yǔ)言(FunctionalLanguage)基本運(yùn)算單位是函數(shù)，如LISP、ML……邏輯式(基于規(guī)則)語(yǔ)言(LogicalLanguage)基本運(yùn)算單位是謂詞，如Prolog，Yacc……2024/2/55程序設(shè)計(jì)語(yǔ)言的分類面向?qū)ο笳Z(yǔ)言(Object-OrientedLanguage)以對(duì)象為核心，如Smalltalk、C++、Java、Ada(程序包)……具有識(shí)認(rèn)性（對(duì)象）、類別性（類）、多態(tài)性和繼承性2024/2/561.2程序設(shè)計(jì)語(yǔ)言的翻譯翻譯程序(Translator)將某一種語(yǔ)言描述的程序(源程序——SourceProgram)翻譯成等價(jià)的另一種語(yǔ)言描述的程序(目標(biāo)程序——ObjectProgram)的程序。翻譯程序源程序目標(biāo)程序(*.C/*.PAS)(*.OBJ/*.EXE)2024/2/572024/2/581.2程序設(shè)計(jì)語(yǔ)言的翻譯解釋程序(Interpreter)一邊解釋一邊執(zhí)行的翻譯程序口譯與筆譯（單句提交與整篇提交）源程序輸入數(shù)據(jù)計(jì)算結(jié)果解釋程序2024/2/591.2程序設(shè)計(jì)語(yǔ)言的翻譯編譯程序(Compiler)將源程序完整地轉(zhuǎn)換成機(jī)器語(yǔ)言程序或匯編語(yǔ)言程序，然后再處理、執(zhí)行的翻譯程序高級(jí)語(yǔ)言程序→匯編/機(jī)器語(yǔ)言程序源程序目標(biāo)程序編譯程序2024/2/5101.2程序設(shè)計(jì)語(yǔ)言的翻譯SP Compiler

S-Source O-Object OP P-ProgramInput RS

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

語(yǔ)法樹(shù)2024/2/522波蘭表示問(wèn)題——Lukasiewicz1929年發(fā)明

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

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

T1=10+20

T2=num+square

T3=T1*T2sum=T3

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

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

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

b

a例：inta,b;int簡(jiǎn)變

0

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