編譯原理

袁彩虹

yuanch@程序設計語言什么是編譯？機器語言(MachineLanguage)0、1代碼匯編語言(AssembleLanguage)：助記符高級語言(HighLevelLanguage)：定義數(shù)據(jù)、描述算法（程序） 如：C、Pascal、C++、Java、SQL高級語言低級語言學習的意義(1)一門基礎專業(yè)課,對于”計算機專業(yè)”的同學而言,類似于”高等數(shù)學”對于”理工科”學生工作和學習的影響,使其”享用一輩子”.(2)作用

＊有利于大家對”程序設計語言”的理解

→較迅速掌握新的語言工具.

＊包含許多軟件技術,對于以后從事軟件設計很有價值.→從軟件工程看，編譯器是一個很好的實例，所介紹的概念和技術能應用到一般的軟件設計之中。

＊蘊涵著計算機學科中解決問題的思路﹑抽象問題和解決問題的方法.課程要求1、認真聽課，認真理解書中基本概念、基本原理與基本算法；2、弄懂書中的例題與習題；3、在看書或理解例題時，一定要動手畫出相應的細節(jié)變化過程，通過畫圖來加深理解；4、在理解的基礎上記憶；5、理論結(jié)合實踐?？己朔绞娇己朔绞剑?/p>

--平時成績占30%--期末考試成績占70%平時成績：

--考勤

--作業(yè)

--實驗第1章引論第2章高級語言及其語法描述第3章詞法分析第4章語法分析——自上而下分析第5章語法分析——自下而上分析第6章屬性文法和語法制導翻譯第7章語義分析和中間代碼產(chǎn)生第8章符號表第9章運行時存儲空間組織第10章優(yōu)化

第11章目標代碼生成目錄第一章引論1.1什么叫編譯程序1.2編譯過程概述1.3編譯程序的結(jié)構(gòu)1.4編譯程序與程序設計環(huán)境（略）1.5編譯程序的生成1.什么是編譯程序？1.1什么叫編譯程序翻譯程序：一種語言程序---------->另一種語言程序源語言目標語言編譯程序：高級語言程序---------->低級語言程序匯編程序：匯編語言程序---------->機器語言程序解釋程序：源語言程序---------->邊解釋邊執(zhí)行（1）編譯方式：先編譯后執(zhí)行。（2）解釋方式：以源程序作為輸入，但不產(chǎn)生目標代碼，而是邊解釋邊執(zhí)行源程序本身。2.“高級語言程序”的執(zhí)行方式1.1什么叫編譯程序編譯和解釋的主要區(qū)別：是否產(chǎn)生目標代碼！3.“編譯程序”在計算機系統(tǒng)中的位置較接近于“硬件”1.1什么叫編譯程序4.發(fā)展20世紀50年代第一個編譯程序——FORTRAN編譯程序目前：編譯原理與技術得到迅速發(fā)展，現(xiàn)已形成一套比較成熟的系統(tǒng)化的理論與方法，并開發(fā)出了一些好的編譯程序的實現(xiàn)語言、環(huán)境與工具。當時普遍認為設計和實現(xiàn)編譯程序是一件十分困難、令人生畏的事情1.1什么叫編譯程序1.2編譯過程概述Theelephantateanbanana.什么是語言？forK:=1to100do begin M:=I+10*K; N:=J+10*K end一.類比自然語言翻譯和編譯過程英→漢編譯的工作過程1)識別單詞……………詞法分析2)分析句子語法結(jié)構(gòu)…………………語法分析3)根據(jù)句子含義初步翻譯…………語義分析與中間代碼產(chǎn)生4)修飾譯文…………………優(yōu)化5)寫出最后譯文…………………目標代碼生成1.2編譯過程概述1.詞法分析forK:=1to100do begin M:=I+10*K; N:=J+10*K end

基本字for

標識符K

賦值號:=

常數(shù)1

基本字to

常數(shù)100

基本字do

基本字begin......1.2編譯過程概述詞法分析

——

規(guī)則：規(guī)則描述工具：任務：依循詞法規(guī)則正規(guī)式和有限自動機（FA）輸入源程序，對構(gòu)成源程序的字符串進行掃描和分解，識別出一個個的單詞符號，如基本字、標識符、常數(shù)、算符、界符等。1.2編譯過程概述2.語法分析forK:=1to100do begin M:=I+10*K; N:=J+10*K end規(guī)則：規(guī)則描述工具：任務：依循語法規(guī)則上下文無關文法在詞法分析的基礎上，根據(jù)語言的語法規(guī)則，對單詞符號串進行語法分析，識別出各類語法單位，最終判斷輸入串是否構(gòu)成語法上正確的“程序”。1.2編譯過程概述3.語義分析和中間代碼產(chǎn)生規(guī)則：規(guī)則描述工具：任務：語義規(guī)則屬性文法兩部分工作：1、對每種語法范疇進行靜態(tài)語義檢查2、若語義正確，則進行中間代碼翻譯對語法分析器識別出的各類語法單位，分析其含義并進行初步翻譯（產(chǎn)生中間代碼）。

中間代碼：一種獨立于具體硬件的記號系統(tǒng)，更接近于機器代碼

1.2編譯過程概述forK:=1to100dobeginM:=I+10*K;N:=J+10*Kend；

K:=1L1:if100<KgotoL2T1:=10*KM:=I+T1T2:=10*KN:=J+T2

K:=K+1gotoL1L2:語義分析后產(chǎn)生的中間代碼：三地址代碼具體實現(xiàn)：三元式，四元式，間接三元式1.2編譯過程概述

K:=1L1:if100<KgotoL2T1:=10*KM:=I+T1T2:=10*KN:=J+T2

