中間語言

中間語言(中間代碼)是一種面向語法，易於翻譯成目標程式的源程式的等效內部表示代碼。其可理解性及易於生成目標代碼的程度介於源語言和目標語言之間。常用的中間語言有逆波蘭表示、四元式、三元式和樹表示等。

基本介紹

• 中文名：中間語言
• 外文名：Intermediate Language
• 常用形式：逆波蘭表示、四元式、三元式等

中間語言的優點

1、中間語言與具體機器特性無關，一種中間語言可以為生成多種不同型號的目標機的目標代碼服務。

2、可對中間語言進行與機器無關的最佳化，有利於提高目標代碼的質量。

3、把源程式映射成中間代碼表示，再映射成目標代碼的工作分在幾個階段進行，使編譯算法更加清晰。

對於中間語言，要求其不但與機器無關，而且有利於代碼生成。

常用的中間語言

逆波蘭表示

逆波蘭表示又稱後綴表示法，它是最簡單的一種中間代碼表示形式，早在編譯程式出現之前，它就用於表示算術表達式。

只包含簡單變數（包括常數）的表達式的逆波蘭式定義如下：

①每個變數a是逆波蘭式；

②如果E₁和E₂是逆波蘭式，則E₁E_2ω也是逆波蘭式，其中ω是任一運算符。

從上面的定義可以看出，逆波蘭表示法是將運算對象寫在前面，把運算符寫在後面（後綴），例如，把a+b寫成ab+，把a*b寫成ab*。所以用這種表示法表示的表達式也稱為後綴式。一般來說，若 θ 是一個k（≥1）目算符，它對後綴式e₁，e₂，...，e_k作用的結果將被表示為e₁e₂...e_k。

逆波蘭表示法的特點是不再需要括弧來明顯地規定表達式運算的順序。例如，表達式(x-y)*z將被表示為xy-z*。根據運算對象和運算符出現的先後位置，以及每個算符的目數，就完全決定了一個表達式的分解。表達式和它的逆波蘭式中的運算對象順序是完全一致的，即，表達式中的所有運算對象，均按原序排在其逆波蘭式中。

四元式

四元式也是一種比較普遍採用的中間代碼形式，

其形式為：（OP，ARG1，ARG2，RESULT）

其中：OP為運算符，ARG1為第一運算對象，ARG2為第二運算對象，RESULT為運算結果。

運算對象和運算結果有時指用戶自定義的變數，有時指編譯程式引進的臨時變數。我們很容易將一個表達式或一個語句表示為一組四元式。例如表達式a+b的四元式為：（ +，a，b，T）在四元式表示法中，特別規定，對於單目運算符（單目減、邏輯非、類型轉換等），其四元式中的ARG2為空，一般用符號“/”或“ -”表示。例如表達式-a的四元式為：（ -，a，/，T）

三元式

三元式表示是與四元式類似的一種表示法，所不同的僅是三元式中沒有表示運算結果的部分，凡要涉及到運算結果的均用三元式的位置或序號來代替。

三元式的形式為：（OP，ARG1，ARG2）

其中，OP為運算符，ARG1為第一運算對象，ARG2為第二運算對象。運算對象ARG1，ARG2可以是變數名，也可以是三元式的編號。

例如，表達式a+b*c的三元式表示為：

①（*，b，c）

②（ +，a，①）

其中，三元式中的元素①表示第一個三元式的結果。

樹表示

樹形表示是三元式的翻版。在樹的表示中，樹葉均為運算對象，即常量或變數，其他結點表示運算符。表達式的樹形表示很容易實現：簡單變數或常量的樹就是該變數或常量自身，如果表達式

e₁和e₂的樹分別為T₁和T₂，那么e₁+e₂，e₁* e₂，-e的樹分別為圖1，表達式a* b+c* d樹形表示為圖2，後序遍歷上述二叉樹便可得到該表達式的逆波蘭表示ab*cd*+。

我們很容易把三元式表示成樹形表示。每個三元式（OP，ARG1，ARG2）對應一棵二叉子樹，OP為子樹的根，ARG1和ARG2為子樹的兩棵子樹，它們或為末端結點（終結符）或為下代子樹的根，最後一個三元式③對應樹的根。下圖給出了三元式和樹形表示的對應關係。

一般而言，雙目運算對應二叉子樹，多目運算對應多叉子樹。但是，為了便於安排存儲空間，一棵多叉子樹可以通過引進新結點而表示成一棵二叉子樹。