1、編編 譯譯 原原 理理 （第二版）（第二版）鄭鄭 洪洪 編著編著第第2章章 程程 序序 語語 言言高高 級級 語語 言言1中中 間間 語語 言言22.1 高高 級級 語語 言言v 2.1.1 高級語言的分類高級語言的分類 1過程式語言過程式語言 過程式語言以語句為核心，命令驅動。過程式語言設計的程序以語過程式語言以語句為核心，命令驅動。過程式語言設計的程序以語句為最小執行單位，程序由一系列的語句組成。句為最小執行單位，程序由一系列的語句組成。 這種語言設計的程序通常具有如下形式：這種語言設計的程序通常具有如下形式：語句語句1;語句語句2;語句語句n; 2面向對象語言面向對象語言 面向對象語言（

2、面向對象語言（Object-Oriented Language）是如今使用最廣、）是如今使用最廣、最為重要的語言。它的主要特征是支持封裝性、繼承性和多態性；最為重要的語言。它的主要特征是支持封裝性、繼承性和多態性；把復雜的特性和用于這些數據的操作裝在一起，構成對象；對簡單把復雜的特性和用于這些數據的操作裝在一起，構成對象；對簡單對象進行擴充，繼承簡單對象的特性，從而設計出復雜的對象。對象進行擴充，繼承簡單對象的特性，從而設計出復雜的對象。 3應用式語言應用式語言 將已知的函數作為新開發函數的參數，利用函數的嵌套與遞歸使得將已知的函數作為新開發函數的參數，利用函數的嵌套與遞歸使得程序的功能由簡單

3、變為復雜，最終滿足程序設計的要求。程序的功能由簡單變為復雜，最終滿足程序設計的要求。 這種語言的結構形式是：這種語言的結構形式是：函數函數n（函數函數2（函數（函數1（數據）（數據） 4基于規則的語言基于規則的語言 基于規則的語言以判斷基于規則的語言以判斷選擇語句為基本執行單位。其程序的執行選擇語句為基本執行單位。其程序的執行過程是：檢查一定的條件，當它滿足時選擇適當的操作。最有代表過程是：檢查一定的條件，當它滿足時選擇適當的操作。最有代表性的基于規則語言是性的基于規則語言是PROLOG。 其程序結構形式為：其程序結構形式為：條件條件1動作動作1條件條件2動作動作2條件條件n動作動作nv 2.

4、1.2 數據類型及其操作數據類型及其操作 （1）數值數據：數值數據包括整數、實數、復數以及這些類型的雙長（或多倍長）精度數。對數值類型的數據可描述為算術運算集合。 （2）邏輯數據：很多語言有專門用于布爾代數的數據類型，即邏輯型數據類型。有的語言甚至還有位串型數據。對邏輯數據可實施邏輯運算（and、or、not等）。 （3）字符數據：有些語言可以處理字符或字符串。字符數據類型用來承載字符或字符串。對字符數據的操作有很多，包括判斷、轉換以及對字符串的各種加工。 （4）指針類型：指針類型的數據不是用來描述客觀事物的，它的作用是為運算提供數據的地址。v 常見的結構型數據類型有以下幾種：常見的結構型數據

5、類型有以下幾種： 1數組 一個數組是由同一類型數據組成的有序的集合。數組下標與數組元一個數組是由同一類型數據組成的有序的集合。數組下標與數組元素的存儲地址密切相關，二者呈線性關系。因此數組元素也稱為下素的存儲地址密切相關，二者呈線性關系。因此數組元素也稱為下標變量。標變量。N維數組的每個元素有維數組的每個元素有N個下標。由個下標。由N個下標決定數組元素個下標決定數組元素的存儲位置。的存儲位置。 2記錄 記錄是由不同類型數據所組成的集合。記錄結構中每個元素所占有記錄是由不同類型數據所組成的集合。記錄結構中每個元素所占有的存儲空間可能互不相同，記錄的元素稱為分量。的存儲空間可能互不相同，記錄的元素

6、稱為分量。 例如，例如，C語言采用下面的形式定義記錄：語言采用下面的形式定義記錄：struct student char name8; int studclass; float math; 結構分量是通過名字而不是像數組元素那樣通過下標訪問的。結構分量的名字是所謂復合名字，例如“結構名.分量名”。結構分量的使用與基本數據結構定義的變量相同，如下述3個賦值語句： =LIMING student.studclass=3 student.math=95.4 每個分量的存儲地址由記錄結構的首地址與相應分量的偏移地址相加而成。記錄結構的每個分量（域）所占用的存儲字節數稱為該域的長

