第5章 編譯器.

Presentation on theme: "第5章 編譯器."— Presentation transcript:

1 第5章 編譯器

2 內容 5.1節將討論「單階段作業的編譯器」的基本功能 5.2節討論機器相關的擴充功能 5.3節討論機器不相關的擴充功能
5.4節討論一些不同的編譯器設計方法 5.5節提出五個範例

3 5.1 編譯器的基本功能 通常使用文法（grammar），來描述一個高階語言的規則。
文法會明確地指出該程式語言中，合法敘述（statement）的形式（form）和語法（syntax）。 編譯的程序包括三個步驟 語彙掃描（scanning） 語法分析（parsing） 產生機器碼（code generation）

4 5.1 編譯器的基本功能 符記是程式語言中最基本的組成單元。 「語彙分析」（lexical analysis）
掃瞄程式碼中的敘述，找出其中的符記並加以分類的動作 「掃描器」（scanner） 語法分析（parsing或syntactic analysis） 當編譯器完成語彙分析之後，會將程式中的每一筆敘述，歸類為文法中的某一種語言結構 語法分析器（parser） 產生目的碼:機器碼

5 圖5.1　Pascal程式範例

6 5.1.1 文法 一個程式語言的文法是指一種正式的格式，用來描述該語言中程式和個別敘述的語法（syntax）或形式（form）
文法並不描述個別敘述的語意（semantic）或意義（meaning）。

7 兩個敘述的語法相同，但語意卻不同 I := J + K X := Y + I 變數X和Y都是實數 變數I、J、和K是整數

8 BNF（Backus-Naur Form）
編寫文法所使用的標記方式 <read> ::= READ ( <id-list> ) 空白字元沒有任何意義。 介於小於符號（<）和大於符號（>）之間的字串，稱之為「非終端符號」（nonterminal symbol） 符號「::=」用來表示「::=」左邊的識別名稱，在文法中，被定義成「::=」右邊的樣子。 未介於小於符號和大於符號之間的字串或字元，稱之為「終端符號」（terminal symbol）

9 簡化的Pascal文法

10 分析樹（parse tree）/語法樹（syntax tree）
依據文法來分析原始程式中的敘述，並以樹狀結構來展示此分析的結果。 READ ( VALUE )

11 指定敘述（assignment statement）<
assign> ::= id := <exp> <exp> ::= <term> | <exp> + <term> | <exp> - <term>

12 圖5.4　展示圖5.1中程式碼的語法分析樹

13 圖5.4　展示圖5.1中程式碼的語法分析樹

14 5.1.2 語彙分析 掃瞄原始碼並辨識出敘述中所有符記的動作
決定了在程式原始碼中那些部份是符記；例如，關鍵字（keyword）、運算子（operator）、識別字（identifier）、整數（integer）、浮點數（floating-point number）、字元字串（character string）等。 語彙掃描器會輸出一連串的符記。

15 識別字 <ident> ::= <letter> | <ident> <letter> | <ident> <digit> <letter> ::= A | B | C | D | ... | Z <digit> ::= 0 | 1 | 2 | 3 | ... | 9

16 圖5.5　展示圖5.2中文法的符記代碼表

17 圖5.6 針對圖5.1 之程式碼進行語彙掃描所產生的結果
圖5.6　針對圖5.1 之程式碼進行語彙掃描所產生的結果

18 有限自動機 有限自動機是由一組有限集合的狀態，和一組狀態之間的轉換集合所組成。
有一個狀態是起始狀態（starting state），另外會有一個或多個狀態是最終狀態（final states）。 每一個圓形是代表一個狀態（states），圓形中間有狀態的編號，而圓形與圓形之間的箭頭，則代表狀態之間的轉換（transitions）。

19 有限自動機 使用有限自動機，可以辨別大部分程式語言的符記。
可以從有限自動機（finite automaton）的起始狀態開始，依照所掃描的每一個字元，從一個狀態轉換至下一個狀態。 如果比對下一個字元之後並沒有符合的轉換，或是已經沒有字元可以掃描時，有限自動機就會停止。 如果有限自動機是停止在非最終狀態（non-final state）時，表示有限自動機無法辨識（或是拒絕）該字串；而當有限自動機是停止在最終狀態（final state）時，則表示有限自動機可以辨識（或接受）該字串。

20 圖5.7　有限自動機

21 圖5.8 可辨識一般程式語言符記的有限自動機

