編譯原理-第1章

1、2021-12-81南京郵電大學(xué)計算機學(xué)院沙 超第一章第一章 概概 述述2021-12-83第一章第一章 概概 述述第一章第一章 概概 述述人與人之間交流人與人之間交流信息的一種語言信息的一種語言 動物之間通過動動物之間通過動物語言交流信息物語言交流信息以數(shù)理邏輯、集合論和統(tǒng)計以數(shù)理邏輯、集合論和統(tǒng)計數(shù)學(xué)來描述的一種語言。例數(shù)學(xué)來描述的一種語言。例如，用計算機進行幾何定理如，用計算機進行幾何定理的證明的證明人和計算機進行信息交流人和計算機進行信息交流的一種語言，它遵循一定的一種語言，它遵循一定的語法和語義的規(guī)則的語法和語義的規(guī)則第一章第一章 概概 述述2021-12-86第一章第一章 概概 述

2、述2021-12-87第一章第一章 概概 述述2021-12-88第一章第一章 概概 述述2021-12-89第一章第一章 概概 述述2021-12-810第一章第一章 概概 述述2021-12-811第一章第一章 概概 述述2021-12-812第一章第一章 概概 述述2021-12-813第一章第一章 概概 述述 FORTRAN語言語言 (FORmula TRANslator 公式翻譯公式翻譯 )1954年由美國年由美國IBM公司研制，主要用于公司研制，主要用于科學(xué)計算科學(xué)計算 ALGOL語言語言 (ALGOrithmic Language 算法語言算法語言)1960年原西德應(yīng)用數(shù)學(xué)和力學(xué)

3、學(xué)會研制出來，年原西德應(yīng)用數(shù)學(xué)和力學(xué)學(xué)會研制出來， 主要用于主要用于科學(xué)科學(xué)計算計算，它第一次采用形式化語法描述體系，它第一次采用形式化語法描述體系 BNF范式（巴范式（巴科斯科斯瑙爾范式）瑙爾范式） 。2021-12-814第一章第一章 概概 述述 在在60年代初期年代初期編譯技術(shù)編譯技術(shù)與理論研究受到高度重視，與理論研究受到高度重視，并得到發(fā)展，這也促使了多種新程序設(shè)計語言的研制。并得到發(fā)展，這也促使了多種新程序設(shè)計語言的研制。除了若干普通過程性程序設(shè)計語言外，還研制了一些其除了若干普通過程性程序設(shè)計語言外，還研制了一些其它風格的程序設(shè)計語言如：它風格的程序設(shè)計語言如：LISP、APL、B

4、ASIC等。等。2021-12-815第一章第一章 概概 述述 LISP語言語言 BASIC語言語言2021-12-816第一章第一章 概概 述述 結(jié)構(gòu)化程序設(shè)計思想，即任何程序都可以用順結(jié)構(gòu)化程序設(shè)計思想，即任何程序都可以用順序、選擇、循環(huán)這三種結(jié)構(gòu)語句來構(gòu)造。從序、選擇、循環(huán)這三種結(jié)構(gòu)語句來構(gòu)造。從1968年年開始，不同的結(jié)構(gòu)程序設(shè)計語言陸續(xù)問世，如：開始，不同的結(jié)構(gòu)程序設(shè)計語言陸續(xù)問世，如：PASCAL、Ada、C等等2021-12-817第一章第一章 概概 述述 PASCAL語言語言 以法國數(shù)學(xué)家以法國數(shù)學(xué)家PASCAL命名，在命名，在70年代初由瑞士工業(yè)大學(xué)年代初由瑞士工業(yè)大學(xué) NW

5、irth創(chuàng)建。以前的數(shù)據(jù)結(jié)構(gòu)就是用創(chuàng)建。以前的數(shù)據(jù)結(jié)構(gòu)就是用PASCAL來寫程序的。來寫程序的。 C語言語言 取自于取自于BCPL語言第二個字母，于語言第二個字母，于1972-1973年由美國貝爾年由美國貝爾實驗室研制。實驗室研制。C語言具有高級語言和低級語言的特征，應(yīng)用十語言具有高級語言和低級語言的特征，應(yīng)用十分廣泛。分廣泛。2021-12-818第一章第一章 概概 述述2021-12-819第一章第一章 概概 述述 面向?qū)ο笫秸Z言：面向?qū)ο笫秸Z言：在傳統(tǒng)過程式語言中，數(shù)據(jù)與處理它們的子程序在傳統(tǒng)過程式語言中，數(shù)據(jù)與處理它們的子程序互不相關(guān)，而在面向?qū)ο笫秸Z言中則把這兩者統(tǒng)一作為對象封裝在一

