ch1編譯原理課件

1、1編譯原理2022-4-252自我介紹自我介紹 姓名：張鑒新姓名：張鑒新 QQ:13273606QQ:132736062022-4-253開課目的：開課目的： 介紹設(shè)計(jì)與構(gòu)造程序設(shè)計(jì)語言介紹設(shè)計(jì)與構(gòu)造程序設(shè)計(jì)語言編譯程序編譯程序的的原理與方法原理與方法源程序源程序編譯編譯程序程序目標(biāo)程序目標(biāo)程序連接連接可執(zhí)行程序可執(zhí)行程序預(yù)備知識(shí)：預(yù)備知識(shí)：形式語言與自動(dòng)機(jī)、形式語言與自動(dòng)機(jī)、一門以上的一門以上的高級(jí)程序設(shè)高級(jí)程序設(shè)計(jì)語言計(jì)語言匯編語言匯編語言數(shù)據(jù)結(jié)構(gòu)等數(shù)據(jù)結(jié)構(gòu)等2022-4-254內(nèi)容簡(jiǎn)介：內(nèi)容簡(jiǎn)介：第一部分：編譯概述第二部分：文法和語言第三部分：詞法分析器第四部分：語法分析技術(shù)第五部分：語

2、法制導(dǎo)翻譯及中間代碼第六部分：程序運(yùn)行時(shí)的存貯分配問題第七部分：代碼優(yōu)化 第八部分：目標(biāo)代碼生成 2022-4-255第一章編譯簡(jiǎn)介第一章編譯簡(jiǎn)介 編譯器就是一個(gè)編譯器就是一個(gè)程序程序，它，它讀入讀入用某種語言用某種語言編寫的源程序，并編寫的源程序，并翻譯翻譯成一個(gè)成一個(gè)與之等價(jià)與之等價(jià)的的另一種語言編寫的源程序。另一種語言編寫的源程序。編譯器編譯器源程序源程序目標(biāo)程序目標(biāo)程序錯(cuò)誤信息錯(cuò)誤信息Fortran、Pascal、Java、 C .另一種程序另一種程序設(shè)計(jì)語言、設(shè)計(jì)語言、匯編語匯編語言、機(jī)言、機(jī)器語言器語言1.1什么叫編譯程序什么叫編譯程序2022-4-2561.2編譯過程概述編譯過程

3、概述編譯程序的工作，從輸入源程序開始，到輸出編譯程序的工作，從輸入源程序開始，到輸出目標(biāo)程序結(jié)束，與自然語言之間的翻譯有很多相似目標(biāo)程序結(jié)束，與自然語言之間的翻譯有很多相似之處。之處。 一段英文翻譯成中文，一段英文翻譯成中文，需經(jīng)下列步驟：需經(jīng)下列步驟：識(shí)別出句子中的單詞識(shí)別出句子中的單詞分析句子的語法結(jié)構(gòu)分析句子的語法結(jié)構(gòu)根據(jù)句子的含義進(jìn)行初步分析根據(jù)句子的含義進(jìn)行初步分析對(duì)譯文進(jìn)行修飾對(duì)譯文進(jìn)行修飾寫出最后的譯文寫出最后的譯文編譯程序編譯程序詞法分析詞法分析代碼優(yōu)化代碼優(yōu)化語法分析語法分析語義分析及中語義分析及中間代碼生成間代碼生成目標(biāo)代碼生成目標(biāo)代碼生成構(gòu)成編譯程構(gòu)成編譯程序各個(gè)階段序各