22 圖5.9　可辨識圖5.5中所有符記的有限自動機

23 圖5.10 用 (a) 演算法和 (b) 有限自動機的表列式來辨識符記

24 5.1.3 語法分析 語法分析就是依據程式語言所使用的文法，分析程式原始碼並建構語法分析樹。
由上而下的方法是根據文法規則，從樹根（root）開始，建構完整的語法分析樹，而樹的終端節點（terminal node）就是程式碼中的敘述 由下而上的方法則是從樹的終端節點開始，把節點合併成更上層的節點，一層又一層地向上建構，直到語法分析樹的根為止

25 運算子優先順序分析法 由下而上的分析方法，又稱為運算子優先順序法 加法「+」的優先順序比乘法「*」低，可以用下列寫法表示之

26 圖5.11 依據圖5.2 的文法所建立之運算子優先順序的矩陣

27 圖5.12 依據運算子優先順序來分析READ 敘述

28 圖5.13 用運算子優先順序分析法來分析一個指定敘述

29 圖5.13 用運算子優先順序分析法來分析一個指定敘述

30 「移動－化減」分析法（shift-reduce parsing）
「移動」是把目前的符記置入堆疊的最上層 「化減」是依照文法規則，將堆疊最上層的符記翻譯成符號。

31 圖5.14　「移動－化減分析法」的範例

32 圖5.14　「移動－化減分析法」的範例

33 圖5.14　「移動－化減分析法」的範例

34 「遞迴－下降」分析法 由上而下（top-down）的語法分析方法，又稱之為「遞迴－下降」分析法（recursive descent parsing） 將包含許多的程序，而每一個程序分別負責不同的「非終端符號」（nonterminal symbol），當語法分析器呼叫某個程序時，該程序將從輸入的資料中找出一個，以目前的符記為開頭的子字串（substring），並將此子字串翻譯成該程序所負責的非終端符號。 當遭遇到此種多定義的非終端符號時，必須先檢視 下一個輸入的符記，才能夠決定應採用哪一個定義。

35 圖5.15 適用於「遞迴－下降」分析法的Pascal 修正文法

36 圖5.16 使用「遞迴－下降」分析法來分析READ 敘述

37 圖5.16 使用「遞迴－下降」分析法來分析READ 敘述

38 圖5.17 用「遞迴－下降」分析法分析一個指定敘述

39 圖5.17 用「遞迴－下降」分析法分析一個指定敘述

40 圖5.17 用「遞迴－下降」分析法分析一個指定敘述

41 圖5.17 用「遞迴－下降」分析法分析一個指定敘述

42 5.1.4 目的碼的產生 在目的碼產生技術中，包含了一組對應到文法規則的常式（routine。也被稱為「語意常式」（semantic routine）。 這些常式會直接產生目的碼，但是較複雜的編譯器則可能會先產生中介碼（intermediate form），然後分析這些中介碼，並試著產生效率較好的目的碼。 利用兩種資料結構來儲存資料，分別是串列（list）和堆疊（stack）。

43 資料結構 「LISTCOUNT」變數是用於記錄目前有幾個項目存在串列中。
符記修飾子（token specifiers），在此以S（符記）來代表 「LOCCER」變數，來記錄所編譯之程式中下一個可用的位址 將「節點修飾子」（node specifier）S(<term>1) 設定成 rA，表示此運算的結果會存放於暫存器A中。

44 圖5.18　一個READ敘述的目的碼產生

45 圖5.19　一個指定敘述的目的碼產生

46 圖5.19　一個指定敘述的目的碼產生

47 圖5.19　一個指定敘述的目的碼產生

48 圖5.19　一個指定敘述的目的碼產生

49 圖5.19　一個指定敘述的目的碼產生

50 圖5.19　一個指定敘述的目的碼產生

51 圖5.19　一個指定敘述的目的碼產生

52 圖5.20　針對圖5.2中文法的目的碼產生常式

53 圖5.20　針對圖5.2中文法的目的碼產生常式

54 圖5.20　針對圖5.2中文法的目的碼產生常式

55 圖5.20　針對圖5.2中文法的目的碼產生常式

56 圖5.21 針對圖5.1中程式碼所產生的目的碼（用組合語言來表示）
圖5.21　針對圖5.1中程式碼所產生的目的碼（用組合語言來表示）

57 圖5.21 針對圖5.1中程式碼所產生的目的碼（用組合語言來表示）
圖5.21　針對圖5.1中程式碼所產生的目的碼（用組合語言來表示）

