編譯原理王者之路

---

王者導(dǎo)航

• 編譯原理王者之路
• 前言
• 一、學(xué)習(xí)路線
• • 1、課本路線
  • 2、技術(shù)路線
• 二、基礎(chǔ)知識(shí)
• • 1、基礎(chǔ)概念
  • • 1.1 編譯程序（翻譯程序）
    • 1.2 交叉編譯程序
    • • 1.2.1 宿主機(jī)
      • 1.2.2 目標(biāo)機(jī)
  • 1.3 編譯前端
  • 1.4 編譯后端
  • 1.5 程序設(shè)計(jì)環(huán)境
  • 1.6 程序語(yǔ)言
  • • 1.6.1 語(yǔ)法
    • • 1.6.1.1 詞法規(guī)則和語(yǔ)法規(guī)則
    • 1.6.2 語(yǔ)義
• 三、程序語(yǔ)言的語(yǔ)法描述
• • 1、基礎(chǔ)概念
  • • 1.1 符號(hào)串
    • 1.2 空字
    • 1.3 文法
    • • 1.4 上下文無(wú)關(guān)文法（重點(diǎn)）
  • 2、上下文無(wú)關(guān)文法
  • • 2.1 定義
    • 2.2 推導(dǎo)過(guò)程
    • • 2.2.1 最左推導(dǎo)
      • 2.2.2 最右推導(dǎo)
    • 2.3 語(yǔ)法分析樹(shù)
    • • 2.3.1 定義
      • 2.3.2 二義性
• 四、詞法分析
• • 1、任務(wù)
  • 2、過(guò)程
  • • 2.1 詞法分析器的輸入輸出
    • • 2.1.1 輸入
      • 2.1.2 輸出
    • 2.2 輸入、預(yù)處理
    • 2.3 單詞符號(hào)的識(shí)別-超前搜索
    • 2.4 狀態(tài)轉(zhuǎn)換圖
    • 2.5 正規(guī)表達(dá)式和有限自動(dòng)機(jī)
    • • 2.5.1 正規(guī)表達(dá)式
      • • 2.5.1.1 正規(guī)集定義
        • 2.5.1.2 正規(guī)式定義
        • 2.5.1.3 正規(guī)式和正規(guī)集遞歸定義
      • 2.5.2 有限自動(dòng)機(jī)
      • • 2.5.2.1 確定有限自動(dòng)機(jī)
        • 2.5.2.2 非確定有限自動(dòng)機(jī)
        • 2.5.2.3 子集法
• 五、語(yǔ)法分析
• • 1、任務(wù)
  • 2、自上而下分析方法
  • • 2.1 主旨
    • 2.2 缺點(diǎn)應(yīng)對(duì)方法
    • • 2.2.1 消除文法的左遞歸
      • 2.2.2 消除回溯，提取左因子
      • 2.2.3 LL(1)分析條件
      • 2.2.4 LL(1)分析
  • 3、自下而上分析方法
  • • 3.1 主旨
    • 3.2 過(guò)程
    • 3.3 算符優(yōu)先分析
    • 3.4 LR分析
    • • 3.4.1 定義
      • 3.4.2 操作
• 六、語(yǔ)義分析和中間代碼產(chǎn)生
• • 1、任務(wù)
  • 2、語(yǔ)義分析
  • 3、中間代碼生成
  • • 3.1 中間語(yǔ)言形式
    • • 3.1.1 后綴式
      • 3.1.2 三地址代碼
      • • 3.1.2.1 一般形式
        • 3.1.2.2 四元式
      • 3.1.2.3 三元式
      • 3.1.2.4 間接三元式
• 七、優(yōu)化
• • 1、任務(wù)
  • 2、原則
  • • 2.1 等價(jià)原則
    • 2.2 有效原則
    • 2.3 合算原則
  • 3、方法
  • • 3.1 刪除公共子表達(dá)式
    • 3.2 復(fù)寫(xiě)傳播
    • 3.3 刪除無(wú)用代碼
    • 3.4 強(qiáng)度削弱
    • 3.5 刪除歸納變量
