：參考資料等編著，電子工業(yè)1、編譯原理，主要參考資料：1、程序設(shè)計語言編譯原理，陳火旺編著，國防工業(yè)2、Compilers:Principles,Techniques,and

Tools。By:Alfred

V.Aho,Ravi

Sethi,Jeffrey

D.Ullman，人民郵電1、加深對程序 執(zhí)行過程的理解2、為了進一步編好程序為什么要設(shè)置編譯原理課程？本課程基本框架1、引論2、基礎(chǔ)知識：文法3、詞法分析理論模型——正規(guī)文法與有限自實現(xiàn)——詞法分析程序4、語法分析理論模型：自上而下分析——下推自自下而上分析——優(yōu)先分析和LR分析實現(xiàn)——遞歸下降分析法、YACC5、中間代碼生成語法制導(dǎo)翻譯6、符號表的組織與管理7、運行時數(shù)據(jù)區(qū)的管理：靜態(tài) 管理、棧式 管理、堆式 管理8、中間代碼優(yōu)化：局部優(yōu)化、循環(huán)優(yōu)化、窺孔優(yōu)化9、目標代碼生成第一章

編譯概述1.1翻譯程序與編譯程序程序設(shè)計語言–高級語言–匯編語言–機器語言在計算機上如何執(zhí)行一個高級語言程序？–把高級語言程序翻譯成機器語言程序–運行所得的機器語言程序求得計算結(jié)果翻譯–在不改變語義的條件下，把某種語言的源程序轉(zhuǎn)換成另一種語言程序——目標語言程序。解釋–接受某高級語言的一個語句輸入，進行解釋并控制計算機執(zhí)行，馬上得到這句的執(zhí)行結(jié)果，然后再接受下一句。第一章

編譯概述1.1翻譯程序與編譯程序解釋–以源程序作為輸入，不產(chǎn)生目標程序，一邊解釋一邊執(zhí)行。–優(yōu)點：直觀易懂，結(jié)構(gòu)簡單，易于實現(xiàn)人機–缺點：效率低第一章

編譯概述1.1翻譯程序與編譯程序編譯–由高級語言轉(zhuǎn)換為低級語言,然后對編譯出來的目標程序進行運行計算編譯與解釋的區(qū)別：解釋器是源程序的一個執(zhí)行系統(tǒng)，而編譯程序是源程序的一個轉(zhuǎn)換系統(tǒng)；解釋程序的工作結(jié)果是源程序的執(zhí)行結(jié)果，而編譯程序的工作結(jié)果是得到等價于源程序的某中目標機程序。第一章

編譯概述1.1翻譯程序與編譯程序基于編譯的高級語言源程序的執(zhí)行過程

–兩階段：編譯——運行源程序編譯程序目標代碼編譯時初始數(shù)據(jù)目運標行代子碼程序計算結(jié)果運行時第一章

編譯概述1.1翻譯程序與編譯程序基于編譯的高級語言源程序的執(zhí)行過程–三個階段的轉(zhuǎn)換：編譯——匯編——運行源程序編譯程序程匯序編語言目標編譯階段程機序器語言目標匯編程序匯編階段計算結(jié)果運行階段初始數(shù)據(jù)運行系統(tǒng)第一章 編譯概述1.1翻譯程序與編譯程序第一章

編譯概述1.2

編譯過程和編譯程序的基本結(jié)構(gòu)編譯過程–從輸入源程序開始到輸出目標程序為止的整個過程?？煞譃槲鍌€階段：詞法分析、語法分析、語義分析及中間代碼生成、代碼優(yōu)化、目標代碼生成源程序詞法分析器語法分析器生及語成中義間分代析碼器代碼優(yōu)化目標代碼生成目標程序出錯處理第一章 編譯概述1.2編譯過程和編譯程序的基本結(jié)構(gòu)編譯程序的基本結(jié)構(gòu)表格管理第一章 編譯概述1.2編譯過程和編譯程序的基本結(jié)構(gòu)編譯程序功能結(jié)構(gòu)1.詞法分析任務(wù)–輸入源程序，對構(gòu)成源程序的字符串進行掃描和分解，依照詞則，識別出一個個的單詞，并轉(zhuǎn)化為機器易于使用的內(nèi)碼形式。單詞–是高級語言中有實在意義的最小語法單位，它由字符構(gòu)成。詞

則–定義了單詞符號的形成規(guī)則Void

jisuan(){inty,c,d;float

x,a,b;x=a+b*50;y=c+)d*(x+b;}第一章 編譯概述1.2編譯過程和編譯程序的基本結(jié)構(gòu)編譯程序功能結(jié)構(gòu)詞法分析識別右邊程序中的單詞基本字：Void

,int,