K:=K+1gotoL1L2:序號OPARG1ARG2RESULT(1)(2)(3)(4)(5)(6)(7)(8)(9):=j<*+*++j110010I10JKKKT1KT21K(9)T1MT2NK(2)四元式序列：1.2編譯過程概述任務：對中間代碼進行加工變換，以期在最后階段能產(chǎn)生出更為高效（省時間和空間）的目標代碼。規(guī)則:等價變換規(guī)則包括：公共子表達式的提取、循環(huán)優(yōu)化、刪除無用代碼等1.2編譯過程概述4.優(yōu)化序號OPARG1ARG2RESULT(1)(2)(3)(4)(5)(6)(7)(8)(9):=j<*+*++j110010I10JKKKT1KT21K(9)T1MT2NK(2)序號OPARG1ARG2RESULT(1)(2)(3)(4)(5)(6)(7)(8)(9):=:=:=j<+++jII1100MNK

K10101MNK(9)MNK(2)優(yōu)化前優(yōu)化后1.2編譯過程概述任務：把中間代碼變換成特定機器上的低級語言代碼，實現(xiàn)最后的翻譯。5.目標代碼生成

絕對指令代碼/可重定位的指令代碼/匯編指令代碼有賴于硬件系統(tǒng)結(jié)構(gòu)和機器指令含義1.2編譯過程概述1.3編譯程序的結(jié)構(gòu)一.編譯程序總框圖1.表格管理編譯各階段都要涉及到構(gòu)造、查找或 更新有關表格。表格的作用：

登記源程序的各類信息和編譯各階段的進展狀況。符號表：

用來登記源程序中出現(xiàn)的每個名字以及名字的各種屬性。

舉例：名字——變量名/常量名/過程名…？ 變量名——類型？/內(nèi)存？/地址？1.3編譯程序的結(jié)構(gòu)2.出錯處理每一階段都可能檢測出錯誤，絕大多 數(shù)錯誤可在前三階段檢測出來任務：設法發(fā)現(xiàn)錯誤，并把有關錯誤信息報告給用戶

語法錯誤：源程序中不符合語法/詞法規(guī)則的錯誤。 詞法/語法分析時檢測語義錯誤：源程序中不符合語義規(guī)則的錯誤。

語義分析/運行時檢測出來1.3編譯程序的結(jié)構(gòu)二.遍1.編譯過程的劃分：上述劃分的五個階段僅僅是邏輯功能上的一種劃分2.遍（Pass）對源程序或源程序的中間結(jié)果從頭到尾掃描一次，并作有關的加工處理，生成新的中間結(jié)果或目標程序。具體實現(xiàn)時，受各方面（如源語言、設計要求等）限制，往往組織成若干遍1.3編譯程序的結(jié)構(gòu)3.注意：既可以將幾個不同階段合為一遍，也可以把一個階段的工作分為若干遍例如：詞法分析+語法分析 一遍語法分析+語義分析與中間代碼產(chǎn)生一遍優(yōu)化

若干遍單遍代碼不太有效。根據(jù)系統(tǒng)資源的狀況、運行目標的要求等，可以將一個編譯程序設計形成多遍掃描的形式，在每一遍掃描中完成不同的任務。1.3編譯程序的結(jié)構(gòu)當一遍中包含若干階段時，各階段的工作是穿插進行的。例如：識別出一個語法單位時語法分析器詞法分析器語義分析和中間代碼產(chǎn)生器識別語法結(jié)構(gòu)需要下一個單詞時單詞符號1.3編譯程序的結(jié)構(gòu)三.編譯前端與后端1、前端：

由與源語言有關但與目標機無關的那些部分組成包括——詞法分析、語法分析、語義分析與中間代碼產(chǎn)生、部分代碼優(yōu)化工作

2、后端： 包括編譯程序中與目標機有關的那些部分，如與目標機有關的代碼優(yōu)化和目標代碼生成等。不依賴于源語言而僅僅依賴于中間語言1.3編譯程序的結(jié)構(gòu)1.5編譯程序的生成一.設計目標

目標程序小，執(zhí)行速度快編譯程序小，執(zhí)行速度快診斷能力強，可靠性強可移植性，可擴充性

如何實現(xiàn)編譯器？直接用可運行的代碼編制太費力！STI源語言編譯程序?qū)崿F(xiàn)語言目標語言一般采用高級語言實現(xiàn)，可用T形圖表示如下：表現(xiàn)語言翻譯的T形圖1.5編譯程序的生成問題：已知A機上有一個用A代碼實現(xiàn)的高級語言L1的編譯程序，可以用L1實現(xiàn)在A機上能運行一個新語言L2編寫的程序。

L1AA已知條件目標L2L1A二.多級編譯程序

1、本機編譯器利用

分析：1.5編譯程序的生成條件目標L2L1AL1AAL2AAL1語言寫成的L2語言的編譯程序A代碼寫成的L1語言的編譯程序得到A代碼寫成的L2語言的編譯程序P0P1P2說明：P0——L2語言的編譯程序，用L1語言實現(xiàn)

P1——L1語言的編譯程序，用A代碼實現(xiàn)

P2——L2語言的編譯程序，用A代碼實現(xiàn)

1.5編譯程序的生成問題：能否用A機上有的高級語言L實現(xiàn)在B機上運行L語言程序？LAA條件目標LLB2、交叉編譯/移植（思考）1.5編譯程序的生成LAA條件LLB目標LLBLAALABLLBLBB說明：過程在A機上運行的產(chǎn)生B代碼的L編譯程序源程序（L語言編寫）1.5編譯程序的生成1.5編譯程序的生成3、自編譯過程

通過一系列自展途徑而形成編譯程序的過程叫做自編譯過程。

1.5編譯程序的生成三.