• 八、目標(biāo)代碼生成
• • 1、任務(wù)
  • 2、輸入輸出
  • 3、目標(biāo)代碼的形式
  • • 3.1 能夠立即執(zhí)行的機(jī)器語(yǔ)言代碼
    • 3.2 待裝配的機(jī)器語(yǔ)言模塊
    • 3.3 匯編語(yǔ)言代碼
  • 4、基本問(wèn)題
  • • 4.1 代碼生成器的輸入
    • 4.2 指令選擇
    • 4.3 寄存器分配
    • 4.4 計(jì)算順序選擇

---

前言

??近期，學(xué)期末，編譯原理期末考試，借此機(jī)會(huì)，對(duì)編譯原理這門(mén)課程與技術(shù)進(jìn)行整理匯總，形成體系大綱。編譯原理偏向于計(jì)算機(jī)應(yīng)用程序的底層，也是計(jì)算機(jī)程序員應(yīng)該了解的相關(guān)原理。其次，像現(xiàn)在的機(jī)器學(xué)習(xí)等進(jìn)行自然語(yǔ)言處理時(shí)，也會(huì)運(yùn)用相關(guān)準(zhǔn)則與方法。

---

本博文主要是參考《程序設(shè)計(jì)語(yǔ)言 編譯原理（第3版）》（陳火旺等人著）

---

一、學(xué)習(xí)路線

1、課本路線

2、技術(shù)路線

編譯程序的工作過(guò)程一般可以劃分為五個(gè)階段：詞法分析、語(yǔ)法分析、語(yǔ)義分析與中間代碼產(chǎn)生、優(yōu)化、目標(biāo)代碼生成。主要是對(duì)字符串進(jìn)行分析處理.
本博文也將按照這五個(gè)階段依次介紹每個(gè)階段的任務(wù)、方法及其實(shí)現(xiàn)。

二、基礎(chǔ)知識(shí)

1、基礎(chǔ)概念

1.1 編譯程序（翻譯程序）

??能夠把某一種語(yǔ)言程序（稱為源語(yǔ)言程序，如C、Java之類(lèi)的高級(jí)語(yǔ)言）轉(zhuǎn)換成另一種語(yǔ)言程序（稱為目標(biāo)語(yǔ)言程序，如匯編語(yǔ)言或者機(jī)器語(yǔ)言之類(lèi)的低級(jí)語(yǔ)言）的程序，后者和前者在邏輯上是等價(jià)的。

1.2 交叉編譯程序

1.2.1 宿主機(jī)

運(yùn)行編譯程序的計(jì)算機(jī)

1.2.2 目標(biāo)機(jī)

運(yùn)行編譯程序所產(chǎn)生的目標(biāo)程序的計(jì)算機(jī)

---

如果一個(gè)編譯程序產(chǎn)生不同于其宿主機(jī)的機(jī)器代碼，稱其為交叉編譯程序。

1.3 編譯前端

主要是對(duì)編譯程序的劃分。前端主要由與源語(yǔ)言有關(guān)但與目標(biāo)機(jī)無(wú)關(guān)的部分組成。如此法分析、語(yǔ)法分析、語(yǔ)義分析與中間代碼產(chǎn)生，有的代碼優(yōu)化工作也可以包括在前端。

1.4 編譯后端

主要是對(duì)編譯程序的劃分。后端包括編譯程序中與目標(biāo)機(jī)有關(guān)的那部分，通常不依賴于源語(yǔ)言而僅僅依賴于中間語(yǔ)言。如與目標(biāo)機(jī)有關(guān)的代碼優(yōu)化和目標(biāo)代碼生成等。

1.5 程序設(shè)計(jì)環(huán)境

編輯程序、編譯程序、連接程序、調(diào)試工具等工具的集成

1.6 程序語(yǔ)言