58 5.2 相依於機器的編譯器特性 5.2.1 節介紹一種可以將程式碼轉換成中間形式的常用方法
5.2.2節將會使用此種中間形式，來討論與機器相依的目的碼最佳化技術 5.3節利用類似的中間形式，來討論一些與機器不相依的目的碼最佳化技術。

59 5.2.1 程式的中間形式 operation, op1, op2, result SUM := SUM + VALUE
以四項形式來呈現此敘述，結果如下： + , SUM, VALUE, i1 :=, i1 , , SUM

60 四項形式的中介碼 具有許多的優點 可以重新排列這些中介碼的順序，以刪除多餘的載入（load）和儲存（store）運算，如此便可以減少對記憶體的存取，以提高執行的效率 盡量使用暫存器或暫時變數（temporary variables），來存放中間結果（intermediate result）ij，這對執行效率的提升具有相當的幫助

61 圖5.22　展示圖5.1中程式原始碼的中介碼

62 5.2.2 相依於機器之目的碼的最佳化 在大多數處理器中，都會有通用暫存器（general-purpose registers），可以用來存放常數、變數的值、以及中間結果（intermediate results）等 如何有效率地使用和分配數量有限的暫存器 可以將程式分割成一些基本區塊（basic blocks），一個基本區塊中會有一連串的中介碼。 程式流程圖（flow graph）

63 圖5.23　將圖5.22的中介碼劃分成基本區塊和流程圖

64 圖5.24　重新排列中介碼以進行目的碼的最佳化

65 圖5.24　重新排列中介碼以進行目的碼的最佳化

66 具有高階指令（high-level machine instructions）的機器
其他「相依於機器之目的碼最佳化」的方法 利用機器的特性或是特殊指令 較有效率的迴圈控制指令或定址模式 具有高階指令（high-level machine instructions）的機器

67 5.3 不相依於機器的編譯器特性 5.3.1節將介紹如何處理陣列（array）的結構化變數（structured variables）。
5.3.2節討論不相依於機器之目的碼的最佳化技術。

68 5.3.1 結構化變數 編譯具備陣列（array）、記錄（record）、字串（string）、和集合（set）等結構化變數的程式
配置儲存空間，以及如何產生目的碼，以引用這些空間。

69 陣列 ARRAY[l..u] OF INTEGER ARRAY [l1..u1, l2..u2] OF INTEGER
分配給該陣列的字組數量：(u1-l1+1)*(u2-l2+1) 「列位順序」（row-major order） 「行位順序」（column-major order）

70 圖5.25 B：ARRAY[0..3, 1..6] 以 (a) 「列位順序」及 (b) 「行位順序」的方式來儲存

71 陣列元素的位址 A : ARRAY[l...u] OF INTEGER
A[s] 相對於陣列基底位址的位址如下： w * (s-l) B : ARRAY [l1..u1, l2..u2] OF INTEGER B[s1, s2] 的相對位址如下： w * [(s1-l1) * (u2-l2+1) + (s2-l2)]

72 圖5.26　陣列引用的中介碼

73 5.3.2 不相依於機器之目的碼的最佳化 「共同子運算式的刪除」是一項重要的目的碼最佳化技術。 「迴圈常量的移除」
某個子計算式在程式中出現了許多次，也就是在程式中的不同部位，重複著相同的運算。 所產生的目的碼應該只會計算一次，第二次以後的目的碼會直接使用已知的計算結果。 「迴圈常量的移除」 「迴圈常量」:其值並不會隨著迴圈的輪迴而改變 在進入迴圈之前，先行計算出該常量的值

74 圖5.27 刪除「共同子運算式」和「迴圈常量」以達成目的碼的最佳化
圖5.27　刪除「共同子運算式」和「迴圈常量」以達成目的碼的最佳化

75 圖5.27 刪除「共同子運算式」和「迴圈常量」以達成目的碼的最佳化
圖5.27　刪除「共同子運算式」和「迴圈常量」以達成目的碼的最佳化

76 圖5.27 刪除「共同子運算式」和「迴圈常量」以達成目的碼的最佳化
圖5.27　刪除「共同子運算式」和「迴圈常量」以達成目的碼的最佳化

77 圖5.27 刪除「共同子運算式」和「迴圈常量」以達成目的碼的最佳化
圖5.27　刪除「共同子運算式」和「迴圈常量」以達成目的碼的最佳化