7、度。通過累加分量的長度可計算出各分量的偏移量。 占占8個字節，個字節，student.studclass占占2個字節，個字節，student.math占占4個字節，可計算三者對應的偏移量為個字節，可計算三者對應的偏移量為0、8、10，若，若student記錄結構在記錄結構在運行時被分配一個基址運行時被分配一個基址a，則其各分量的地址為：，則其各分量的地址為：:astudent.studclass:a+8student.math:a+10 3字符串、表格和隊列 不同的語言根據不同的需要會拓展出一些實用數據類型。不同的語言根據不同的需要會拓展出一些實

8、用數據類型。 有越來越多的語言把字符串作為一種基本的數據類型，串的長度不有越來越多的語言把字符串作為一種基本的數據類型，串的長度不加限制。這種數據類型給各種處理文字語言的程序帶來很多便利。加限制。這種數據類型給各種處理文字語言的程序帶來很多便利。v 2.1.3 語句與表達式語句與表達式 1語句 每當用戶創建了一個名稱，就要用說明語句來說明這個名稱所指對每當用戶創建了一個名稱，就要用說明語句來說明這個名稱所指對象的意義，是一種變量、一種操作、還是一個子程序。而執行性語象的意義，是一種變量、一種操作、還是一個子程序。而執行性語句就是描述計算機操作的，其還可分為賦值語句、控制語句、輸入句就是描述計算

9、機操作的，其還可分為賦值語句、控制語句、輸入/輸出語句。輸出語句。 （1）說明語句 說明語句的作用在于定義名字的屬性，即賦予名字意義，如：說明語句的作用在于定義名字的屬性，即賦予名字意義，如：int x; C語言定義整型變量語言定義整型變量 （2）賦值語句：賦值語句在不同的程序設計語言中可能有不同的語句形式，但實現功能基本相同。 例如：例如：X：=Y PASCAL賦值語句賦值語句 （3）控制語句：計算機程序之所以能夠實現各種強大的功能，原因是有了控制語句。控制語句的核心操作就是：判斷選擇，這是一切智能行為的基礎。 條件語句if E then Sif E then S else S1 循環語句w

10、hile(E) B do S repeat S until Bfor I:=E1 step E2 until E3 do S過程調用語句call p(x1,x2,xn)返回語句return(E)無條件轉移語句goto L 2表達式 表達式由運算對象和算符組成，對于多數程序語言來說，表達式的形式規則如下： （1）變量（包括下標變量）是表達式。 （2）若E1、E2為表達式，是一個二元算符，則E1E2是表達式。表達式一般采用中綴形式。 （3）若E是表達式，為一元算符，則E或E是表達式。 （4）若E是表達式，則（E）是表達式。 一般程序設計語言中算術算符和邏輯算符的優先順序：乘冪 （*或）一元負 （-

11、）乘、除 （*，/，）加減 （+，-）關系符 （，=，=）非 （，not或NOT）與 （ ，&，and或AND）或 （ ，|，or或OR）等值 （，或equi）v 2.1.4 程序的結構程序的結構 1FORTRAN 一個一個FORTRAN程序由一個主程序和若干個（可以是程序由一個主程序和若干個（可以是0個）輔程序段組成。個）輔程序段組成。 PROGRAM MAIN END SUBROUTINE SUB1 END SUBROUTINE SUBn END 輔程序段可以是函數、過程或數據塊。每個程序段由一系列說明語句和執行語句組成，各段可以獨立編譯，這對于模塊設計特別合適。 2C語言 一般由

12、一個主函數和若干個（可以是一般由一個主函數和若干個（可以是0個）函數組成。個）函數組成。 C語言的程序結構如下：語言的程序結構如下：main() type function1 (參數表) type functionn （參數表） 3PASCAL PASCAL語言的特點是允許子程序嵌套定義，一個PASCAL程序可以看作是由操作系統調用的一個子程序，而子程序中又可以定義別的子程序。 （1）一個子程序B1中說明的名字X只在B1中有效。 （2）如果B2是B1的一個內層子程序，且B2中對X沒有新的說明，則原來的名字在B2中仍然有效。如果B2對X重新作了說明，那么B2中對X的任何引用都是指重新說明過的那個