4、個(gè)階段I am a teacher.2022-4-257編譯器的各個(gè)階段：編譯器的各個(gè)階段：編譯器是分編譯器是分階段執(zhí)行的。階段執(zhí)行的。每個(gè)階段將源每個(gè)階段將源程序從一種表程序從一種表示轉(zhuǎn)換成另一示轉(zhuǎn)換成另一種表示種表示源程序源程序詞法分析器詞法分析器錯(cuò)錯(cuò)誤誤處處理理器器符符號(hào)號(hào)管管理理表表語法分析器語法分析器語義分析器語義分析器中間代碼生成器中間代碼生成器代碼優(yōu)化器代碼優(yōu)化器代碼生成器代碼生成器編譯的各編譯的各個(gè)階段個(gè)階段2022-4-258各分析階段各分析階段隨著編譯器各個(gè)階段的進(jìn)展，源程序的內(nèi)部表示隨著編譯器各個(gè)階段的進(jìn)展，源程序的內(nèi)部表示不斷地發(fā)生變化。不斷地發(fā)生變化。以以sum=fi

5、rst+count *10為例為例1。詞法分析。詞法分析讀入源程序讀入源程序完成的任務(wù)：完成的任務(wù)：識(shí)別出單詞：識(shí)別出單詞：sum、=、first、+、count 、 *、 10并用記號(hào)方式表示識(shí)別出的單詞并用記號(hào)方式表示識(shí)別出的單詞關(guān)鍵字、標(biāo)識(shí)關(guān)鍵字、標(biāo)識(shí)符、常數(shù)、算符、常數(shù)、算符和界符符和界符例：例：id1、id2、id3表示表示sum、first 、count記號(hào)表示邏輯記號(hào)表示邏輯上相關(guān)的字符上相關(guān)的字符序列，常用整序列，常用整數(shù)來表示數(shù)來表示上述單詞表示為：上述單詞表示為：id1=id2+id3*102022-4-259語法分析語法分析在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，在詞法分

6、析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，把單詞符號(hào)串組成各類語法單位把單詞符號(hào)串組成各類語法單位.具體的說，語法分析是在單詞流的基礎(chǔ)上建具體的說，語法分析是在單詞流的基礎(chǔ)上建立一個(gè)層次結(jié)構(gòu)立一個(gè)層次結(jié)構(gòu)-建立語法樹建立語法樹賦值語句賦值語句標(biāo)識(shí)符標(biāo)識(shí)符=表達(dá)式表達(dá)式 id1表達(dá)式表達(dá)式標(biāo)識(shí)符標(biāo)識(shí)符 id2 +表達(dá)式表達(dá)式表達(dá)式表達(dá)式*標(biāo)識(shí)符標(biāo)識(shí)符 id3表達(dá)式表達(dá)式 整數(shù)整數(shù) 102022-4-2510語義分析階段語義分析階段語義分析利用語法分析階段確定的層次結(jié)構(gòu)來識(shí)語義分析利用語法分析階段確定的層次結(jié)構(gòu)來識(shí)別表達(dá)式和語句中的操作信息及類型信息別表達(dá)式和語句中的操作信息及類型信息= + id1id2*

7、id3inttorealtemp1=count*10temp2=first+temp1 temp1 temp2sum=temp2對(duì)于例子中的常數(shù)對(duì)于例子中的常數(shù)10，語義分析將進(jìn)行，語義分析將進(jìn)行類型轉(zhuǎn)換類型轉(zhuǎn)換 inttoreal(10) 102022-4-2511中間代碼生成階段中間代碼生成階段本階段將產(chǎn)生源程序的一個(gè)顯式中間表示本階段將產(chǎn)生源程序的一個(gè)顯式中間表示這種中間表示可以看成是某種抽象的這種中間表示可以看成是某種抽象的程序，通常是與平臺(tái)無關(guān)的程序，通常是與平臺(tái)無關(guān)的其重要性質(zhì)：其重要性質(zhì)：1.易于產(chǎn)生易于產(chǎn)生2.易于翻譯成目標(biāo)程序易于翻譯成目標(biāo)程序下面是用下面是用三地址碼三地址碼