程序語(yǔ)言主要由語(yǔ)法和語(yǔ)義兩方面定義，有描述數(shù)據(jù)和對(duì)數(shù)據(jù)的運(yùn)算這兩大功能。

1.6.1 語(yǔ)法

可以形成或者產(chǎn)生一個(gè)合式的程序的一組規(guī)則。
任何語(yǔ)言程序都可以看成是一定字符集（稱為字母表）上的一字符串（有限序列）。

1.6.1.1 詞法規(guī)則和語(yǔ)法規(guī)則

這組規(guī)則包含詞法規(guī)則和語(yǔ)法規(guī)則（或產(chǎn)生規(guī)則）。
（字母組成單詞，單詞組成詞語(yǔ)，詞語(yǔ)組成句子）

1.6.2 語(yǔ)義

可以定義一個(gè)程序的意義的一組規(guī)則。

三、程序語(yǔ)言的語(yǔ)法描述

1、基礎(chǔ)概念

1.1 符號(hào)串

由∑（字母表）中的符號(hào)所構(gòu)成的一個(gè)有窮序列。

1.2 空字

不包含任何符號(hào)的序列

1.3 文法

文法是描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則（即語(yǔ)法規(guī)則）

1.4 上下文無(wú)關(guān)文法（重點(diǎn)）

所定義的語(yǔ)法范疇（或語(yǔ)法單位）是完全獨(dú)立于這種范疇可能出現(xiàn)的環(huán)境的一種文法。
一個(gè)上下無(wú)關(guān)文法包括四個(gè)部分，故上下文無(wú)關(guān)文法是一個(gè)四元式。

• 一組終結(jié)符號(hào)
  終結(jié)符號(hào)是組成語(yǔ)言的基本符號(hào)，在程序語(yǔ)言中為單詞符號(hào)，如基本字、標(biāo)識(shí)符等。
• 一組非終結(jié)符號(hào)
  非終結(jié)符號(hào)代表語(yǔ)法范疇，是一個(gè)類(lèi)或者集合的記號(hào)，每個(gè)非終結(jié)符代表一定符號(hào)串的集合（由終結(jié)符號(hào)和非終結(jié)符號(hào)組成的符號(hào)串）
• 一個(gè)開(kāi)始符號(hào)
  一個(gè)特殊的非終結(jié)符號(hào)，通常稱為句子（最大的）
• 一組產(chǎn)生式
  產(chǎn)生式是定義語(yǔ)法范疇的一種書(shū)寫(xiě)規(guī)則，左邊是非終結(jié)符（大的），中間是→，讀作產(chǎn)生，右邊是終結(jié)符號(hào)或者與非終結(jié)符號(hào)組成的符號(hào)串（小的）。

簡(jiǎn)單理解就是對(duì)其進(jìn)行就事論事處理，不必考慮上下文。根據(jù)上下文無(wú)關(guān)文法的組成，簡(jiǎn)單理解為把一個(gè)句子揉碎，分為4個(gè)部分。
其中心思想是從開(kāi)始符號(hào)出發(fā)，反復(fù)連續(xù)使用產(chǎn)生式，對(duì)非終結(jié)符實(shí)行替換與展開(kāi)，產(chǎn)生僅由終結(jié)符號(hào)組成的表達(dá)式。

2、上下文無(wú)關(guān)文法

2.1 定義

上下文無(wú)關(guān)文法屬于2型文法。文法分為四種：0型、1型、2型、3型。0型強(qiáng)于1型，以此類(lèi)推。

2.2 推導(dǎo)過(guò)程

2.2.1 最左推導(dǎo)

每次總是選擇最左側(cè)的符號(hào)進(jìn)行替換

2.2.2 最右推導(dǎo)

每次總是選擇最右側(cè)的符號(hào)進(jìn)行替換

2.3 語(yǔ)法分析樹(shù)

2.3.1 定義

用一棵樹(shù)表示一個(gè)句型的推導(dǎo)