6、起互不相關(guān)，而在面向?qū)ο笫秸Z言中則把這兩者統(tǒng)一作為對象封裝在一起處理。面向?qū)ο笫秸Z言的一個重要概念是類。處理。面向?qū)ο笫秸Z言的一個重要概念是類。Smalltalk、C+、JAVA、C#等都是面向?qū)ο笫秸Z言。（抽象性、封裝性、繼承性、多態(tài)性、消等都是面向?qū)ο笫秸Z言。（抽象性、封裝性、繼承性、多態(tài)性、消息驅(qū)動）息驅(qū)動） 網(wǎng)絡(luò)語言：網(wǎng)絡(luò)語言：隨著隨著Internet網(wǎng)的發(fā)展，要求能夠在網(wǎng)絡(luò)上運行各種不同網(wǎng)的發(fā)展，要求能夠在網(wǎng)絡(luò)上運行各種不同的高級程序設(shè)計語言，為此人們研制出的高級程序設(shè)計語言，為此人們研制出JAVA、C#等網(wǎng)絡(luò)編程語言。等網(wǎng)絡(luò)編程語言。2021-12-820第一章第一章 概概 述述2

7、021-12-821第一章第一章 概概 述述2021-12-822第一章第一章 概概 述述2021-12-823第一章第一章 概概 述述2021-12-824第一章第一章 概概 述述2021-12-825第一章第一章 概概 述述 剛剛我們介紹了機器語言、匯編語言及高級程序剛剛我們介紹了機器語言、匯編語言及高級程序設(shè)計語言，并且知道只有機器語言編的程序才能被計設(shè)計語言，并且知道只有機器語言編的程序才能被計算機識別，為了能使匯編語言和高級程序設(shè)計語言編算機識別，為了能使匯編語言和高級程序設(shè)計語言編寫的程序被計算機接受，必須將它們轉(zhuǎn)換成具體的機寫的程序被計算機接受，必須將它們轉(zhuǎn)換成具體的機器語言程序

8、。我們將要介紹的匯編程序、解釋程序和器語言程序。我們將要介紹的匯編程序、解釋程序和編譯程序就是完成這種轉(zhuǎn)換功能的翻譯程序。編譯程序就是完成這種轉(zhuǎn)換功能的翻譯程序。2021-12-826第一章第一章 概概 述述翻譯程序翻譯程序 將一種語言程序（稱為源程序）改造成另一種等將一種語言程序（稱為源程序）改造成另一種等價的語言程序（稱為目標程序）的程序。價的語言程序（稱為目標程序）的程序。源語言源語言 書寫源程序的語言稱為源語言。書寫源程序的語言稱為源語言。目標語言目標語言 書寫目標程序的語言稱為目標語言。書寫目標程序的語言稱為目標語言。 2021-12-827第一章第一章 概概 述述源程序源程序匯編程

9、序匯編程序目標程序目標程序結(jié)果數(shù)據(jù)結(jié)果數(shù)據(jù)初始數(shù)據(jù)初始數(shù)據(jù)2021-12-828第一章第一章 概概 述述源程序源程序解釋解釋程序程序結(jié)果數(shù)據(jù)結(jié)果數(shù)據(jù)初始數(shù)據(jù)初始數(shù)據(jù)2021-12-829第一章第一章 概概 述述2021-12-830第一章第一章 概概 述述源程序源程序編譯程序編譯程序目標程序（機器語言）目標程序（機器語言）源程序源程序編譯程序編譯程序目標程序目標程序（匯編語言）（匯編語言）匯編程序匯編程序目標程序目標程序（機器語言）（機器語言）目標程序目標程序（機器語言）（機器語言）運行系統(tǒng)運行系統(tǒng)可執(zhí)行程序可執(zhí)行程序結(jié)果數(shù)據(jù)結(jié)果數(shù)據(jù)2021-12-831第一章第一章 概概 述述 2021-1