8、和和四元式四元式表示的例子：表示的例子：temp1=inttoreal*10temp2=id3+temp1temp3=id2+temp2id1=temp22022-4-2512代碼優(yōu)化階段代碼優(yōu)化階段試圖改進(jìn)中間代碼，以產(chǎn)生執(zhí)行速度較快試圖改進(jìn)中間代碼，以產(chǎn)生執(zhí)行速度較快的機(jī)器代碼的機(jī)器代碼對(duì)上面中間代碼進(jìn)行優(yōu)化處理后，產(chǎn)生對(duì)上面中間代碼進(jìn)行優(yōu)化處理后，產(chǎn)生如下的代碼：如下的代碼：temp1=id3*10.0id1=id2+temp1temp1=inttoreal*10temp2=id3+temp1temp3=id2+temp2id1=temp22022-4-2513代碼生成階段代碼生成階段生

9、成可重定位的機(jī)器代碼或匯編代碼生成可重定位的機(jī)器代碼或匯編代碼Movf R2，id3Mult R2, #60.0Movf R1, id2Addf R2, R1Movf id1, R22022-4-2514編譯器的一個(gè)基本功能是編譯器的一個(gè)基本功能是記錄源程序中使記錄源程序中使用的標(biāo)識(shí)符用的標(biāo)識(shí)符并將它們并將它們記載到符號(hào)表中記載到符號(hào)表中。符號(hào)表是一個(gè)數(shù)據(jù)結(jié)構(gòu)。符號(hào)表是一個(gè)數(shù)據(jù)結(jié)構(gòu)。每個(gè)標(biāo)識(shí)符在符號(hào)表中都每個(gè)標(biāo)識(shí)符在符號(hào)表中都有一條記錄有一條記錄名字名字記號(hào)記號(hào)類型類型種屬種屬 addrid1id2 b a例：例：int a,b;int簡(jiǎn)變簡(jiǎn)變 0 4 并并收集與每個(gè)標(biāo)識(shí)符相關(guān)的各種收集與每個(gè)

10、標(biāo)識(shí)符相關(guān)的各種屬性信息，屬性信息，int簡(jiǎn)變簡(jiǎn)變1.3符號(hào)表管理符號(hào)表管理2022-4-25151.41.4編譯各階段的分組編譯各階段的分組一、前端和后端一、前端和后端 前端包括詞法分析、語法分析、前端包括詞法分析、語法分析、語義分析，以及相關(guān)的錯(cuò)誤處理和符語義分析，以及相關(guān)的錯(cuò)誤處理和符號(hào)表的建立號(hào)表的建立 前端依賴于源程序并在很大程度前端依賴于源程序并在很大程度上獨(dú)立于目標(biāo)機(jī)器。上獨(dú)立于目標(biāo)機(jī)器。2022-4-2516 后端主要包括代碼優(yōu)化、代碼生成和后端主要包括代碼優(yōu)化、代碼生成和相關(guān)錯(cuò)誤處理。相關(guān)錯(cuò)誤處理。 后端依賴于目標(biāo)機(jī)器。后端依賴于目標(biāo)機(jī)器。 后端處理對(duì)象是由前端產(chǎn)生的結(jié)果，即后端處理對(duì)象是由前端產(chǎn)生的結(jié)果，即中間代碼中間代碼 前端生成與平臺(tái)無關(guān)的字節(jié)碼前端生成與平臺(tái)無關(guān)的字節(jié)碼 后端是由與平臺(tái)有關(guān)的解釋器對(duì)所生后端是由與平臺(tái)有關(guān)的解釋器對(duì)所生成的字節(jié)碼文件進(jìn)行解釋執(zhí)行成的字節(jié)碼文件進(jìn)行解釋執(zhí)行Java語言的編譯采用的是前端后端方式。語言的編譯采用的是前端后端方式。2022-4-2517二、編譯的遍二、編譯的遍 編譯的若干階段通常是以一遍來實(shí)編譯的若干階段通常是以一遍來實(shí)現(xiàn)的，每遍讀一次輸入文件、產(chǎn)生一個(gè)現(xiàn)的，每遍讀一次輸入文件、產(chǎn)生一個(gè)輸出文件。輸出文件。2