2.3.2 二義性

如果一個(gè)文法存在一個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱這個(gè)文法是二義的。
主要是針對(duì)文法而言的。

四、詞法分析

1、任務(wù)

從左至右逐個(gè)字符地對(duì)源程序進(jìn)行掃描，產(chǎn)生一個(gè)個(gè)的單詞符號(hào)，把作為字符串的源程序改造成為單詞符號(hào)串的中間程序。
簡(jiǎn)單來(lái)說(shuō)，就是把一整個(gè)字符串劃分為一個(gè)個(gè)單詞符號(hào)。

2、過(guò)程

2.1 詞法分析器的輸入輸出

2.1.1 輸入

源程序

2.1.2 輸出

單詞符號(hào)，有五種

• 關(guān)鍵字
  程序語(yǔ)言定義的具有固定意義的標(biāo)識(shí)符
• 標(biāo)識(shí)符
  表示各種名字
• 常數(shù)
• 運(yùn)算符
• 界符

程序的關(guān)鍵字、運(yùn)算符、界符是確定的。

2.2 輸入、預(yù)處理

第一步是輸入源程序文本，輸入串一般放在一個(gè)緩沖區(qū)內(nèi)，此外，大多數(shù)情況下還要對(duì)輸入串進(jìn)行預(yù)處理，比如剔除注解、空白符、回車(chē)符、換行符等。

2.3 單詞符號(hào)的識(shí)別-超前搜索

• 詞法分析器調(diào)用預(yù)處理子程序處理一串輸入字符串
• 放入掃描緩沖區(qū)
• 從此緩沖區(qū)逐一識(shí)別單詞符號(hào)
• 處理完后調(diào)用預(yù)處理子程序裝入新串

超前搜索：超前掃描許多個(gè)字符，超前到能夠肯定磁性的地方為止。

2.4 狀態(tài)轉(zhuǎn)換圖

一種設(shè)計(jì)詞法分析器的好工具。轉(zhuǎn)換圖是一張有限方向圖。
組成

• 結(jié)點(diǎn)
  代表狀態(tài)，用圓圈表示
• 終態(tài)、初態(tài)
  一張狀態(tài)轉(zhuǎn)換圖有初態(tài)（單圈表示）和至少一個(gè)終態(tài)（雙圈表示）
• 連結(jié)
  狀態(tài)之間用箭弧進(jìn)行連接
• 標(biāo)記
  在箭弧上，表示箭弧始結(jié)點(diǎn)狀態(tài)下可能出現(xiàn)的輸入字符或字符類(lèi)

2.5 正規(guī)表達(dá)式和有限自動(dòng)機(jī)

2.5.1 正規(guī)表達(dá)式

2.5.1.1 正規(guī)集定義

程序設(shè)計(jì)語(yǔ)言的單詞表、詞匯集構(gòu)成的集合，即是字的集合。它有一定特殊性，我們稱之為正規(guī)集。用來(lái)代表程序語(yǔ)言的單詞表。

2.5.1.2 正規(guī)式定義

可以說(shuō)是正規(guī)集的名稱。

• 正規(guī)集可以用正規(guī)表達(dá)式（簡(jiǎn)稱正規(guī)式）表示
• 正規(guī)表達(dá)式是表示正規(guī)集一種方法
• 一個(gè)字集合是正規(guī)集當(dāng)且僅當(dāng)它能用正規(guī)式表示

2.5.1.3 正規(guī)式和正規(guī)集遞歸定義

$\epsilon$ 和$?$都是$\Sigma$上的正規(guī)式，它們所表示的正規(guī)集為$\{\epsilon \}$和$?$
任何$\alpha$ $?$ $\Sigma$， 則$\alpha$是$\Sigma$上的正規(guī)式，它所表示的正規(guī)集為$\{\alpha \}$
假定$e_1$和$e_2$都是$\Sigma$上的正規(guī)式，它們所表示的正規(guī)集為L(zhǎng)($e_1$)和L($e_2$)，則：
1）($e_1$|$e_2$)為正規(guī)式，它所表示的正規(guī)集為L(zhǎng)($e_1$) $\cup$ L($e_2$)

