1、編譯原理第一章 編譯原理概論,教學(xué)計劃,時間：20162017第學(xué)1期 周學(xué)時：2 周數(shù)：18 考核方式：考試 教材：呂映之,編譯原理,清華大學(xué) 參考書：程序設(shè)計語言編譯原理,編譯原理,第一章 編譯原理概述 第三章 文法和語言 第四章 詞法分析 第五章 自頂向下語法分析 第六章 自底向上語法分析 第七章 LR分析法簡介 第八章 語法制導(dǎo)翻譯和中間代碼生成 第九章 符號表 第十章 目標(biāo)程序運行時的存儲組織 第十一章 代碼優(yōu)化 第十二章 代碼生成概述,第一章 編譯原理概述,1.0 編譯系統(tǒng)在計算機(jī)系統(tǒng)中的地位 1.1 什么是編譯系統(tǒng) 1.2 編譯過程 1.3 編譯程序的結(jié)構(gòu) 1.4 編譯階段的組合

2、 1.5 編譯系統(tǒng)和軟件工具,1.0 編譯系統(tǒng)在計算機(jī)系統(tǒng)中的地位,一、編譯系統(tǒng)在計算機(jī)系統(tǒng)中的地位 二、編譯系統(tǒng)在課程體系中的地位,一、編譯系統(tǒng)在計算機(jī)系統(tǒng)中的地位,計算機(jī)系統(tǒng)中三大核心技術(shù)之一,二、編譯系統(tǒng)在課程體系中的地位,計算機(jī)八大主干課之一 先修課 程序設(shè)計 數(shù)據(jù)結(jié)構(gòu) 后續(xù)課 ,1.1 什么是編譯系統(tǒng),一、計算機(jī)系統(tǒng)的構(gòu)成 二、語言系統(tǒng) 三、基本概念 四、發(fā)展歷史,一、計算機(jī)系統(tǒng)的構(gòu)成,操作系統(tǒng),編譯系統(tǒng),裸機(jī),應(yīng)用系統(tǒng),二、語言系統(tǒng),高級程序設(shè)計語言1,高級程序設(shè)計語言2,機(jī)器語言,源語言,目標(biāo)語言,翻譯1,翻譯2,三、基本概念,翻譯：它把一種語言(稱作源語言)書寫的句子翻譯成另一

3、種語言(稱作目標(biāo)語言)的句子的等價變換過程 源語言程序 目標(biāo)語言程序 翻譯程序 分類 編譯程序：筆譯 解釋程序：口譯 注： 翻譯程序是一種等價變化。 匯編程序：是將匯編語言等價變化為機(jī)器語言的特殊翻譯程序。,四、發(fā)展歷史,50s：直接構(gòu)造的方式，如FORTRAN 60s：自展開技術(shù)，如PASCAL 70s：編譯的編譯 工具：LEX/YACC,1.2 編譯過程,一、高級語言處理過程 二、編譯過程,一、高級語言處理過程,預(yù)處理器,編譯器,匯編器,裝配連接編輯,骨架程序,源程序,目標(biāo)匯編程序,可重定位機(jī)器代碼,絕對機(jī)器碼,二、編譯過程,1、詞法分析 2、語法分析 3、語義分析 4、中間代碼生成 5、

4、代碼優(yōu)化 6、目標(biāo)代碼生成,1、詞法分析,任務(wù)： 從左到右讀入一個一個字符，并將其組合為一個一個字。 分類： 保留字； 標(biāo)識符； 數(shù)字； 界符。 分析方法和工具： 正規(guī)文法、正規(guī)式和有限自動機(jī)。 例：,示例,對如下C源程序片斷： int a; a = a + 2; 詞法分析后可能返回: 單詞類型 單詞值 保留字 int 標(biāo)識符(變量名) a 界符 ; 標(biāo)識符(變量名) a 算符(賦值) = 標(biāo)識符(變量名) a 算符(加) + 整數(shù) 2 界符 ；,2、語法分析,任務(wù)： 在詞法分析的基礎(chǔ)上，將單詞序列組合成各種合法的語法單元。 分類： 表達(dá)式； 語句：順序語句、分叉語句、循環(huán)語句；復(fù)合語句； 程

5、序：函數(shù) / 子程序 / 分程序；程序。 分析方法和工具：上下文無關(guān)文法。 例：,示例,id1:=id2+id3*N,示例,賦值語句,標(biāo)識符,表達(dá)式,表達(dá)式,+,表達(dá)式,表達(dá)式,標(biāo)識符,整數(shù),標(biāo)識符,:=,表達(dá)式,*,示例,:= := := :=“+” :=“*” :=“(”“)” :=“:=”,3、語義分析,任務(wù)： 對語法單元進(jìn)行語義（靜態(tài)）檢查，收集類型信息。 分析方法和工具： 屬性文法。 例：,示例,int arr 2, abc; abc = arr * 10; /* error */ p() float rate, initial, position; position := init

6、ial + rate * 60 /* error */ /* error */ /* warning */; ,4、中間代碼生成,任務(wù)： 將于程序變成稱為中間語言的中間代碼的內(nèi)部形式。 分類： 三元式； 間接三元式； 四元式； 逆波蘭記號； 樹形表示。 例：,示例,id1:= id2 + id3 * 60 (1)(inttoreal,60-t1) (2)(*,id3t1t2) (3)(+,id2t2t3) (4)(:=,t3-id1),5、代碼優(yōu)化,任務(wù)： 對中間代碼進(jìn)行等價變換，以產(chǎn)生更有效的代碼（省時間、省空間）。 分類： 公共子表達(dá)式 循環(huán)優(yōu)化 刪除無用代碼 例：,示例,id1:= id

7、2 + id3 * 60 (1)(inttoreal60-t1 ) (2)( * id3t1t2 ) (3)( +id2t2t3 ) (4)( :=t3-id1) 變換 (1) ( *id360.0 t1) (2) ( + id2 t1 id1),6、目標(biāo)代碼生成,任務(wù)： 把中間代碼變換成特定機(jī)器上的絕對指令代碼或可重定位的指令代碼或匯編指令代碼。 例：,示例,(*,id360.0t1) (+,id2t1id1),movfid3,R2 mulf#60.0,R2 movfid2,R1 addfR2,R1 movfR1,id1,1.3 編譯程序的結(jié)構(gòu),出 錯 處 理,語法分析程序,語義分析程序,目標(biāo)代碼生成程序,詞法分析程序,中間代碼生成程序,代碼優(yōu)化程序,表 格 管 理,1.4 編譯階段的組合,一、遍 二、前端與后端,一、遍,定義： “遍”也稱為“趟”，是對源程序或其等價的中間語言程序從頭到尾掃描并完成規(guī)定任務(wù)的過程。 注： 既可以將編譯的不同階段合并為一遍，例如：將詞法與語法分析合并為一遍； 也可將編譯的一個階段分為若干遍，例如：優(yōu)化階段往往分為若干遍。 多遍編譯的優(yōu)缺點： 遍數(shù)多結(jié)構(gòu)清晰，占內(nèi)存少； 但讀寫中間文件的次數(shù)多，將會影響數(shù)度。,二、前端與后端,前端： 由編譯系統(tǒng)終于目標(biāo)計算機(jī)無關(guān)的階段。 后端： 由編譯系統(tǒng)終于目標(biāo)計算機(jī)有關(guān)