float標識符：a,

b,c,d,

x,y,jisuan整常數(shù)：50運算符:：+,-,*,=界限符：{};,()第一章 編譯概述1.2編譯過程和編譯程序的基本結(jié)構(gòu)編譯程序功能結(jié)構(gòu)?1.轉(zhuǎn)詞換法內(nèi)分容析–對基本字、運算符、界限符的轉(zhuǎn)換–標識符的轉(zhuǎn)換–常數(shù)的轉(zhuǎn)換第一章 編譯概述1.2編譯過程和編譯程序的基本結(jié)構(gòu)編譯程序功能結(jié)構(gòu)詞法分析注：1)一般內(nèi)碼可用二元式（類號、內(nèi)碼）表示。對于標識符與常數(shù)是由用戶任意使用的，數(shù)目無限，解決辦法是給標識符分配一個類號，不同的標識符用它的符號表 地址（或變量地址）來區(qū)分，將這些地址當作內(nèi)碼給出。2)描述詞 則的有效工具是正規(guī)式和有限自定單詞如何構(gòu)成短語、–語言的規(guī)則，又稱為文語句、過程和程序2）語法檢查——通過語法分解，確定整個輸入串是否構(gòu)成語法上正確的句子、程序等。語則的表示：BNF如<Word>::={}，A::=a|b|cB注：語法分析對說明語句的處理是要填符號表，而對一般語句處理規(guī)則是構(gòu)造語法樹。第一章 編譯概述1.2編譯過程和編譯程序的基本結(jié)構(gòu)編譯程序功能結(jié)構(gòu)2.語法分析任務(wù)：1）組詞成句——在詞法分析的基礎(chǔ)上，根據(jù)語言的語

則或文法，把單詞符號組成各類的語法單位，如：短語、子句、語句、過程、程序。第一章 編譯概述1.2編譯過程和編譯程序的基本結(jié)構(gòu)編譯程序功能結(jié)構(gòu)2.語法分析例：賦值語句的語

則?A::=V=E?E::=T|E+T?T::=F|T*F?F::=V|(E)|C?V::=標識符?C::=常數(shù)第一章 編譯概述1.2編譯過程和編譯程序的基本結(jié)構(gòu)編譯程序功能結(jié)構(gòu)2.語法分析語法分析方法：推導(dǎo)（derive)和歸約(reduce)–推導(dǎo)：從文法的開始符號開始，按照語則，每次選擇某規(guī)則右部的一個候選式取代左部，直至識別了語句或者找到錯誤為止。其過程可用語法樹描述。–推導(dǎo)可分為：最左推導(dǎo)、最右推導(dǎo)–歸約：按照語

則，每次選擇某規(guī)則左部取代右部的一個候選式–規(guī)約可分為：最右歸約、最左歸約–注：語法＝詞 則＋語

則第一章 編譯概述1.2編譯過程和編譯程序的基本結(jié)構(gòu)編譯程序功能結(jié)構(gòu)3.語義分析及中間代碼生成任務(wù)在語法分析正確的基礎(chǔ)上，按照相應(yīng)語義規(guī)則，產(chǎn)生介于源代碼和目標代碼之間的一種代碼。注：這種中間代碼不依賴于機器，但又便于產(chǎn)生依賴于機器的目標代碼。兩階段工作–對每種語法范疇進行靜態(tài)語義檢查–若語義正確，就進行中間代碼的翻譯中間代碼形式–四元式、三元式、逆波蘭式–注：1）中間代碼是為后續(xù)的優(yōu)化和目標代碼生成提供方便，因此中間代碼的選擇往往與所采用的優(yōu)化技術(shù)和計算機硬件結(jié)構(gòu)有關(guān)。2）用得最廣的是四元式。第一章 編譯概述1.2

編譯過程和編譯程序的基本結(jié)構(gòu)編譯程序功能結(jié)構(gòu)4.代碼優(yōu)化任務(wù)對產(chǎn)生的中間代碼進行加工變換，以期在最后階段能產(chǎn)生更為高效（省時間、省空間）的目標代碼依據(jù)原則：程序的等價變換規(guī)則主要優(yōu)化內(nèi)容刪除公共子表達式、合并已知量、刪除無用賦值語句、循環(huán)優(yōu)化等第一章 編譯概述1.2編譯過程和編譯程序的基本結(jié)構(gòu)編譯程序功能結(jié)構(gòu)5.目標代碼生成任務(wù)：把中間代碼程序轉(zhuǎn)化成具體機器的指令序列注：轉(zhuǎn)換過程需涉及具體機器的指令系統(tǒng)以及寄存器分配等硬件功能。第一章 編譯概述1.2編譯過程和編譯程序的基本結(jié)構(gòu)編譯程序功能結(jié)構(gòu)6.表格與表格管理表格作用：–用于記錄源程序的各種信息以及編譯過程中的各種狀況，以便后續(xù)階段使用。與編譯前三階段有關(guān)的表格有：–符號表、常數(shù)表、標號表、分程序表、中間代碼表等。–注：在編譯過程中，隨著源程序的不斷被改造，編譯的各階段常常需要不同的表格，編譯過程的絕大多數(shù)時間是花在查表、造表和更新表格的事務(wù)上。在大多數(shù)的編譯程序中，表格專門由表格管理程序來處理。NAMEINFORMATIONm整型、變量地址n整型、變量地址k整型、變量地址第一章 編譯概述1.2