10、2-832第一章第一章 概概 述述2021-12-833第一章第一章 概概 述述2021-12-834第一章第一章 概概 述述2021-12-835第一章第一章 概概 述述翻譯外文資料翻譯外文資料 編譯過程編譯過程2021-12-836第一章第一章 概概 述述2021-12-837第一章第一章 概概 述述2021-12-838第一章第一章 概概 述述2021-12-839第一章第一章 概概 述述2021-12-840第一章第一章 概概 述述2021-12-841第一章第一章 概概 述述2021-12-842第一章第一章 概概 述述2021-12-843第一章第一章 概概 述述所以經(jīng)詞法分析后，

11、其內(nèi)部編碼形式于機器內(nèi)為如下形式所以經(jīng)詞法分析后，其內(nèi)部編碼形式于機器內(nèi)為如下形式: 1 000 3 777 2 012 1 004 3 000 2 007 3 002 2 007PROGRAM example ; VAR R , H , 3 004 2 014 1 003 2 012 1 001 3 004 2 013 4 000 S : real ; BEGIN S := 2 2 005 5 001 2 005 3 000 2 005 2010 3 002 2 006 * 3.1416 * R * ( H + 3 000 2 011 1 002 2 015 R ) END .2021-12

12、-844第一章第一章 概概 述述2021-12-845第一章第一章 概概 述述2021-12-846第一章第一章 概概 述述2021-12-847第一章第一章 概概 述述2021-12-848第一章第一章 概概 述述2021-12-849第一章第一章 概概 述述 目標代碼生成就是將中間語言代碼轉(zhuǎn)換成機器語目標代碼生成就是將中間語言代碼轉(zhuǎn)換成機器語言程序或匯編語言程序，最后完成翻譯。言程序或匯編語言程序，最后完成翻譯。2021-12-850第一章第一章 概概 述述2021-12-851第一章第一章 概概 述述2021-12-852第一章第一章 概概 述述 一遍掃描編譯程序一遍掃描編譯程序源程序源

13、程序 第一遍掃描程序第一遍掃描程序 中間語言中間語言1 多遍掃描編譯程序多遍掃描編譯程序 中間語言中間語言n-1 第第n趟掃描程序趟掃描程序 目標程序目標程序源程序源程序 編譯程序編譯程序 目標程序目標程序2021-12-853第一章第一章 概概 述述 2021-12-854第一章第一章 概概 述述2021-12-855第一章第一章 概概 述述2021-12-856第一章第一章 概概 述述2021-12-857第一章第一章 概概 述述2021-12-858第一章第一章 概概 述述2021-12-859第一章第一章 概概 述述2021-12-860第一章第一章 概概 述述2021-12-861第

14、一章第一章 概概 述述假設(shè)在假設(shè)在 A 機器上已有一個機器上已有一個C語言可供運行語言可供運行 , 即用即用 A 機器上的機器上的 A 代碼書寫的、產(chǎn)生代碼書寫的、產(chǎn)生 A 目標代碼的目標代碼的 C語言的編譯程序，如下圖：語言的編譯程序，如下圖：2021-12-862第一章第一章 概概 述述2021-12-863第一章第一章 概概 述述2021-12-864第一章第一章 概概 述述2021-12-865第一章第一章 概概 述述2021-12-866第一章第一章 概概 述述2021-12-867第一章第一章 概概 述述2021-12-868第一章第一章 概概 述述把已有的編譯程序的把已有的編譯程序的T形圖寫在中間下方形圖寫在中間下方，即表示在，即表示在A機器已有機器已有C的編的編譯程序，譯程序，左上方是需要編寫的編譯程序的左上方是需要編寫的編譯程序的T形圖形圖，即表示用，即表示用C語言寫一個語言寫一個C語言的編譯程序，變成語言的編譯程序，變成B機器代碼，機器代碼，右邊是要得到的編譯程序的右邊是要得到的編譯程序的T形圖形圖，即表示用即表示