2）($e_1$ $?$ $e_2$)為正規(guī)式（做連接），它所表示的正規(guī)集為L(zhǎng)($e_1$)L($e_2$)（連接）

3）($e_1$)${}^{?}$ 為正規(guī)式，它所表示的正規(guī)集為(L($e_1$))${}^{?}$（閉包）

2.5.2 有限自動(dòng)機(jī)

2.5.2.1 確定有限自動(dòng)機(jī)

一個(gè)確定有限自動(dòng)機(jī)（DFA）M是一個(gè)五元式
M=(S, $\Sigma$, f, $S_0$ , F),其中:
1.S:有窮狀態(tài)集，即包含起點(diǎn)重點(diǎn)在內(nèi)的，各個(gè)狀態(tài)
2.$\Sigma$:輸入字母表(有窮)，即狀態(tài)改變的條件
3.f:狀態(tài)轉(zhuǎn)換函數(shù)，為 S $\times$ $\Sigma$ $\to$ S 的單值部分映射，即由A狀態(tài)到B狀態(tài)的改變
f(s,a) = s’ 表示：當(dāng)現(xiàn)行狀態(tài)為s ，輸入字符為a時(shí)，將狀態(tài)轉(zhuǎn)換到下一狀態(tài)s’，s’稱為s的一個(gè)后繼狀態(tài)
4.$S_0$ $\in$ S:是唯一的一個(gè)初態(tài)，即起點(diǎn)唯一
5.F$?$ S ：終態(tài)集(可空)，即最終狀態(tài)，不唯一。

對(duì)于Σ * 中的任何字$\alpha$，若存在一條從初態(tài)到某一終態(tài)的道路，且這條路上所有弧上的標(biāo)記符依序連接成的字等于$\alpha$，則稱$\alpha$為DFA M 所識(shí)別(接收)

2.5.2.2 非確定有限自動(dòng)機(jī)

NFA
定義 略
DFA是NFA的一個(gè)特例
對(duì)于Σ * 中的任何字$\alpha$，若存在一條從某一初態(tài)到某一終態(tài)的道路，且這條路上所有弧上的標(biāo)記符依序連接成的字等于$\alpha$，則稱$\alpha$為NFA M 所識(shí)別(接收)

2.5.2.3 子集法

將NFA確定化為DFA的方法

五、語(yǔ)法分析

1、任務(wù)

在詞法分析識(shí)別出單詞符號(hào)串的基礎(chǔ)上，分析并判定程序的語(yǔ)法結(jié)構(gòu)是否符合語(yǔ)法規(guī)則。
即按文法的產(chǎn)生式，識(shí)別輸入符號(hào)串是否為一個(gè)句子。
從概念上講，建立一棵與輸入串相匹配的語(yǔ)法分析樹(shù)。
根據(jù)語(yǔ)法分析樹(shù)的建立方法，分為兩類(lèi)，一類(lèi)是自上而下分析方法，另一類(lèi)是自下而上分析方法。

2、自上而下分析方法

2.1 主旨

對(duì)于任何輸入串，試圖用一切可能的辦法，從文法開(kāi)始符號(hào)（根結(jié)）出發(fā)，自上而下為輸入串建立一棵語(yǔ)法樹(shù)。
這種方法是帶回溯的，如果其中一個(gè)不符合，要回頭看是否有別的候選。

2.2 缺點(diǎn)應(yīng)對(duì)方法

2.2.1 消除文法的左遞歸

含左遞歸的文法會(huì)使自上而下的分析過(guò)程陷入無(wú)限循環(huán)

2.2.2 消除回溯，提取左因子

