第一章 編譯系統(tǒng)概論.ppt

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

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

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

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

5、序：函數(shù) / 子程序 / 分程序；程序。 分析方法和工具：上下文無(wú)關(guān)文法。 例：,示例,id1:=id2+id3*N,示例,賦值語(yǔ)句,標(biāo)識(shí)符,表達(dá)式,表達(dá)式,+,表達(dá)式,表達(dá)式,標(biāo)識(shí)符,整數(shù),標(biāo)識(shí)符,:=,表達(dá)式,*,示例,:= := := :=“+” :=“*” :=“(”“)” :=“:=”,3、語(yǔ)義分析,任務(wù)： 對(duì)語(yǔ)法單元進(jìn)行語(yǔ)義（靜態(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ù)： 將于程序變成稱為中間語(yǔ)言的中間代碼的內(nèi)部形式。 分類： 三元式； 間接三元式； 四元式； 逆波蘭記號(hào)； 樹形表示。 例：,示例,id1:= id2 + id3 * 60 (1)(inttoreal,60-t1) (2)(*,id3t1t2) (3)(+,id2t2t3) (4)(:=,t3-id1),5、代碼優(yōu)化,任務(wù)： 對(duì)中間代碼進(jìn)行等價(jià)變換，以產(chǎn)生更有效的代碼（省時(shí)間、省空間）。 分類： 公共子表達(dá)式 循環(huán)優(yōu)化 刪除無(wú)用代碼 例：,示例,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ī)器上的絕對(duì)指令代碼或可重定位的指令代碼或匯編指令代碼。 例：,示例,(*,id360.0t1) (+,id2t1id1),movfid3,R2 mulf#60.0,R2 movfid2,R1 addfR2,R1 movfR1,id1,1.3 編譯程序的結(jié)構(gòu),出 錯(cuò) 處 理,語(yǔ)法分析程序,語(yǔ)義分析程序,目標(biāo)代碼生成程序,詞法分析程序,中間代碼生成程序,代碼優(yōu)化程序,表 格 管 理,1.4 編譯階段的組合,一、遍 二、前端與后端,一、遍,定義： “遍”也稱為“趟”，是對(duì)源程序或其等價(jià)的中間語(yǔ)言程序從頭到尾掃描并完成規(guī)定任務(wù)的過(guò)程。 注： 既可以將編譯的不同階段合并為一遍，例如：將詞法與語(yǔ)法分析合并為一遍； 也可將編譯的一個(gè)階段分為若干遍，例如：優(yōu)化階段往往分為若干遍。 多遍編譯的優(yōu)缺點(diǎn)： 遍數(shù)多結(jié)構(gòu)清晰，占內(nèi)存少； 但讀寫中間文件的次數(shù)多，將會(huì)影響數(shù)度。,二、前端與后端,前端： 由編譯系統(tǒng)終于目標(biāo)計(jì)算機(jī)無(wú)關(guān)的階段。 后端： 由編譯系統(tǒng)終于目標(biāo)計(jì)算機(jī)有關(guān)