78 其它最佳化的方法 使用比較有效率的運算，來置換比較沒有效率的運算。 「減低運算的強度」方法 「折疊」（folding）方法
「展開迴圈」（loop unrolling）方法 「合併迴圈」（loop jamming）方法

79 圖5.28 以「減低運算的強度」進行目的碼的最佳化
圖5.28　以「減低運算的強度」進行目的碼的最佳化

80 5.3.3 記憶體空間的配置 靜態配置（static allocation）
暫時變數，包括用於存放回歸位址（return address）的暫時變數，都是位在程式中的固定位址。 遞迴（recursive）和動態記憶體配置（dynamic allocation）

81 圖5.29　在遞迴呼叫時使用靜態記憶體配置

82 動態記憶體配置（dynamic storage allocation）技術
當以遞迴方式呼叫SUB副程式時，必須要能夠保留SUB副程式中所有變數的值。這些變數包括參數（parameters）、暫時變數（temporaries）、回歸位址（return addresses）、暫存器儲存區（register save areas）等。 用一個堆疊（stack）來存放所有的活動記錄，而現行的記錄是位在堆疊的最頂端。

83 圖5.30　在遞迴呼叫時使用自動記憶體配置

84 圖5.30　在遞迴呼叫時使用自動記憶體配置

85 自動（automatic）記憶體配置 當程序被呼叫時，才會配置所有變數的記憶體空間。

86 程式設計師可以指定配置記憶體空間 FORTRAN 90 PASCAL C ALLOCATE (MATRIX(ROWS, COLUMNS))
DEALLOCATE (MATRIX) PASCAL NEW(P) DISPOSE(P) C MALLOC(SIZE) FREE(P)

87 5.3.4 區塊結構語言 在某些語言中，一個程式將會劃分成許多的單元，稱之為區塊（blocks）。
一個區塊是程式的一部份，它可以宣告自己的識別字。 例如，在Pascal語言中的程序（procedures）和函式（functions）即是一個區塊。

88 圖5.31　原始程式中的巢狀區塊

89 區塊結構 大部分的區塊結構語言，都是採用自動記憶體配置技術，為變數配置其記憶體空間。
常見方法之一，是利用一種稱之為「顯示」（display）的資料結構 「顯示」結構中存放的是最近活動記錄的指標，其指向目前區塊以及所有外層區塊的活動記錄。當某區塊中的程式所引用到的變數，是由外層區塊所宣告時，產生的目的碼就會利用「顯示」結構，來找出包含這個變數的活動記錄。

90 圖5.32　圖5.31中程序所使用的「顯示」結構

91 圖5.32　圖5.31中程序所使用的「顯示」結構

92 5.4 編譯器設計的選項 5.4.1 節將會簡短地討論，當選擇單次或多次的編譯架構時，所需要考量的因素以及二種架構的個別優點。
5.4.2節將介紹解譯器（interpreter） 5.4.3節會介紹虛擬碼系統（P-code systems） 5.4.4節將要介紹「撰寫編譯器的系統」

93 5.4.1 劃分成多階段 5.2節和5.3節討論一些目的碼最佳化的技術，大部分技術都不能實現於單階段的編譯架構。
某些言語可以接受識別的宣告是位在其使用之後。此時，單階段的編譯器必能夠解決跳躍指令中「向前引用」（forward reference）的問題，其採用的技術與單階段的組譯器相似。 如果編譯速度是最大的考量時，單階段編譯方式可能是較佳的選擇。 如果程式在每次編譯後，會執行許多次或是處理大量的資料，那麼目的碼的執行速度，將會遠比編譯的速度更為重要。

94 5.4.2 解譯器 編譯器會把程式原始碼翻譯成機器碼，解譯器則是直接執行原始程式。
解譯器也會對程式原始碼進行語彙分析和語法分析，並且將原始程式翻譯成內部形式（internal form），然後執行之。 可以把解譯器視為一群副程式的集合，而這些副程式會依據內部形式的內容來執行，以達到原始程式所要進行的動作。

95 5.4.2 解譯器 雖然解譯的過程相當簡單而且快速，但是最後的執行速度卻緩慢許多。 非常容易地在執行期間進行除錯（debug）的動作。
某些語言的特性，可能會將其導向於解譯的方式:變數的型態是可以在程式的執行過程中，予以修改；動態範圍（dynamic scoping）

