計算機編譯原理實用全套PPT

計算機編譯(biānyì)原理第一頁，共29頁。第一章編譯(biānyì)概述第二頁，共29頁。翻譯器翻譯器（翻譯程序）：把某一種語言程序(稱為源語言程序)等價地轉換成另一種語言程序(稱為目標語言程序)的軟件。翻譯程序根據(jù)所處理(chǔlǐ)的對象和實現(xiàn)的途徑不同又分為：匯編程序、編譯程序和解釋程序。匯編程序：如果源語言是某種匯編語言，而目標語言是某種計算機的機器語言，這樣的一個翻譯程序就稱為匯編程序。第三頁，共29頁。編譯器與解釋器編譯器（編譯程序）：如果源語言是某種高級語言，而目標語言是某種低級語言（匯編語言或機器語言），這樣的一個翻譯程序就稱為編譯程序。解釋器（解釋程序）：這是另外一種(yīzhǒnɡ)類型的翻譯程序，在翻譯過程中它按照高級語言源程序在計算機上執(zhí)行的動態(tài)順序對源程序的語句逐條翻譯（解釋），邊解釋邊執(zhí)行直至結束，它不產(chǎn)生目標程序，它的工作結果就是源程序的執(zhí)行結果，這樣的一個翻譯程序就稱為解釋程序。第四頁，共29頁。編譯器與解釋器例5假設(jiǎshè)有源程序：read(x);write("x=",x);第五頁，共29頁。編譯器與解釋器特點：1．編譯器：工作效率高，即時間快、空間省；交互性與動態(tài)特性差、可移植性差。大多數(shù)PL采用此種方法(fāngfǎ)翻譯；2．解釋器：工作效率低，即時間慢、空間費；交互性與動態(tài)特性好、可移植性好。早期的Basic和現(xiàn)在的Java等?；竟δ埽憾呦嗤?；所采用的技術：從翻譯的角度來講，兩種方式所涉及的原理、方法(fāngfǎ)、技術相似。第六頁，共29頁。編譯器根據(jù)不同的用途和側重，編譯程序還可進一步分類。專門用于幫助程序開發(fā)和調試的編譯程序稱為診斷編譯程序（DiagnosticCompiler）；著重于提高目標代碼效率的編譯程序叫優(yōu)化編譯程序（OptimizingCompiler）?，F(xiàn)在很多編譯程序同時提供(tígōng)了調試、優(yōu)化等多種功能，用戶可以通過“開關”進行選擇。運行編譯程序的計算機稱宿主機，運行編譯程序所產(chǎn)生目標代碼的計算機稱目標機。如果一個編譯程序產(chǎn)生不同于其宿主機的機器代碼，則稱它為交叉編譯程序(CrossCompiler)。如果不需重寫編譯程序中與機器無關的部分就能改變目標機，則稱該編譯程序為可變目標編譯程序（RetargetableCompiler）。第七頁，共29頁。編譯(biānyì)的階段編譯器從邏輯上可以分成若干階段，每個階段把源程序從一種表示(biǎoshì)變換成另一種表示(biǎoshì)。第八頁，共29頁。利用編譯器編寫工具：詞/語法、語法制導翻譯、代碼生成、數(shù)據(jù)流分析等；例5假設(jiǎshè)有源程序：read(x);write("x=",x);任務：在語義分析的同時將源程序變換成一種內部表示形式（中間代碼）。id,1=id,2+id,360t2=id3t1任務(rènwu)：審查源程序有無語義錯誤，為代碼生成收集類型信息（類型檢查）。錯誤診斷和報告(bàogào)第二十八頁，共29頁。如：面向目標機器的優(yōu)化，目標代碼生成，以及相關出錯處理和符號表操作。描述工具：上下文無關文法現(xiàn)在很多編譯程序同時提供(tígōng)了調試、優(yōu)化等多種功能，用戶可以通過“開關”進行選擇。當掃描器識別出一個名字（標識符）后，它把該名字填入到符號表中。遍（pass趟）：對源程序或其等價的中間語言程序從頭到尾掃描并完成規(guī)定任務的過程(guòchéng)。(+ id2 t2 t3)當處理到名字的使用性出現(xiàn)時，要對名字的屬性進行查證。編譯(biānyì)的階段把英文翻譯為中文識別出句子中的一個個單詞；分析句子的語法結構；根據(jù)(gēnjù)句子的含義進行初步翻譯；對譯文進行修飾；寫出最后的譯文。詞法(cífǎ)分析語法分析中間代碼產(chǎn)生優(yōu)化目標代碼產(chǎn)生第九頁，共29頁。詞法(cífǎ)分析任務(rènwu):輸入源程序，對構成源程序的字符串進行掃描和分解，識別出一個個單詞符號。依循的原則：構詞規(guī)則描述工具：正規(guī)式和有限自動機對識別出的單詞符號用內部形式（內部碼）表示。對不符合詞法規(guī)則的非法字符串作相應的詞法出錯處理。第十頁，共29頁。詞法(cífǎ)分析詞法分析器id,1