若關(guān)于 A 的語(yǔ)法規(guī)則符合如下形式：A → δβ1 | δβ2 | … | δβn | δ | γ1 | γ2 | … | γm
則提取左公因子
A → δA/ | γ1 | γ2 | … | γm
A/ → β1 | β2 | … | βn | ε |
繼續(xù)檢查 A 與 A/ 的候選式是否可以繼續(xù)提取

反復(fù)提取左公共因子（包括新引入的非終結(jié)符），就可以使得所有候選首符集兩兩不相交

2.2.3 LL(1)分析條件

• 文法不含左遞歸
• 文法中每一個(gè)非終結(jié)符 A 的各個(gè)產(chǎn)生式的候選首符集不相交，即若 A → α1 | α2 | … | αn
  FIRST(αi)∩FIRST(αj) = ?，i ≠ j
• 對(duì)于文法中的每個(gè)非終結(jié)符 A，若它的某個(gè)候選首符集包含 ε，則 FIRST(αi)∩FOLLOW(A) = ?

2.2.4 LL(1)分析

一個(gè)文法，先消除左遞歸，再提取公共左因子，得到的文法 G 若滿足以上條件，
則稱文法 G 為L(zhǎng)L(1)文法，可以進(jìn)行LL(1)分析
過(guò)程如下

假設(shè)當(dāng)前等待匹配的符號(hào)為 a，進(jìn)行匹配的非終結(jié)符為A，A 的所有產(chǎn)生式為 A → α1 | α2 | … | αn，

• 若 a ∈ FIRST(αi)，則將 A 推導(dǎo)為 αi，a得到匹配，斯巴拉西，繼續(xù)分析下一個(gè)符號(hào) ①
• 若 a ? FIRST(αi)
• 若 ε ∈ FIRST(αi)，且 a ∈ FOLLOW(A)，則將 A 推導(dǎo)為 ε，a 交給 A 后面的串匹配 ②
  否則，匹配失敗，a 此時(shí)在輸入串中是語(yǔ)法錯(cuò)誤 ③

如果這個(gè)文法是LL(1)文法，則每一步都能且只能在①②③中確定，每一步都只有一種情況。這就是LL(1)分析

3、自下而上分析方法

3.1 主旨

從輸入串開(kāi)始，逐步進(jìn)行歸約，直到歸約到文法的開(kāi)始符號(hào)。
從語(yǔ)法分析樹(shù)角度來(lái)看，從語(yǔ)法樹(shù)的末端開(kāi)始，步步向上歸約，直到根結(jié)。

3.2 過(guò)程

是一種移進(jìn)-歸約法，用先進(jìn)后出的棧，把輸入串一個(gè)個(gè)移到棧內(nèi)，當(dāng)棧頂形成某個(gè)產(chǎn)生式的候選式時(shí)，把棧頂?shù)囊徊糠痔鎿Q成（歸約為）該產(chǎn)生式的左部符號(hào)。

3.3 算符優(yōu)先分析

定義算符之間的某種優(yōu)先關(guān)系，借助于這種優(yōu)先關(guān)系尋找可歸約串和進(jìn)行歸約。
不是一種規(guī)范歸約。

3.4 LR分析

3.4.1 定義

在規(guī)范歸約過(guò)程中，一方面記住已移進(jìn)和歸約出的整個(gè)符號(hào)串，即記住歷史，另一方面根據(jù)所用的產(chǎn)生式推測(cè)未來(lái)可能用到的輸入符號(hào)，對(duì)未來(lái)進(jìn)行展望。

一個(gè)LR分析器實(shí)質(zhì)上是一個(gè)帶先進(jìn)后出寄存器棧的確定有限狀態(tài)自動(dòng)機(jī)。

3.4.2 操作

• 移進(jìn)
• 歸約
• 接收
• 報(bào)錯(cuò)

六、語(yǔ)義分析和中間代碼產(chǎn)生

1、任務(wù)