96 5.4.3 虛擬碼編譯器 進行原始程式分析，並且產生中間型式（intermediate form），然後依此以解譯的方式執行。
虛擬碼編譯器產生的中間形式，是虛擬機器（pseudo-machine或P-machine）的機器語言。

97 圖5.33　虛擬碼編譯器的產生和執行

98 可攜性（portability） 只要系統內具有虛擬機器（虛擬碼解譯器），則虛擬機器就可以直接執行虛擬機器的目的碼，而程式不需要重新編譯。
虛擬機器的目的程式，通常會比同功能的機器碼更小，因此特別適合於小記憶容量的機器。 以解譯方式執行虛擬碼程式的速度，遠不及功能相同的真正機器碼程式。

99 5.4.4 編譯器的編譯器 「編譯器的編譯器」（compiler-compilers）是可以用於協助編譯器的建立工作，此類工具亦稱之為編譯器產生器（compiler generator）或翻譯器撰寫系統（translator-writing system）。

100 圖5.34 採用「編譯器的編譯器」之自動化編譯器建
圖5.34　採用「編譯器的編譯器」之自動化編譯器建

101 編譯器的編譯器 「編譯器的編譯器」所提供的彈性重度並不相同，能夠節省的工作也並不一致
相較於完全重新製作的編譯器，「編譯器的編譯器」所製作出來的編譯器，可能會需要較多的記憶體，而且編譯速度也會比較慢。 YACC

102 5.5 編譯器範例 5.5.1節將介紹SunOS的C語言編譯器 5.5.2節會介紹GNAT（GNU NYU Ada Translator）
5.5.3節介紹Cray公司的MPP FORTRAN編譯器5.5.4節介紹由昇陽電腦（Sun Microsystems）所發展的Java編譯器。 5.5.5節介紹YACC的「編譯器的編譯器」

103 5.5.1 SunOS的C語言編譯器 翻譯的程序是從C的前置處理器開始，執行檔案引入（include）和巨集處理（macro processing）等功能（請參考4.4.3節）；接著，前置處理器的輸出會傳至編譯器，開始真正的編譯工作。其中，使用者可以指定目的碼最佳化的等級。最後，編譯器會產生組合語言的程式，並交由組譯器來產生機械碼。 可以設定4種目的碼的最佳化等級 可以產生除錯工具

104 5.5.2 GUN NYU Ada翻譯器 GNU軟體系統中的一個Ada編譯器，可以支援Ada95和Ada83二種語言。
GNAT的語法分析，是採用人工撰寫之遞迴而漸降（hand-coded recursive descent）的分析器。 語意分析（semantic analysis）和擴展（expansion）是相互串連在一起。 GNAT到GNU的階段會追蹤抽象語法樹，並呼叫產生器來建立一些對應的GCC樹片段。當產生每一個片段時，GCC後端將會產生對應目的碼

105 圖5.35 GNAT的整體架構

106 5.5.3 Cray MPP FORTRAN編譯器 分派工作給予處理元 DIMENSION A(256)
CDIR$ SHARED A(:BLOCK)

107 5.5.3 Cray MPP FORTRAN編譯器 MPP FORTRAN編譯器提供了一些工具，可用於同步（synchronize）一些平行運作的程式。 另一種同步的方式是，讓處理元之間互通信號（signal）。

108 5.5.4 Java編譯器和執行環境 Java編譯器的運作方式，是依循5.4.3節中所述的虛擬碼（P-code）
Java編譯器所產生的目的碼，稱之為位元組碼（bytecode），是一種與實際硬體架構無關，並且執行於Java虛擬機器（Java Virtual Machine）上的高階目的碼。 有許多時候可能會需要較高的執行效率。在此種狀況下，可以在執行之時將Java的bytecode翻譯成所處平台的機械碼。

109 5.5.5 編譯器的編譯器 — YACC 一個產生語法分析器的程式
LEX是一種語彙掃描器的產生程式，可以產生YACC所需的語彙掃描器。

110 圖5.37　LEX和YACC輸入規格的範例

111 YACC 根據圖5.37(a) 中的輸入規格，下列敘述 let x = y * z 經過掃描後，產生的語彙符記如下：
LET ID ASSIGN ID MUL ID YACC產生的語法解析器，所使用的語法解析技術是一種「由下而上」分析法，稱之為LALR(1) 。LALR(1) 是一種受到些微限制的「移動－化減」分析法。