=

id,2

+

id,3

60position=initial+rate

60符號表

positioninitialrate.........123第十一頁，共29頁。語法分析任務:在詞法分析的基礎上，根據(jù)語言的語法規(guī)則把單詞符號串分解成各類語法單位。如程序、語句、表達式等。依循的原則：語法規(guī)則描述工具：上下文無關文法通過語法分析確定整個輸入串是否構成一個語法上正確的程序，對不符合(fúhé)語法規(guī)則的單詞序列作相應的語法出錯處理。詞法分析是一種線性分析，而語法分析是一種層次結構分析。第十二頁，共29頁。語法分析表達式的語法特征：任何一個標識符都是表達式任何一個數(shù)都是表達式如果(rúguǒ)e1和e2都是表達式，那么e1+e2e1*e2(e1)也都是表達式表達式表達式表達式標識符表達式表達式(initial)標識符(rate)數(shù)(60)*+initial+rate*60分析樹第十三頁，共29頁。語法分析語法分析器id,1

=

id,2

+

id,3

60=+60id,1id,2id,3符號表

positioninitialrate.........123語法(yǔfǎ)樹第十四頁，共29頁。語義分析(fēnxī)任務(rènwu)：審查源程序有無語義錯誤，為代碼生成收集類型信息（類型檢查）。依循的原則：語義規(guī)則語義分析的一個重要部分是類型檢查，編譯器檢查每個算符的運算對象，看它們的類型是否適當。如：實數(shù)作為數(shù)組下標，報錯；整數(shù)和實數(shù)進行運算時，將整數(shù)轉變?yōu)閷崝?shù)。第十五頁，共29頁。語義分析(fēnxī)語義分析器=+60id,1id,2id,3=+Inttorealid,1id,2id,360符號表

positioninitialrate.........123第十六頁，共29頁。中間(zhōngjiān)代碼生成任務：在語義分析的同時將源程序變換成一種內部表示形式（中間代碼）。“翻譯”僅僅在這里才開始涉及到。中間代碼：一種結構簡單(jiǎndān)、含義明確的記號系統(tǒng)。原則：容易生成；容易將它翻譯成目標代碼。中間代碼：三元式，四元式，樹形結構等。四元式：（運算符，運算對象1，運算對象2，結果）第十七頁，共29頁。中間(zhōngjiān)代碼生成中間代碼生成器t1=inttoreal(60)t2=id3t1t3=id2+t2id1=t3=+inttorealid,1id,2id,360符號表