語(yǔ)義分析包括靜態(tài)語(yǔ)義檢查和翻譯，主要有類(lèi)型檢查、控制流檢查、一致性檢查、相關(guān)名字檢查、作用域分析等工作。
編譯程序采用了獨(dú)立于機(jī)器的、復(fù)雜性介于源語(yǔ)言和機(jī)器語(yǔ)言之間的中間語(yǔ)言。
好處是

• 便于進(jìn)行與機(jī)器無(wú)關(guān)的代碼優(yōu)化工作
• 是編譯程序改變目標(biāo)機(jī)更容易
• 是編譯程序的結(jié)構(gòu)在邏輯上更為簡(jiǎn)單明確，編譯前端和后端的接口更為清晰。-

2、語(yǔ)義分析

語(yǔ)義分析的任務(wù)就是對(duì)結(jié)構(gòu)上正確的源程序進(jìn)行上下文有關(guān)性質(zhì)的審查，審查源程序是否有無(wú)語(yǔ)義錯(cuò)誤，為代碼生成階段收集類(lèi)型信息。

3、中間代碼生成

3.1 中間語(yǔ)言形式

主要有抽象語(yǔ)法樹(shù)、后綴式、三地址代碼（三元式、四元式、間接三元式）、DAG圖表示

3.1.1 后綴式

把運(yùn)算量（操作數(shù)）寫(xiě)在前面，算符（操作符）寫(xiě)在后面

3.1.2 三地址代碼

3.1.2.1 一般形式

x：=y op z

3.1.2.2 四元式

一個(gè)帶有四個(gè)域的記錄結(jié)構(gòu)，這四個(gè)域分別為op、arg1、arg2、result
arg表示參數(shù)，一般在等號(hào)右邊，op代表操作符，result代表結(jié)果，一般在：左邊

3.1.2.3 三元式

把四元式中的result去掉
一個(gè)帶有三個(gè)域的記錄結(jié)構(gòu)，這四個(gè)域分別為op、arg1、arg2
參數(shù)含義同四元式

3.1.2.4 間接三元式

用一張間接碼表輔以三元式表來(lái)表示中間代碼
調(diào)整運(yùn)算順序時(shí)，只需重新安排間接碼表即可，無(wú)需改動(dòng)三元式表

七、優(yōu)化

1、任務(wù)

對(duì)程序進(jìn)行等價(jià)變換，使得從變換后的程序處罰，能發(fā)生更有效的目標(biāo)代碼，通常稱這種變換為優(yōu)化。
其中包括控制流分析、數(shù)據(jù)流分析、代碼變換過(guò)程。

2、原則

2.1 等價(jià)原則

經(jīng)過(guò)優(yōu)化后不應(yīng)改變程序運(yùn)行的結(jié)果

2.2 有效原則

使優(yōu)化后所產(chǎn)生的目標(biāo)代碼運(yùn)行時(shí)間較短，占用的存儲(chǔ)空間少

2.3 合算原則

應(yīng)盡可能以較低的代價(jià)取得較好的優(yōu)化效果。

3、方法

3.1 刪除公共子表達(dá)式

3.2 復(fù)寫(xiě)傳播

3.3 刪除無(wú)用代碼

3.4 強(qiáng)度削弱

3.5 刪除歸納變量

八、目標(biāo)代碼生成

1、任務(wù)

以源程序的中間代碼為輸入，產(chǎn)生等價(jià)的目標(biāo)代碼為輸出

2、輸入輸出

代碼生成器的輸入包括中間代碼和符號(hào)表中的信息
代碼生成器的輸出是經(jīng)變換后的目標(biāo)代碼

3、目標(biāo)代碼的形式

3.1 能夠立即執(zhí)行的機(jī)器語(yǔ)言代碼

3.2 待裝配的機(jī)器語(yǔ)言模塊

3.3 匯編語(yǔ)言代碼

4、基本問(wèn)題

4.1 代碼生成器的輸入

4.2 指令選擇

4.3 寄存器分配

4.4 計(jì)算順序選擇

總結(jié)

以上是生活随笔為你收集整理的编译原理王者之路的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。