13、X。 4Java Java很重要的概念是類（Class）及繼承（Heritanced）。Java同時支持多態性（Polymorphism）和動態綁定（Dynamic Binding）等特性。class Car int calor-number; int door-number; int speed; push-break() Add oil() class Trash-Car extends Car double amount; fill-trash() 2.2 中中 間間 語語 言言v 2.2.1 逆波蘭表示法逆波蘭表示法逆波蘭表示表達式 高級語言表示表達式 ab* a*b ab*c+ a*

14、b+c abcd/+* a*(b+c/d) ab*cd*+ a*b+c*d 高級語言表達式E的逆波蘭表示法可這樣定義： （1）若）若E是高級語言中的一個變量或常數，則是高級語言中的一個變量或常數，則E的逆波蘭表示式仍的逆波蘭表示式仍是是E。 （2）若高級語言中的表達式為）若高級語言中的表達式為E1 op E2，其中，其中，op是一個二元算是一個二元算符，符，E1、E2也是表達式，則逆波蘭式表示為也是表達式，則逆波蘭式表示為E1 E2 op，其中，其中，E1是是E1的逆波蘭式，的逆波蘭式，E2是是E2的逆波蘭式。的逆波蘭式。 （3）若高級語言中的表達式為（）若高級語言中的表達式為（E），則逆波蘭

15、表示式為去掉括號），則逆波蘭表示式為去掉括號的的E，E為為E的逆波蘭表示式。的逆波蘭表示式。 若把逆波蘭表達式視為一個字符串，則計算逆波蘭式的算法為： （1）讀入字串左端的一個字。）讀入字串左端的一個字。 （2）如果讀入空字，計算結束。）如果讀入空字，計算結束。 （3）如果讀入一個操作數，將操作數推進棧，轉（）如果讀入一個操作數，將操作數推進棧，轉（1）。）。 （4）如果讀入一個一元操作符，取棧頂一個操作數與一元操作符）如果讀入一個一元操作符，取棧頂一個操作數與一元操作符進行運算，并將運算結果推進棧，轉（進行運算，并將運算結果推進棧，轉（1）。）。 （5）如果讀入一個二元操作符，取棧頂兩個操作

16、數與二元操作符）如果讀入一個二元操作符，取棧頂兩個操作數與二元操作符進行運算，并將運算結果推進棧，轉（進行運算，并將運算結果推進棧，轉（1）。）。v 【例【例2.1】有以下用高級語言所編寫的表達式：】有以下用高級語言所編寫的表達式：3+5*4轉換為逆波蘭表達式為：354*+ 計算逆波蘭表達式計算逆波蘭表達式354*+的過程的過程步 驟 序 號棧計 算待處理字符串說 明1354*+初始狀態2354*+讀操作數3，進棧33 54*+讀操作數5，進棧43 5 4*+讀操作數4，進棧535*4+讀操作符*，計算5*463 20+將計算結果20進棧73+20讀操作符+，計算3+20823將計算結果23進

17、棧923讀入空，計算結束v 2.2.2 三地址代碼三地址代碼 三地址代碼是由下面一般形式的語句構成的序列。x:=y op z其中x、y、z是變量名或編譯時產生的臨時變量名；y、z還可以是常數；op代表某種操作符。這種中間語言的特點有兩個。 （1）非常接近匯編語言形式，包括匯編語言中最基本的操作。）非常接近匯編語言形式，包括匯編語言中最基本的操作。 （2）每個語句中賦值號的右邊只有一個操作符，使得句子意義最）每個語句中賦值號的右邊只有一個操作符，使得句子意義最小且不可分。小且不可分。 三地址代碼的具體實現常以記錄的形式表示，通常有3種表示方法：四元式、三元式、間接三元式。 四元式的一般形式為：四元式的一般形式為：操作符操作數1操作數2運算結果三地址碼 四元式x:=A (:=， A， ， x)x:=op A (op， A， ， x) x:=A op B (op， A，B， x)對于轉移類語句，上述四元式記錄的內涵要做適當的修改： 例如，下面的三地址碼轉移類語句用四元式表示為： 三地址碼 四元式goto L (JP， ， ， L)if a relop b goto L (Jrelop， a， b， L)if a goto L (J， a， ， L)call p, n (call， n， ， p)retur