編譯過程和編譯程序的基本結(jié)構(gòu)編譯程序功能結(jié)構(gòu)6.表格與表格管理符號表：用來登記源程序中的常量名、變量名、數(shù)組名、過程名等的性質(zhì)、定義和 狀況。值14常數(shù)表登記各類常量(直接量)值注：標號表可與符號表合并(登記標號的定義與

)NAMEINFORMATION………….10四元式序號4標號表第一章 編譯概述1.2

編譯過程和編譯程序的基本結(jié)構(gòu)編譯程序功能結(jié)構(gòu)6.表格與表格管理NAMEINFORMATION………….INCWAP二目子程序、四元式序號1第一章 編譯概述1.2

編譯過程和編譯程序的基本結(jié)構(gòu)編譯程序功能結(jié)構(gòu)6.表格與表格管理

名表：登記過程的層號，分程序符號表的 (指分程序結(jié)構(gòu)的語言)等6.表格與表格管理中間代碼表：記錄四元式序列的表序號OPARG1ARG2RESULT（1）＝Im（2）=jn（3）=1k（4）J<100k(9)（5）+m10m（6）+n10n（7）+k1k（8）j(4)（9）return第一章 編譯概述1.2編譯過程和編譯程序的基本結(jié)構(gòu)編譯程序功能結(jié)構(gòu)7.出錯處理任務(wù)如果源程序有錯誤，編譯程序應(yīng)設(shè)法發(fā)現(xiàn)錯誤，并報告給用戶。注：查錯無形式化的辦法解決。完成：由專門的出錯處理程序來完成錯誤類型:–語法錯誤:在詞法分析和語法分析階段檢測出來。–語義錯誤：一般在語義分析階段檢測。第一章 編譯概述1.2

編譯過程和編譯程序的基本結(jié)構(gòu)編譯程序功能結(jié)構(gòu)8.遍產(chǎn)生背景一個具體的編譯器體系結(jié)構(gòu)可能按功能結(jié)構(gòu)方式組織起來，也可能是按別的方式組織起來。

“別的方式”從形式上看就是分遍的問題；按遍數(shù)可把編譯器分為一遍的和多遍的。第一章 編譯概述1.2

編譯過程和編譯程序的基本結(jié)構(gòu)編譯程序功能結(jié)構(gòu)8.遍遍：指對源程序或源程序的中間結(jié)果從頭到尾掃描一次，并做有關(guān)的加工處理，生成新的中間結(jié)果或目標代碼的過程。–注：遍與前述階段的含義毫無關(guān)系。第一章 編譯概述1.2

編譯過程和編譯程序的基本結(jié)構(gòu)編譯程序功能結(jié)構(gòu)8.遍一遍掃描的好處–避免重復(fù)性工作，編譯速度快。一遍掃描的缺點–發(fā)生語法或語義錯誤時，前面所作的工作可能要半途而廢。–不便于分工，不便于優(yōu)化，算法不清晰。第一章 編譯概述1.2

編譯過程和編譯程序的基本結(jié)構(gòu)編譯程序功能結(jié)構(gòu)8.遍多遍掃描的好處–節(jié)省內(nèi)存空間，提高目標代碼質(zhì)量，使編譯的邏輯結(jié)構(gòu)清晰，算法清晰。多遍掃描的缺點–編譯時間較長。–注：在內(nèi)存 情況下，還是遍數(shù)盡可能少些為好。語法分析掃描器語義子程序源程序目標代碼編譯程序一遍掃描（以語法分析為中心）第一章 編譯概述1.3編譯程序的生成方法目前已有方法：1.直接用機器語言編寫編譯程序2.用匯編語言編寫編譯程序–注：編譯程序 部分常用匯編語言編寫3.用高級語言編寫編譯程序–注：這是普遍采用的方法4.自編譯5.編譯工具:LEX(詞法分析)與YACC(用于自動產(chǎn)生

LALR分析表)6.移植（同種語言的編譯程序在不同類型的機器之間移植）在某機器上為