positioninitialrate.........123第十八頁，共29頁。中間(zhōngjiān)代碼生成上面的例子表示(biǎoshì)成四元式：(inttoreal 60 - t1)(* id3 t1 t2)(+ id2 t2 t3)(:= t3 - id1)第十九頁，共29頁。代碼優(yōu)化任務：對于前階段產(chǎn)生的中間代碼進行加工變換，以期在最后階段產(chǎn)生更高效的目標代碼。依循的原則：程序的等價變換規(guī)則優(yōu)化的主要方面有：公共子表達式的提取(tíqǔ)、循環(huán)優(yōu)化、刪除無用代碼等等。第二十頁，共29頁。代碼優(yōu)化代碼優(yōu)化器t1=inttoreal(60)t2=id3t1t3=id2+t2id1=t3t1=id3*60.0id1=id2+t1符號表

positioninitialrate.........123第二十一頁，共29頁。代碼生成任務:把中間代碼變換成特定機器上的目標代碼。特點：與硬件系統(tǒng)結構和指令含義有關，涉及到硬件系統(tǒng)功能部件的運用、機器指令的選擇、各種數(shù)據(jù)類型變量的存儲空間分配以及寄存器和后緩寄存器的調度等。目標代碼三種形式:絕對指令代碼:可直接運行可重定位指令代碼:需要(xūyào)連接裝配（多數(shù)）匯編指令代碼:需要(xūyào)進行匯編第二十二頁，共29頁。代碼生成代碼生成器MOVFid3,R2MULF#60.0,R2MOVFid2,R1ADDFR2,R1MOVFR1,id1t1=id3*60.0id1=id2+t1符號表

positioninitialrate.........123第二十三頁，共29頁。符號表管理(guǎnlǐ)符號表：用來登記源程序中出現(xiàn)的每個名字以及名字的各種屬性。例如，一個名字是常量名、變量名，還是過程名等等；若是變量名，它的類型、所占內存、地址等等。通常，編譯程序在處理到名字的定義性出現(xiàn)時，要把名字的各種屬性填入到符號表中；當處理到名字的使用性出現(xiàn)時，要對名字的屬性進行查證。當掃描器識別出一個名字（標識符）后，它把該名字填入到符號表中。但這時不能完全確定名字的屬性，它的各種屬性要在后續(xù)(hòuxù)的各階段才能填入。例如，名字的類型等要在語義分析時才能確定，而名字的地址可能要到目標代碼生成才能確定。第二十四頁，共29頁。錯誤診斷和報告(bàogào)出錯處理程序：發(fā)現(xiàn)源程序中的錯誤，把有關錯誤信息報告給用戶。語法錯誤語義錯誤好的編譯程序應能最大限度地發(fā)現(xiàn)源程序中的各種錯誤，準確地指出錯誤的性質和發(fā)生錯誤的地點，并且(bìngqiě)能將錯誤所造成的影響限制在盡可能小的范圍內，使得源程序的其余部分能繼續(xù)被編譯下去，以便進一步發(fā)現(xiàn)其它可能的錯誤。第二十五頁，共29頁。階段(jiēduàn)的分組有關名詞：前端（frontend）：主要依賴于源語言而與目標機器無關的編譯階段。如：詞法分析、語法分析、語義分析、中間代碼生成、部分優(yōu)化工作、與前端有關的出錯處理工作和符號表管理工作。后端（backend）：依賴于目標機而一般不依賴于源語言，只與中間代碼有關的編譯階段。如：面向目標機器的優(yōu)化，目標代碼生成，以及相關出錯處理和符號表操作。遍（pass趟）：對源程序或其等價的中間語言程序從頭到尾掃描并完成規(guī)定任務的過程(guòchéng)。每一遍掃描可完成上述一個階段或多個階段的工作。階段與遍是不同的概念。一遍可以由若干段組成，一個階段也可以分若干遍來完成。第二十六頁，共29頁。編譯器的編寫(biānxiě)直接使用匯編語言和程序設計語言；利用編譯器編寫工具：詞/語法、語法制導翻譯、代碼生成、數(shù)據(jù)流分析等；基于編譯器基礎架構的編譯器構造(gòuzào)系統(tǒng)（開放式編譯器，如